算法通关村第十二关—字符串经典基础面试题(白银)

? ? ? ? ? ? ? 字符串经典基础面试题

一、反转的问题

1.1 反转字符串

? LeetCode344.题目要求：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。
? 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用○()的额外空间解决这一问题。

示例1：
输入：s=["h","e","","","o"]
输出：["o","1","1","e","h"]
示例2：
输入：s=["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

利用双指针法，left在数组左边，right在数组右边，同时向中间移动，每次交换两个指针对应的数值即可

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while(left < right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left ++;
            right --;
        }
    }
}

1.2 K个一组反转

? LeetCode541 给定一个字符串S和一个整数k,从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。
·如果剩余字符少于k个，则将剩余字符全部反转。
·如果剩余字符小于2k但大于或等于k个，则反转前k个字符，其余字符保持原样。

输入：s="abcdefg",k=2
输出："bacdfeg"
示例2：
输入：s="abcd",k=2
输出："bacd"

? 我们直接按题意进行模拟就可以：反转每个下标从2k的倍数开始的，长度为k的子串。若该子串长度不足k,则反转整个子串。
v下面是讲义的代码，先把字符串变成字符数组，方便处理，感觉比我自己用StringBuffer要方便很多

public String reverseStr(String s,int k){
    if (s == null ｜｜ s.length() == 0) return s;
    int n = s.length();
    char[] arr =s.toCharArray();
    for(int i = 0; i < n; i += 2 * k){
        reverse(arr,i,Math.min(i + k, n) - 1);
    }
    return new String(arr);
}
public void reverse(char[] arr,int left,int right){
    while (left < right){
        char temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

我的代码如下：

class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer str = new StringBuffer(s);
        int len = str.length();
        int sum = len / (2 * k);
        int res = len % (2 * k);
        int left = 0, right = k; //左闭右开
        for(int i = 0; i < sum; i++){
            StringBuffer temp = new StringBuffer(str.substring(left, right));
            str.replace(left, right, temp.reverse().toString());
            left += 2 * k;
            right += 2 * k;
        }
        if(res >= k){
            StringBuffer temp = new StringBuffer(str.substring(left, right));
            str.replace(left, right, temp.reverse().toString());
        }
        else{
            StringBuffer temp = new StringBuffer(str.substring(left, str.length()));
            str.replace(left, str.length(), temp.reverse().toString());
        }
        return str.toString();
    }
}

1.3 仅仅反转字母

? LeetCode.917 给定一个字符串S，返回“反转后的”字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例1：
输入："ab-cd"
输出："dc-ba"
示例2：
输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"
示例3：
输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"

方法1：使用栈
? 将s中的所有字母单独存入栈中，所以出栈等价于对字母反序操作.(或者,可以用数组存储字母并反序数组)然后，遍历s的所有字符，如果是字母我们就选择栈顶元素输出。

class Solution{
    public String reverseOnlyLetters(String S){
        Stack<Character> letters = new Stack();
        for (char c: S.toCharArray())
        if (Character.isLetter(c))
            letters.push(c);
        StringBuilder ans = new StringBuilder();
        for (char c: S.toCharArray()){
            if (Character.isLetter(c))
                ans.append(letters.pop());
            else
                ans.append(c);
        }
        return ans.toString();
    }

方法2：双指针
? 一个接一个输出s的所有字符。当遇到一个字母时，我们希望找到逆序遍历字符串的下一个字母。所以我们这么做：维护一个指针j从后往前遍历字符串，当需要字母时就使用它。(i从头到尾，j从尾到头)

class Solution{
    public String reverseOnlyLetters(String S){
        if (S == null || S.length() == 0){
            return S;
        }
        StringBuilder ans = new StringBuilder();
        int j = S.length() - 1;
        for(int i = 0; i < S.length(); ++i){
            if (Character.isLetter(S.charAt(i))){
                while(!Character.isLetter(S.charAt(j)))
                j--;
                ans.append(S.charAt(j--));
            }else{
                ans.append(S.charAt(i));
            }
        }
        return ans.toString();
    }
}

官方题解的双指针，时间复杂度击败100%

class Solution {
    public String reverseOnlyLetters(String s) {
        int n = s.length();
        char[] arr = s.toCharArray(); //字符串变成字符数组
        int left = 0, right = n - 1;
        while (true) {
            //双指针
            while (left < right && !Character.isLetter(s.charAt(left))) { // 判断左边是否扫描到字母
                left++;
            }
            while (right > left && !Character.isLetter(s.charAt(right))) { // 判断右边是否扫描到字母
                right--;
            }
            if (left >= right) {
                break;
            }
            swap(arr, left, right);
            left++;
            right--;
        }
        return new String(arr);
    }

