谷入普昂

Posted on Edited on In Disqus:

迎难而上，祝我好运。

LRU Cache(146)

  • 模拟Least Recently Used缓存，当要插入新的entry(key, value)时规模不够，最近最少用到的entry会被清除。要求get和put都是O(1)。
  • 由于有键值对，肯定要有Map。key是整数，而put的时候，value不能真的存给的整数value，而是存双向链表中的一个节点，该节点的val再存给定的整数value。put还需要考虑是否是更新，更新则要把原节点val更新后拖到头部；在get的时候，也要注意拖到链表头部。当需要移除最近最少使用元素的时候，就需要把最后一个节点删掉，同时在map中删掉，所以链表节点中还需要存key才能去map中删。双向链表根据节点来删除是O(1)的，因为可以直接访问前后两个节点（单向链表提供待删除节点和它前一个节点也可以做到constant time）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class LRUCache {
    private class DoublyListNode {
        int key;
        int value;
        DoublyListNode prev;
        DoublyListNode next;
        private DoublyListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    int capacity;
    int currSize;
    DoublyListNode head, tail;
    HashMap<Integer, DoublyListNode> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<Integer, DoublyListNode>();
        currSize = 0;
        head = new DoublyListNode(0, 0);    // 伪头部
        tail = new DoublyListNode(0, 0);    // 伪尾部
        head.prev = null;
        head.next = tail;
        tail.prev = head;
        tail.next = null;
    }
    public int get(int key) {
        DoublyListNode node = map.get(key);
        if (node != null) {
            moveToFirst(node);
            return node.value;
        } else {
            return -1;
        }
    }
    public void put(int key, int value) {
        DoublyListNode node = map.get(key);
        if (node == null) {
            node = new DoublyListNode(key, value);
            currSize++;
            if (currSize > capacity) {
                currSize--;
                map.remove(popLast().key);  // 尾部的
            }
            add(node);
            map.put(key, node);
        } else {
            node.value = value;
            moveToFirst(node);
        }
    }
    private void add(DoublyListNode node) {
        DoublyListNode nextOfHead = head.next;
        head.next = node;       // 插入到头部的下一位，需要调整头指针的指向
        node.prev = head;
        nextOfHead.prev = node;
        node.next = nextOfHead;
    }
    private void remove(DoublyListNode node) {
        DoublyListNode prevOfNode = node.prev;
        DoublyListNode nextOfNode = node.next;
        
        prevOfNode.next = nextOfNode;
        nextOfNode.prev = prevOfNode;
    }
    private DoublyListNode popLast() {
        DoublyListNode last = tail.prev;
        remove(last);
        return last;
    }
    // 被get了，就需要挪到头部，先删除再插入到头部即可
    private void moveToFirst(DoublyListNode node) {
        remove(node);
        add(node);
    }
}
  • follow-up：要求写成Generics的形式，不能认定键和值是int。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class LRUCache<T, U> {
    class DoublyListNode {
        T key;
        U val;
        DoublyListNode prev;
        DoublyListNode next;

        public DoublyListNode() {
            
        }
        public DoublyListNode(T key, U val) {
            this.key = key;
            this.val = val;
        }
    }
    int capacity;
    int currSize;
    DoublyListNode head, tail;
    Map<T, DoublyListNode> map;
    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        head = new DoublyListNode();
        tail = new DoublyListNode();
        head.prev = null;
        head.next = tail;
        tail.prev = head;
        tail.next = null;
    }
    
    public U get(T key) {
        if (map.containsKey(key)) {
            moveToFirst(map.get(key));
            return map.get(key).val;
        } else {
            return null;
        }
    }
    
    public void put(T key, U value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
            DoublyListNode node = new DoublyListNode(key, value);
            map.put(key, node);
            add(node);
        } else {
            DoublyListNode node = new DoublyListNode(key, value);
            map.put(key, node);
            add(node);
            currSize++;
            if (currSize > capacity) {
                map.remove(tail.prev.key);
                remove(tail.prev);
                currSize--;
            }
        }
    }
    private void remove(DoublyListNode node) {
        DoublyListNode prev = node.prev;
        prev.next = node.next;
        node.next.prev = prev;
    }
    private void add(DoublyListNode node) {
        DoublyListNode oldFirst = head.next;
        node.next = oldFirst;
        oldFirst.prev = node;
        head.next = node;
        node.prev = head;
    }
    private void moveToFirst(DoublyListNode node) {
        remove(node);
        add(node);
    }
}

