剣指offerブラシ問題まとめ——文字列編(一)

星:1,3
1.文字列の配置
【タイトル】文字列を入力し、辞書順にその文字列のすべての配列を印刷します.例えば、文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷されます.
9を超えない文字列を入力します(文字が重複する可能性があります)、文字には大文字と小文字のみが含まれます.
【コード】

package swear2offer.strs;

import java.util.ArrayList;
import java.util.TreeSet;

public class StrRange {

    /**
     *        ，                   。
     *         abc,         a,b,c
     *              abc,acb,bac,bca,cab   cba。
     *
     *        ,     9(       ),          。
     * */

    StringBuilder path = new StringBuilder();
    //   HashSet        stringBuilder     
    TreeSet<String> paths = new TreeSet<>();
    //     
    boolean[] flag;
    ArrayList<String> res = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {

        if (str.equals("") || str == null) return res;

        char[] arr = str.toCharArray();
        flag = new boolean[arr.length];

        All(arr,0);

        res.addAll(paths);

        return res;
    }

    /**
     *          ，          
     * */
    public void All(char[] str, int len) {

        //       
        if (len == str.length) {
            paths.add(path.toString());
            return;
        }

        for (int i=0; i<str.length; i++) {
            if (!flag[i]) {
                flag[i] = true;
                path.append(str[i]);
                All(str,len+1);
                flag[i] = false;
                path.deleteCharAt(path.length()-1);
            }
        }

    }

    public static void main(String[] args) {
        String s = "abc";
        System.out.println(new StrRange().Permutation(s).toString());
    }
}

【考える】

は、重複がない場合は全配列であり、重複がある場合はsetを用いて重さを除去し、また辞書順出力が必要であるためtreesetを用いて結果を保存する.

フル配列この場合、通常は遡及を使用する必要があります.遡及のいくつかのポイント:

演算子forサイクル

単一パスとパスの合計数

タグ配列

遡及用

遡及終了の条件

遡及式

2.配列を最小にする
【テーマ】
正の整数配列を入力し、配列内のすべての数字をつなぎ合わせて1つの数に並べ、つなぎ合わせることができるすべての数字の中で最小の1つを印刷します.例えば配列{3,32321}を入力すると、この3つの数字が並べられる最小数字は321323となる.
【コード】

	/**
     *          ，                 ，
     *                  。       {3，32，321}，
     *                    321323。
     *
     *        ，
     *     ，   ，   ，    ，  
     * */
    TreeSet<String> paths;
    StringBuilder path;
    boolean[] flag;

    public String PrintMinNumber(int [] numbers) {

        int n;

        n = numbers.length;

        if (n == 0 || numbers == null) return "";

        paths = new TreeSet<>();
        path = new StringBuilder();
        flag = new boolean[n];

        Find(numbers,0);

        return paths.first();


    }

    /**
     * n       
     *                
     * */
    public void Find(int[] a, int n) {
        if (n == a.length) {
            paths.add(path.toString());
            return;
        }

        int i;

        for (i=0; i<a.length; i++) {
            if (!flag[i]) {
                flag[i] = true;
                path.append(a[i]);

                Find(a,n+1);

                flag[i] = false;
                //           ，          
                int start,end;
                String add = a[i]+"";
                start = path.length() - add.length();
                end = path.length();
                path.delete(start, end);
            }
        }
    }

【考える】
遡及的な方法で複雑さを作るには、この問題ではソート方法を使用して、配列を文字列に変えてから、これらの文字列をソートしてから、文字列を接続することもできます.
3.最初に1回しか現れない文字
【テーマ】
1つの文字列(0<=文字列長<=10000、すべてアルファベットからなる)に1番目に1回しか現れない文字を見つけ、その位置を返し、ない場合は-1(大文字と小文字を区別する必要がある)を返す.
【コード】

