0371-0380

371. Sum of Two Integers $\star$

372. Super Pow $\star\star$

373. Find K Pairs with Smallest Sums $\star\star$

374. Guess Number Higher or Lower $\star$

375. Guess Number Higher or Lower II $\star\star$

376. Wiggle Subsequence $\star\star$

377. Combination Sum IV $\star\star$

 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
func combinationSum4(nums []int, target int) int {
    // return func1(nums, target);
    return func2(nums, target);
}

// 1. complete-knapsack-problm
// !! ERROR, Can't use CKP
func func1(nums []int, target int) int {
    N := len(nums);
    if N <= 0 || target < 0 {
        return 0;
    }

    pack := make([]int, target+1);
    pack[0] = 1;

    for i := 0; i < N; i++ {
        for v := 0; v <= target; v++ {
            if v >= nums[i] {
                pack[v] = max(pack[v], 1 + pack[v-nums[i]]);
            }
        }
    }

    return pack[target];
}

// 2. standard DP, dp[n] means combinations to n
// O(n^2) time
func func2(nums []int, target int) int {
    dp := make([]int, target+1);
    dp[0] = 1;
    for i := 1; i <= target; i++ {
        for _, n := range nums {
            if i >= n {
                dp[i] += dp[i-n];
            }
        }
    }
    return dp[target];
}

func max(a int, b int) int {
    if a > b {
        return a;
    }
    return b;
}

378. Kth Smallest Element in a Sorted Matrix $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int kthSmallest(vector<vector<int>>& matrix, int k) {
    int l = matrix[0][0];
    int r = matrix.back().back();

    while (l < r) {
      int m = (l + r) >> 1;
      int count = 0;
      for (auto& row : matrix)
        count += upper_bound(row.begin(), row.end(), m) - row.begin();
      if (count >= k)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }
};

379. Design Phone Directory $\star\star$

380. Insert Delete GetRandom O(1) $\star\star$

 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
class RandomizedSet {
 public:
  bool insert(int val) {
    if (map.count(val)) return false;
    map[val] = vals.size();
    vals.push_back(val);
    return true;
  }

  bool remove(int val) {
    if (!map.count(val)) return false;
    int index = map[val];
    map[vals.back()] = index;
    map.erase(val);
    swap(vals[index], vals.back());
    vals.pop_back();
    return true;
  }

  int getRandom() {
    int index = rand() % vals.size();
    return vals[index];
  }

 private:
  vector<int> vals;
  unordered_map<int, int> map;
};