去重压缩

1047-删除字符串中的所有相邻重复项

image.png
题意分析：
解题思路：

  • 栈实现。即将入栈元素与栈顶元素进行对比。
  • StringBuilder实现。top 指针指向 sb 的‘栈’顶位置。

注意点：
代码：

  1.     public String removeDuplicates(String s) {
  2.         if (s.length() < 2) {
  3.             return s;
  4.         }
  5.         StringBuilder sb = new StringBuilder();
  6.         int top = -1;
  7.         for (int i = 0; i < s.length(); i++) {
  8.             char ch = s.charAt(i);
  9.             if (top >= 0 && sb.charAt(top) == ch) {
  10.                 sb.deleteCharAt(top);
  11.                 top--;
  12.             } else {
  13.                 sb.append(ch);
  14.                 top++;
  15.             }
  16.         }
  17.         return sb.toString();
  18.     }

*1209-删除字符串中的所有相邻重复项II

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     /**
  2.      * 用辅助数组记录所有字符位置出现的次数，重复则倒退。
  3.      * @param s
  4.      * @param k
  5.      * @return
  6.      */
  7.     public String removeDuplicates(String s, int k) {
  8.         StringBuilder sb = new StringBuilder(s);
  9.         // 记录元素连续出现次数
  10.         int[] cnts = new int[s.length()];
  11.         for (int i = 0; i < sb.length(); i++) {
  12.             if (i == 0 || sb.charAt(i) != sb.charAt(i-1)) {
  13.                 cnts[i] = 1;
  14.             } else {
  15.                 cnts[i] = cnts[i-1] + 1;
  16.                 if (cnts[i] == k) {
  17.                     sb.delete(i-k+1, i+1);
  18.                     i = i - k;
  19.                 }
  20.             }
  21.         }
  22.         return sb.toString();
  23.     }
  25.     /**
  26.      * 用辅助栈单独记录连续元素出现的次数，重复则倒退。
  27.      * @param s
  28.      * @param k
  29.      * @return
  30.      */
  31.     public String removeDuplicates2(String s, int k) {
  32.         StringBuilder sb = new StringBuilder(s);
  33.         // 记录元素连续出现次数
  34.         Stack<Integer> stack = new Stack<>();
  35.         for (int i = 0; i < sb.length(); i++) {
  36.             if (i == 0 || sb.charAt(i) != sb.charAt(i-1)) {
  37.                 stack.push(1);
  38.             } else {
  39.                 stack.push(stack.pop() + 1);
  40.                 if (stack.peek() == k) {
  41.                     // sb删除重复的k个元素，然后更新i位置继续遍历。
  42.                     sb.delete(i-k+1, i+1);
  43.                     i = i - k;
  45.                     // 栈中等于k的元素出栈
  46.                     stack.pop();
  47.                 }
  48.             }
  49.         }
  50.         return sb.toString();
  51.     }

*443-压缩字符串

image.png
题意分析：

  • 思路有点像删除数组中的重复元素，边扫描边更新历史字符，并记录重复字符的长度。

解题思路：

  • 双指针原地更新。read 和 write 指针同时走动，read 指针负责向前读取字符，write 指针更新字符扫描记录。
    • 时间复杂度：O(n)。
    • 空间复杂度：O(1)。

注意点：

  • 字符如果出现一次则不需要记录次数，超过十次需要分别每个元素的值。

代码：

  1.        /**
  2.      * 双指针。读指针和写指针，read指针不停扫描，write指针更新数据
  3.      * @param chars
  4.      * @return
  5.      */
  6.     public int compress(char[] chars) {
  7.         int n = chars.length;
  8.         int read = 0, write = 0;
  9.         // 记录一个字符的起始位置
  10.         int start = 0;
  11.         for (read = 0; read < n; read++) {
  12.             // 判断字符变化的 read 位置，以及 read 指针是否走到了最后一个节点
  13.             if (read == n-1 || chars[read] != chars[read+1]) {
  14.                 chars[write++] = chars[read];
  15.                 int nums = read - start + 1;
  17.                 if (nums > 1) {
  18.                     // sb用来记录重复字符的数量
  19.                     StringBuffer sb = new StringBuffer();
  20.                     while (nums > 0) {
  21.                         sb.append(nums % 10);
  22.                         nums /= 10;
  23.                     }
  24. //                    System.out.println("sb = " + sb.toString());
  26.                     // 将 sb 中的数量存在在 chars 数据中
  27.                     for (int i = sb.length() - 1; i >= 0; i--) {
  28.                         chars[write++] = sb.charAt(i);
  29.                     }
  30.                 }
  31.                 // 更新元素第一次出现的位置
  32.                 start = read + 1;
  33.             }
  34.         }
  35. //        System.out.println(Arrays.toString(chars));
  36.         // 求解，write指针是记录压缩后的字符位置
  37.         return write;
  38.     }