奇偶归一

  • 对于任何一个数，如果是偶数的话就除以2，是奇数的话乘以3+1，最后这么算经过若干次运算总会变成1.给一个范围[m, n]，求其中所有数字算成1所需要的步数的最大值。
  • 大概考察的是cache提速。从m开始计算，将所有中间过程遇到的数字都存入map。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int maxStep(int m, int n) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = m; i <= n; i++) {
            ans = Math.max(getStep(map, i), ans);
        }
        return ans;
    }
    private int getStep(Map<Integer, Integer> map, int num) {
        Queue<Integer> q = new LinkedList<>();
        while (num != 1 && !map.containsKey(num)) {
            q.add(num);
            if (num % 2 == 1) {
                num = num * 3 + 1;
            } else {
                num /= 2;
            }
        }
        int base = map.get(num);
        int ret = base + q.size();
        while (!q.isEmpty()) {
            map.put(q.peek(), base + q.size());
            q.poll();
        }
        return ret;
    }
}

215. kth-largest-element-in-an-array

  • 求一个无序的int数组，经过排序后的第k个大的元素。
  • ME：立刻想到了quickSort的应用，写出来是这样。我在这里用的是『以首元素为pivot』，而不是之前一直写的『以中间元素为pivot』的快排，不太熟悉，参考了princeton课件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 1 || k > nums.length) {
            return 0;
        }
        return quickSort(nums, 0, nums.length - 1, k);
    }
    private int quickSort(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }
        int pivot = nums[start], left = start, right = end + 1;
        while (left < right) {
            while (nums[++left] < pivot) {
                if (left == end) {
                    break;
                }
            }
            while (nums[--right] > pivot) {
                if (right == start) {
                    break;
                }
            }
            if (left < right) {
                swap(nums, left, right);
            }
        }
        swap(nums, start, right);
        int currK = end + 1 - right;    // 如果是求第k小的就不用这样转一下了
        if (currK == k) {
            return nums[right];
        } else if (k > currK) {
            return quickSort(nums, start, right - 1, k - currK);
        } else {
            return quickSort(nums, right + 1, end, k);
        }
    }
    private void swap(int[] nums, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

  • TA：这个是一个总结，可以使用Java内置的priorityQueue（其实就是小根堆），将原数组的每个元素插入进去，始终维持规模为K，最后剩下的队首就是了。
1
2
3
4
5
6
7
8
9
10
11
public int findKthLargest(int[] nums, int k) {
    final PriorityQueue<Integer> pq = new PriorityQueue<>();    // 第k小就反过来排序就好了
    for(int val : nums) {
        pq.offer(val);

        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

692. top-k-frequent-words

  • 给一个String数组，求出现频率top k的字符串。
  • 跟347类似。先用Map存每个单词出现的频数，再自定义根据频数minHeap存这些Map.Entry，然后每次都check堆的规模，一旦大于k就直接把最小的poll出来，这样就保证在minHeap中的一定是top k.最后就直接逆序插入结果List。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> ans = new ArrayList<>();
        if (words == null || words.length == 0 || k == 0) {
            return ans;
        }
        // 统计每个单词出现的频数
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (!map.containsKey(word)) {
                map.put(word, 1);
            } else {
                map.put(word, map.get(word) + 1);
            }
        }
        // 将entry按照频数从小到大插入PQ，若规模>k则直接poll掉最小的
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a, b) -> {
            return a.getValue() != b.getValue()? 
                a.getValue() - b.getValue() : b.getKey().compareTo(a.getKey());
        });
        for (Map.Entry<String, Integer> e : map.entrySet()) {
            pq.offer(e);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        // 取PQ元素，逆序插入结果
        while (!pq.isEmpty()) {
            ans.add(0, pq.poll().getKey());
        }
        return ans;
    }
}
  • follow-up：如果给定的输入不是一个完整的数组，而是一个stream，即每次都只能取得一个单词，然后立即返回top k，如何改进？
  • 关键在于无法在最开始就获得完整的频数统计Map，在插入minHeap的时候就无法知道后续的Entry需不需要覆盖PQ中的值。因此需要一个额外的Map记录具体那些Entry目前被存放在minHeap中；当新的单词出现，就先更新map中的项，然后再看看它是否在PQ中，在则需要更新（我只能想到把k个元素全抖出来再加进去），不在则跟minHeap的peek比较决定是否需要替换。这样时间是O(N)的统计频数、O(logN)的插入minHeap、O(KlogK)的更新(?)和最后O(K)的倒入List。