public int FirstNotRepeatingChar(String str) {

        if (str.length() == 0 || str == null) return -1;

        int n,i,count;
        LinkedHashMap<Character, int[]> map;
        int[] arr;
        char[] strs;

        map = new LinkedHashMap<>();
        strs = str.toCharArray();
        arr = new int[2];
        n = strs.length;
        count = 0;

        for (i=0; i<n; i++) {
            if (map.get(strs[i]) == null) {
                count = 1;
            } else {
                count = map.get(strs[i])[0] + 1;
            }
            arr = new int[2];//      ，         ，       
            arr[1] = i;
            arr[0] = count;
            map.put(strs[i],arr);
        }


        count = -1;
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<Character,int[]> entry = (Map.Entry<Character,int[]>)it.next();
            if (entry.getValue()[0] == 1) {
                count = entry.getValue()[1];//  
                break;
            }
        }

        return count;
    }

【考える】

文字は26文字の英語文字しかないと慣性的に考えず、大文字、-、+などの記号文字もあるので、文字の桁数によって256ビットの文字であるべきです.

int[] count = new int[256];//hashのようなもので文字の出現回数を格納するのは便利です

この問題は本質的にhash解決であり,通常の配列では順序が保証されないためであるが,可能である文字を配列の下付き文字とし,文字の出現回数は問題の属性に従って順次判断できる.
【コード】

/**
 *
 *    ，   hash    ，           26     ，    ，-、+     ，
 *          ，   256   。
 *    ，        ，                  ，       hash    。
 *    ，   ASCII  ，         ，         。
 *    ，      hash ，  key    ，        ;
 */
	public int FirstNotRepeatingChar(String str) {
        if(str==null || str.length() == 0)return -1;
        int[] count = new int[256];
        //     hash             ，   
        for(int i=0; i < str.length();i++)
            count[str.charAt(i)]++;
        //           ka    ，                     hash      
        for(int i=0; i < str.length();i++)
            if(count[str.charAt(i)]==1)
                return i;
        return -1;
    }

4.左折文字列
【テーマ】
アセンブリ言語には、ループ左シフト(ROL)というシフト命令があります.この命令の演算結果を文字列でシミュレートするという簡単なタスクがあります.指定された文字列Sに対して、Kビットをループ左シフトした後のシーケンスを出力してください.たとえば、文字列S="abcXYZdef"は、ループ左シフト3ビット後の結果、すなわち"XYZdefabc"を出力するように要求されます.簡単じゃないの?OK、やれ!
【コード】

public String LeftRotateString(String str,int n) {

        if (str.equals("") || str==null) return "";

        int len,i;
        String sb1,sb2;

        len = str.length();
        if (len == n) return str;

        if (len < n) {
            n = n % len;
        }

        sb1 = str.substring(0,n);
        sb2 = str.substring(n,len);


        return sb2+sb1;
    }

5.単語の順序を反転
【テーマ】
牛客は最近新入社員のFishが来て、毎朝いつも英語の雑誌を持って、ノートに文を書いています.同僚のCatはFishが書いた内容に興味を持ち、ある日Fishに借りてめくったが、意味が読めなかった.たとえば、「student.a am I」です.後になって、こいつはもともと文の単語の順番を反転していたことに気づいた.正しい文は「I am a student.」だったはずだ.Catはこれらの単語の順序を一つ一つ反転してはいけません.彼を助けることができますか.
【コード】

public String ReverseSentence(String str) {
        if (str.equals(" ")) return " ";
        if (str.equals("") || str == null) return "";


        int len,i,mid;
        String temp;
        StringBuilder res;

        String[] strs = str.split(" ");

        len = strs.length;
        mid = len >> 1;

        //             
        if (len == 0) return str;

        for (i=0; i<mid; i++) {
            temp = strs[i];
            strs[i] = strs[len -1 - i];
            strs[len -1 - i] = temp;
        }

        res = new StringBuilder();
        for (i=0; i<len; i++) {
            res.append(strs[i]);
            res.append(" ");
        }
        res.deleteCharAt(res.length()-1);

        return res.toString();
    }

【考える】
文字列が複数のスペースが抜けやすい場合、このときsplit関数を用いる、得られる配列長は0である.