易贝

Posted on | Edited on | In | | Views:
Symbols count in article: 44k | Reading time ≈ 46 mins.

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

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;
    }