437. path-sum-iii

  • 给一个二叉树，给一个目标值sum，求有几条从上往下累加的路径之和等于sum。
  • 递归DFS，每次深入之前都先减掉当前节点的值。但这样子的时间复杂度是O(N^2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int pathSum(TreeNode root, int sum) {    // calculate path num starting from root
        if (root == null) {
            return 0;
        }
        return dfs(root, sum)   // taking the given node
            + pathSum(root.left, sum) + pathSum(root.right, sum); // start from left/right child
    }
    private int dfs(TreeNode node, int target) {    // dig to find path num taking current node
        if (node == null) {
            return 0;
        }
        return (node.val == target? 1 : 0) + dfs(node.left, target - node.val) + dfs(node.right, target - node.val);
    }
}
  • 更高效的做法是利用Map做cache将中间算出来的结果暂存起来。在每一步DFS过程中，先累积当前节点的val到currSum，然后求(currSum - target)在map中是否有记录。然后就是往左右孩子递归求多少种ways。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return getPath(root, 0, sum, map);
    }
    private int getPath(TreeNode root, int currSum, int target, Map<Integer, Integer> map) {
        if (root == null) {
            return 0;
        }
        currSum += root.val;
        int ways = map.getOrDefault(currSum - target, 0);       // 为什么是currSum - target
        map.put(currSum, map.getOrDefault(currSum, 0) + 1); 
        // 
        ways += getPath(root.left, currSum, target, map) + getPath(root.right, currSum, target, map);
        map.put(currSum, map.get(currSum) - 1);
        return ways;
    }
}

322. coin-change

  • 给一个数组表示有哪些面值的硬币，然后给一个目标值，求最少用多少枚硬币能达到的这个目标值。
  • ME：这个很明显的DP，所以我会做，写出来是这样。思路是从前往后更新DP数组，一开始全部初始化为-1表示不可达，dp[i]表示面值为i需要多少枚硬币，显然dp[0]应为0。对coin面值数组排序保证从小到大排列，然后开始从1更新。若i - coin[j] >= 0说明可以从该状态加一枚coin[j]的硬币到达状态i，更新之，否则就可以直接跳出内层循环了，因为再往后看其他面值的coin只会负得更多。最后取dp[amount]即得。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return 0;
        }
        Arrays.sort(coins);     // 从小到大取硬币
        int[] dp = new int [amount + 1];
        Arrays.fill(dp, -1);    // 初始化为-1表示无解
        dp[0] = 0;
        
        for (int i = 1; i < dp.length; i++) {           // 从前往后更新每一个可能的值
            for (int j = 0; j < coins.length; j++) {    // 从小的面值开始更新
                int index = i - coins[j];
                if (index >= 0) {
                    if (dp[index] >= 0) {
                        dp[i] = dp[i] < 0? dp[index] + 1: Math.min(dp[i], dp[index] + 1);
                    }
                } else {
                    break;
                }
            }
        }
        return dp[amount];
    }
}
  • TA：我的是Bottom-up的DP，从无到有累积到目标值。还有一种Top-down的思路，利用递归来直接从目标值往回减。递归的结束条件有两种，一个是target减完变成了负数，则不存在，返回0；若target恰好是0，那么直接返回0表示不需要额外添加硬币；还有就是如果在之前的结果中已经计算出了DP的值，直接返回即可。否则就逐个取出coin面值，然后用当前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
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return 0;
        }
        return helper(coins, amount, new int [amount]);
    }
    private int helper(int[] coins, int target, int[] dp) {
        if (target < 0) {
            return -1;  // 硬币用过头了，不能继续
        }
        if (target == 0) {
            return 0;   // 不需要新的硬币了，直接返回
        }
        if (dp[target - 1] != 0) {
            return dp[target - 1];
        }
        // 找到
        int min = Integer.MAX_VALUE;
        for (int coin: coins) {
            int temp = helper(coins, target - coin, dp);    // 当前target减去硬币面额需要多少枚
            if (temp >= 0) {
                min = Math.min(temp + 1, min);
            }
        }
        dp[target - 1] = min == Integer.MAX_VALUE? -1: min; // -1表示凑不出
        return dp[target - 1];
    }
}

