孤狗

Posted on | Edited on | In | | Views:
Symbols count in article: 99k | Reading time ≈ 1:43

迎难而上，祝我好运。

2021版本

受欢迎的元素

  • 给一个数组，求其中受欢迎的元素（出现频数超过一半）。Map统计即可。
  • 若数组排好序了，求出现频数超过n/4的。既然排好序就可以考虑直接通过前后比较来计数了，不需要额外空间。
  • follow-up: 优化时间复杂度？排好序就应该想下有没有贪心/挪指针/二分查找了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    public int getPopularElement(int[] sorted) {
        if (sorted == null || sorted.length == 0) {
            // throw new InputValidationExcpetion();
            return -1;
        }
        int n = sorted.length, threshold = n / 4;
        if (countElement(sorted, sorted[n / 4]) > threshold) {
            return sorted[n / 4];
        } else if (countElement(sorted, sorted[n / 2]) > threshold) {
            return sorted[n / 2];
        } else if (countElement(sorted, sorted[(n * 3) / 4]) > threshold) {
            return sorted[(n * 3) / 4];
        } else {
            // throw new NotFoundException();
            return -1;
        }
    }
    private int countElement(int[] arr, int target) {
        int firstIndex = binarySearchFirst(arr, target);
        int lastIndex = binarySearchLast(arr, target);
        return lastIndex - firstIndex + 1;
    }
    private int binarySearchFirst(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {          // [left, right)
            int mid = left + (right - left) / 2;
            if (arr[mid] >= target) {   // [left, mid)
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private int binarySearchLast(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {   // [mid + 1, right)
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }

flip一次求最多1的数量

  • 给一个硬币面朝上朝下的0/1一维数组，求通过最多一次局部翻转(翻转起止位置自己定)能够得到的最大1的个数。

  • 本质上就是求0比1数量多最多的subarray段，类似用贪心做法求max subarray sum。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    public int maxSumAfterFlip(int[] coins) {
        if (coins == null || coins.length == 0) {
            return 0;
        }
        int currSum = 0, maxSum = 0, ones = 0;
        int left = 0, right = 0, len = coins.length;
        while (left < len) {
            if (coins[left] == 0) {
                right = left;
                currSum = 0;
                while (right < len) {
                    if (coin[right] == 0) {
                        currSum++;
                    } else {
                        ones++;
                        currSum--;
                    }
                    if (currSum <= 0) {
                        break;      // 这一段的0和1持平，直接忽略
                    }
                    // 表示这一段0比1多多少，也就是翻转后会多出多少1
                    maxSum = Math.max(currSum, maxSum);
                    left++;
                    right++;
                }
            }
            left++;
        }
        return maxSum + ones;
    }

  • follow-up：如果要记录起止位置？那么就在内层while循环中maxSum需要更新时对start, end赋值即可。

  • follow-up：如果将一维数组换成二维matrix，求其中submatrix flip之后最多能得到的1的数量？

2018版本

10. regular-expression-matching

  • 输入两个字符串，写个支持.和*的正则表达式判断的method。例如s = "ab", p = "a*", 为True。
  • 目标字符串s和正则字符串p之间相互比较，就需要维护一个boolean的二维数组dp[i][j]，表示s[0~i-1]与p[0~j-1]是否匹配。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
      public boolean isMatch(String s, String p) {
          if (s == null || p == null || s.equals(p)) {
              return true;
          }
          char[] sChar = s.toCharArray(), pChar = p.toCharArray();
          int m = sChar.length, n = pChar.length;
          boolean[][] dp = new boolean [m + 1][n + 1];
          
          // initial the dp states
          dp[0][0] = true;
          for (int j = 2; j <= n; j++) {
              dp[0][j] = pChar[j - 1] == '*' && dp[0][j - 2];
          }
          
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  if (pChar[j - 1] == '*') {  
                      // check if ignoring curr pattern
                      // OR (the char is matched AND ignoring curr pattern)
                      dp[i][j] = (dp[i][j - 2]) // 不取pattern
                          || ((sChar[i - 1] == pChar[j - 2] || pChar[j - 2] == '.') && dp[i - 1][j]);
                  } else {
                      // check if char is matched for curr pattern
                      dp[i][j] = dp[i - 1][j - 1] 
                          && (sChar[i - 1] == pChar[j - 1] || pChar[j - 1] == '.');
                  }
              }
          }
          return dp[m][n];
      }
    }

36. valid-sudoku

  • 给一个二维char数组，里面是一个未完成的数独9x9棋盘，要求每一行、每一列、每个3x3方块中数字1-9有且仅有出现一次。判断这个棋盘是否符合数独规则，返回布尔值。

  • 方法一：直接双重循环遍历，注意可以利用index的变换同时判断行、列和box的情况

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        for (int i = 0; i < board.length; i++) {
            Set<Character> rowSet = new HashSet<>();
            Set<Character> colSet = new HashSet<>();
            Set<Character> boxSet = new HashSet<>();
            int rowIndex = 3 * (i / 3), colIndex = 3 * (i % 3);
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.' && !rowSet.add(board[i][j])) {
                    return false;
                }
                if (board[j][i] != '.' && !colSet.add(board[j][i])) {
                    return false;
                }
                if (board[rowIndex + j / 3][colIndex + j % 3] != '.' 
                    && !boxSet.add(board[rowIndex + j / 3][colIndex + j % 3])) {
                    return false;
                }
            }
        }
        return true;
    }

  • 方法二：利用String encoding，直接将每个数字出现的行、列、box情况encode成String存入set。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        Set<String> set = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    if (!set.add(board[i][j] + " in row " + i) 
                        || !set.add(board[i][j] + " in col " + j) 
                        || !set.add(board[i][j] + " in block " + (i / 3) + '-' + (j / 3))) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

37. sudoku-solver

  • 给一个二位char数组，里面是一个未完成的数独9x9棋盘，要求每一行、每一列、每个3x3方块中数字1-9有且仅有出现一次。解出数独，解有且仅有一种，直接在原二维数组中将.改为数字的char。
  • 暴力dfs，确定一个位置后就进入下一层DFS去判断。时间复杂度为O(9^m)，m为可填的空位数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    final String inRow = " in row ";
    final String inCol = " in col ";
    final String inBlk = " in blk ";
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return;
        }
        
        Set<String> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    set.add(board[i][j] + inRow + i);
                    set.add(board[i][j] + inCol + j);
                    set.add(board[i][j] + inBlk + i/3 + "-" + j/3);
                }
            }
        }
        dfs(board, set);
    }
    private boolean dfs(char[][] board, Set<String> set) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int c = 0; c < 9; c++) {
                        char temp = (char)(c + '1');
                        String row = temp + inRow + i;
                        String col = temp + inCol + j;
                        String blk = temp + inBlk + i/3 + "-" + j/3;
                        if (!set.contains(row) && !set.contains(col) && !set.contains(blk)) {
                            set.add(row);
                            set.add(col);
                            set.add(blk);
                            board[i][j] = temp;
                            if (dfs(board, set)) {
                                return true;
                            } else {
                                set.remove(row);
                                set.remove(col);
                                set.remove(blk);
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

41. first-missing-positive

  • 给一个乱序整数数组，要求返回所缺正整数中的最小值。要求constant space，O(n).例如[3,4,-1,1]，返回2.
  • 尝试将在合理范围内的正数[1, nums.length]放入对应的位置，即与它的值对应的索引进行swap，注意执行swap之前需要判断该对应处的元素是否已经处在正确的位置，已经是正确位置就不能swap。最后从头遍历一波，第一个放错位置的即为所求。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length) {
                i++;
            } else if (nums[nums[i] - 1] != nums[i]) { // warning: not nums[i] != i + 1
                // critical: avoid re-overwriting that correct spot
                swap(nums, i, nums[i] - 1); // i is curr index, nums[i] - 1 is where it should be
            } else {
                i++;
            }
        }
        i = 0;
        while (i < nums.length && nums[i] == i + 1) {
            i++;
        }
        return i + 1;
    }
    private void swap(int[] nums, int i, int j) {
        int temp =  nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

42. trapping-rain-water

  • 给一个int数组，其中包含每个索引处墙的高度。求装满水时的横截面的积水的面积。
  • 利用双指针，left向后更新maxLeft，right往前更新maxRight。每次在left处和right处的高度中取较小值与maxLeft和maxRight进行比较，如果是凹的就直接累加高度差即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int area = 0, maxLeft = 0, maxRight = 0;
        int left = 0, right = height.length - 1;
        while (left <= right) {
            if (height[left] <= height[right]) {    // curr value less than some right value
                if (maxLeft <= height[left]) {
                    maxLeft = height[left];
                } else {                            // curr value is also less than left value
                    area += maxLeft - height[left]; // means it is concave
                }
                left++;
            } else {
                if (maxRight <= height[right]) {
                    maxRight = height[right];
                } else {
                    area += maxRight - height[right];
                }
                right--;
            }
        }
        return area;
    }

43. multiply-strings

  • 给两个字符串形式的int，模拟乘法求他们的积，返回字符串。
  • 观察index的关系，num1的第i个数字乘以num2的第j个数字得到的两位数将出现在结果数的第i + j和第i + j + 1位。因此就从最低位开始，双重循环相乘，不断更新结果数组即可。注意数组中保存的是一位数，有进位需要存到前一个位置。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null
            || num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        int m = num1.length(), n = num2.length();
        int[] result = new int [m + n];
        char[] cnum1 = num1.toCharArray(), cnum2 = num2.toCharArray();
        
        // from least significant bit
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mult = (cnum1[i] - '0') * (cnum2[j] - '0');
                int first = i + j, second = i + j + 1;
                int sum = mult + result[second];    // add carry from prev steps
                result[first] += sum / 10;  // accumulate
                result[second] = sum % 10;  // overwrite
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int i = 0;
        // find the first non-zero item
        while (i < result.length && sb.length() == 0 && result[i] == 0) {
            i++;
        }
        while (i < result.length) {
            sb.append(result[i++]);
        }
        return sb.length() == 0? "0": sb.toString();
    }