滑动窗口系列

3-无重复字符的最长字串

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     /**
  2.     * Hash记录重复字符出现位置
  3.     */
  4.     public int lengthOfLongestSubstring(String s) {
  5.         int i = 0, j = 0;
  6.         Map<Character, Integer> map  = new HashMap<>();
  7.         int len = 0;
  8.         for (j = 0; j < s.length(); j++) {
  9.             if (map.containsKey(s.charAt(j))) {
  10.                 // i 起始值不能回退
  11.                 i = Math.max(map.get(s.charAt(j)) + 1, i);
  12.             }
  13.             len = Math.max(len, j - i + 1);
  14.             map.put(s.charAt(j), j);
  15.         }
  16.         return len;
  17.     }
  19.     /**
  20.     * 滑动窗口。"abcabcbb"
  21.      */
  22.     public int lengthOfLongestSubstring2(String s) {
  23.         int left = 0, right = 0;
  24.         int len = 0;
  25.         Map<Character, Integer> window = new HashMap<>();
  26.         while (right < s.length()) {
  27.             char ch = s.charAt(right);
  28.             right++;
  29.             if (window.containsKey(ch)) 
  30.                 window.put(ch, window.get(ch) + 1); 
  31.             else 
  32.                 window.put(ch, 1);
  34.             // 更新左窗口 left
  35.             while (window.get(ch) > 1) {
  36.                 char chdel = s.charAt(left);
  37.                 left++;
  38.                 window.put(chdel, window.get(chdel) - 1);
  39.             }
  41.             len = Math.max(len, right - left);
  42.         }
  43.         return len;
  44.     }

567-字符串的排列

image.png
题意分析：
解题思路：

  • 滑动窗口。

注意点：
代码：

  1.     public boolean checkInclusion(String s1, String s2) {
  2.         String str = s2, substr = s1;
  3.         int left = 0, right = 0;
  4.         Map<Character, Integer> window = new HashMap<>();
  5.         Map<Character, Integer> need = new HashMap<>();
  6.         // 关键变量，记录 window 中数据是否包含 need 的元素
  7.         int valid = 0;
  8.         for (int i = 0; i < substr.length(); i++) {
  9.             char ch = substr.charAt(i);
  10.             if (need.containsKey(ch)) need.put(ch, need.get(ch) + 1); else need.put(ch, 1);
  11.         }
  13.         while (right < str.length()) {
  14.             char chadd = str.charAt(right);
  15.             right++;
  17.             // 更新窗口数据
  18.             if (need.containsKey(chadd)) {
  19.                 if (window.containsKey(chadd)) window.put(chadd, window.get(chadd) + 1); else window.put(chadd, 1);
  20.                 if (window.get(chadd).equals(need.get(chadd))) {
  21.                     valid++;
  22.                 }
  23.             }
  25.             // 缩小窗口
  26.             while (valid == need.size()) {
  27.                 if (right - left == substr.length()) {
  28.                     return true;
  29.                 }
  30.                 char chdel = str.charAt(left);
  31.                 left++;
  33.                 // 更新窗口数据
  34.                 if (need.containsKey(chdel)) {
  35.                     if (window.get(chdel).equals(need.get(chdel))) {
  36.                         valid--;
  37.                     }
  38.                     window.put(chdel, window.get(chdel) -1);
  39.                 }
  40.             }
  41.         }
  42.         return false;
  43.     }