238. product-of-array-except-self

  • 给一个数组num[]，求对应长度的数组使得output[i]为所有数的积除了num[i]，要求O(N)且不能用除法。
  • ME：不给我用除法我整个人是懵逼的，脑子一下转不过来，陷入江局。。。
  • TA：这个给出了如何从辅助数组到O(1)space的思考过程。首先这个辅助数组的方法我怎么就想不出来呢，left数组从左开始每一格存储的是『除了当前数字的前面数字之积』，right数组从右开始存储的是『除了当前数字的后续数字之积』，然后再来一波对应把left和right乘起来就得到了『除了当前数字前面和后面数字之积』。这怎么能想不到呐？？写出来是这样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length < 1) {
            return new int [0];
        }
        int[] ans = new int [nums.length];
        int[] left = new int [nums.length];
        int[] right = new int [nums.length];
        left[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        right[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        
        for (int i = 0; i < nums.length; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
}

至于从O( N )到O( 1 )的空间复杂度，知道了之后也没啥了，以后再碰到尽量想起来吧。既然每一个地方都需要用到它左边所有项之积和右边所有项之积，而如果只维护left和right两个值，无法在循环到第一位的时候就获得右边所有数的积，怎么办？答主的做法是在一步循环里，对两端进行更新，也就是每个位置会被更新两次，一次是随left更新，一次是随right更新，left和right就分别从左和从右向另一端去乘。妙哉！如果把这个one-pass拆开来写，就是这样的.

1
2
3
4
5
6
7
8
9
10
11
12
public int[] productExceptSelf(int[] nums) {
    int[] result = new int[nums.length];
    for (int i = 0, tmp = 1; i < nums.length; i++) {
        result[i] = tmp;
        tmp *= nums[i];
    }
    for (int i = nums.length - 1, tmp = 1; i >= 0; i--) {
        result[i] *= tmp;
        tmp *= nums[i];
    }
    return result;
}

正则 10

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

4. Median of 2 sorted arrays

  • 给两个int数组，返回二者合并后的中位数。
  • 朴素的做法，逐个merge，然后分奇数、偶数求中位数。注意这里需要返回的是double。时间复杂度Linear,O((m + n)/2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len_total = nums1.length + nums2.length;
    int len_total_half = len_total >> 1;
    int[] merged = new int [len_total];
    
    int i = 0, j = 0, len = 0;
    boolean finished = false;
    while (!finished && i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            merged[len++] = nums1[i++];
        } else {
            merged[len++] = nums2[j++];
        }
        if (len > len_total_half) {
            finished = true;
        }
    }
    while (!finished && i < nums1.length) {
        merged[len++] = nums1[i++];
        if (len > len_total_half) {
            finished = true;
        }
    }
    while (!finished && j < nums2.length) {
        merged[len++] = nums2[j++];
        if (len > len_total_half) {
            finished = true;
        }
    }
    
    if (len_total % 2 == 1) {
        return merged[len_total_half];
    } else {
        return (double)((merged[len_total_half] + merged[len_total_half-1])/2.0);
    }
  • follow-up：要求在O(log(m+n))的时间复杂度以内？
  • 中位数可以把有序数组分成等长的两部分，因此在数组1取i个元素、数组2取j个元素，使得i + j == 剩余数字个数并且满足大小关系
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
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; // odd: i = j, even: i = j - 1
    
    // 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;
}

5. Longest palindromic substring

  • 给一个字符串，返回最长的回文子串（自对称）。
  • 这个似乎也是暴力法，只是用了更优雅的方式——双指针分别扩展，而我的暴力法是双指针向中间合拢，扩展的方式在worst case下复杂度也是O( n^2 )。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private int start, maxLen;
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        char[] sChar = s.toCharArray();
        start = 0;
        maxLen = 1;
        for (int i = 0; i < sChar.length; i++) {
            expand(sChar, i, i);        // odd
            expand(sChar, i, i + 1);    // even
        }
        return s.substring(start, start + maxLen);
    }
    private void expand(char[] sChar, int left, int right) {
        while (left >= 0 && right < sChar.length
               && sChar[left] == sChar[right]) {
            left--;
            right++;
        }
        if (maxLen < right - left - 1) {    // warning
            start = left + 1;               // warning not left
            maxLen = right - left - 1;      // warning
        }
    }
}
  • 这题也是典型的DP题，dp[i][j]表示字符串的substring[i, j] - inclusive是否自对称。当i、j对应位置的字符相等时，再看看它们所夹的i + 1、j - 1部分是否自对称即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int maxLen = 1, start = 0;
        for (int right = 1; right < len; right++) {
            for (int left = right; left >= 0; left--) {
                dp[left][right] = s.charAt(left) == s.charAt(right) && (right - left < 2 || dp[left + 1][right - 1]);
                if (dp[left][right] && right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    start = left;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

3 sum

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

202. happy-number

  • 给一个正整数，判断它是否Happy。所谓happy指的是求各位的数字的平方和，得到的是1则是happy，不是1就继续这样算平方和。不是happy的数会陷入循环。
  • ME：递归加Set标记是否轮回搞定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public boolean isHappy(int n) {
        if (n < 1) {
            return false;
        }
        HashSet<Integer> set = new HashSet<>();
        return isHappy(n, set);
    }
    private boolean isHappy(int n, HashSet<Integer> set) {
        if (set.contains(n)) {
            return false;
        }
        set.add(n);
        int newN = 0;
        while (n != 0) {
            int digit = n % 10;
            newN += digit * digit;
            n /= 10;
        }
        if (newN == 1) {
            return true;
        }
        return isHappy(newN, set);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public boolean isHappy(int n) {
        int slow, fast = n;
        do {
            slow = next(slow);
            fast = next(next(fast));
            if (slow == 1 || fast == 1) {
                return true;
            }
        } while (slow != fast);
        return false;
    }
    
    public int next(int n) {
        int result = 0;
        while (n > 0) {
            int remainder = n % 10;
            result += remainder * remainder;
            n /= 10;
        }
        return result;
    }
}

sort array with only 0 and 1

  • 对一个只含有0和1的数组排序。
  • 前后双指针。
  • 木桶排序。

string repetition

  • 给一个String和重复次数N，返回重复这么多次的String。
  • naive的办法是O(N)，但其实可以O(logN)，就是每次循环时折半，拼接之前将原字符串拼一遍。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String repeat(String str, int num) {
    if (num <= 0) {
        return "";
    }
    StringBuilder result = new StringBuilder();
    StringBuilder sb = new StringBuilder(str);

    while (true) {
        if ((num & 1) != 0) {
            result.append(sb);
        }
        num /= 2;
        if (num == 0) {
            break;
        }
        sb.append(sb);
    }
    return result.toString();
}

366. find-leaves-of-binary-tree

  • 给一个二叉树，求一层层仰视时所能看到的节点，看完后删除这些节点后继续仰视下一层。注意不是层级遍历！
  • 其实就是利用高度的定义，对于每个节点对应地放到它所属的高度的位置即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        height(root, ans);
        return ans;
    }
    private int height(TreeNode node, List<List<Integer>> ans) {
        if (node == null) {
            return -1;  // 保证叶子节点高度为0
        }
        int h = 1 + Math.max(height(node.left, ans), height(node.right, ans));  // 当前节点的高度 = 左右较大者 + 1
        if (ans.size() == h) {  // 叶子结点高度为0，索引也为0
            ans.add(new ArrayList<>());
        }
        ans.get(h).add(node.val);
        return h;
    }
}

513. find-bottom-left-tree-value

  • 给一个二叉树，求最下面一层最左边的节点。
  • 方法一：Iterative，从右往左进行层级遍历，最后一个遍历到的节点就是最下层的最左节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        TreeNode curr = null;
        while (!q.isEmpty()) {
            curr = q.poll();
            if (curr.right != null) {
                q.offer(curr.right);
            }
            if (curr.left != null) {
                q.offer(curr.left);
            }
        }
        return curr.val;
    }
}
  • 方法二：Recursive, 正常地从左到右前序遍历，但是会track深度，第一个达到新的深度的节点就一定是最左边的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int ans = 0, h = 0;
    public int findBottomLeftValue(TreeNode root) {
        find(root, 1);
        return ans;
    }
    public void find(TreeNode root, int level) {
        if (h < level) {
            ans = root.val;
            h = level;
        }
        if (root.left != null) {
            find(root.left, level + 1);
        }
        if (root.right != null) {
            find(root.right, level + 1);
        }
    }
}