44. wildcard-matching

  • 和前面的regular-expression-matching很像，但这里用?代表任意一个字符、用*代表任意长度的任意字符而不依赖它前面的字符（而且不只能匹配单一个字符，直接匹配任意长度的任意字符组合）。总的来说比上一题简单，要讨论的情况少了。
  • 维护一个二维boolean数组，dp[i][j]表示s[0~i-1]和p[0~j-1]是否匹配。初始化方面，对于空的p，dp[i][0]仍是除dp[0][0]外全部false，不可能用空的p去匹配非空的s；对于空的s，dp[0][j]就要看当前是否是'*'且考虑dp[0][j-1]。接着双重循环更新dp
    -> 若当前字符p[j-1]是'*'，则考虑取p的*但不匹配s当前字符时，s[0~i-1]和p[0~j-2]的匹配情况，即dp[i][j-1]；或将'*'假设为s[i-1]那个字符，看看s[0~i-2]与p[0~i-1]的匹配情况，即dp[i-1][j]；或者不取*也不匹配s当前字符，s[0~i-2]和p[0~j-2]的匹配情况，即dp[i-1][j-1].
    -> 若当前字符p[j-1]不是'*'，就直接看s[i-1]和p[j-1]的匹配情况再结合dp[i-1][j-1]了。
    除了DP，这个题目似乎还可以用贪心给两个字符串分别用一个指针一直向后挪。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    public boolean isMatch(String s, String p) {
        if (s == null || p == null || s.equals(p)) {
            return true;
        }
        int m = s.length(), n = p.length();
        char[] sChar = s.toCharArray(), pChar = p.toCharArray();
        boolean[][] dp = new boolean [m + 1][n + 1];
        dp[0][0] = true;    // "" fits ""
        for (int j = 1; j <= n; j++) {   // only "x*" can fit ""
            if (pChar[j - 1] == '*') {
                dp[0][j] = dp[0][j - 1];
            } else {
                dp[0][j] = false;
            }
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pChar[j - 1] == '*') {  // don't take * or view * as one char or just
                                            // get rid of the char in sChar
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 1][j - 1];
                } else {
                    if (pChar[j - 1] == sChar[i - 1] || pChar[j - 1] == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        return dp[m][n];
    }

56. merge-intervals

  • 给一个Interval类的list，将重叠部分进行合并，返回合并之后的list。

  • 方法一：使用自定义排序，按照start再按照end排序，然后入栈，每次与栈顶比较。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null) {
            return new ArrayList<Interval>();
        }
        Collections.sort(intervals, 
            (a, b) -> a.start != b.start ？ 
                a.start - b.start : a.end - b.end;
        );
        Stack<Interval> stack = new Stack<>();
        for (Interval itv: intervals) {
            if (stack.isEmpty()) {
                stack.push(itv);
            } else {
                Interval curr = stack.peek();
                if (itv.start > curr.end) {
                    stack.push(itv);
                } else {
                    stack.peek().end = Math.max(itv.end, curr.end);
                }
            }
        }
        // directly get List from stack with constructor
        return new ArrayList<Interval>(stack);    
    }

  • 方法二：将左、右boundary分别排序，然后快慢指针遍历。当left[fast + 1] > right[fast]，说明slow~fast可以组成一个独立的interval，存入list后将慢指针放到fast + 1即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> ans = new ArrayList<Interval>();
        if (intervals == null) {
            return ans;
        }
        int len = intervals.size();
        int[] left = new int [len];     // all left boundary
        int[] right = new int [len];    // all right boundary
        for (int i = 0; i < len; i++) {
            left[i] = intervals.get(i).start;
            right[i] = intervals.get(i).end;
        }
        Arrays.sort(left);
        Arrays.sort(right);
        // fast will select right bound and fast+1 is the candidate for next left bound
        // when candidate is valid, store curr interval (slow, fast) and move slow to candidate
        // for next left bound
        for (int fast = 0, slow = 0; fast < len; fast++) {
            if (fast == len - 1 || left[fast + 1] > right[fast]) {
                ans.add(new Interval(left[slow], right[fast]));
                slow = fast + 1;
            }
        }
        return ans;
    }

59. spiral-matrix-ii

  • 给一个整数n，生成一个n*n的二维数组方阵，使得螺旋式遍历的结果为1,2,3,…,n^2。
  • 直接用循环搞。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    public int[][] generateMatrix(int n) {
        // Declaration
        int[][] matrix = new int[n][n];
        
        // Edge Case
        if (n == 0) {
            return matrix;
        }
        
        // Normal Case
        int rowStart = 0;
        int rowEnd = n - 1;
        int colStart = 0;
        int colEnd = n - 1;
        int num = 1; //change
        
        while (rowStart <= rowEnd && colStart <= colEnd) {
            for (int i = colStart; i <= colEnd; i++) {
                matrix[rowStart][i] = num++;   //change
            }
            rowStart++;
            
            for (int i = rowStart; i <= rowEnd; i++) {
                matrix[i][colEnd] = num++;     //change
            }
            colEnd--;
            
            for (int i = colEnd; i >= colStart; i--) {
                if (rowStart <= rowEnd)
                    matrix[rowEnd][i] = num++; //change
            }
            rowEnd--;
            
            for (int i = rowEnd; i >= rowStart; i--) {
                if (colStart <= colEnd)
                    matrix[i][colStart] = num++; //change
            }
            colStart++;
        }
        
        return matrix;
    }

72. edit-distance

  • 给两个字符串word1, word2，求使用addition, replacement, removement三种操作的情况下最少多少步可以从word1转换成word2。
  • dp[i][j]表示当前长度i的子字符串1转换成长度j的子字符串2最少需要的操作数。初始条件显然是dp[0][x] = dp[x][0] = x。对于任意一个dp[i][j]，需要由上、左上、左三个方格的计算结果决定，往上dp[i-1][j]表示一个deletion，往左dp[i][j-1]表示一个addition，左上dp[i-1][j-1]表示一个replacement。每次选取三者中最小的，加上1就是当前的最小操作数了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }
        int len1 = word1.length(), len2 = word2.length();
        int[][] dp = new int [len1 + 1][len2 + s1];
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    // s1取i-1、s2取j-1个字符的情况，然后s1和s2都取，不需要增加操作数
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        // left: s1取i、s2取j-1个字符的操作数，现在相当于需要往s1中加s2对应位置的字符才能匹配上
                        // up: s1取i-1、s2取j个字符的操作数，相当于要从s1中删除字符才能匹配上
                        // left-up: s1取i-1、s2取j-1个字符的操作数，现在相当于要进行替换才能匹配上
                        int left = dp[i][j - 1], up = dp[i - 1][j], upLeft = dp[i - 1][j - 1];
                        dp[i][j] = Math.min(Math.min(left, up), upLeft) + 1;
                    }
                }
            }
        }
        return dp[len1][len2];
    }

91. decode-ways

  • 给一个纯数字的字符串，看有多少中方式解析成对应的字母A-Z。如12可解析为AB或L两种，返回2。
  • 联想到“跳楼梯的方式”那题，每次可以选择1位数或者2位数，dp[i]表示取i个字符总共有多少decode的方式，那么当前的方式数就取决于前一位或者前两位的方式数。注意如果取两位digit，需要判断是否在10~26范围之内。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[ n+ 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        for (int i = 2; i <= n; i++) {
            int first = Integer.valueOf(s.substring(i - 1, i));
            int second = Integer.valueOf(s.substring(i - 2, i));
            if (first >= 1 && first <= 9) {
                dp[i] += dp[i - 1];  
            }
            if (second >= 10 && second <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }

95. unique-binary-search-trees-ii

  • 只给一个整数n表示二分查找树的节点数，返回所有结构不同的树。而上一问（96）则只是输出不同树的个数，只是个小DP。

  • 方法一：DP。dp[i]表示节点数为i的时候后所有可能的unique BST根节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[] dp = new List[n + 1];
        dp[0] = new ArrayList<TreeNode>();
        if (n < 1) {
            return dp[0];
        }
        dp[0].add(null);  // 空BST
        
        // BST: left children all smaller, right all larger.
        // each time fix the root, take prev as left subtree, and prev with offset as right subtree.
        // 固定跟节点，左子树节点数从0到n
        for (int nodeNum = 1; nodeNum <= n; nodeNum++) {
            dp[nodeNum] = new ArrayList<TreeNode>();
            for (int leftNum = 0; leftNum < nodeNum; leftNum++) {
                for (TreeNode leftNode: dp[leftNum]) {
                    for (TreeNode rightNode: dp[nodeNum - leftNum - 1]) {
                        TreeNode curr = new TreeNode(leftNum + 1);
                        curr.left = leftNode;
                        curr.right = addOffset(rightNode, leftNum + 1);
                        dp[nodeNum].add(curr);
                    }
                }
            }
        }
        return dp[n];
    }
    // its kinda tricky to come up with this offset
    private TreeNode addOffset(TreeNode node, int offset) {
        if (node == null) {
            return null;
        }
        TreeNode newNode = new TreeNode(node.val + offset);
        newNode.left = addOffset(node.left, offset);
        newNode.right = addOffset(node.right, offset);
        return newNode;
    }

  • 方法二：分治法，分别build左右两边的子树。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public List<TreeNode> generateTrees(int n) {
        if (n < 1) {
            return new ArrayList<TreeNode>();
        }
        return generate(1, n);
    }
    private List<TreeNode> generate(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {      // recursion end condition
            result.add(null);
            return result; 
        }
        // take i as root val
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = generate(start, i - 1);   // generate all possible left subtree
            List<TreeNode> right = generate(i + 1, end);    // gennerate all possible right subtree
            for (TreeNode l: left) {
                for (TreeNode r: right) {
                    TreeNode node = new TreeNode(i);    // set root val
                    node.left = l;
                    node.right = r;
                    result.add(node);
                }
            }
        }
        return result;
    }

OA: Email地址处理

  • 给String数组包含email地址，如name@domain，其中name需要将(1)dots(‘.’) between some characters去除 (2)如果有’+’，’+’和后面的全去除。将处理完的email地址归类，统计每个email出现个数，返回里面>1个email兄弟的个数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public int getEmailCount(String[] emails) {
        if (emails == null || emails.length == 0) {
            return 0;
        }
        Map<String, Set<String>> map = new HashMap<>();
        int count = 0;
        for (String email : emails) {
            int atIndex = email.indexOf("@");
            if (atIndex == -1) {
                continue;
            }
            String simplifiedEmail = simplify(email.substring(0, atIndex)) + email.substring(atIndex);
            map.putIfAbsent(simplifiedEmail, new HashSet<String>());
            map.get(simplifiedEmail).add(email);
        }
        for (Map.Entry<String, Set<String>> e : map.entrySet()) {
            if (e.getValue().size() > 1) {
                count++;
            }
        }
        return count;
    }
    private String simplify(String local) {
        return local.replaceAll("(?<=[a-zA-Z]+)\\.+(?=[a-zA-Z]+)|(\\+.*)", "");
    }

OA: 两个篮子取水果

  • lc 159变种。只有两个篮子可以放水果，每个篮子只能放一样水果，但可以放无数个相同的水果。从任意一个位置开始往右取，求最多取多少水果。
  • 滑动窗口。

OA: 上一个最接近时间

  • 类似于lc 681. 给一个时间string如hh:mm，求前一个最近的时间，可以重复使用已有的数字。
  • 将所有出现过的数字存入TreeSet，从最低位开始尝试将当前数字替换成比他小的最大的数，若存在这样的数就是previou closest time了，若没有这样的数则需要替换成最大值，注意需要validate。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    public static String prevClosestTime(String time) {
        if (time == null || time.length() != 5) {
            return null;
        }
        TreeSet<Integer> digitSet = new TreeSet<>();
        char maxChar = '0';
        for (char c : time.toCharArray()) {
            if (c != ':') {
                digitSet.add(c - '0');
                maxChar = (char) Math.max(maxChar, c);
            }
        }
        char[] ans = time.toCharArray();
        for (int i = 4; i >= 0; i--) {
            if (i != 2) {
                int currDigit = ans[i] - '0';
                Integer temp = digitSet.lower(currDigit);
                if (temp != null) {
                    ans[i] = (char) (temp + '0');
                    return String.valueOf(ans);
                } else {
                    updateDigitToMax(ans, i, maxChar, digitSet);
                }
            }
        }
        return String.valueOf(ans);
    }
    private static void updateDigitToMax(char[] ans, int i, char maxChar, TreeSet<Integer> digitSet) {
        if (i == 3 && maxChar > '5') {
            ans[i] = (char) (digitSet.floor(5) + '0');
        } else if (i == 1 && ans[i - 1] == '2' && maxChar > '3') {
            ans[i] = (char) (digitSet.floor(3) + '0');
        } else if (i == 0 && maxChar > '2') {
            ans[i] = (char) (digitSet.floor(2) + '0');
        } else {
            ans[i] = maxChar;
        }
    }

