字符串

字符串

字符串相加

  • 使用两个指针 index-- 即可
public String addStrings(String num1, String num2) {
    if (num1 == null) {
        return num2;
    }

    if (num2 == null) {
        return num1;
    }

    final StringBuilder sb = new StringBuilder(Math.max(num1.length(), num2.length()) + 1);

    int index1 = num1.length() - 1;
    int index2 = num2.length() - 1;

    int remainder = 0;

    while (index1 >= 0 && index2 >= 0) {
        char a = num1.charAt(index1);
        char b = num2.charAt(index2);
        int num = ((a - '0') + (b - '0')) + remainder;

        remainder = num / 10;
        num %= 10;

        sb.append(num);

        index1--;
        index2--;
    }

    while (index1 >= 0) {
        char a = num1.charAt(index1);

        int num = (a - '0') + remainder;
        remainder = num / 10;
        num %= 10;

        sb.append(num);

        index1--;
    }

    while (index2 >= 0) {
        char b = num2.charAt(index2);

        int num = (b - '0') + remainder;
        remainder = num / 10;
        num %= 10;

        sb.append(num);

        index2--;
    }

    if (remainder != 0) {
        sb.append(remainder);
    }

    return sb.reverse().toString();
}

最长回文子串

采用中心扩展法,以 i 坐标的字符往两边扩展,以 ii + 1 左边的字符往两边扩展,然后看哪个 length 比较大。

public String longestPalindrome(String s) {
    if (s.length() < 2) {
        return s;
    }
    
    String max = s.substring(0, 1);
    for (int i = 0; i < s.length() - 1; i++) {
        String a = expand(s, i, i);
        String b = expand(s, i, i + 1);
        
        if (a.length() > max.length()) {
            max = a;
        }
        
        if (b.length() > max.length()) {
            max = b;
        }
    }
    
    return max;
}

// 返回最长的回文字符串
private String expand(String s, int centerI, int centerJ) {
    String max = "";
    
    while (centerI >= 0 && centerJ < s.length() && s.charAt(centerI) == s.charAt(centerJ)) {
        max = s.substring(centerI, centerJ + 1);
        
        centerI--;
        centerJ++;
    }
    
    return max;
}

无重复字符的最长 substring

i 索引用于在字符串上从左向右进行扫描。如下图所示,[索引left, 字符B] 之间的所有字符都是不重复的,接下来 i 遇到了第二个 A。那么这个时候是不是应该将 [索引left, 第一个字符A] 之间的所有字符都从 Map 中移除掉。这样能够保证 Map 里面放的是 [第一个字符A的下一个字符, 第二个字符A] 这段的所有字符。

所以,我们的 Map 应该的 key 应该是字符value 应该是这个字符当前的索引位置

left.......A.......BA
  |________________| (无重复)
  |________| (删除)
public int lengthOfLongestSubstring(String s) {
    char[] arr = s.toCharArray();
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0;
    int left = 0;
    
    int i = 0;
    while (i < arr.length) {
        if (map.containsKey(arr[i])) {
            // 我们需要持续不断的从左侧移除构成当前 map 的字符串的字符
            // 这个 position 一定是大于等于 left 的
            int position = map.get(arr[i]);
            
            // 移除所有字符串
            for (int j = left; j <= position; j++) {
                map.remove(arr[j]);
            }
            
            // 更新 left 的值
            left = position + 1;
            map.put(arr[i], i);
        } else {
            map.put(arr[i], i);
        }
        
        maxLen = Math.max(maxLen, map.size());
        i++;
    }
    
    return maxLen;
}

字符串转换整数 (atoi)

感觉最难的也就是处理溢出的部分。不光要通过 value * 10 / 10 是否等于 value 来判断,加完值之后也要通过 value 是否已经小于 0 来判断是否这个时候已经溢出。

public int myAtoi(String s) {
    s = s.trim();

    // 默认正数
    boolean positive = true;
    // 已经读取了 sign
    boolean hasReadSign = false;
    int value = 0;

    int index = 0;
    while (index < s.length()) {
        char c = s.charAt(index);

        if (c == '+' || c == '-') {
            if (hasReadSign) {
                break;
            }

            hasReadSign = true;
            positive = c == '+';
        } else if (c >= '0' && c <= '9') {

            // 123
            // 0 * 10 + 1 = 1
            // 1 * 10 + 2 = 12
            // 12 * 10 + 3 = 123
            //
            // 00123
            // 0 * 10 + 0 = 0
            // 0 * 10 + 0 = 0
            // ...
            boolean earlyExit = false;

            while (index < s.length()) {
                c = s.charAt(index);
                if (!(c >= '0' && c <= '9')) {
                    earlyExit = true;
                    break;
                }

                // 如何防止溢出
                if (value * 10 / 10 != value) {
                    return positive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                }

                value = value * 10 + (c - '0');

                // 加完溢出了
                if (value < 0) {
                    return positive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                }

                index++;
            }

            if (earlyExit) {
                break;
            }

            continue;
        } else {
            // 汇入了其他字符
            break;
        }

        index++;
    }

    return positive ? value : -value;
}

最小覆盖子串

原题

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

// s 包含 t 中的所有字母的最小窗口
//
public class MinimumWindowSubstring {

    public String minWindow(String s, String t) {
        if (s.length() == 0 || s.length() < t.length()) {
            return "";
        }

        int minLeft = 0;
        int minLen = s.length() + 1;

        int left = 0;
        int right = 0;

        // t 字符串的个数 count
        int count = t.length();

        // 建立一个 t 的map
        // t: a a b b b c
        // { a:2, b:3, c:1 }
        Map<Character, Integer> map = new HashMap<>();
        for (char c: t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        while (right < s.length()) {
            char c = s.charAt(right);

            if (map.containsKey(c)) {
                // oldFreq 代表完成 t 所有字符,当前字符还需要多少 freq
                int oldFreq = map.get(c);
                map.put(c, oldFreq - 1);

                if (oldFreq > 0) {
                    // 仅在 oldFreq > 0 的情况下
                    // t 字符串 count--
                    count--;
                }
            }

            while (count == 0) {
                if ((right - left) + 1 < minLen) {
                    minLen = (right - left) + 1;
                    minLeft = left;
                }

                c = s.charAt(left);

                if (map.containsKey(c)) {
                    int oldFreq = map.get(c);
                    map.put(c, oldFreq + 1);

                    if (oldFreq == 0) {
                        count++;
                    }
                }

                // 移动 left 指针
                left++;
            }

            right++;
        }

        return minLen > s.length() ? "" : s.substring(minLeft, minLeft + minLen);
    }

}

字符串解码

原题

输入:s = "3[a2[c]]"
输出:"accaccacc"

解法:

public class Solution {
    int ptr;

    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;

        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }

        return getString(stk);
    }

    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }

    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}