reverse LinkedList

  • 反转一个链表。
  • Iterative: 用循环每次两两反转。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode currNext = curr.next;
        curr.next = prev;

        prev = curr;
        curr = currNext;
    }
    return prev;
}
  • Recursive: 递归往后反转之后，当前节点的下一个节点就会变成最后一个节点，直接把当前节点拼到最后即可。
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;
}

186. reverse-words-in-a-string-ii

  • 给一个char数组，反转单词出现顺序。I love programming变成programming love I。
  • 先反转全部，再根据空格位置反转每个单词。
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
class Solution {
    public void reverseWords(char[] str) {
        if (str == null || str.length == 0) {
            return;
        }
        reverse(str, 0, str.length - 1);
        int start = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == ' ') {
                reverse(str, start, i - 1);
                start = i + 1;
            }
        }
        reverse(str, start, str.length - 1);
    }
    private void reverse(char[] str, int start, int end) {
        while (start < end) {
            char temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            start++;
            end--;
        }
    }
}

implement linkedhashmap

  • HashMap：首先讨论普通的HashMap，底层其实就是Entry的数组(bucket)，根据hashCode找到bucket的存放位置，再根据equals判断key是否相等。每个Entry是一个节点，带有next引用，这样就可以形成一个链表了。
  • LinkedHashMap：与HashMap相比，需要维护put时的顺序，这里是通过加入before和after来构建双向链表，put时就可以进行赋值这样在remove的时候也可以O(1)完成。为了方便删除，也可以用dummy头部的方式简化操作。

