易贝

Posted on Edited on In Disqus:

迎难而上，祝我好运。面朝大海，春暖花开。

k way merge

  • LC23。给K个排好序的链表头节点数组，将他们merge到一个list中。
  • 方法一：利用PriorityQueue存储，先一波流将所有链表头加入pq，然后每次poll掉最小的同时将它后续的节点也放进pq中。pq的offer, poll, remove复杂度都是log(N)，因此在这里维护规模为K的就需要log(K)，而总共有KN个节点，时间复杂度是O(KNlogK)。
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;
}
  • 方法二：递归+分治法，归结为merge两个List的问题。时间复杂度是O(KNlogK)，因为一开始K个数组，需要遍历每个元素合并之后形成K/2个数组，以此类推，每次需要遍历需要O(KN)，总共有logK次，因此是O(KNlogK)。
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
// divide and conquer
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;
    }
}

longest common substring

  • 给两个String，求最长的连续的共同的子串。例如s1 = 12358和s2 = 1242358，最长的子序列就是2358.
  • DP.用二维int数组维护dp[i][j]表示s1以i结尾处、s2以j结尾处的substring情况。当s1.charAt(i) == s2.charAt(j)时，就更新为dp[i - 1][j - 1] + 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static String maxCommonSubstring(String s1, String s2) {
    if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
        return "";
    }
    int len1 = s1.length(), len2 = s2.length();
    int[][] dp = new int[len1][len2];
    int maxLen = 0, index = -1;
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            if (s1.charAt(i) == s2.charAt(j)) {
                dp[i][j] = i > 0 && j > 0 ? dp[i - 1][j - 1] + 1 : 1;
                if (maxLen < dp[i][j]) {
                    maxLen = dp[i][j];
                    index = i;
                }
            }
        }
    }
    return index < 0 ? "" : s1.substring(index + 1 - maxLen, index + 1);
}

reverse word in string

  • 给一个字符串和一个分隔符，将每个单词翻转，同时大小写翻转。注意这个Zillow的那个翻转字符串不一样。skip.

decimal to hex

  • 将一个十进制数转换成十六进制。
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 toHex(int num) {
    if (num == 0) {
        return "0";
    }
    long longNum = num & 0x00000000ffffffffL;   // 不能直接强制转换，不然会保留符号
    String hexStr = "";
    while (longNum != 0) {
        // System.out.println();
        hexStr = map[(int)(longNum % 16)] + hexStr;
        longNum /= 16;
    }
    return hexStr;
}

