剑指offer刷题总结——字符串篇（一）

灰太狼 2021-09-21 03:28 266阅读 0赞

> 星级：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.把数组排成最小的数 ###

**【题目】**

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 \{3，32，321\}，则打印出这三个数字能排成的最小数字为 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.第一个只出现一次的字符 ###

**【题目】**

在一个字符串 (0<= 字符串长度 <=10000，全部由字母组成) 中找到第一个只出现一次的字符，并返回它的位置，如果没有则返回 -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.