    public void swap(char[] arr, int left, int right) {
        char temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

1.4 反转字符串里的单词

方法1：使用语言提供的方法来解决

? 很多语言对字符串提供了split(拆分)，reverse(反转)和join(连接)等方法，因此我们可以简单的调
用内置的API完成操作：
1.使用split将字符串按空格分割成字符串数组；
2.使用reverse将字符串数组进行反转；
3.使用join方法将字符串数组拼成一个字符串。

//在正则表达式中，\s代表空白字符（包括空格、制表符、换行符等)，而+表示匹配一次或多次。
//因此，\s+可以匹配一个或多个连续的空白字符。(在使用时需要使用双反斜杠\\来转义反斜杠\)
class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

方法2：自己实现上述功能

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = trimSpaces(s);

        // 翻转字符串
        reverse(sb, 0, sb.length() - 1);

        // 翻转每个单词
        reverseEachWord(sb);

        return sb.toString();
    }

    public StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        // 将字符串间多余的空白字符去除
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }

            ++left;
        }
        return sb;
    }

    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;

        while (start < n) {
            // 循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            // 翻转单词
            reverse(sb, start, end - 1);
            // 更新start，去找下一个单词
            start = end + 1;
            ++end;
        }
    }
}

二、验证回文串

? LeetCode.125.给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。

示例1：
输入："Aman,a plan,a canal:Panama'"
输出：true
解释："amanaplanacanalpanama"是回文串
示例2：
输入："race a car"
输出：false
解释："raceacar'"不是回文串

? 这个题我们可以有多种思路，最简单的方法是对字符串S进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串sgood中。这样我们只需要判断sgood是否是一个普通的回文串即可。如果不使用语言的特性，我们可以使用双指针思想来处理。
? 初始时，左右指针分别指向Sg00d的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明sgood是回文串。

class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        int n = sgood.length();
        int left = 0, right = n - 1;
        while (left < right) {
            if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
}

使用java的reverse()来判断字符串

class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        return sgood.toString().equals(sgood_rev.toString());
    }
}

在原字符串上进行判断

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
}

三、字符串中的第一个唯一字符

? LeetCode:387.给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回-1。假定该字符串只包含小写字母。

示例：
s = "leetcode"
返回0
s = "loveleetcode"
返回2

? 我们可以对字符串进行两次遍历，在第一次遍历时，我们使用哈希映射(或数组)统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回-1。

class Solution {
    public int firstUniqChar(String s) {
        int[] a = new int[26];
        for(int i = 0; i < s.length(); i++){
            a[(int)s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s.length(); i++){
            if(a[(int)s.charAt(i) - 'a'] == 1) return i;
        }
        return -1;
    }
}

四、判定是否互为字符重排

? LeetCode242给定两个字符串s1和s2,请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例1：
输入：s1="abcadfhg",s2="bcafdagh"
输出：true
示例2：
输入：s1="abc",s2="bad"
输出：false

? 第一种方法：将两个字符串全部从小到大或者从大到小排列，然后再逐个位置比较，这时候不管两个原始字符串是什么，都可以判断出来。代码也不复杂：

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

? 第二种方法：使用Hash,注意这里我们不能简单的存是否已经存在，因为字符可能在某个串里重复存在，例如"abac"。我们可以记录出现的次数，如果一个字符串经过重新排列后，能够变成另外一个字符串，那么它们的每个不同字符的出现次数是相同的。如果出现次数不同，那么表示两个字符串不能够经过重新排列得到。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}