最大正方形

  • 类似LC 221，给一个0/1 grid，求其中最大的正方形面积。
  • DP。当前位置为1，则需要看看左、左上、上三个方向的最小值+1作为边长，最后返回最大的即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int rowTotal = matrix.length, colTotal = matrix[0].length;
    int max = 0;
    int[][] dp = new int[rowTotal][colTotal];
    for (int i = 0; i < rowTotal; i++) {
        for (int j = 0; j < colTotal; j++) {
            if (matrix[i][j] == '1') {
                dp[i][j] = getMin(dp, i, j) + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }
    return max * max;
}
private int getMin(int[][] dp, int i, int j) {
    int up = i > 0 ? dp[i - 1][j] : 0;
    int left = j > 0 ? dp[i][j - 1] : 0;
    int upLeft = i > 0 && j > 0 ? dp[i - 1][j - 1] : 0;
    return Math.min(Math.min(up, left), upLeft);
}

第N个BLAH数

  • 如果一个数字可以被5，7，11整除 那么这个数称之为BLAH数 (5,7,10,11,14,15…). 求第n个BLAH数。
  • 用三个变量存下一个5、7、11整除的blah数，从1到n每次取最小的，并更新到下一个。注意出现重复的时候就需要跳到下一个。

移动0到数组末尾

  • 给一个数组，将所有的0移动到数组末尾，其余数组需要维持相对次序。
  • 先走一波循环讲非0的项往前覆盖，走完之后剩余的数直接覆盖为0即可。
1
2
3
4
5
6
7
8
9
public void moveZeroes(int[] nums) {
    int k = 0;
    for (int i = 0; i < nums.length; ++i){
        if (nums[i] != 0) nums[k++] = nums[i];
    }
    for(; k < nums.length; ++k){
        nums[k] = 0;
    }
}

反转链表

  • 给一个链表头，反转之。LC 206
  • 方法一：Iterative就直接前后两个节点直接把next指向对调一下就好了。
  • 方法二：Recursive就先将当前节点后面的节点都reverse一波，当前节点的next原本指的是后续第一个节点、现在就变成了后续最末尾的节点，那么调整一下next指向即可。
1
2
3
4
5
6
7
8
9
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

找第一次、最后一次出现位置

  • LC 34给一个有序数组，给一个target，找第一个和最后一个出现的位置。复习一波二分查找了。
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 int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int [] {-1, -1};
        }
        int first = searchFirst(nums, target);
        if (first == -1) {
            return new int [] {-1, -1};
        }
        int last = searchLast(nums, target);
        return new int[] {first, last};
    }
    private int searchFirst(int[] nums, int target) {
        // hope to biase to the front
        // invariant relation: A[start] < target <= A[end] 
        int start = -1, end = nums.length;
        while (end - start > 1) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {   // end need to be more aggresive
                end = mid;      // shrink down
            } else {
                start = mid;    // step up
            }
        }
        return end == nums.length || nums[end] != target? -1: end;  // end will proceed at front
    }
    private int searchLast(int[] nums, int target) {
        // biase to the back
        // invariant relation: A[start] <= target < A[end] 
        int start = -1, end = nums.length;
        while (end - start > 1) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > target) {
                end = mid;      // shrink down
            } else {            // start need to be more aggressive
                start = mid;    // step up
            }
        }
        return start;
    }
}

二维矩阵二分查找

  • LC 240。矩阵中每一行、每一列都是有序的，给一个target，判断是否存在。
  • 方法一：仍然是二分查找的思想，取行和列的中间元素，若target小了则需要到左侧细长竖矩形和上方的肥扁矩形查找，否则是到右侧的细长竖矩形和下方的肥扁矩形中查找。
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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        return binarySearch(matrix, target, -1, -1, matrix.length, matrix[0].length);
    }
    private boolean binarySearch(int[][] matrix, int target, 
                                 int lowRow, int lowCol, int hiRow, int hiCol) {
        if (hiCol - lowCol <= 2 || hiRow - lowRow <= 2) {
            return false;
        }
        int midCol = lowCol + (hiCol - lowCol) / 2;
        int midRow = lowRow + (hiRow - lowRow) / 2;
        if (target == matrix[midRow][midCol]) {
            return true;
        }
        if (target < matrix[midRow][midCol]) { 
            if (binarySearch(matrix, target, lowRow, lowCol, midRow + 1, hiCol)) {
                // (lowRow, lowCol) to (midRow + 1, hiCol), exclusive
                return true;
            } else if (binarySearch(matrix, target, lowRow, lowCol, hiRow, midCol)) {
                // (lowRow, lowCol) to (hiRow, midCol)
                return true;
            } else {
                return false;
            }
        } else {
            if (binarySearch(matrix, target, midRow - 1, lowCol, hiRow, hiCol)) {
                // (midRow - 1, lowCol) to (hiRow, hiCol), exclusive
                return true;
            } else if (binarySearch(matrix, target, lowRow, midCol, hiRow, hiCol)) {
                // (lowRow, lowCol) to (hiRow, midCol)
                return true;
            } else {
                return false;
            }
        }
    }
}
  • 方法二：直接扫，首先从右上角开始，如果小了说明当前这一行都不可能了，如果大了说明当前这列都不可能了，因此每次都会排除掉一整行/一整列，时间复杂度是O(M + N)，相当于线性查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length ==0 || matrix[0].length == 0) {
        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;
}