implement priority queue

  • priority queue类似于小根堆，需要保证根节点比两个孩子都小就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private int createMinHeap(ListNode[] lists, int end) {    // end is inclusive
    if (end < 0 || end > lists.length) {
        return -1;
    }
    if (lists[0] == null) {
        swap(lists, 0, end);
        if (--end <= 0) {
            return end;
        }
    }
    for (int i = (end - 1)/2; i >= 0; i--) {
        end = maintainMinHeap(lists, i, end);
    }
    return end;
}
private int maintainMinHeap(ListNode[] lists, int start, int end) {
    if (lists[0] == null) {
        swap(lists, 0, end);
        if (--end <= 0) {
            return end;
        }
    }
    int fatherIndex = start;
    while (fatherIndex <= end) {
        int smallerIndex = 2*fatherIndex + 1;
        if (smallerIndex > end) {
            break;
        } else {
            if (smallerIndex < end 
               && lists[smallerIndex+1].val < lists[smallerIndex].val) {
                smallerIndex ++; 
            }
            if (lists[smallerIndex].val < lists[fatherIndex].val) {
                swap(lists, fatherIndex, smallerIndex);
                fatherIndex = smallerIndex;
            } else {
                break;
            }
        }
    }
    return end;
}

572. subtree-of-another-tree

  • 给两棵树，判断后者是不是前者的子树。子树指的是还有一个任意节点为根的子树，结构、数值完全一样。
  • 递归搞定。先判断两个树是否相同，若相同直接就是子树了。若不同则需要到左右子树进行递归，判断t是否是左／右的子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        return isSame(s, t) ? true : isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        return s.val == t.val ? isSame(s.left, t.left) && isSame(s.right, t.right) : false;
    }
}

remove-duplicates-from-sorted-array

  • 给一个已排好序的int数组，删除其中的重复项，返回长度。玛德我一开始以为只需要返回一个长度而不用对原数组开刀，还在想这题这么衣洗。题目说的leave beyond length是说该长度之后数组里是什么内容不关心，又不是说besides。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[len] != nums[i]) { // lazy move len
                nums[++len] = nums[i];  // when num[i] is diff from nums[len]
            }
        }
        return ++len;   // since last one cannot be compared to next different element
    }
}

