劍指offer-之-字串

劍指offer刷題筆記–字串

5.替換空格 難度：簡單

本題比較簡單，整體思路是先定義一個StringBuffer型別的字串，將字串化為字符陣列遍歷一遍，當遇到空格時，將“%20”加入到新定義的字串中，否則直接加入當前遍歷到的字符即可，注意最后要將StringBuffer型別轉化為String型別，

class Solution {
    public String replaceSpace(String s) {
        StringBuffer res = new StringBuffer();
        for(char c : s.toCharArray()){
            if(c == ' '){
                res.append("%20");
            }else{
                res.append(c);
            }
        }
        return res.toString();
    }
}

38. 字串的排列 難度：中等

本題主要思想是回溯+剪枝，回溯通過遞回來實作，剪枝是因為該字串中可能存在相同的字符，因此需要用HashSet來判斷重復字符進而進行剪枝，

class Solution {
    char[] c;
    List<String> res = new ArrayList<>();
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    public void dfs(int x){
        if(x == c.length-1){
            res.add(String.valueOf(c));
            return;
        }
        Set<Character> set = new HashSet<>();
        for(int i = x; i<c.length;++i){
            if(set.contains(c[i]))  continue;
            set.add(c[i]);
            swap(x,i);
            dfs(x+1);
            swap(x,i);
        }
    }
    public void swap(int a, int b){
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

45. 把陣列排成最小的數 難度：中等

本題可通過將整型陣列轉化為字串陣列，然后通過我們重寫的排序方法將該陣列排序，排序完成后將該字串陣列轉化為字串回傳即可，

我們定義的排序如下：

設x和y為兩個數字字串，若 x+y > y+x,則x應該排在y后面，反之x應該排在y前面，

此處的x+y和y+x表示的是這兩個字串組成的實際數字，

如 “(1”+“2” = 12) < (“2”+“1”=21)

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0;i<nums.length;++i){
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
        StringBuffer res = new StringBuffer();
        for(String s : strs){
            res.append(s);
        }
        return res.toString();
    }
}

46. 把數字翻譯成字串 難度：中等

本題主要思想為動態規劃，通過先將數字轉化為字串再從頭到尾遍歷，通過動態規劃的思想得出全部的翻譯方法，具體操作和“青蛙跳臺階”問題相似，不同的地方有兩點：

1.遍歷字串的程序中，每次都要先判斷當前字符和前一個字符組合在一起的數字是否在10~25之間，如果在這個范圍內，那么dp[i] = dp[i-1]+dp[i-2]，否則dp[i] = dp[i-1]，

2.初始化的時候，將0位數的翻譯方法設定為1的原因是：如字串中前兩個字符組成的數字在10~25之間，說明dp[1] = 2,但是dp[0] = 1時顯而易見的，所以我們就設定dp[-1] = 1;

dp[i]表示以i下標對應字符結尾的字串中的翻譯方法總數，

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1;//設0位數時的翻譯方法為1
        int b = 1;//1位數時的翻譯方法為1
        for(int i = 2; i <= s.length();++i){
            String tmp = s.substring(i-2,i);
            int c = (tmp.compareTo("10")>=0 && tmp.compareTo("25")<=0) ? a+b : a;
            b = a;
            a = c;
        }
        return a;
    }
}

48. 最長不含重復字符的子字串 難度：中等

本題的主要思想是動態規劃，但是需要用到哈希表來存盤資料，tmp是以當前字符為尾字符的最長不含重復字符字串的最大長度，res為當前遍歷到的最長不包含重復字符的字串的最大長度，

哈希表中存盤的key：字串中的字符，value：該字符在字串中的下標，

因為字符有可能是重復的，所以當遍歷到重復字符時，會重繪哈希表中該字符的value值，而 i 為字符在這次重繪前該字符的下標，那么當前的i和j對應的就是該字串中相同的兩個字符下標，j - i就是 以 j 對應的字符為尾字符的字串長度，

但是j-i這個字串里面可能有其他重復字符，所以我們將tmp與j-i來比較，重繪tmp的值，讓tmp存盤的是不含重復字符的子字串長度，

如果tmp >= j - i,說明j-i對應字串在tmp對應字串中，那么將tmp重繪為j-i，

如果tmp < j - i,說明 j - i 對應的字串中包含tmp對應的字串，那么j-i中必然有重復字符，所以將不能將tmp重繪為j-i，只需要將tmp+1即可，

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int tmp = 0;
        int res = 0;
        for(int j = 0; j < s.length(); ++j){
            int i = map.getOrDefault(s.charAt(j),-1);
            map.put(s.charAt(j),j);
            tmp = (tmp < j-i) ? tmp+1 : j-i;
            res = Math.max(res,tmp);
        }
        return res;
    }
}

58 .翻轉單詞順序 I 難度：簡單

本題用雙指標法：創建兩個指標i,j，分別指向每個單詞的首尾，從后往前遍歷，通過兩個指標將單詞一個個加入到新創建的字串中，需要注意的點是要先去掉字串的首尾空格，

class Solution {
    public String reverseWords(String s) {
        s = s.trim();//洗掉首尾空格
        int i = s.length()-1;
        int j = i;
        StringBuffer res = new StringBuffer();
        while(i >= 0){
            while(i >= 0 && s.charAt(i) != ' ')     i--;//找到單詞的頭部
            res.append(s.substring(i+1,j+1)+" ");		//將單詞加入res中
            while(i >= 0 && s.charAt(i) == ' ')     i--;//找到單詞的尾部
            j=i;								//讓j指向單詞尾部
        }
        return res.toString().trim();
    }
}
 

58 . 左旋轉字串 II 難度：簡單

本題用分割字串的操作即可完成，需要注意的是：substring()方法的作用區間是左閉右開，

lass Solution {
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        return s.substring(n,len)+s.substring(0,n);
    }
}

部分代碼參考LeetCode作者：Krahets