[数据结构与算法]剑指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