实现LRU

  • LC 146. 实现Cache就是用Map，但是least recent特性就需要额外的数据结构来提升效率：双向链表。Map中存放key - Node映射，所有的cache都放在一个双向链表上，每次get的时候就将get到的node挪到第一位。put时若capacity超了就将链表最后一个节点删除即可。
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 LRUCache {
    class Node {
        int key;
        int val;
        Node prev;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            prev = null;
            next = null;
        }
    }
    Map<Integer, Node> map;
    Node fakeHead, fakeTail;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        fakeHead = new Node(-1, -1);
        fakeTail = new Node(-1, -1);
        fakeHead.next = fakeTail;
        fakeTail.prev = fakeHead;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node ret = map.get(key);
            moveToFirst(ret);
            return ret.val;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (map.containsKey(key)) {
            Node oldNode = map.get(key);
            oldNode.val = value;
            moveToFirst(oldNode);
            return;
        }
        if (map.size() == capacity) {
            map.remove(fakeTail.prev.key);
            remove(fakeTail.prev);
        }
        Node newNode = new Node(key, value);
        insertToFirst(newNode);
        map.put(key, newNode);
    }
    
    private void moveToFirst(Node node) {
        remove(node);
        insertToFirst(node);
    }
    private void insertToFirst(Node node) {
        node.next = fakeHead.next;
        fakeHead.next = node;
        node.prev = fakeHead;
        node.next.prev = node;
    }
    private void remove(Node node) {
        if (node.prev == null) {
            return;
        }
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

2018.3.23 Onsite

15. 3Sum
  • 给一个int数组，列出三个数使得它们的和为0.
  • 先排序，然后固定当前数，设置target为0 - curr，然后用双指针在后方找，当left + right == target就是一组数了。
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 List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }   
        Arrays.sort(nums);  // sort from least to largest
        
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // fix nums[i] and let two pointers get target's indices
            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);
                    do {
                        left++; // for duplicate
                    } while (left < right && nums[left] == nums[left - 1]);
                    do {
                        right--;
                    } while (right > left && nums[right] == nums[right + 1]);
                    
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return ans;
    }
}
216. combination sum
  • 在1～9中选k个数之和等于n，求所有可能的组合。DFS/backtracking搞定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(k, n, 1, ans, new ArrayList<>());
        return ans;
    }
    private void dfs(int k, int n, int start, List<List<Integer>> ans, List<Integer> curr) {
        if (n == 0 && curr.size() == k) {
            ans.add(new ArrayList<Integer>(curr));
            return;
        }
        for (int i = start; i <= 9; i++) {
            curr.add(i);
            dfs(k, n - i, i + 1, ans, curr);
            curr.remove(curr.size() - 1);
        }
    }
}
535. tinyURL
  • 实现长URL和短URL的互相转换。
  • 在生成短链接时，先利用随机数生成index逐个字符地拼接成短链接，然后判断是否存在。
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
public class Codec {
    private static final String HOST = "http://tinyurl.com/";
    private static final String CHAR = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int LIMIT = CHAR.length();
    