438-找到字符串中所有字母异位词

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public List<Integer> findAnagrams(String s, String p) {
  2.         String str = s, substr = p;
  3.         Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
  4.         for (int i = 0; i< substr.length(); i++) {
  5.             char ch = substr.charAt(i);
  6.             if (need.containsKey(ch)) need.put(ch, need.get(ch) + 1); else need.put(ch, 1);
  7.         }
  9.         int left = 0, right = 0;
  10.         // 记录是否是可行解
  11.         int valid = 0;
  13.         List<Integer> list = new ArrayList<>();
  14.         while (right < str.length()) {
  15.             char chadd = str.charAt(right);
  16.             right++;
  18.             // 记录「可行解」
  19.             if (need.containsKey(chadd)) {
  20.                 if (window.containsKey(chadd)) window.put(chadd, window.get(chadd) + 1); else window.put(chadd, 1);
  21.                 if (window.get(chadd).equals(need.get(chadd))) {
  22.                     valid++;
  23.                 }
  24.             }
  26.             // 缩小窗口
  27.             while (valid == need.size()) {
  28.                 // 判断是否要更新结果
  29.                 if (right - left == substr.length()) {
  30.                     list.add(left);
  31.                 }
  32.                 char chdel = str.charAt(left);
  33.                 left++;
  35.                 // 更新「可行解」
  36.                 if (need.containsKey(chdel)) {
  37.                     if (window.get(chdel).equals(need.get(chdel))) {
  38.                         valid--;
  39.                     }
  40.                     window.put(chdel, window.get(chdel) - 1);
  41.                 }
  42.             }
  43.         }
  44.         return list;
  45.     }

76-最小覆盖子串

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public String minWindow(String s, String t) {
  2.         String str = s, substr = t;
  3.         Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
  4.         for (int i = 0; i< substr.length(); i++) {
  5.             char ch = substr.charAt(i);
  6.             if (need.containsKey(ch)) need.put(ch, need.get(ch) + 1); else need.put(ch, 1);
  7.         }
  9.         int left = 0, right = 0;
  10.         // 记录是否是可行解
  11.         int valid = 0;
  13.         int start = -1;
  14.         int len = Integer.MAX_VALUE;
  15.         while (right < str.length()) {
  16.             char chadd = str.charAt(right);
  17.             right++;
  19.             // 记录「可行解」
  20.             if (need.containsKey(chadd)) {
  21.                 if (window.containsKey(chadd)) window.put(chadd, window.get(chadd) + 1); else window.put(chadd, 1);
  22.                 if (window.get(chadd).equals(need.get(chadd))) {
  23.                     valid++;
  24.                 }
  25.             }
  27.             // 缩小窗口
  28.             while (valid == need.size()) {
  29.                 // 判断是否要更新结果
  30.                 if (right - left < len) {
  31.                     start = left;
  32.                     len = right - left;
  33.                 }
  34.                 char chdel = str.charAt(left);
  35.                 left++;
  37.                 // 更新「可行解」
  38.                 if (need.containsKey(chdel)) {
  39.                     if (window.get(chdel).equals(need.get(chdel))) {
  40.                         valid--;
  41.                     }
  42.                     window.put(chdel, window.get(chdel) - 1);
  43.                 }
  44.             }
  45.         }
  46.         System.out.println("start=" + start + "; len = " + len);
  47.         return (start == -1) ? "" : str.substring(start, start+len);
  48.     }

未分类

*1081-不同字符的最小子序列

image.png
题意分析：

  • 去掉字符串中的重复字符，并保证字符的相对顺序，且去重后在字典序中序列最小。

解题思路：

  • 三步曲。
    • 去重。
    • 去重后字符相对顺序不能打乱。（单调递减栈）
    • 字典序列最小。（这一点最难）

注意点：

  • 记录每个字符次数 HashMap。
  • 记录每个字符是否被访问过。 isAccessed = new boolean[size]。这里是以 ASCII 字符作为索引的 size 要好好理解。