OA: 开花时间

  • 给一个数组，index表示开花时间，element表示开花的位置，第i天arr[i]位置的花会开，为了维持M个group，问最晚的天数k。
  • 考虑逆向处理，这样就可以保证先找到是最晚天数。在最后一天所有的花都开了，使用TreeSet存放没有开的花的index，往前找最大的天数、往后找最小的天数，若前后都间隔了>= k，说明前后都满足连续>= k朵花开放的条件，这样clusterCount++。但是若当前没有开导致前后的小于k，就需要减少clusterCount。当clusterCount == m时就是最晚的、有m个至少k朵花开放的天数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    public static int getDay(int[] flowers, int k, int m) {
        if (flowers == null || flowers.length == 0) {
            return 0;
        }
        TreeSet<Integer> posSet = new TreeSet<>();
        int count = 1;
        for (int day = flowers.length - 1; day >= 0; day--) {
            Integer prevPos = posSet.lower(flowers[day]);
            if (prevPos == null) {
                prevPos = 0;
            }
            Integer nextPos = posSet.higher(flowers[day]);
            if (nextPos == null) {
                nextPos = flowers.length + 1;
            }
            int prevBloomLen = flowers[day] - prevPos - 1;
            int nextBloomLen = nextPos - flowers[day] - 1;
            if (prevBloomLen >= k && nextBloomLen >= k) {
                count++;
            } else if (prevBloomLen < k && nextBloomLen < k) {
                count--;
            }
            if (count >= m) {
                return day;
            }
            posSet.add(flowers[day]);
        }
        return -1;
    }

以下是实习面经

求有序数组的平方数

  • 给一个有序数组，求其中各项平方后的结果并排好序。
  • 方法一：双指针，一个从0开始往后，一个从最后一个元素往前，比较大小然后从后往前地存入结果数组。O(N)。
  • 方法二：从前往后，找到第一个非负数开始，往前后两个方向merge，搜索部分复杂度O(N)，merge部分复杂度O(N)。

  • 方法三：既然是有序，那么查找的时候就用二分查找，找『0插入的地方』，然后往两边merge。搜索部分复杂度O(logN)，merge部分复杂度O(N)。再来复习一遍二分查找找第一个出现／插入的位置：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    private int binarySearch(int[] nums, int target) {
        int start = -1, end = nums.length;
        while (end - start > 1) {
            int mid = start + (end - start) / 2;
            // invariant relation: nums[start] < target <= nums[end]
            if (nums[mid] >= target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        return end;
    }

  • follow-up：这次是求x ^ 2 + a * x而不单单是平方了。

  • 思路也是类似，找到函数的最小值，往两边merge，这里对称轴出现在-a/2，所以找到这个值之后往两边merge即可。

String字符交换

  • 给两个字符，问能否交换str1的两个字符得到str2.
  • 需要考虑两个字符串本身是否相等？长度小于2？

  • 方法一：从前往后遍历两个数组，把不同的位置拼到List里，然后判断不同的是否恰好两位且可以互换。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    private boolean convert(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        List<Integer> arr = new ArrayList<>();
        char[] sChar1 = s1.toCharArray();
        char[] sChar2 = s2.toCharArray();
        for (int i = 0; i < sChar1.length; i++) {
            if (sChar1[i] != sChar2[i]) {
                arr.add(i);
            }
        }
        if (arr.size() != 2) {
            return false;
        }
        if (sChar1[arr.get(0)] == sChar2[arr.get(1)] && sChar1[arr.get(1)] == sChar2[arr.get(0)]) {
            return true;
        }
        return false;
    }

  • 方法二：优化空间，不用额外的List，而是直接用一个变量记录第一个不同的索引，之后再出现不同直接判断就可以了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    private boolean convert(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        char[] sChar1 = s1.toCharArray();
        char[] sChar2 = s2.toCharArray();
        int index = -1, count = 0;
        for (int i = 0; i < sChar1.length; i++) {
            if (sChar1[i] != sChar2[i]) {
                count++;
                if (count > 2) {
                    return false;
                }
                if (index == -1) {
                    index = i;
                } else {
                    if (sChar1[index] != sChar2[i] || sChar2[index] != sChar1[i]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

同义词 734 737

  • 给一堆同义词[(“restaurant”, “cafe”), (“ratings”, “reviews”), …]，再给一些queries[(“restaurant ratings”, “cafe reviews”), …]，要求返回每个query里的对应词是否都是synonym。

  • 如果不需要考虑传递性，就直接把字符作为key、对应的所有同义词的set作为value存入map，正反都放一次，比如map.get("restaurant").add("cafe")), map.get("restaurant").add("cafe")，这样在query的时候就可以直接调用了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    // 维护一个总的map，每个单词作为key，对等的单词塞入它维护的Set中
    // 有对称性所以需要正反都加
    public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {
        if (words1 == null || words2 == null || pairs == null
            || words1.length != words2.length) {
            return false;
        }
        
        Map<String, Set<String>> map = new HashMap<>();
        for (int i = 0; i < pairs.length; i++) {
            if (!map.containsKey(pairs[i][0])) {
                map.put(pairs[i][0], new HashSet<>());
            }
            if (!map.containsKey(pairs[i][1])) {
                map.put(pairs[i][1], new HashSet<>());
            }
            map.get(pairs[i][0]).add(pairs[i][1]);  // 构建a->b
            map.get(pairs[i][1]).add(pairs[i][0]);  // 构建b->a
        }
        
        for (int i = 0; i < words1.length; i++) {
            if (words1[i].equals(words2[i])) {
                continue;
            }
            if (map.get(words1[i]) == null || !map.get(words1[i]).contains(words2[i])) {
                return false;
            }
        }
        return true;
    }

  • 需要考虑是否可以传递，比如a=b, b=c -> a=c?，可能就需要有个并查集找共同老大。或者直接通过DFS遍历所有可达点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    // 和前一个版本的区别是这个可以无限传递a=b=c=d...
    // 还是map维护每个单词等价的单词，但匹配不上的话还得看它的set里所有单词对应的单词是否能匹配到
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1 == null || words2 == null || pairs == null
            || words1.length != words2.length) {
            return false;
        }
        // 表示每个单词直接相连的同义词
        Map<String, Set<String>> map = new HashMap<>();
        for (int i = 0; i < pairs.length; i++) {
            if (!map.containsKey(pairs[i][0])) {
                map.put(pairs[i][0], new HashSet<>());
            }
            if (!map.containsKey(pairs[i][1])) {
                map.put(pairs[i][1], new HashSet<>());
            }
            map.get(pairs[i][0]).add(pairs[i][1]);  // 构建a->b
            map.get(pairs[i][1]).add(pairs[i][0]);  // 构建b->a
        }
        
        for (int i = 0; i < words1.length; i++) {
            if (words1[i].equals(words2[i])) {
                continue;
            }
            if (!map.containsKey(words1[i])) {
                return false;
            }
            if (!dfs(words1[i], words2[i], map, new HashSet<String>())) {
                return false;
            }
        }
        return true;
    }
    private boolean dfs(String start, String end, Map<String, Set<String>> map, Set<String> visited) {
        if (map.get(start).contains(end)) {     // 终止条件：start连接着end
            return true;
        }
        visited.add(start);
        Set<String> neighbors = map.get(start);
        if (neighbors == null) {
            return false;
        }
        for (String neighbor : neighbors) {
            if (!visited.contains(neighbor) && dfs(neighbor, end, map, visited)) {
                return true;
            }
        }
        return false;
    }

  • 或者通过并查集，初始化时每个单词都是自己的root；然后根据同义词关系将前者的老大设为后者。判断句子是否同义时就找两个单词的老大是否相等即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    // 并查集。初始化时每个单词都是自己的root；然后根据同义词关系将前者的老大设为后者。
    // 判断句子是否同义时就找两个单词的老大是否相等即可
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        }
        Map<String,String> map = new HashMap<>();
        for (String[] pair : pairs) {     // 开始时每个老大都是自己
            map.put(pair[0], pair[0]);
            map.put(pair[1], pair[1]);
        }
        for (String[] pair : pairs) {
            String par1 = findParent(pair[0], map);
            String par2 = findParent(pair[1], map);
            if (!par1.equals(par2)) {
                map.put(par1, par2);    // par1的老大设为par2
            }
        }
        for (int i = 0; i < words1.length; i++) {
            if (words1[i].equals(words2[i])) {
                continue;
            }
            if (!map.containsKey(words1[i]) || !map.containsKey(words2[i])) {
                return false;
            }
            String par1 = findParent(words1[i], map);
            String par2 = findParent(words2[i], map);
            if (!par1.equals(par2)) {
                return false;
            }
        }
        return true;
    }
    public String findParent(String str, Map<String,String> map){
            while (!str.equals(map.get(str))) { // 追溯str的老大
                str = map.get(str);              
            }
            return str;
    }

flip game 293 294

  • 给一个只含有+和-的字符串，两个人每次选择一个++flip成--。
  • 第一问：求下一步所有可能的情况。直接找连续出现的++然后取前面部分的substring拼上--再拼上后续部分即可。
  • 第二问：问先开始的玩家能否保证赢（操作后再也没有++让对方没法再flip）。暴力的方法是从头开始循环找到每个startsWith("++")，然后替换成--再递归判断对方能否稳赢。一旦对方没法稳赢，就直接return了。但是复杂度略高。可以用Set或者Map缓存中间结果，避免重复递归。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        // O(n!!) 复杂度。递归找，找到++的时候就替换成--然后递归判断对方能否保证赢，不能就直接返回true了。
        public boolean canWin(String s) {
            if (s == null || s.length() < 2) {
                return false;
            }
            Map<String, Boolean> map = new HashMap<>();  // 存放已经访问过的的String
            return canWin(s, map);
        }
        private boolean canWin(String s, Map<String, Boolean> map) {
            if (map.containsKey(s)) {
                return map.get(s);
            }
            for (int i = 0; i < s.length(); i++) {
                if (s.startsWith("++", i)) {
                    String t = s.substring(0, i) + "--" + s.substring(i + 2);
                    if (!canWin(t, map)) {   // 轮到对方操作，判断
                        map.put(s, true);
                        return true;
                    }
                }  
            }
            map.put(s, false);     // 缓存起来
            return false;
        }
    }

首个prefix不匹配字符串

  • 给出一个按字典序排好序的字符串数组dictionary，找出其中第一个不是以指定字符串prefix作为前缀的字符串。如[aa, aaa, ax, b, c], aa -> ax
  • 看到“排好序”，“找”，就想到二分查找了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Google {
        // O(logN)二分查找第一个不符合要求的XD
        public String firstUnmatch(String[] words, String prefix) {
            int lo = 0, hi = words.length - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (words[mid].startsWith(prefix)) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            return lo == words.length || words[lo].startsWith(prefix)? 
            		"none": words[lo];
        }
    }

flatten iterator 251

  • 给一个二维List，要求模拟一维iterator，用hasNext和next从头到尾遍历。

  • 方法一： 第一版的两个iterator遍历的方法，其实不必要存下整个vec2d。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    public class Vector2D implements Iterator<Integer> {
        private List<List<Integer>> vec2d;
        private Iterator<Integer> itCol = null;
        private Iterator<List<Integer>> itRow = null;
        public Vector2D(List<List<Integer>> vec2d) {
            this.vec2d = vec2d;
            if (vec2d == null || vec2d.size() == 0) {
                itRow = null;
            } else {
                itRow = vec2d.iterator();
                itCol = itRow.next().iterator();
            }
        }
        @Override
        public Integer next() {
            if (!itCol.hasNext()) {
                return null;
            }
            Integer ret = itCol.next();
            return ret;
        }
        @Override
        public boolean hasNext() {
            if (itCol == null) {
                return false;
            }
            if (itCol.hasNext()) {
                return true;
            }
            while (itCol != null && !itCol.hasNext()) {
                if (itRow != null) {
                    if (!itRow.hasNext()) {
                        return false;
                    } else {
                        while (itRow.hasNext()) {
                            List<Integer> newRow = itRow.next();
                            itCol = newRow.iterator();
                            if (itCol.hasNext()) {
                                return true;
                            }
                        }
                    }
                } else {
                    return false;
                }
            }
            return false;
        }
    }
    /**
     * Your Vector2D object will be instantiated and called as such:
     * Vector2D i = new Vector2D(vec2d);
     * while (i.hasNext()) v[f()] = i.next();
     */

  • 经过简洁：省略了很多条件语句。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    public class Vector2D implements Iterator<Integer> {
        // 只用到两个iterator，一个存第几行，一个存当前行的第几列
        Iterator<List<Integer>> itRow;
        Iterator<Integer> itCol;
        public Vector2D(List<List<Integer>> vec2d) {
            itRow = vec2d.iterator();   
        }
        @Override
        public Integer next() {
            if (itCol.hasNext()) {
                return itCol.next();
            } else {
                return null;
            }
        }
        @Override
        public boolean hasNext() {
            // 当itCol为空或当前行没有next 并且还有后续行的时候
            while ((itCol == null || !itCol.hasNext()) && itRow.hasNext()) {
                itCol = itRow.next().iterator();    // 持续挪
            }
            return itCol != null && itCol.hasNext();   // 空或新行行首
        }
    }

判断二叉树是否对称 101

  • recursive：对称就是在递归判断左子树和右子树是否对称

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return helper(root.left, root.right);
        }
        private boolean helper(TreeNode left, TreeNode right) {
            if (left == null && right == null) {
                return true;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val == right.val) {    // 首先保证节点值相等
                // 然后判断左-左和右-右 以及 左-右和右-左
                return helper(left.left, right.right) && helper(left.right, right.left);
            }
            return false;
        }
    }

  • iterative：用Stack吞吐，左先入栈再到右，弹出判断左右是否相等。然后先入左-左再入右-右，然后左-右和右-左（保证对称）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root.left);
            stack.push(root.right);
            while (!stack.isEmpty()) {
                TreeNode left = stack.pop();        // take two nodes from stack top
                if (stack.isEmpty()) {
                    return false;                   // should always have 2 at 
                }
                TreeNode right = stack.pop();
                if (left == null && right == null) {
                    continue;
                }
                if (left == null || right == null
                   || left.val != right.val) {      // ensure equal
                    return false;
                }
                stack.push(left.left); // push 2 symmetric positions into stack
                stack.push(right.right);
                stack.push(left.right);
                stack.push(right.left);
            }
            return true;
        }
    }

  • follow-up：判断多叉树是否对称。直觉就是把left、right换成一个List<TreeNode>，判断对称的时候一个从前往后取子节点、另一个从后往前取子节点。