    Map<String, String> url2tiny = new HashMap<>();
    Map<String, String> tiny2url = new HashMap<>();
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (url2tiny.containsKey(longUrl)) {
            return HOST + url2tiny.get(longUrl);
        }
        String ret = null;
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++) {
                int index = (int) (Math.random() * LIMIT);
                sb.append(CHAR.charAt(index));
            }
            ret = sb.toString();
        } while (tiny2url.containsKey(ret));
        
        url2tiny.put(longUrl, ret);
        tiny2url.put(ret, longUrl);
        return HOST + ret;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return tiny2url.get(shortUrl.replace(HOST, ""));
    }
}
4. Median of 2 sorted arrays
  • 给两个int数组，返回二者合并后的中位数，要求在O(log(m+n))的时间复杂度以内。
  • 上来可以先讲讲mergesort的那种线性扫到中位数的O(m + n)做法。二分查找找的是能将两个数组恰好分成两个部分的index，而且确定了第一个数组的index之后，第二个数组的index也就确定了（因为每个部分取多少数是已知的）。
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
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; // but why (n + m + 1)/2?
        
        // 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;
    }
}
572. Subtree of Another Tree
  • 给两个二叉树，判断其中一棵是否说另一个的子树（存在val、结构完全相同的子树）。
  • naive的方法是无脑recursive，但是这样每个节点可能会被重复访问。另一种做法是用preorder将两个树encode成字符串，然后用contains判断是否是substring即可。但注意这个contains本身并不是O(N)的，可以提一句KMP算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 public class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        StringBuilder spre = new StringBuilder();
        StringBuilder tpre = new StringBuilder();
        preOrder(s, spre.append(","));
        preOrder(t, tpre.append(","));
        return spre.toString().contains(tpre.toString());
    }
    public void preOrder(TreeNode root, StringBuilder str){
        if(root == null){
            str.append("#,");
            return;
        }
        str.append(root.val).append(",");
        preOrder(root.left, str);
        preOrder(root.right, str);
    }
}
130. surrounded-regions
  • 给一个只含有XXOO的char二维数组，要求把所有被X完美包围的O替换成X，而绵延到边界的O就不替换。
  • 先将四个边边遍历一波，将所有的O以及连绵的O替换成特殊字符，然后再从头遍历，将特殊字符换回O、将中间的O换成X。
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
public class Solution {
    private class Point {
        int x;
        int y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int m = board.length, n = board[0].length;
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                bfs(board, 0, i);
            }
            if (board[m-1][i] == 'O') {
                bfs(board, m - 1, i);
            }
        }
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][n-1] == 'O') {
                bfs(board, i, n - 1);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '!') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void bfs(char[][] board, int x, int y) {
        int m = board.length, n = board[0].length;
        Queue<Point> q = new LinkedList<Point>();
        q.add(new Point(x, y));
        board[x][y] = '!';
        while (!q.isEmpty()) {
            Point curr = q.poll();
            int i = curr.x;
            int j = curr.y;
            if (i > 0 && board[i-1][j] == 'O') {        // up
                q.add(new Point(i-1, j));
                board[i-1][j] = '!';
            }
            if (i < m - 1 && board[i+1][j] == 'O') {    // down
                q.add(new Point(i+1, j));
                board[i+1][j] = '!';
            }
            if (j > 0 && board[i][j-1] == 'O') {        // left
                q.add(new Point(i, j-1));
                board[i][j-1] = '!';
            }
            if (j < n - 1 && board[i][j+1] == 'O') {    // left
                q.add(new Point(i, j+1));
                board[i][j+1] = '!';
            }
        }
    }
}

2016.10.5 Onsite