remove-duplicates-from-sorted-array-ii

  • 给一个排好序的int数组，对它进行操作使得其中任意元素至多出现两次，返回经过修改后的数组长度。至于该长度之后的内容怎样，并不在意。
  • 定义窗口为2，判断当前数字和距离当前末尾往前两格的数字是否相等，不相等才能加入进来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int i = 0;
        for (int num: nums) {
            if (i < 2 || num > nums[i - 2]) {   
                nums[i] = num;
                i++;
            }
        }
        return i;
    }
}

127. word-ladder

很图论的题，每一个单词看作节点，路径有无根据「能否改一个字母变成它」判断，在BFS过程中可达就直接入queue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0
          || beginWord.length() != endWord.length() || wordList == null || wordList.size() == 0) {
            return 0;
        }
        Set<String> wordSet = new HashSet<>(wordList);
        Queue<String> toVisit = new LinkedList<>();
        bfs(beginWord, wordSet, toVisit);
        int dist = 2;
        while (!toVisit.isEmpty()) {
            int size = toVisit.size();
            for (int i = 0; i < size; i++) {
                String curr = toVisit.poll();
                if (curr.equals(endWord)) {
                    return dist;
                } else {
                    bfs(curr, wordSet, toVisit);
                }
            }
            dist++;
        }
        return 0;
    }
    
    private void bfs(String beginWord, Set<String> wordSet, Queue<String> toVisit) {
        wordSet.remove(beginWord);
        StringBuilder sb = new StringBuilder(beginWord);
        for (int i = 0; i < sb.length(); i++) {
            char origin = sb.charAt(i);
            for (int k = 0; k < 26; k++) {
                char c = (char)('a' + k);
                sb.setCharAt(i, c);
                String curr = sb.toString();
                if (wordSet.contains(curr)) {
                    toVisit.add(curr);
                    wordSet.remove(curr);
                }
            }
            sb.setCharAt(i, origin);
        }
    }
}

126. word-ladder-ii

词典中每一个词都是一个node，要从起点到终点，如果要记录这些最短的路径具体是怎么走的，就需要在BFS判断可不可达并构建临街表的基础上再来一个DFS，从起点开始一直往后（不走回头路利用的是后出现的节点的距离一定是先经过的节点的距离+1），如果到了终点就把经过的路径存起来。最后形成的就是路径的列表了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        wordSet.add(beginWord);
        Map<String, List<String>> neighborMap = new HashMap<>();
        Map<String, Integer> distanceMap = new HashMap<>();
        List<List<String>> ans = new ArrayList<>();

        bfs(beginWord, endWord, wordSet, neighborMap, distanceMap);
        dfs(beginWord, endWord, neighborMap, distanceMap, new Arraylist<String>(), ans);
        return ans;
    }
    // 用BFS构建邻接表并维护离起点的距离
    private void bfs(String beginWord, String endWord, Set<String> wordSet, 
    Map<String, List<String>> neighborMap, Map<String, Integer> distanceMap) {
        for (String word: wordSet) {
            neighborMap.put(word, new ArrayList<String>());
        }
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        distanceMap.put(beginWord, 0);
        while (!q.isEmpty()) {
            int size = q.size();
            boolean reached = false;
            for (int i = 0; i < size; i++) {
                String currWord = q.poll();
                int currDistance = distanceMap.get(currWord);
                List<String> neighborList = getNeighborList(currWord, wordSet);
                for (String neighbor: neighborList) {
                    neighborMap.get(currWord).add(neighbor);
                    if (!distanceMap.containsKey(neighbor)) {
                        distanceMap.put(neighbor, currDistance + 1);
                        if (neighbor.equals(endWord)) {
                            reached = true;
                        } else {
                            q.add(neighbor);
                        }
                    }
                }
            }
            if (reached) {
                break;
            }
        }
    }
    // 通过替换字母并判断是否在dict中产生给定词的邻居
    private List<String> getNeighborList(String currWord, Set<String> wordSet) {
        char[] cstr = currWord.toCharArray();
        List<String> ret = new ArrayList<>();

        for (int i = 0; i < cstr.length; i++) {
            char origin = cstr[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == origin) {
                    continue;
                }
                cstr[i] = c;
                String temp = new String(cstr);
                if (wordSet.contains(temp)) {
                    ret.add(temp);
                }
            }
            cstr[i] = origin;
        }
        return ret;
    }
    // 从起点开始往它的邻居DFS
    private void dfs(String currWord, String endWord, Map<String, List<String>> neighborMap,
    Map<String, Integer> distanceMap, List<String> path, List<List<String>> ans) {
        path.add(currWord);
        if (currWord.equals(endWord)) {
            ans.add(new ArrayList<String>(path));
        } else {
            int currDistance = distanceMap.get(currWord);
            List<String> neighborList = neighborMap.get(currWord);
            for (String neighbor: neighborList) {
                if (distanceMap.get(neighbor) == currDistance + 1) {
                    dfs(neighbor, endWord, neighborMap, distanceMap, path, ans);
                }
            }
        }
        path.remove(path.size() - 1);
    }
}