outbound spiral

  • 給一個String 用outbound spiral方式輸出，例如abcd -> cdba，abcde -> cdbae。(其实没太看懂这题啥意思。。。)
  • 双指针，从中间点开始往两边取。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Google {
        public spiralString(String s) {
            StringBuilder sb = new StringBuilder();
            char[] sChar = s.toCharArray();
            int right = sChar.length / 2, left = right - 1;
            return sb.toString();
        }
    }

Longest substirng with k distinct characters 340

  • 给一个字符串和k，求最长子字符串的长度使得其中只含有k个不同的字符。
  • substring问题->双指针。O(N)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Google {
        // 双指针，right向前直到多过允许的k个，然后挪left直到恢复到k个
        public int longestSubstringK(String s, int k) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            Map<Character, Integer> map = new HashMap<>();
            int maxLen = 0, currCharNum = 0, left = 0;
            char[] sChar = s.toCharArray();
            for (int right = 0; right < sChar.length; right++) {
                if (!map.containsKey(sChar[right])) {
                    currCharNum++;
                    map.put(sChar[right], 1);
                } else {
                    map.put(sChar[right], map.get(sChar[right]) + 1);
                }
                if (currCharNum > k) {
                    while (currCharNum > k && left < sChar.length) {
                        Integer temp = map.get(sChar[left]);
                        if (temp == 1) {
                            map.remove(sChar[left]);
                            currCharNum--;
                        } else {
                            map.put(sChar[left], temp - 1);
                        }
                        left++;
                    }
                }
                maxLen = Math.max(maxLen, right - left + 1);
            }
            return maxLen;
        }
    }

正则 10

  • 输入两个字符串，写个支持.和*的正则表达式判断的method。
  • 目标字符串s和正则字符串p之间相互比较，就需要维护一个boolean的二维数组dp[i][j]，表示s[0~i-1]与p[0~j-1]是否匹配。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
      public boolean isMatch(String s, String p) {
          if (s == null || p == null || s.equals(p)) {
              return true;
          }
          char[] sChar = s.toCharArray(), pChar = p.toCharArray();
          int m = sChar.length, n = pChar.length;
          boolean[][] dp = new boolean [m + 1][n + 1];
          
          // initial the dp states
          dp[0][0] = true;
          for (int j = 2; j <= n; j++) {
              dp[0][j] = pChar[j - 1] == '*' && dp[0][j - 2];
          }
          
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  if (pChar[j - 1] == '*') {  
                      // check if ignoring curr pattern
                      // OR (the char is matched AND ignoring curr pattern)
                      dp[i][j] = (dp[i][j - 2]) 
                          || ((sChar[i - 1] == pChar[j - 2] || pChar[j - 2] == '.') && dp[i - 1][j]);
                  } else {
                      // check if char is matched for curr pattern
                      dp[i][j] = dp[i - 1][j - 1] 
                          && (sChar[i - 1] == pChar[j - 1] || pChar[j - 1] == '.');
                  }
              }
          }
          return dp[m][n];
      }
    }

X删除字眼

  • 给一个字符串如aabbaac，给一个forbidden字眼a，返回删除后的字符串bbc，若不存在就返回本身。
  • O(N)直接用StringBuilder拼接。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Google {
        // 直接拼接
        public void deleteChar(String s, char c) {
            StringBuilder sb = new StringBuilder();
            char[] sChar = s.toCharArray();
            for (char temp: sChar) {
                if (temp != c) {
                    sb.append(temp);
                }
            }
            return sb.toString();
        }
    }

字母矩阵移动组成单词

  • 给一个列数生成由大写字母组成的矩阵，再给一个单词，从左上角开始挪动，求挪动的路径（用&连接).
  • 求路径，用BFS可以保证最短。在point中加入一个path段记录到达该处的路径，一旦找到目标字符就直接把path拼进去。再以该处为起点继续找后续字符（需要清空path）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    class Google {
        class Point {
            int row, col;
            String path;
            public Point(int row, int col, String path) {
                this.row = row;
                this.col = col;
                this.path = path;
            }
        }
        final private int CHAR_NUM = 26;
        public String moveWord(int width, String target) {
            if (target == null || target.length() == 0) {
                return new ArrayList<String>();
            }
            char[][] table = buildTable(width);
            int rows = table.length, cols = table[0].length;
            char[] targetChar = target.toCharArray();
            Point curr = new Point(0, 0);
            StringBuilder sb = new StringBuilder();
            boolean first = true;
            for (int i = 0; i < targetChar.length; i++) {
                curr = bfs(table, curr, targetChar[i], new boolean[][] visited);
                if (!first) {
                    sb.append(" & ");
                }
                sb.append(curr.path);
                curr.path = "";     // 重置当前点为起点
                first = false;
            }
            return sb.toString();
        }
        private Point bfs(char[][] table, Point p, char c, boolean[][] visited, String path, StringBuilder sb) {
            if (visited[p.row][p.col]) {
                return null;
            }
            Queue<Point> q = new LinkedList<>();
            q.add(p);
            while (!q.isEmpty()) {
                Point curr = q.poll();
                if (table[curr.row][curr.col] == c) {     // 找到了
                    return curr;
                }
                visited[curr.row][curr.col] = true;       // 标记当前坐标点已访问
                if (curr.col < table[0].length - 1 && !visited[curr.row][curr.col + 1]) {
                    q.add(new Point(curr.row, curr.col + 1, curr.path + "R"));
                }
                if (curr.row < table.length - 1 && !visited[curr.row + 1][curr.col]) {
                    q.add(new Point(curr.row + 1, curr.col, curr.path + "D"));
                }
                if (curr.col > 0 && !visited[curr.row][curr.col - 1]) {
                    q.add(new Point(curr.row, curr.col - 1, curr.path + "L"));
                }
                if (curr.row > 0 && !visited[curr.row - 1][curr.col]) {
                    q.add(new Point(curr.row - 1, curr.col, curr.path + "U"));
                }
            }
            return null;
        }
        private char[][] buildTable(int width) {
            int height = CHAR_NUM / width;
            if (CHAR_NUM % width > 0) {
                height++;
            }
            char[][] table = new char[height][width];
            char c = 'A';
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width && c < 'Z'; j++) {
                    table[i][j] = c++;
                }
            }
            return table;
        }
    }

43. multiply-strings

解析在此

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null
           || num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        int m = num1.length(), n = num2.length();
        int[] result = new int [m + n];
        char[] cnum1 = num1.toCharArray(), cnum2 = num2.toCharArray();
        
        // from least significant bit
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mult = (cnum1[i] - '0') * (cnum2[j] - '0');
                int first = i + j, second = i + j + 1;
                int sum = mult + result[second];    // add carry from prev steps
                result[first] += sum / 10;  // accumulate
                result[second] = sum % 10;  // overwrite
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int i = 0;
        // find the first non-zero item
        while (i < result.length && sb.length() == 0 && result[i] == 0) {
            i++;
        }
        while (i < result.length) {
            sb.append(result[i++]);
        }
        return sb.length() == 0? "0": sb.toString();
    }
}

