算法通关村第12关【白银】| 字符串经典问题

一、反转问题

1.反转字符串

思路：双指针，反转数组一个套路

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length -1;
        while(l
            char c = s[l];
            s[l] = s[r];
            s[r] = c;
            l++;
            r--;
        }
    
    }
}

2.k个一组反转

思路：每k个进行一次反转函数，从i++变成i+=2*k

class Solution {
    public String reverseStr(String s, int k) {
        if(s == null || s.length() == 0){
            return s;
        }
        int len = s.length();
        char[] str = s.toCharArray();
        for(int i = 0;i2*k){
            revers(str,i,Math.min(i+k-1,len-1));
        }
        return new String(str);
    }
 
    public void revers(char[] s,int l,int r){
        while(l
            char c = s[l];
            s[l] = s[r];
            s[r] = c;
            l++;
            r--;
        }
    }
}

3.仅仅反转字母

思路：

方法一、双指针

class Solution {
    public String reverseOnlyLetters(String s) {
        if(s==null || s.length() == 0){
            return s;
        }
        int l = 0;
        int r = s.length() -1;
        char[] str = s.toCharArray();
        while(l
            while(l
                l++;
            }
            while(r>=0&&!Character.isLetter(str[r])){
                r--;
            }
            if(l
                char c = str[l];
                str[l] = str[r];
                str[r] = c;
                l++;
                r--;
            }
        }
        return new String(str);
    }
}

方法二、使用栈，实现出栈反转

字母压入栈中，遇到字母弹出栈顶拼接进结果集

class Solution {
    public String reverseOnlyLetters(String s) {
        if(s==null || s.length() == 0){
            return s;
        }
        char[] str = s.toCharArray();
        Stack stack = new Stack();
        for(int i = 0;i
            if(Character.isLetter(str[i])){
                stack.push(str[i]);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(char c : str){
            if(Character.isLetter(c)){
                sb.append(stack.pop());
            }else{
                sb.append(c);
            }
        }
        return new String(sb);
    }
}

4.反转字符串中的单词

思路：整体反转+局部反转 = 区间反转

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = trimSpaces(s);
        int len = sb.length();
        reverse(sb,0,len - 1);
        int i = 0;
        for(int j = 0;j<=len;j++){
            if(j == len||sb.charAt(j) == ' '){
                reverse(sb,i,j-1);
                i = j+1;
            }
        }
        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);
        }
    }
 
}

二、验证回文串

思路：双指针，跳过非字母数字

class Solution {
    public boolean isPalindrome(String s) {
        if(s == null || s.length() == 0){
            return true;
        }
        int l = 0;
        int r = s.length() - 1;
        char[] str = s.toCharArray();
        while(l
            while(l
                l++;
            }
            while(l
                r--;
            }
            if(Character.toLowerCase(str[l]) != Character.toLowerCase(str[r])){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

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

 思路：哈希表来映射索引，当出现次数超过1就赋值-1标记，最后遍历一遍哈希表返回最小值

class Solution {
    public int firstUniqChar(String s) {
        HashMap map = new HashMap<>();
        int min = Integer.MAX_VALUE;
        int len = s.length();
        for(int i = 0;i
            char c = s.charAt(i);
            if(map.containsKey(c)){
                map.put(c,-1);
            }else{
                map.put(c,i);
            }   
        }
        for(Object o : map.values()){
            Integer v = (Integer) o;
            if(v != -1 && v
                min = v;
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

四、有效的字母异位词

思路：

方法一、排序，之后比较是否相等

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);
    }
}

方法二、哈希表存储，比较出现次数是否相同

数组实现

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] temp = new int[26];
        for(char c : s.toCharArray()){
            temp[c-'a'] += 1; 
        }
        for(char c : t.toCharArray()){
            temp[c-'a'] -= 1; 
        }
        for(int i : temp){
            if(i != 0){
                return false;
            }
        }
        return true;
    }
}

集合实现，更有通用性，不是字母也可以比较

class Solution {
    public boolean isAnagram(String s, String t) {
        Map maps = new HashMap<>();
        Map mapt = new HashMap<>();
        for(Character c : s.toCharArray()){
            maps.put(c,maps.getOrDefault(c,0)+1);
        }
        for(Character c : t.toCharArray()){
            mapt.put(c,mapt.getOrDefault(c,0)+1);
        }
        for(Object key  : maps.keySet()){
            if(!mapt.containsKey(key) || !maps.get(key).equals(mapt.get(key))){
                return false;
            }
            mapt.remove(key);
        }
        return mapt.isEmpty() ? true : false;
 
    }
}