代码：

  1. /**
  2.      * 解题思路
  3.      *  1、字符去重
  4.      *  2、字符子顺序不变
  5.      *  3、字典序最小
  6.      * @param s
  7.      * @return
  8.      */
  9.     public String smallestSubsequence(String s) {
  10.         // 用栈保存遍历字符串的字符
  11.         Stack<Character> stack = new Stack<>();
  12.         // 记录字符是否已经存在
  13.         boolean[] isExisted = new boolean[s.length()];
  14.         // 记录每个字符出现的次数（求最小字典序时会用到）
  15.         Map<Character, Integer> cntMap = new HashMap<>();
  16.         // 初始化字符出现次数
  17.         for (char ch : s.toCharArray()) {
  18.             if (!cntMap.containsKey(ch))
  19.                 cntMap.put(ch, 1);
  20.             else
  21.                 cntMap.put(ch, cntMap.get(ch) + 1);
  22.         }
  24.         // 更新栈
  25.         for (char ch : s.toCharArray()) {
  26.             // 每遍历一个字符对应的计数减 1。（后续串中该元素还剩多少个）
  27.             cntMap.put(ch, cntMap.get(ch) - 1);
  29.             // 重复字符不处理
  30.             if (isExisted[ch - 'a'] == true) continue;
  32.             // 重点是处理入栈的小字符
  33.             while (!stack.isEmpty() && ch < stack.peek()) {
  34.                 if (cntMap.get(stack.peek()) == 0)
  35.                     break;
  36.                 isExisted[stack.pop() - 'a'] = false;
  37.             }
  39.             // 常规入栈并标记动作
  40.             stack.push(ch);
  41.             isExisted[ch - 'a'] = true;
  42. //            System.out.println(isExisted.length + " : " + Arrays.toString(isExisted));
  43.         }
  45.         // 出栈字符与实际字符反向
  46.         StringBuilder sb = new StringBuilder();
  47.         while (!stack.isEmpty()) {
  48.             sb.append(stack.pop());
  49.         }
  50.         return sb.reverse().toString();
  51.     }

171-Excel 表列序号image.png

题意分析：
解题思路：
注意点：
代码：

  1.     public int titleToNumber(String columnTitle) {
  2.         int ret = 0;
  3.         for (int i = 0; i < columnTitle.length(); i++) {
  4.             char ch = columnTitle.charAt(i);
  5.             int val = ch - 'A' + 1;
  6.             ret += val * Math.pow(26, columnTitle.length() - i -1);
  7.         }
  8.         return ret;
  9.     }

415-字符串相加（大数相加）

image.png
题意分析：

  • 两个大数以字符串的形式做加法。

解题思路：

  • 按位计算，个位+个位，十位+十位……
    • 时间复杂度：max(O(m), O(n))

注意点：
扩展：

  • 多个大数相加如何处理，超过 INT 最大值如何处理，如果有负数又如何处理。

代码：

  2.     /**
  3.      * 解题思路：按位相加，如何处理 sum 和 carry
  4.      *
  5.      * 扩展：
  6.      *  1、如果处理多个字符串的相加
  7.      *  2、如果相加中包含负数该如何处理
  8.      *  3、相加后如何判断超过 Int 类型限制（大数相加）
  9.      * @param num1
  10.      * @param num2
  11.      * @return
  12.      */
  13.     public String addTwoStrings(String num1, String num2) {
  14.         int i = num1.length() - 1, j = num2.length() - 1;
  15.         StringBuilder sb = new StringBuilder();
  16.         int carry = 0, sum = 0;
  17.         while (i >= 0 || j >= 0) {
  18.             // 双指针按位相加，如果没有位则按0值处理
  19.             int a = i >= 0 ? num1.charAt(i) - '0' : 0;
  20.             int b = j >= 0 ? num2.charAt(j) - '0' : 0;
  21. //            System.out.println("a = " + a + "; b = " + b);
  22.             sum = a + b + carry;
  23.             carry = sum / 10;
  24.             sb.append(sum % 10);
  25.             i--;
  26.             j--;
  27.         }
  28.         if (carry == 1) sb.append(carry);
  29.         return sb.reverse().toString();
  30.     }
  32.     /**
  33.      * 多个字符串相加
  34.      * @param strs
  35.      * @return
  36.      */
  37.     public String addMultiStrings(String[] strs) {
  38.         if (strs.length == 1) return strs[0];
  39.         String twoSum = addTwoStrings(strs[0] , "0");
  40.         System.out.println("first = " + twoSum);
  41.         for (int i = 1; i < strs.length; i++) {
  42.                 twoSum = addTwoStrings(strs[i], twoSum);
  43.                 System.out.println("iter twoSum = " + twoSum);
  44.         }
  45.         return twoSum;
  46.     }

模版

题意分析：
解题思路：
注意点：
扩展：
代码：