格子中最长连续 562

  • 给一个只有0和1的int二维数组，求横或竖或两个对角方向上最长连续出现1的个数。

  • 方法一：O(N^2)从每个点出发往四个方向分别遍历，求最长长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class Solution {
        // O(N^3)：矩阵遍历每个点是N^2，对每个点在扫四个方向是4N
        public int longestLine(int[][] M) {
            if (M == null || M.length == 0 || M[0].length == 0) {
                return 0;
            }
            int longest = 0;
            for (int i = 0; i < M.length; i++) {
                for (int j = 0; j < M[0].length; j++) {
                    if (M[i][j] == 1) {
                        longest = Math.max(longest, getLongest(M, i, j));
                    }
                }
            }
            return longest;
        }
        // 右、下、右下、左下
        final private int[][] directions = new int[][] {{0, 1}, {1, 0}, {1, 1}, {1, -1}}; 
        private int getLongest(int[][] M, int row, int col) {
            int maxLen = 1;
            for (int[] direction: directions) {
                int len = 1;
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                // 持续在一个方向上继续走
                while (isValidPosition(M, newRow, newCol) && M[newRow][newCol] == 1) {
                    len++;
                    newRow += direction[0];
                    newCol += direction[1];
                }
                maxLen = Math.max(maxLen, len);
            }
            return maxLen;
        }
        private boolean isValidPosition(int[][] M, int row, int col) {
            return row >= 0 && col >= 0 &&
                row < M.length && col < M[0].length;
        }
    }

  • 方法二：类似于DP，记录下四个方向各自的最大长度。参考这个被lz
    和N皇后问题很像。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
        // O(N^2)时间，O(M+N)空间
        public int longestLine(int[][] M) {
            // validation
            if (M == null || M.length == 0 || M[0].length == 0) {
                return 0;
            }
            int rows = M.length, cols = M[0].length;
            int longest = 0;
            int[] bucketCol = new int [cols];
            int[] bucketDiag1 = new int [rows + cols];
            int[] bucketDiag2 = new int [rows + cols];
            for (int i = 0; i < rows; i++) {
                int row = 0;                // 新行初始化为0
                for (int j = 0; j < cols; j++) {
                    if (M[i][j] == 1) {     // 当前为1，对应更新bucket
                        row++;
                        bucketCol[j]++;
                        bucketDiag1[j + i]++;
                        bucketDiag2[j - i + M.length]++;
                        longest = Math.max(longest, row);
                        longest = Math.max(longest, bucketCol[j]);
                        longest = Math.max(longest, bucketDiag1[j + i]);
                        longest = Math.max(longest, bucketDiag2[j - i + M.length]);
                    } else {
                        row = 0;
                        bucketCol[j] = 0;
                        bucketDiag1[j + i] = 0;
                        bucketDiag2[j - i + M.length] = 0;
                    }
                }
            }
            return longest;
        }
    }

给出一系列字母求相除结果 399

  • 给一系列字符串的倍数关系，给出后续query的结果。
  • 图论。可以抽象成一个双向图，每个字符串都作为节点，然后权重就是两个节点的商。我的做法分三步：遍历一遍形成str到index的映射，然后建立邻接矩阵并把权重填充进去（正反都放，不存在就是0），最后就query的时候就用DFS，遍历当前节点所有能走到的节点看看能否到达终点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            if (equations == null || values == null || queries == null || 
               equations.length == 0 || values.length == 0 || queries.length == 0
               || equations.length != values.length) {
                return new double[0];
            }
            double[] ans = new double [queries.length];
            
            // create string to index mapping and get the total # of str
            int index = 0;
            Map<String, Integer> str2Index = new HashMap<>();
            for (String[] equation: equations) {
                if (!str2Index.containsKey(equation[0])) {
                    str2Index.put(equation[0], index++);
                }
                if (!str2Index.containsKey(equation[1])) {
                    str2Index.put(equation[1], index++);
                }
            }
            
            // update the values into matrix
            double[][] matrix = new double[index][index];
            for (int i = 0; i < values.length; i++) {
                int from = str2Index.get(equations[i][0]);
                int to = str2Index.get(equations[i][1]);
                matrix[from][to] = values[i];
                matrix[to][from] = 1.0 / values[i];
            }
            
            // query with dfs
            for (int i = 0; i < queries.length; i++) {
                if (!str2Index.containsKey(queries[i][0]) || !str2Index.containsKey(queries[i][1])) {
                    ans[i] = -1.0;
                } else {
                    boolean[] visited = new boolean[index];
                    int from = str2Index.get(queries[i][0]);
                    int to = str2Index.get(queries[i][1]);
                    if (from == to) {
                        ans[i] = 1.0;
                    } else {
                        //System.out.println("from: " + from + " to " + to);
                        double temp = dfs(matrix, visited, str2Index, from, to);
                        ans[i] = isZero(temp)? -1.0: temp; 
                    }
                }
            }
            return ans;
        }
        private double dfs(double[][] matrix, boolean[] visited, Map<String, Integer> str2Index, int from, int to) {
            if (matrix[from][to] > 0) {
                return matrix[from][to];
            } else {
                visited[from] = true;
                for (int i = 0; i < matrix.length; i++) {
                    //System.out.println("    from: " + from + " to " + to);
                    if (matrix[from][i] > 0 && !visited[i]) {
                        double temp = dfs(matrix, visited, str2Index, i, to);
                        if (temp > 0) {
                            return matrix[from][i] * temp;
                        }
                    }
                }
                visited[from] = false;
                return 0.0;
            }
        }
        private boolean isZero(double val) {
            return Math.abs(val) < 0.00000001;
        }
    }

十进制转七进制 可参考405

  • 十进制转二进制就是除+膜。不过需要注意负数除法的时候不能带上最前面都符号位。
  • 推广到div进制。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    final private char[] map = {'0', '1', '2', '3','4','5','6','7','8','9','a','b','c','d','e','f'};
        public String trans(int num, int div) {
            if (num == 0) {
                return "0";
            }
            long longNum = num & 0x00000000ffffffffL;   // 不能直接强制转换，不然会保留符号
            String hexStr = "";
            while (longNum != 0) {
                // System.out.println();
                hexStr = map[(int)(longNum % div)] + hexStr;
                longNum /= div;
            }
            return hexStr;
        }

九宫格 面巾

  • 给一个只含有数字【1到9】的矩阵，从矩阵中寻找九宫格(3x3的正方形，横着加，竖着加，对角线加都是15)，返回矩阵中这样的九宫格的个数。
  • 遍历所有九宫格的中心点，求对角线x2、行x3、列x3。有个hint是，只有中心点是5的九宫格才有可能符合要求，因此只需要在5处跑一遍3x3的判断即可。