BST验证

  • 常见的错误是直接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 dvcq(TreeNode root, long min, long max) {
    if (root == null) {
        return true;
    }
    if (root.val <= min || root.val >= max) {
        return false;
    }
    return dvcq(root.left, min, Math.min(root.val, max))
            && dvcq(root.right, Math.max(root.val, min), max);
}

22. generate-parentheses

  • 给一个int表示括号的对儿数，输出所有符合括号匹配规则的字符串，存入List中返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (n < 1) {
            return ans;
        }
        
        dfs(n, 0, 0, "", ans);
        return ans;
    }
    private void dfs(int n, int left, int right, String s, List<String> ans) {
        if (left == n && right == n) {
            ans.add(s);
            return;
        }
        if (left < n)
            dfs(n, left + 1, right, s + "(", ans);
        
        if (right < left)
            dfs(n, left, right + 1, s + ")", ans);
    }
}
class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>();
        if (n < 1) {
            return new ArrayList<String>();
        }
        
        dp.add(Arrays.asList(""));
        for (int i = 1; i <= n; i++) {
            List<String> curr = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                for (String first: dp.get(j)) {
                    for (String second: dp.get(i - 1 - j)) {
                        curr.add("(" + first + ")" + second);
                    }
                }
            }
            dp.add(curr);
        }
        
        return dp.get(n);
    }
}

袜子匹配

  • 给一个数组表示袜子的编号，匹配到一双之后就输出，未匹配的最后输出。例如1, 3, 2, 1, 1, 2, 4输出1, 2, 3, 1, 4.
  • 用LinkedHashSet维护插入Set的顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static List<Integer> matchSocks(List<Integer> socks) {
    Set<Integer> set = new LinkedHashSet<>();
    List<Integer> ans = new ArrayList<>();
    for (int sock : socks) {
        if (set.contains(sock)) {
            set.remove(sock);
            ans.add(sock);
        } else {
            set.add(sock);
        }
    }
    ans.addAll(set);
    return ans;
}

销售额统计

  • 给一堆每一天的销售情况数据List，统计每一天销售最多货物的销售员，返回Map<String, String>，key是日期的字符串，value是售货员名字.
  • 从List中提取信息，对于每一天维护一个Map<String, Set<Seller>>，每一个Seller中有名字和count，此外还需要维护一个当天的最大值max的Map<String, Integer>，如果插入时发现count比max大就更新一波。

Vending machine

  • 设计自动售货机。用户put required money or more, 给它相应的物品以及显示余额；用户didnt put enough money, 不给物品，显示商品所需实际价格。
  • 不知道具体是什么要求，如果只是判断钱够不够感觉只需要在一个方法里面放一个if就行了啊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Item {
    String id;
    double price;
    int count;
}
class VendingMachine {
    private Map<String, Item> itemMap;
    public VendingMachine(Map<String, Item> itemMap) {
        this.itemMap = itemMap;
    }
    public void putMoney(String itemId, double inputPrice) {
        Item item = itemMap.get(itemId);
        if (item.count == 0) {
            // 没了
            return;
        }
        if (inputPrice > item.price) {
            // 显示余额
        } else {
            // 钱不够
        }
    }
}