剑指offer--字符串 - 《数据结构与算法》

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] carry = new char[length * 3];
        int size = 0;
        for(int i = 0; i < length; i++){
            char c = s.charAt(i);
            if(c == ' '){
                carry[size++] = '%';
                carry[size++] = '2';
                carry[size++] = '0';
            }else{
                carry[size++] = c;
            }
        }
        String newStr = new String(carry, 0, size);
        return newStr;
    }
}

剑指 Offer 48. 最长不含重复字符的子字符串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //l、r 分别维护滑动窗口的左右边界
        //哈希表用来快速查找元素是否在窗口里面存在
        int left = 0 , right = 0, max = 0;
        Map<Character,Integer > map = new HashMap<>();
        for(int i = 0 ; i < s.length(); i++){
            char ch = s.charAt(i);
            //如果元素在哈希表中存在，left后移到该重复字符后面，删除该结点
            //理论上哈希表里面，left以前的数据不存在了，但是实际上依旧存在
            //为防止left倒退，使用max函数，使得left只能后移
            if(map.containsKey(ch)){
                left = Math.max(left , map.get(ch) + 1);
                //map.remove(ch);
            }
            //更新右边界
            right = i;
            //此时哈希表中一定不存在该元素了，将新元素添加到表中
            map.put(ch , i);
            max = Math.max(max , right - left + 1);
        }
        return  max;
    }
}

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

class Solution {
    public boolean isValid(String s) {
        //判空
        if(s.length() == 0) return true;
        Stack<Character> stack = new Stack<>();
        for(char ch : s.toCharArray()){
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }else{
                    char temp = stack.pop();
                    if(ch == ')'){
                        if(temp != '('){
                            return false;
                        }
                    }
                    if(ch == '}'){
                        if(temp != '{'){
                            return false;
                        }
                    }
                    if(ch == ']'){
                        if(temp != '['){
                            return false;
                        }
                    }
                }
            }
        }
        return stack.isEmpty()? true: false;
    }
}

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

class Solution {
    public String reverseWords(String s) {
        s = s.trim(); //去除收尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0){
            while(i >= 0 && s.charAt(i) != ' ') i--; //找到空格
            res.append(s.substring(i + 1, j + 1) + " "); //添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--;     //跳过空格  可能包含多个空格
            j = i;
        }
        return res.toString().trim();
    }
}

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

class Solution {
    public String reverseLeftWords(String s, int n) {
        String res = "";
        for(int i = n; i < s.length(); i++)
            res += s.charAt(i);
        for(int i = 0; i < n; i++)
            res += s.charAt(i);
        return res;
    }
}

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < s.length(); i++)
            res.append(s.charAt(i));
        for(int i = 0; i < n; i++)
            res.append(s.charAt(i));
        return res.toString();
    }
}

剑指 Offer 67. 把字符串转换成整数

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

class Solution {
    public int strToInt(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        int idx = 0;
        while (idx < n && chars[idx] == ' ') {    // 去掉前导空格
            idx++;
        }
        if (idx == n) return 0;   //去掉前导空格以后到了末尾了
        boolean negative = false;
        if (chars[idx] == '-') {
            //遇到负号
            negative = true;
            idx++;
        } else if (chars[idx] == '+') {
            // 遇到正号
            idx++;
        } else if (!Character.isDigit(chars[idx])) {
            // 其他符号
            return 0;
        }
        int ans = 0;
        while (idx < n && Character.isDigit(chars[idx])) {
            int digit = chars[idx] - '0';
            if (ans > (Integer.MAX_VALUE - digit) / 10) {
                // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。
                return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            ans = ans * 10 + digit;
            idx++;
        }
        return negative? -ans : ans;
    }
}

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

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

剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character, Boolean> hash = new HashMap<>();
        char[] ch = s.toCharArray();
        for(char c : ch){
            hash.put(c, !hash.containsKey(c)); //先插入true, 重复插入为false
        }
        for(char c : ch){
            if(hash.get(c)){
                return c;
            }
        }
        return ' ';
    }
}

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