698. partition-to-k-equal-sum-subsets
  • 给一个数组，判断是否能划分成K个sum相等的子集。
  • 累加当前元素后到达下一层，判断是否达到了targetSum并且确实有元素（防止targetSum == 0且有负数的case）的情况下，开始往后遍历下一个group。
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 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length || k < 1) {
            return false;
        }
        if (k == 1) {
            return true;
        }
        int sum = IntStream.of(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int targetSum = sum / k;
        boolean[] visited = new boolean[nums.length];
        return checkPartition(nums, visited, 0, targetSum, 0, k, 0);
    }
    public boolean checkPartition(int[] nums, boolean[] visited, int startIndex, int targetSum, int currSum, int k, int elementCount) {
        if (k == 0) {      // 必须算完才行
            return true;
        }
        if (currSum == targetSum && elementCount > 0) {     // 保证每个部分真正有元素存入
            return checkPartition(nums, visited, 0, targetSum, 0, k - 1, 0);
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (checkPartition(nums, visited, i + 1, targetSum, currSum + nums[i], k, elementCount + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }
}
252. meeting-rooms
  • 给一个Interval的数组，每个Interval含有meeting的开始和结束时间戳，问是否能参加所有会议。
  • 贪心算法，根据start排序，然后取前后两个看有没有overlap。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        Arrays.sort(intervals, (a, b) -> a.start - b.start);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
}

2018.5.1 电面

97. interleaving-string
  • 给三个字符串s1, s2, s3，判断s3是否由s1和s2拼接而成，这里的拼接可以是交错的，但必须维持字符原本的出现顺序。
  • 方法一：DP。dp[i][j]表示从s1中取i个字符、从s2中取j个字符能否交错组成s3[i + j - 1]。判断时若从s1中取i个字符，即s1[i] == s3[i + j - 1]且dp[i - 1][j]能交错形成，或者从s2中取j个字符，即s2[j] == s3[i + j - 1]且dp[i][j - 1]能交错，则当前这个也可以，设为true即可。
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 isInterleave(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null) {
        return false;
    }
    int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
    if (len1 + len2 != len3) {
        return false;
    }
    char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
    boolean[][] dp = new boolean [len1 + 1][len2 + 1];
    
    for (int i = 0; i < dp.length; i++) {
        for (int j = 0; j < dp[0].length; j++) {
            if (i == 0) {
                if (j == 0) {
                    dp[i][j] = true; 
                } else {
                    dp[i][j] = cs2[j - 1] == cs3[i + j - 1] && dp[i][j - 1];
                }
            } else {
                if (j == 0) {
                    dp[i][j] = cs1[i - 1] == cs3[i + j - 1] && dp[i - 1][j];
                } else {
                    // take char from s1(move i) or from s2(move j)
                    dp[i][j] = (dp[i - 1][j] && cs1[i - 1] == cs3[i + j - 1])
                        || (dp[i][j - 1] && cs2[j - 1] == cs3[i + j - 1]);
                }
            }
        }
    }
    return dp[len1][len2];
}
  • 方法二：DFS。也需要利用二维boolean数组标记是否能组成interleaving字符串，若之前已经判断是false了就不用继续DFS了。判断时也是分别尝试从s1中和s2中取字符，然后与s3比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isInterleave(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) {
        return false;
    }
    char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
    boolean[][] invalid = new boolean [cs1.length + 1][cs2.length + 1];
    return dfs(cs1, cs2, cs3, 0, 0, invalid);
}
private boolean dfs(char[] cs1, char[] cs2, char[] cs3, int i, int j, boolean[][] invalid) {
    if (invalid[i][j]) {
        return false;
    }
    if (i + j == cs3.length) {  // end case: reach the end of s3
        return true;
    }
    if ((i < cs1.length && cs1[i] == cs3[i + j] && dfs(cs1, cs2, cs3, i + 1, j, invalid))
        || (j < cs2.length && cs2[j] == cs3[i + j] && dfs(cs1, cs2, cs3, i, j + 1, invalid))) {
        return true;
    }
    invalid[i][j] = true;
    return false;
}
  • 方法三：BFS。和DFS类似，将可达的i/j组合存入queue，直到遍历完s3。
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 boolean isInterleave(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) {
        return false;
    }
    char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
    boolean[][] visited = new boolean [cs1.length + 1][cs2.length + 1];
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[] {0, 0});
    while (!q.isEmpty()) {
        int[] curr = q.poll();
        if (visited[curr[0]][curr[1]]) {
            continue;
        }
        if (curr[0] + curr[1] == cs3.length) {  // reaches the end of s3
            return true;
        }
        if (curr[0] < cs1.length && cs1[curr[0]] == cs3[curr[0] + curr[1]]) {
            q.add(new int[] {curr[0] + 1, curr[1]});
        }
        if (curr[1] < cs2.length && cs2[curr[1]] == cs3[curr[0] + curr[1]]) {
            q.add(new int[] {curr[0], curr[1] + 1});
        }
        visited[curr[0]][curr[1]] = true;
    }
    return false;
}

2018.4.6

279. perfect-squares
  • 给一个正整数，求至少由多少个平方数相加能得到它。
  • DP。dp[i]表示数字i至少需要多少个平方数相加，那么对于每个i，遍历i - j * j即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int numSquares(int n) {
    if (n <= 0) {
        return 0;
    }
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}
[???]
  • 给一个BST，给一个区间[min, max]，将在区间之外的节点删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public TreeNode deleteOutliers(TreeNode root, int min, int max) {
    if (root == null || min > max) {
        return null;
    }
    if (root.val > max) {
        return deleteOutliers(root.left, min, max);
    } else if (root.val < min) {
        return deleteOutliers(root.right, min, max);
    } else {
        root.left = deleteOutliers(root.left, min, root.val - 1);
        root.right = deleteOutliers(root.right, root.val + 1, max);
        return root;
    }
}