字符串重组

  • 版本一：pattern和str，判断是否match。比如：输入“acg”和“abcdefg”，输出true。但“agc”和“abcdefg”就不对了，因为顺序不同。双指针。

  • 版本二：莉蔻567。不同之处在于不是subsequence而是严格的substring，且顺序不需要关注，因为是后者包含前者的permutation。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class Solution {
        public boolean checkInclusion(String s1, String s2) {
            if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0 ) {
                return false;
            }
            char[] s1Char = s1.toCharArray();
            Map<Character, Integer> map = new HashMap<>();
            int len1 = s1Char.length;
            for (int i = 0; i < len1; i++) {   // 统计s1中每个字母出现个数，作为producer
                map.put(s1Char[i], map.getOrDefault(s1Char[i], 0) + 1);
            }
            
            char[] s2Char = s2.toCharArray();
            int count = map.size();
            int left = 0, right = 0;
            while (right < s2Char.length) {     // 遍历s2作为consumer消耗字符，直到map中所有字符消耗完
                if (map.containsKey(s2Char[right])) {
                    map.put(s2Char[right], map.get(s2Char[right]) - 1);
                    if (map.get(s2Char[right]) == 0) {
                        count--;
                    }
                }
                while (count == 0) {            // 左指针补回来，直到map中出现available的字符
                    if (right - left + 1 == len1) {
                        return true;
                    }
                    if (map.containsKey(s2Char[left])) {
                        map.put(s2Char[left], map.get(s2Char[left]) + 1);
                        if (map.get(s2Char[left]) > 0) {
                            count++;
                        }
                    }
                    left++;
                }
                right++;
            }
            return false;
        }
    }

  • 与之类似的莉蔻

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    class Solution {
        // O(N)双指针。先一波流统计p中各个字符出现的频数，然后consume掉map中的字符直到没有available的
        // 此时判断左右指针之间长度是否等于目标的长度，然后挪动左指针重新往map中加回去，直到出现可选字符
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> ans = new ArrayList<Integer>();
            if (s == null || p == null || s.length() == 0 || p.length() == 0) {
                return ans;
            }
            Map<Character, Integer> map = new HashMap<>();
            char[] pChar = p.toCharArray();
            int pLen = pChar.length;
            for (char c: pChar) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            char[] sChar = s.toCharArray();
            int count = map.size();     // 还有count个不同的字符可选
            int left = 0, right = 0;
            while (right < sChar.length) {
                if (map.containsKey(sChar[right])) {
                    map.put(sChar[right], map.get(sChar[right]) - 1);
                    if (map.get(sChar[right]) == 0) {
                        count--;    // 可选字符少了一个
                    }
                }
                while (count == 0) {
                    if (right - left + 1 == pLen) {
                        ans.add(left);
                    }
                    if (map.containsKey(sChar[left])) {
                        map.put(sChar[left], map.get(sChar[left]) + 1);
                        if (map.get(sChar[left]) > 0) {
                            count++;    // 恢复可选字符
                        }
                    }
                    left++;
                }
                right++;
            }
            return ans;
        }
    }

  • 最长无重复字符的子串长度、 最长至多两个不同字符的字串长度、 最长至多k个不同字符的字串长度.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        char[] sChar = s.toCharArray();
        int left = 0, right = 0, ans = 1;
        while (right < sChar.length) {
            if (!map.containsKey(sChar[right])) {   // 首次出现
                map.put(sChar[right], right);       // 存出现的索引
            } else {
                ans = Math.max(ans, right - left);  // 出现重复字符c，更新长度
                left = Math.max(map.get(sChar[right]) + 1, left);   // 跳到c上次出现索引的下一位或不动
                map.put(sChar[right], right);       // 更新c的"最后一次出现索引"
            }
            right++;
        }
        return Math.max(ans, right - left);     // 可能需要看最后一段
    }
    // 双指针，右指针负责加入新的字符，一旦和当前范围内除了最后出现字符的另一个字符不同，说明超过了2，则需要更新到最后出现字符首次出现处。
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int ans = 1;
        int firstIndex = 0, lastIndex = -1;
        char[] sChar = s.toCharArray();
        for (int i = 1; i < sChar.length; i++) {
            if (sChar[i] == sChar[i - 1]) { // 连续相同的，直接往后挪
                continue;
            }
            if (lastIndex > -1 && sChar[i] != sChar[lastIndex]) {
                ans = Math.max(ans, i - firstIndex);
                firstIndex = lastIndex + 1;
            }
            lastIndex = i - 1;  // sChar[i]与前一个字符不同，则前一个字符的最后一个出现位置是i - 1
        }
        return Math.max(sChar.length - firstIndex, ans);
    }
    // 双指针，right向前直到多过允许的k个，然后挪left直到恢复到k个
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 0, currCharNum = 0, left = 0;
        char[] sChar = s.toCharArray();
        for (int right = 0; right < sChar.length; right++) {
            if (!map.containsKey(sChar[right])) {
                currCharNum++;
                map.put(sChar[right], 1);
            } else {
                map.put(sChar[right], map.get(sChar[right]) + 1);
            }
            if (currCharNum > k) {
                while (currCharNum > k && left < sChar.length) {
                    Integer temp = map.get(sChar[left]);
                    if (temp == 1) {
                        map.remove(sChar[left]);
                        currCharNum--;
                    } else {
                        map.put(sChar[left], temp - 1);
                    }
                    left++;
                }
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

  • 莉蔻还有类似的双指针破双字符串的题，如 76最小长度的substring ，即给一个t，求s中最短的字符串使得t中出现的字母都包含在该子串中。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    class Solution {
        public String minWindow(String s, String t) {
            if (s == null || t == null) {
                return "";
            }
            Map<Character, Integer> map = new HashMap<>();
            char[] tChar = t.toCharArray();
            for (char c: tChar) {   // 统计每个字母出现的频数
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            int minLen = Integer.MAX_VALUE, start = 0;
            char[] sChar = s.toCharArray();
            int count = map.size();     // count表示可用的不同字符数
            int left = 0, right = 0;
            while (right < sChar.length) {
                if (map.containsKey(sChar[right])) {
                    map.put(sChar[right], map.get(sChar[right]) - 1);
                    if (map.get(sChar[right]) == 0) {
                        count--;
                    }
                }
                while (count == 0) {    // 没有avaliable的字符，需要左指针补回来
                    while (!map.containsKey(sChar[left])) {
                        left++;
                    }
                    int currLen = right - left + 1;
                    if (minLen > currLen) {
                        minLen = currLen;
                        start = left;
                    }
                    map.put(sChar[left], map.get(sChar[left]) + 1);
                    if (map.get(sChar[left]) > 0) {
                        count++;
                    }
                    left++;
                }
                right++;
            }
            return minLen == Integer.MAX_VALUE? "": s.substring(start, start + minLen);
        }
    }

  • 上面这个需要和 727最小长度的subsequence 区分，这里除了出现的字符一样，出现分的先后顺序也要一致。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    public String minWindow(String S, String T) {
        // 动态规划, 行为tLen + 1, 列为sLen + 1, dp[][]表示从dp[i][j]到j到这部分字符串是所求，
        // 即T[0, j)是S[0, i)的subsequence with substring S[dp[i][j], j).
        // 初始状态为
        // 状态转换为，若当前字符不匹配，则根据左侧（即S前一个字符）情况决定起始位置（保证最短）
        // 若匹配，则依赖于左上方的结果，即T前一个字符的起始位置。
        // 可进一步压缩空间到O(Slen)
        if (S == null || T == null || S.length() == 0 || T.length() == 0) {
            return "";
        }
        char[] sChar = S.toCharArray();
        char[] tChar = T.toCharArray();
        int sLen = sChar.length, tLen = tChar.length;
        int[] startFrom = new int [sLen + 1];
        Arrays.fill(startFrom, -1);
        int firstOccur = -1;
        for (int j = 1; j <= sLen; j++) {
            if (sChar[j - 1] == tChar[0]) {
                if (firstOccur == -1) {
                    firstOccur = j - 1;
                }
                startFrom[j] = j - 1;
            } else {
                startFrom[j] = startFrom[j - 1];
            }
        }
        
        for (int i = 2; i <= tLen; i++) {
            int newFirstOccur = -1;
            for (int j = firstOccur + 1; j <= sLen; j++) {
                if (sChar[j - 1] == tChar[i - 1]) {
                    if (newFirstOccur == -1) {
                        newFirstOccur = j - 1;
                    }
                    startFrom[j] = startFrom[j];    // don't change
                } else {
                    startFrom[j] = startFrom[j - 1];
                }
            }
            firstOccur = newFirstOccur;
        }
        
        int start = 0, end = sLen, minLen = Integer.MAX_VALUE;
        for (int j = sLen; j > 0 && startFrom[j] != -1; j--) {
            int currLen = j - startFrom[j];
            if (currLen < minLen) {
                start = startFrom[j];
                end = j;
                minLen = currLen;
            }
        }
        return minLen == Integer.MAX_VALUE? "" : S.substring(start, end);
    }

stream observer

  • 已知一组字符串，每次观察一个输入的字符，若输入的字符顺序和字符串组里的match，就返回match的list，否则返回空。问题的形式让我有点懵，涉及到了interface，然后让我自己定义一个class，自定member variable， hierarchy等等
  • 我是用sliding window加上trie做的。先找出list中最长单词的长度k。然后维护一个长度为k的window。建trie的时候注意是反向建，每个单词从最后一个字母开始往前建。同时查的时候也是从window的最右边往前查。但如果有多个匹配（例如abc, abcd都在List中），则需要返回List。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    public static class StreamObserver {
        StringBuilder stream;
        int maxLen;
        TrieNode root;
        List<String> list = new ArrayList<>();
        public StreamObserver(String[] targets) {
            root = new TrieNode();
            maxLen = 0;
            for (int i = 0; i < targets.length; i++) {
                maxLen = Math.max(targets[i].length(), maxLen);
                insert(targets[i]);
            }
            stream = new StringBuilder();
        }
        public List<String> putChar(char c) {
            stream.append(c);
            int len = stream.length();
            String window = stream.substring(Math.max(len - maxLen, 0), len);
            System.out.println("stream: " + stream);
            if (stream.length() > maxLen) {
                stream.deleteCharAt(0);
            }
            return search(window);
        }
        class TrieNode {
            private boolean isWord;
            private TrieNode[] next;
            public TrieNode() {
                isWord = false;
                next = new TrieNode[26];
            }
            public TrieNode getNext(int index) {
                return next[index];
            }
            public void setNext(int index, TrieNode newNode) {
                next[index] = newNode;
            }
            public boolean getIsWord() {
                return isWord;
            }
            public void setIsWord(boolean val) {
                isWord = val;
            }
        }
        
        /** Inserts a word into the trie in reversed order. */
        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }
            char[] wordChar = word.toCharArray();
            TrieNode curr = root;
            for (int i = wordChar.length - 1; i >= 0; i--) {
                int index = wordChar[i] - 'a';
                if (curr.getNext(index) == null) {
                    curr.setNext(index, new TrieNode());
                }
                curr = curr.getNext(index);
            }
            curr.setIsWord(true);
        }
        public List<String> search(String word) {
            char[] wordChar = word.toCharArray();
            TrieNode curr = root;
            for (int i = wordChar.length - 1; i >= 0; i--) {
                int index = wordChar[i] - 'a';
                if (curr.getNext(index) == null) {
                    break;
                }
                curr = curr.getNext(index);
                if (curr.getIsWord()) {
                    list.add(word.substring(i, wordChar.length));
                }
            }
            return list;
        }
        /*
        // Returns if the word is in the trie.
        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            char[] wordChar = word.toCharArray();
            TrieNode curr = root;
            for (int i = wordChar.length - 1; i >= 0; i--) {
                int index = wordChar[i] - 'a';
                if (curr.getNext(index) == null) {
                    return false;
                }
                curr = curr.getNext(index);
            }
            return curr.getIsWord();
        }
        
        // Returns if there is any word in the trie that starts with the given prefix.
        public boolean startsWith(String prefix) {
            if (prefix == null || prefix.length() == 0) {
                return false;
            }
            char[] prefixChar = prefix.toCharArray();
            TrieNode curr = root;
            for (int i = 0; i < prefixChar.length; i++) {
                int index = prefixChar[i] - 'a';
                if (curr.getNext(index) == null) {
                    return false;
                }
                curr = curr.getNext(index);
            }
            return true;
        }
        */
    }

有向无环图最长路径

  • 给出公司并购的关系列表，比如[["baidu", "ofo"], ["mobike", "alibaba"],...]，表示baidu并购了ofo，摩拜并购了阿里巴巴。。。求最长的一个并购链。保证无环。
  • 类似简化版拓扑，完整版拓扑可参考这个submission，不过这里其实只需要找到入度为0的节点，然后更新可达点的同时更新所走的步数。

带时间戳的Map

  • 带时间戳的map: put(k, v, timestamp) get(k , timestamp)EX:

    1
    2
    3
    4
    5
    put(1, haha, 3)
    put(1, ha, 5)
    get(1, 0) -> null
    get(1, 4) -> haha
    get(1, 6) -> ha

  • 维护Map<Integer, Map<Integer, String>>，新插入的key就新建一个TreeMap，然后时间戳为key，String为value存入。读取的时候就取floorKey(timestamp)，也就是最接近的不大于timestamp的值，有的话即为所求了。

  • Follow-up是问用ArrayList, LinkedList, BST, Balanced BST实现的get和put的时间复杂度分别是多少。

树的遍历

  • preorder, inorder, post-order。要求掌握iterative和recursive的方法。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();// 栈顶的先输出
            ans.add(curr.val);
            if (curr.right != null) {   // 栈优先push右子（让它晚点出来）
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
        }
        return ans;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> s = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !s.isEmpty()) {
            while (curr != null) {
                s.push(curr);
                curr = curr.left;   // 栈总是优先push左子
            }
            curr = s.pop();         // 直到无左子
            ans.add(curr.val);
            curr = curr.right;
        }
        return ans;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> val = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            if (curr.left != null) {
                stack.push(curr.left);
            }
            if (curr.right != null) {
                stack.push(curr.right);
            }
            val.push(curr.val); // 栈顶的晚输出
        }
        while (!val.isEmpty()) {
            ans.add(val.pop());
        }
        return ans;
    }

Frequencey Iterator (类似于利口604)

  • 给一个int数组，奇数位是count偶数位是number，实现next和hasNext函数。如[2,4,0,9,5,3]，那输出就是[4,4,3,3,3,3,3]。
  • 自定义类保存数字和对应的频数，然后入Queue开始输出就好了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class FreqNumber {
        int freq;
        int num;
        public FreqNumber(int freq, int num) {
            this.freq = freq;
            this.num = num;
        }
    }
    public class MyIterator {
        Queue<FreqNumber> queue;
        public MyIterator(int[] array) {
            int i = 0, n = array.length;    // 需要保证是偶数个元素
            queue = new LinkedList<>();
            while (i + 1 < n) {
                if (array[i] > 0) {
                    queue.add(new FreqNumber(array[i], array[i + 1]));
                }
                i += 2;
            }
        }
        public int next() throws Exception {
            if (!hasNext()) {
                throw new Exception();
            }
            FreqNumber top = queue.peek();
            if (--top.freq == 0) {
                queue.poll();
            }
            return top.num;
        }
        public boolean hasNext() {
            return !queue.isEmpty();
        }
    }

toeplitz matrix

  • 判断一matrix是不是toeplitz matrix, 就是所有左上到右下对角线的数字都相等。

  • 对角线方向元素其实就是相邻两行元素的前后判断。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public class Google {
        public boolean isToeplitzMatrix(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }
            int rows = matrix.length, cols = matrix[0].length;
            for (int i = 1; i < rows; i++) {
                for (int j = 1; j < cols; j++) {
                    if (matrix[i][j] != matrix[i - 1][j - 1]) {
                        return false;
                    }
                }
            }
            return true;
        }
    }

  • follow-up: 如果matrix特别大，每次只能存两行，只用matrix提供的matrix.next, matrix.has_next, 和matrix.size实现。其实上面的方法已经只存两行了。