class Solution {
    Set<String> res = new HashSet<>();
    public String[] permutation(String s) {
        if(s == null) return new String[]{};
        boolean[] visisted = new boolean[s.length()];
        dfs(s, "", visisted);
        return res.toArray(new String[res.size()]);
    }
    private void dfs(String s, String ch, boolean[] visisted){
        //边界条件判断，当选择的字符长度等于原字符串长度的时候，说明原字符串的字符都已经
        //选完了
        if(s.length() == ch.length()){
            res.add(ch);
            return;
        }
        for(int i = 0; i < s.length(); i++){    ////每一个节点我们都要从头开始选
            char temp = s.charAt(i); 
            if(visisted[i]) continue;           ////已经选择过的就不能再选了
            visisted[i] = true;                 //表示选择当前字符
            dfs(s, ch + String.valueOf(temp), visisted);  //把当前字符选择后，到树的下一层继续选
            visisted[i] = false;                          //递归往回走的时候要撤销选择
        }
    }
}

541. 反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

class Solution {
    public String reverseStr(String s, int k) {
        char[] a = s.toCharArray();
        for(int start = 0; start < a.length; start += 2*k){
            int i = start;
            int j = Math.min(start + k - 1, a.length - 1);
            while(i < j){
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new String(a);
    }
}

459. 重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return kmp(s);
    }
    public boolean kmp(String pattern) {
        int n = pattern.length();
        int[] fail = new int[n];
        Arrays.fill(fail, -1);
        for (int i = 1; i < n; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }
        return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
    }
}

409. 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

class Solution {
    public int longestPalindrome(String s) {
        // 1. counter数组计数，统计每种字母出现的次数
        int[] counter = new int[58];
        for (char c : s.toCharArray()) {
            counter[c - 'A']++;
        }
        // 2. 构造回文串，每种字母使用偶数次
        int res = 0;
        for (int x: counter) {
            res += x - (x & 1);
        }
        // 3. 如果最终的长度小于原字符串的长度，说明存在某个字符出现了奇数次，那可以在最中间再补一个字母。
        return res < s.length()? res + 1: res;
    }
}

647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。示例 1：输入：”abc” 输出：3 解释：三个回文子串: “a”, “b”, “c” 示例 2：

输入：”aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

class Solution {
    public int countSubstrings(String s) {
        int len, ans = 0;
        if (s == null || (len = s.length()) < 1) return 0;
        //dp[i][j]：s字符串下标i到下标j的字串是否是一个回文串，即s[i, j]
        boolean[][] dp = new boolean[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                //当两端字母一样时，才可以两端收缩进一步判断
                if (s.charAt(i) == s.charAt(j)) {
                    //i++，j--，即两端收缩之后i,j指针指向同一个字符或者i超过j了,必然是一个回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        //否则通过收缩之后的字串判断
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {//两端字符不一样，不是回文串
                    dp[i][j] = false;
                }
            }
        }
        //遍历每一个字串，统计回文串个数
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (dp[i][j]) ans++;
            }
        }
        return ans;
    }
}

5. 最长回文子串

回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串

中心扩散法

动态规划

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 0) return s;
        int res = 1;
        int ll = 0, rr = 0;
        //中心点为奇数
        for(int i = 0; i < s.length(); i++){
            int l = i - 1;
            int r = i + 1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                int len = (r - l + 1);
                if(len > res){
                    res = len;
                    ll = l;
                    rr = r;
                }
                l--;
                r++;
            }
        //中心点为偶数
        l = i;
        r = i + 1;
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            int len = (r - l + 1);
            if(len > res){
                res = len;
                ll = l;
                rr = r;
            }
            l--;
            r++;
            }
        }
        return s.substring(ll, rr + 1);
    }
}

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = “bbbab” 输出：4 解释：一个可能的最长回文子序列为 “bbbb” 。示例 2：

输入：s = “cbbd” 输出：2 解释：一个可能的最长回文子序列为 “bb” 。

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len + 1][len + 1];
        for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏
            dp[i][i] = 1; // 初始化
            for (int j = i + 1; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
                }
            }
        }
        return dp[0][len - 1];
    }
}