2018.4.6 电面

53. maximum-subarray
  • 给一个int数组，求最大的subarry sum。
  • 方法一：直接O(N)搞定，维护一个当前的sum，要么是前面累加的结果、要么从当前开始加。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = Integer.MIN_VALUE, prev = 0;
        for (int i = 0; i < nums.length; i++) {
            prev = Math.max(prev + nums[i], nums[i]);
            ans = Math.max(ans, prev);
        }
        return ans;
    }
}
  • 方法二：分治法，要么纯左边、要么纯右边、要么从交界处向左右取元素。
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 int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return getMax(nums, 0, nums.length - 1);
    }
    private int getMax(int[] nums, int left, int right) {
        if (left == right) {    // end case
            return nums[left];
        }   
        int mid = (right + left) / 2;
        int leftMax = getMax(nums, left, mid);          // get max subarray only with left elements
        int rightMax = getMax(nums, mid + 1, right);    // get max ~ right
        int midMax = getMidMax(nums, left, mid, right); // get max sub that uses both left and right
        return Math.max(leftMax, Math.max(rightMax, midMax));
    }
    private int getMidMax(int[] nums, int left, int mid, int right) {
        int leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE;
        int sum = 0;    
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftMax = Math.max(sum, leftMax);   // at least take one element from left
        }
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {    
            sum += nums[i]; 
            rightMax = Math.max(sum, rightMax); // at least take one element from right
        }
        return leftMax + rightMax;
    }
}

2018.4.4 Onsite

103. binary-tree-zigzag-level-order-traversal
  • level层面的遍历二叉树，但是遍历顺序不是固定的从左到右，而是蛇形，这一层从左到右、下一行从右到左。
  • 方法一：BFS+Queue，正一下反一下。
  • 方法二：DFS时将level数也传入，对于偶数层则append到对应的List中，对于奇数层则insert到首位。
Longest common subsequence(注意和前面的max substring有异曲同工之妙)
  • 给两个字符串，求最长的公共子序列的长度。
  • DP。用两个指针i和j分别遍历s1和s2，若字符相同则取dp[i - 1][j - 1] + 1，否则取max{dp[i - 1][j], dp[i][j - 1]}.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxCommonSubsequenceLen(String s1, String s2) {
    if (s1 == null || s2 == null) {
        return 0;
    }
    int len1 = s1.length(), len2 = s2.length();
    int[][] dp = new int[len1][len2];
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            if (s1.charAt(i) == s2.charAt(j)) {
                dp[i][j] = i > 0 && j > 0 ? dp[i - 1][j - 1] + 1 : 1;
            } else {
                dp[i][j] = Math.max(i > 0 ? dp[i - 1][j] : 0, j > 0 ? dp[i][j - 1] : 0);
            }
        }
    }
    return dp[len1 - 1][len2 - 1];
}
  • Follow-up：如果需要返回任意一个这样的字符串呢？
  • 根据DP table一路回溯，若当前两个字符串的所取字符相等则放入结果中。
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 static String maxCommonSubsequence(String s1, String s2) {
    if (s1 == null || s2 == null) {
        return null;
    }
    int len1 = s1.length(), len2 = s2.length();
    int[][] dp = new int[len1][len2];
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            if (s1.charAt(i) == s2.charAt(j)) {
                dp[i][j] = i > 0 && j > 0 ? dp[i - 1][j - 1] + 1 : 1;
            } else {
                dp[i][j] = Math.max(i > 0 ? dp[i - 1][j] : 0, j > 0 ? dp[i][j - 1] : 0);
            }
        }
    }
    char[] ret = new char[dp[len1 - 1][len2 - 1]];
    int index = ret.length - 1, i = len1 - 1, j = len2 - 1;
    while (index >= 0) {
        if (s1.charAt(i) == s2.charAt(j)) {
            ret[index--] = s1.charAt(i);
            i--;
            j--;
        } else {
            if (i > 0 && dp[i][j] == dp[i - 1][j]) {
                i--;
            } else if (j > 0 && dp[i][j] == dp[i][j - 1]) {
                j--;
            }
        }
    }
    return new String(ret);
}