3sum

  • 给一个数组，求其中所有的a, b, c使得a + b + c == 0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            if (nums == null || nums.length == 0) {
                return ans;
            }   
            Arrays.sort(nums);
            
            for (int i = 0; i < nums.length; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                
                // 固定nums[i]用双指针找后面两个数b, c，使b + c == 0 - nums[i]
                int left = i + 1, right = nums.length - 1, target = 0 - nums[i];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum == target) {
                        List<Integer> currList = new ArrayList<>();
                        currList.add(nums[i]);
                        currList.add(nums[left]);
                        currList.add(nums[right]);
                        ans.add(currList);
                        left++;
                        right++;
                        while (left < right && nums[left] == nums[left - 1]) {    // 避免重复
                            left++;
                        }
                        while (right > left && nums[right] == nums[right + 1]) {  // 避免重复
                            right++;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
            return ans;
        }

validate 2D array

  • 2-D array，里面有R,G,B,Y四种类型的element，如果横竖没有三个element是同一类型的话，这个2-Darray就是valid的。先让写个function判断一个2-D array是否valid。

  • 感觉和那个OOXX(348 Design tic tac toe)的游戏很像，不过就不能通过简单的加一减一来搞了。这里就是暴力了，判断当前字符的前一行、下一行，以及前一列、下一列。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public static boolean isValidMatrix(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, cols = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i > 0 && matrix[i - 1][j] == matrix[i][j]) {  // 等于上一行
                    if (i + 1 < rows && matrix[i + 1][j] == matrix[i][j]) {
                        return false;	// 判断下一行
                    }
                }
                colBucket[j] = matrix[i][j];
                if (j > 0 && matrix[i][j] == matrix[i][j - 1]) {
                    if (j + 1 < cols && matrix[i][j + 1] == matrix[i][j]) {
                        return false;
                    } else {
                        j++;
                        if (j < cols) {
                            colBucket[j] = matrix[i][j];
                        }
                    }
                }
            }
        }
        return true;
    }

  • follow-up：能否并行化计算？各种方式有什么优劣？可以replicate原array，每个thread只处理一个颜色。也可以划分成小块，但是边界线情况讨论起来特别复杂，而且会有很多个thread。

2D array search & sum

  • 240 Search a 2D Matrix II，可以直接从第一行的最大列开始找，因为右下方的一定是比当前元素大的，所以只需要查找左下和左前即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     // O(M + N)
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length < 1 || matrix[0].length <1) {
            return false;
        }
        int col = matrix[0].length - 1;
        int row = 0;
        while (col >= 0 && row <= matrix.length-1) {
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                col--;
            } else if (target > matrix[row][col]) {
                row++;
            }
        }
        return false;
    }

  • 304. Range Sum Query 2D - Immutable 也是缓存中间结果的思想，利用额外的O(MN)的空间存下来，需要取sum的时候就减左侧、上侧再加回左上侧结果即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    private int[][] sumRegion;
    public NumMatrix(int[][] matrix) {
        if (matrix.length != 0)  sumRegion = new int[matrix.length + 1][matrix[0].length + 1];
        
        for (int i = 0; i < matrix.length; i++) {
            int sum = 0;
            for (int j = 0; j < matrix[0].length; j++) {
                sum += matrix[i][j];
                sumRegion[i + 1][j + 1] = sum + sumRegion[i][j + 1]; 
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sumRegion[row2 + 1][col2 + 1] - sumRegion[row1][col2 + 1] - sumRegion[row2 + 1][col1] + sumRegion[row1][col1];
    }

  • follow-up是如果要对矩阵时不时进行更新怎么办。如果还是用上面这个的思路，返回sumRegion的时间就不再是constant了，同时update也不是constant。为了更新，还需要把matrix存下来（必须的）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    private int[][] sumRegion;
    private int[][] matrix;
    public NumMatrix(int[][] matrix) {
        if(   matrix           == null
           || matrix.length    == 0
           || matrix[0].length == 0   ){
            return;   
         }
         
         this.matrix = matrix;
         
         int m   = matrix.length;
         int n   = matrix[0].length;
         sumRegion = new int[m + 1][n];
         for(int i = 1; i <= m; i++){
             for(int j = 0; j < n; j++){
                 sumRegion[i][j] = sumRegion[i - 1][j] + matrix[i - 1][j];
             }
         }
    }
    //time complexity for the worst case scenario: O(m)
    public void update(int row, int col, int val) {
        for(int i = row + 1; i < sumRegion.length; i++){
            sumRegion[i][col] = sumRegion[i][col] - matrix[row][col] + val;
        }
        
        matrix[row][col] = val;
    }
    //time complexity for the worst case scenario: O(n)
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ret = 0;
        
        for(int j = col1; j <= col2; j++){
            ret += sumRegion[row2 + 1][j] - sumRegion[row1][j];
        }
        
        return ret;
    }

  • 另一个高效办法是Binary Index Tree。我们先看看range sum 1D的情况，2D的暂时放一放。。。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    int[] nums;
    int[] BIT;
    int n;
    public RangeSum(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.BIT = new int[n + 1];  // n + 1
        initiateBIT();
    }
    public int lowestBit(int x) {   // 获取最低位的1
        return x & -x;
    }
    public void initiateBIT(){
        for(int i = 1; i <= n; i++){
            this.BIT[i] = 0;
            for(int j = i; j > i - lowestBit(i); j--){
                this.BIT[i] = this.BIT[i] + nums[j - 1];
            }
        }
    } 
    //每次都只有后继节点会根据当前节点的变化而变化， 所以步长是i + lowestBit(i)
    public void update(int index, int val){	
        for(int i = index + 1; i <= this.n; i = i + lowestBit(i)){
            this.BIT[i] = this.BIT[i] - this.nums[index] + val;
        }
        this.nums[index] = val;
    }
    //和为所有前驱节点相加， 所以步长是i - lowestBit(i)
    public int getSum(int k){
        int sum = 0;
        for(int i = k + 1; i > 0; i = i - lowestBit(i)){
            sum = sum + this.BIT[i];
        }
        return sum;
    }
    public int getRangeSum(int i, int j){
        return getSum(j) - getSum(i - 1);
    }

voting with timestamp

  • 给一个voteList=[(a, 100), (b, 150), (a, 200)] #(name, timestamp)和时间T，找T时间之前, 得票数最高的人(或任一得票数最高的人)。
  • 直接扫一波vote list，只保留在时间T之前的票存到Map中，顺便记下一个最大值和对应的人名。
  • follow-up：给voteList、时间T，求top k候选人的list。也是先O(N)扫一波统计，然后再一波loop存入Heap，如果Heap规模达到k就需要比较堆顶和当前票数，若当前票数更大就需要把出堆再push。
  • follow-up：给voteList、top k候选人的list，求时间T。只想到最暴力的办法，先把所有出现过的时间t存入从小到大的PriorityQueue，然后从小到大暴力搜“给定voteList和T”，看看求得的list和所给的list是否一致。不过这里每次不是从头开始做，而是累加，即前一个t不行，就取优先队列中的下一个t继续往后加，不用从头来过。

feed tree

  • 一棵树，所有节点的value都是正整数，问只能增加某些节点值的情况下，如何调整使得从root到所有leaf的path上经过的节点值之和相等，返回增加的值的和，使这个和最小.
  • 类似贪心，在后续遍历的过程中顺便求叶子到当前节点的和并返回，再用全局变量根据左右两边孩子的差值确定需要补多少，更新的条件是该节点一定有两个孩子来比较，这样就能保证和最小。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    /*
          1
         / \
        2   3
       / \ / \
      3  2 2  4
            \
             1
          1
         / \
        4   3
       / \ / \
      3  3 3  4
            \
             1
    */
    class Solution {
        private int ans;
        public int minAddToTree(TreeNode root){
            // supposing the tree is binary tree
            ans = 0;
            feedTree(root);
            return ans;
        }
        private int feedTree(TreeNode root){
            // this funciton 'feed' the tree to make all root->leaf path sums equal
            // return: path sum of the tree.
            if (root == null) 
                return 0;
            int leftPath = feedTree(root.left);
            int rightPath = feedTree(root.right);
            if (leftPath != 0 && rightPath != 0) // check if one child is null, if so no need to feed
                ans += Math.abs(leftPath - rightPath);
            return Math.max(leftPath, rightPath) + root.val;
        }
    }

remove node

  • Given a binary tree, write a function to erase a list of nodes from the tree and return the forest created from this operation.自己决定输入输出形式，自己定义treenode结构.

  • 一个思路是，可以在TreeNode中增加parent节点，这样在删除的时候就方便很多，直接设置就可以了。

    1
    2
    3
    4
    5
    6
    7
    class TreeNode {
        int val;
        TreeNode left, right, parent;
        public TreeNode(int val) {
            this.val = val;
        }
    }

  • 如果不加parent，就需要通过postOrder遍历，先递归到当前节点的左和右孩子，再看看孩子是否要删掉，是就直接设为null。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public List<TreeNode> delete(TreeNode root, List<TreeNode> toRemove) {
        List<TreeNode> res = new ArrayList<TreeNode>();
        TreeNode root1 = postorder(root, toRemove, res);
        if(root1 != null) res.add(root);
        return res;
    }
    public TreeNode postorder(TreeNode root, List<TreeNode> toRemove, List<TreeNode> res) {
        if(root == null) return null;
        root.left = postorder(root.left, toRemove, res);
        root.right = postorder(root.right, toRemove, res);
        if (toRemove.contains(root)) {  // 当前节点需要删除
            if (root.left != null) res.add(root.left);
            if (root.right != null) res.add(root.right);
            return null;
        }
        return root;
    }

361. Bomb Enemy

  • 给一个只含有0, W, E的char棋盘，炸弹只能放在0处，炸弹可以向上下左右扩散，求一颗炸弹最多炸死多少E。

  • 对于每一行统计敌人数，一旦遇到W就重置为0；对于每一列则需要维护额外的一个数组，也是遇到W就重置。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
        // O(MN)统计每行、每列可杀E的数量，一旦前面（左或上）碰到W就要重新算一遍
        public int maxKilledEnemies(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            int rows = grid.length, cols = grid[0].length;
            int ans = 0, rowCount = 0;
            int[] colCount = new int [cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (j == 0 || grid[i][j - 1] == 'W') {  // 当上一列是W，就重新往右算当前列可以杀多少E
                        rowCount = 0;
                        for (int k = j; k < cols && grid[i][k] != 'W'; k++) {   // 不会提升复杂度因为只有前一个是W才会开始、到W就结束
                            if (grid[i][k] == 'E') {
                                rowCount++;
                            }
                        }
                    }
                    if (i == 0 || grid[i - 1][j] == 'W') {  // 当上一行是W，就重新往下算当前列可以杀多少E
                        colCount[j] = 0;
                        for (int k = i; k < rows && grid[k][j] != 'W'; k++) {
                            if (grid[k][j] == 'E') {
                                colCount[j]++;
                            }
                        }
                    }
                    if (grid[i][j] == '0') {
                        ans = Math.max(ans, rowCount + colCount[j]);
                    }
                    // else if (grid[i][j] == 'E') {
                    // 	ans = Math.max(ans, rowCount + colCount[j] - 1);
                    // }
                }
            }
            return ans;
        }
    }

  • follow-up：如果在E上也可以放炸弹，要如何修改？那么就加多一个判断是否等于E的步骤，见上面注释部分。

