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$

  • 标准DP，但是测试case不够，是恰好通过[3, 33, 333] 100得输入的
  • 特殊的输入会导致中间结果太大，溢出标准类型可存储的值
  • 详细参考代码和我在leetcode上的diss
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
class Solution {
public:
  int combinationSum4(vector<int> &nums, int target) {
    // return func1(nums, target);
    // return func2(nums, target);
    return func3(nums, target);
  }

  // ** iterative
  int func1(vector<int> &nums, int target) { return helper1(nums, 0, target); }
  int helper1(vector<int> &nums, int sum, int target) {
    if (sum > target) {
      return 0;
    }
    if (sum == target) {
      return 1;
    }

    int res = 0;
    for (int i = 0; i < nums.size(); i++) {
      res += helper1(nums, sum + nums[i], target);
    }
    return res;
  }

  // ** 1D array dp
  int func2(vector<int> &nums, int target) {
    // vector<int> dp(target+1, 0);
    // vector<unsigned int> dp(target+1, 0);
    // vector<unsigned long> dp(target+1, 0);
    // vector<double> dp(target+1, 0);
    vector<long double> dp(target + 1, 0);
    for (auto n : nums) {
      if (n <= target) {
        dp[n] = 1;
      }
    }
    for (int i = 1; i <= target; i++) {
      for (auto n : nums) {
        if (i - n > 0) {
          dp[i] += dp[i - n];
        }
      }
    }

    cout << "size of int = " << sizeof(int) << endl;
    cout << "size of unsigned int = " << sizeof(unsigned int) << endl;
    cout << "size of long = " << sizeof(long) << endl;
    cout << "size of long long =" << sizeof(long long) << endl;
    cout << "size of double =" << sizeof(double) << endl;
    cout << "size of long double =" << sizeof(long double) << endl << endl;

    int cnt0 = 0;
    int cnt1 = 0;
    int cnt2 = 0;
    int cnt3 = 0;
    for (int i = 0; i <= target; i++) {
      // ** signed 4 Bytes integer max
      if (dp[i] > 2147483647) {
        cnt0++;
      }
      // ** unsigned 4 Bytes integer max
      if (dp[i] > 4294967295) {
        cnt1++;
      }
      // ** signed 8 Bytes integer max
      if (dp[i] > 9223372036854775807) {
        cnt2++;
      }
      // ** unsigned 8 Bytes integer max
      if (dp[i] > 18446744073709551615) {
        cnt3++;
      }
    }

    cout << "numbers >2147483647 count = " << cnt0 << endl;
    cout << "numbers >4294967295 count = " << cnt1 << endl;
    cout << "numbers >9223372036854775807 count = " << cnt2 << endl;
    cout << "numbers >18446744073709551615 count = " << cnt3 << endl << endl;

    unsigned int x = 4294967295;
    cout << "x = " << x << endl;
    x += 1;
    cout << "x = " << x << endl;

    return dp[target];
  }

  // ** minus always better to plus in func1()
  // ** NO... also TLE at [1,2,3] 32
  int func3(vector<int> &nums, int target) {
    if (target == 0) {
      return 1;
    }

    int res = 0;
    for (auto n : nums) {
      if (target >= n) {
        res += func3(nums, target - n);
      }
    }

    return res;
  }
};

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