2018.1.21 Onsite

348. design-tic-tac-toe
  • XXOO游戏，两个玩家，每一行、每一列、两条对角线都是一样的话，对应玩家就赢了。要设计一个class，其中包含move函数，给坐标和玩家编号，在图里放，如果该玩家赢了就返回玩家编号。每行、每列需要统计两个玩家各自的个数，如果都是其中一个玩家都就赢了，两条对角线也是。
  • 记录行、列、两条对较线。区分两个玩家的O和X就通过正负一来判断，这样如果有一个玩家赢了就意味着一路相加结果是n或者-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
52
53
54
55
56
57
58
59
60
61
62
class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diag1, diag2;
    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rows = new int [n];
        cols = new int [n];
        diag1 = 0;
        diag2 = 0;
        this.n = n;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        if (row < 0 || row >= n || col < 0 || row >= n || player < 1 || player > 2) {
            return 0;
        }
        int addVal = player == 1? -1: 1;
        // for diag1
        if (row == col) {
            diag1 += addVal;
            if (isConnect(diag1)) {
                return player;
            }
        }
        
        // for diag2
        if (row + col == n - 1) {
            diag2 += addVal;
            if (isConnect(diag2)) {
                return player;
            }
        }
        
        // for row
        rows[row] += addVal;
        if (isConnect(rows[row])) {
            return player;
        }
        
        // for col
        cols[col] += addVal;
        if (isConnect(cols[col])) {
            return player;
        }
        return 0;
    }
    
    private boolean isConnect(int val) {
        return val / n != 0;
    }
}

2017.9.19 Onsite

297. serialize-and-deserialize-binary-tree
  • 实现二叉树的序列化与反序列化。
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
public class Codec {
    private final String NULL_NODE = "N";
    private final String SPLITTER = ",";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }
    private void preorder(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL_NODE).append(SPLITTER);
            return;
        }
        sb.append(root.val).append(",");
        preorder(root.left, sb);
        preorder(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] vals = data.split(SPLITTER);
        Queue<String> q = new LinkedList<>();
        for (String val : vals) {
            q.offer(val);
        }
        return deserialize(q);
    }
    private TreeNode deserialize(Queue<String> q) {
        if (q.isEmpty()) {
            return null;
        }
        String first = q.poll();
        if (first.equals(NULL_NODE)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(q);
        root.right = deserialize(q);
        return root;
    }
}
  • follow-up：如果是BST呢？那么在序列化的时候可以直接忽略掉null节点，因为在反序列化的时候可以直接通过val来判定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
40
41
42
43
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }
    
    private void preorder(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        sb.append(root.val).append(",");
        preorder(root.left, sb);
        preorder(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] vals = data.split(",");
        Queue<Integer> q = new LinkedList<>();
        for (String val : vals) {
            q.offer(Integer.parseInt(val));
        }
        return deserialize(q);
    }
    private TreeNode deserialize(Queue<Integer> q) {
        if (q.isEmpty()) {
            return null;
        }
        TreeNode root = new TreeNode(q.poll());
        Queue<Integer> smallerQueue = new LinkedList<>();
        while (!q.isEmpty() && q.peek() < root.val) {
            smallerQueue.offer(q.poll());
        }
        root.left = deserialize(smallerQueue);
        root.right = deserialize(q);
        return root;
    }
}