以上是地里大概找的一部分面经。

以下是利口上的孤狗tag题。

4. Median of 2 sorted arrays

  • 给两个有序int数组，返回二者合并后的中位数。
  • O(M + N)：归并排序依次合并，合并到一半长度知道中位数了。
  • O(log(M + N))：中位数是用来将数组分割成相等长度的两部分的，因此使用二分查找找出刚好能分成等长的两部分并且前部分的最大值<=后部分的最小值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
     class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if (nums1 == null || nums2 == null) {
                return 0;
            }
            int m = nums1.length, n = nums2.length;
            if (nums1.length > nums2.length) {  // ensure the len of 1 <= 2
                return findMedianSortedArrays(nums2, nums1);
            }
            
            // to ensure equality of the two parts after merged, i + j = m - i + n - j
            int iLo = 0, iHi = m, allMid = (n + m + 1) / 2; // merge odd / even case
            
            // i stands for "how many num taken from nums1 as front part" 0 ~ i-1 | i ~ m-1
            // j stands for "how many num taken from nums2 as front part" 0 ~ j-1 | j ~ n-1
            while (iLo <= iHi) {
                int i = (iLo + iHi) / 2, j = allMid - i;
                
                // nums1[i-1], nums2[j-1] are the largest element of front part of nums1, nums2
                // nums1[i], nums2[j] are the smallest of lag part of nums1, nums2
                if (i < m && nums2[j - 1] > nums1[i]) { // i not big enough
                    iLo = i + 1;
                } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                    iHi = i - 1;
                } else {
                    int maxLeft = 0, minRight = 0;
                    if (i == 0) {
                        maxLeft = nums2[j - 1];
                    } else if (j == 0) {
                        maxLeft = nums1[i - 1];
                    } else {
                        maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                    }
                    
                    if ((m + n) % 2 == 1) { // I think thats why to make (allMid = (n + m + 1)/2)
                        return maxLeft;     // -- to make left part always at least no fewer than right
                    }
                    
                    if (i == m) {
                        minRight = nums2[j];
                    } else if (j == n) {
                        minRight = nums1[i];
                    } else {
                        minRight = Math.min(nums1[i], nums2[j]);
                    }
                    return (maxLeft + minRight) / 2.0;
                }
            }
            return 0;
        }
    }

17. letter-combinations

  • 给一串数字的字符串，求这些数字可能输出的所有字母字符串，对应关系为手机的按键。
  • DFS：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> ans = new ArrayList<>();
            if (digits == null || digits.length() == 0 
               || digits.indexOf('1') >= 0 || digits.indexOf('0') >= 0) {
                return ans;
            }
            final char[][] num2Char = new char [][] {
                {}, 
                {}, 
                {'a', 'b', 'c'}, 
                {'d', 'e', 'f'}, 
                {'g', 'h', 'i'},
                {'j', 'k', 'l'}, 
                {'m', 'n', 'o'}, 
                {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'}, 
                {'w', 'x', 'y', 'z'}
            };
            
            char[] str = digits.toCharArray();
            dfs(str, 0, num2Char, new StringBuilder(), ans);
            return ans;
        }
        private void dfs(char[] str, int index, final char[][] num2Char, StringBuilder sb, List<String> ans) {
            if (index == str.length) {
                ans.add(sb.toString());
                return;
            }
            int temp = str[index] - '0';
            for (int i = 0; i < num2Char[temp].length; i++) {
                sb.append(num2Char[temp][i]);
                dfs(str, index + 1, num2Char, sb, ans);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

20. valid-parentheses

  • 给一个字符串，判断其中三种括号(), [], {}是否匹配。
  • Stack: 左括号本身并不入栈，而是它对应的右括号入栈，这样当右括号出现的时候只需判断二者是否相等或者是否栈已经空了即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public boolean isValid(String s) {
    	Stack<Character> stack = new Stack<Character>();
    	for (char c : s.toCharArray()) {
    		if (c == '(')
    			stack.push(')');
    		else if (c == '{')
    			stack.push('}');
    		else if (c == '[')
    			stack.push(']');
    		else if (stack.isEmpty() || stack.pop() != c)
    			return false;
    	}
    	return stack.isEmpty();
    }

22. generate-parentheses

  • 给一个int表示括号的对儿数，输出所有符合括号匹配规则的字符串，存入List中返回。
  • DFS：左括号、右括号分别
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     // O(2^2n)?
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> ans = new ArrayList<>();
            if (n < 1) {
                return ans;
            }
            
            dfs(n, 0, 0, "", ans);
            return ans;
        }
        private void dfs(int n, int left, int right, String s, List<String> ans) {
            if (left == n && right == n) {
                ans.add(s);
                return;
            }
            if (left < n)
                dfs(n, left + 1, right, s + "(", ans);
            
            if (right < left)
                dfs(n, left, right + 1, s + ")", ans);
        }
    }

23. merge-k-sorted-lists

  • 给一个ListNode节点数组，分别是排好序的若干链表头，要求输出合并后的新链表头.

  • 直接用PriorityQueue：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> {
            return a.val - b.val;
        });
        for (ListNode l: lists) {
            if (l != null)
                pq.add(l);
        }
        ListNode fakeHead = new ListNode(0), curr = fakeHead;
        while (!pq.isEmpty()) {
            curr.next = pq.poll();
            curr = curr.next;
            if (curr.next != null)
                pq.add(curr.next);
        }
        return fakeHead.next;
    }

  • 分治法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    // divide and conquer, O(nlogk)
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        // last two params are used to divide into sub problems
        return mergeKLists(lists, 0, lists.length);
    }
    private ListNode mergeKLists(ListNode[] lists, int start, int end) {
        if (end - start == 1) { // only one list
            return lists[start];
        } else if (end - start == 2) {  // merge two lists
            return mergeTwoLists(lists[start], lists[start + 1]);
        } else {
            int mid = start + (end - start) / 2;
            // cut into first and second halves
            return mergeTwoLists(mergeKLists(lists, start, mid), 
                                 mergeKLists(lists, mid, end)); // warning not mid + 1
        }
    }
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

31. next-permutation

  • 给一个int数组，将它改造成按字典序的下一个排列，若不存在则直接按从小到大的顺序调整。要求In-place对原数组操作，不能申请额外空间。
  • 这个想法从右往左找相邻的两个数使得first < second，然后再从右往左找首次出现的比first大的数，二者对调，然后将second及其之后的内容reverse一下即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    // 1324 -> 1342
    // 6，3，4，9，8，7，1 -> 6，3，7，9，8，4，1 -> 6，3，7，1，4，8，9
    class Solution {
        public void nextPermutation(int[] nums) {
            if (nums == null || nums.length < 2) {
                return;
            }
            for (int i = nums.length - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {    // 找相邻的两个数
                    int j = nums.length - 1;
                    while (j > i) { // 从右往左找第一个大于first的数
                        if (nums[j] > nums[i]) {
                            swap(nums, i, j);   // 
                            reverse(nums, i + 1);
                            return;
                        }
                        j--;
                    }
                }
            }
            reverse(nums, 0);
        }
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        private void reverse(int[] nums, int start) {
            for (int i = start, j = nums.length - 1; i < j; i++, j--) {
                swap(nums, i, j);
            }
        }
    }

42. trapping-rain-water

  • 给一个int数组，其中包含每个索引处墙的高度。求装满水时的横截面的积水的面积。

  • 用两个辅助数组分别表示两侧最高高度，然后再一波遍历看能否装水。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public int trap(int[] height) {
            if (height == null || height.length == 0) {
                return 0;
            }
            int[] hiLeft = new int [height.length];     // leftward highest
            int[] hiRight = new int [height.length];    // rightward highest
            int left = height[0], right = height[height.length - 1];
            for (int i = 1, j = height.length - 2; i < height.length; i++, j--) {
                hiLeft[i] = left;
                left = Math.max(left, height[i]);
                
                hiRight[j] = right;
                right = Math.max(right, height[j]);
            }
            
            int area = 0;
            for (int i = 0; i < height.length; i++) {
                int h = Math.min(hiLeft[i], hiRight[i]);
                if (height[i] < h) {
                    area += (h - height[i]);
                }
            }
            return area;
        }
    }

  • follow-up:不能用额外空间呢？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public int trap(int[] height) {
            if (height == null || height.length == 0) {
                return 0;
            }
            int[] hiLeft = new int [height.length];     // leftward highest
            int[] hiRight = new int [height.length];    // rightward highest
            int left = height[0], right = height[height.length - 1];
            for (int i = 1, j = height.length - 2; i < height.length; i++, j--) {
                hiLeft[i] = left;
                left = Math.max(left, height[i]);
                
                hiRight[j] = right;
                right = Math.max(right, height[j]);
            }
            
            int area = 0;
            for (int i = 0; i < height.length; i++) {
                int h = Math.min(hiLeft[i], hiRight[i]);
                if (height[i] < h) {
                    area += (h - height[i]);
                }
            }
            return area;
        }
    }

676. implement-magic-dictionary

  • 给一个字典需要维护某种结构使得查询比较高效，查询是通过一个单词输入后判断字典中是否存在一个单词只替换输入串中的一个字符就能得到。
  • 有点暴力的方法，在输入一个字符串数组的时候就维护一个从String映射到Character的Map，对于每个单词的每一个字符都换成*作为key，然后被替换的字符作为value存入。之后check的时候也是把每个字符都换成*之后再确认map中有没有对应的key。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    class MagicDictionary {
        // 将每个单词的每个字符都替换成*之后，插入map，key是替换后的字符串，value是被替换掉的那个字符
        // 如果出现替换过后的key一样，则该位可以放任意字符，因为例如hello和hallo只有在第二位不同，如果替换后是h*llo可以任选一个，一定是true。
        Map<String, Character> map = null;
        /** Initialize your data structure here. */
        public MagicDictionary() {
            map = new HashMap<String, Character>();
        }
        
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            if (dict == null || dict.length == 0) {
                return;
            }
            for (String word : dict) {
                StringBuilder sb = new StringBuilder(word);
                int len = word.length();
                for (int i = 0; i < len; i++) {
                    sb.setCharAt(i, '*');
                    Character c = map.get(sb.toString());
                    if (c == null) {
                        map.put(sb.toString(), word.charAt(i));
                    } else {
                        map.put(sb.toString(), '*');
                    }
                    sb.setCharAt(i, word.charAt(i));
                }
            }
        }
        
        /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            int len = word.length();
            StringBuilder sb = new StringBuilder(word);
            for (int i = 0; i < len; i++) {
                sb.setCharAt(i, '*');
                Character c = map.get(sb.toString());
                if (c != null && (c == '*' || c != word.charAt(i))) {
                    return true;
                }
                sb.setCharAt(i, word.charAt(i));
            }
            return false;
        }
    }
    /**
     * Your MagicDictionary object will be instantiated and called as such:
     * MagicDictionary obj = new MagicDictionary();
     * obj.buildDict(dict);
     * boolean param_2 = obj.search(word);
     */