24. swap-nodes-in-pairs

  • 给一个链表头，要去反转所有相邻的节点，返回反转后的头。不可以修改头的val，这能修改next。
  • Iterative:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode swapPairs(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode fakeHead = new ListNode(0);
    fakeHead.next = head;
    ListNode curr = fakeHead;
    while (curr.next != null && curr.next.next != null) {
        ListNode first = curr.next;
        ListNode second = curr.next.next;
        first.next = second.next;
        second.next = first;
        curr.next = second;
        curr = first;       // actually it is curr.next.next
    }
    return fakeHead.next;
}
  • Follow-up: 用Recursive来做呢？
1
2
3
4
5
6
7
8
9
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode temp = head.next;
    head.next = swapPairs(head.next.next);
    temp.next = head;
    return temp;
}

382. linked-list-random-node

  • 面经里说的是“给一个stream of int”取随机取数字，要求每个数字被取到的概率相同。和这个LC原理相同，假设stream元素为[1, 2, 3]，每次只能读入一个数字。一开始读入1，只能保留它，概率为1；然后读入2，这是1和2之间保留谁的概率就是1/2；然后读入3，此时保留的数字与3只能保留一个，为了保证概率均等，需要在0~2中产生随机数，只有等于2的时候才选择索引为2的元素即3，概率为1/3，而上一步保留的那个数字留下来的概率则是1/2 * 2/3 = 1/3，概率依然相等。这个算法还可以推广到取k个元素出来的情况，这样内存中始终就只有非常少量（k + 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
public class Solution {
    ListNode head;
    java.util.Random random;
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        random = new java.util.Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() { 
        ListNode curr = head;
        int ret = curr.val;
        
        for (int i = 1; curr.next != null; i++) {
            curr = curr.next;
            if (random.nextInt(i + 1) == i) {
                ret = curr.val;
            }
        }
        return ret;
    }
}

2017.10.29 电面

98. validate-binary-search-tree
  • 常见的错误是直接greedy，只判断当前节点和孩子的大小。但BST的定义是比「所有的左子树都大、比右都小」。
  • 方法一：中序遍历时每次都判断前后两个元素的大小关系。又分为recursive和iterative的。
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
 // recursive: 全局的prev记录当前节点前一个是谁，比较大小
private TreeNode prev = null;
private boolean validateBST1(TreeNode root) {
    if (root == null) {
        return true;
    }
    if (!validateBST1(root.left)) {
        return false;
    }
    if (prev != null && prev.val >= root.val) {
        return false;
    }
    prev = root;
    return validateBST1(root.right);
}
 
// iterative: 用stack不断深入左节点，直到空再将栈顶与prev比较，然后进入右子树，继续不断向左。
private boolean validateBST2(TreeNode root) {
    if (root == null) {
        return true;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (prev != null && prev.val >= root.val) {
            return false;
        }
        prev = root;
        root = root.right;
    }
    return true;
}
  • 方法二：分治，为左右子树给定范围（min, max），在递归时更新左子树的上界、更新右子树的下界。
1
2
3
4
5
6
7
8
9
10
11
12
13
private boolean validateBST3(TreeNode root) {
    return dvcq(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode root, long min, long max) {
    if (root == null) {
        return true;
    }
    if (root.val <= min || root.val >= max) {
        return false;
    }
    return isValidBST(root.left, min, root.val) && 
        isValidBST(root.right, root.val, max);
}

2018.1.29 电面 + Onsite

235. lowest-common-ancestor-of-a-binary-search-tree
  • 给一个BST和两个其中的节点，求他们的LCA。根据值来划分即可，若p和q的值都在root同侧则递归到那里，一旦发现不同侧就返回当前root。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null || p == root || q == root) {
        return root;
    }
    if (p == q) {
        return p;
    }
    if (Math.max(p.val, q.val) < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (Math.min(p.val, q.val) > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }
}
236. lowest-common-ancestor-of-a-binary-tree
  • 给一个任意的二叉树和两个其中的节点，求他们的LCA。无法用值来比较，只能直接查找节点了。分别往左边和右边找，若root为其中一个节点则返回。这样在上层拿到左边和右边的搜索结果后就可以判断出现在哪一侧，若两边都找到了则说明当前节点就是LCA.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    if (root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    if (left == null && right == null) {
        return null;
    }
    return left == null? right: left;
}