0471-0480

471. Encode String with Shortest Length $\star\star\star$

472. Concatenated Words $\star\star\star$

473. Matchsticks to Square $\star\star$

474. Ones and Zeroes $\star\star$

  • 标准的二维DP问题，注意在func3()中使用了非常常见的，改从小到大迭代为从大到小以节省dp数组的技巧，暂时想不起来是在哪学到的这个技巧
  • 想起来了，在背包九讲的第一讲的优化空间复杂度中学习得到的，这个题应该划分为第4种背包问题，即二维费用背包问题
 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
class Solution {
public:
  int findMaxForm(vector<string> &strs, int m, int n) {
    // return func1(strs, m, n);
    // return func2(strs, m, n);
    return func3(strs, m, n);
  }

  // ** recursive
  // ** time 0(len * 2^N), len = max length of strs, N = strs.size()
  int func1(vector<string> &strs, int m, int n) {
    return helper1(strs, 0, m, n);
  }
  int helper1(vector<string> &strs, int idx, int m, int n) {
    if (idx >= strs.size()) {
      return 0;
    }

    int cnt0 = 0;
    int cnt1 = 0;
    for (int i = 0; i < strs[idx].length(); i++) {
      if (strs[idx][i] == '0')
        cnt0++;
      if (strs[idx][i] == '1')
        cnt1++;
    }

    int notp = helper1(strs, idx + 1, m, n);
    int pick = notp;
    if (cnt0 <= m && cnt1 <= n) {
      pick = 1 + helper1(strs, idx + 1, m - cnt0, n - cnt1);
    }

    return max(notp, pick);
  }

  // ** dp two 2D array
  int func2(vector<string> &strs, int m, int n) {
    vector<vector<int>> dp1(m + 1, vector<int>(n + 1, 0));
    vector<vector<int>> dp2(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < strs.size(); i++) {
      int cnt0 = 0;
      int cnt1 = 0;
      for (int j = 0; j < strs[i].length(); j++) {
        if (strs[i][j] == '0')
          cnt0++;
        if (strs[i][j] == '1')
          cnt1++;
      }
      for (int x = cnt0; x <= m; x++) {
        for (int y = cnt1; y <= n; y++) {
          dp1[x][y] = max(dp2[x][y], 1 + dp2[x - cnt0][y - cnt1]);
        }
      }
      for (int x = 0; x <= m; x++) {
        for (int y = 0; y <= n; y++) {
          dp2[x][y] = dp1[x][y];
        }
      }
      // for (int x = 0; x <= m; x++) {
      //     for (int y = 0; y <= n; y++) {
      //         cout << dp2[x][y] << " ";
      //     }
      //     cout << endl;
      // }
      // cout << "-------" << endl;
    }

    return dp1[m][n];
  }

  // ** dp one 2D array
  int func3(vector<string> &strs, int m, int n) {
    vector<vector<int>> dp1(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < strs.size(); i++) {
      int cnt0 = 0;
      int cnt1 = 0;
      for (int j = 0; j < strs[i].length(); j++) {
        if (strs[i][j] == '0')
          cnt0++;
        if (strs[i][j] == '1')
          cnt1++;
      }
      for (int x = m; x >= cnt0; x--) {
        for (int y = n; y >= cnt1; y--) {
          dp1[x][y] = max(dp1[x][y], 1 + dp1[x - cnt0][y - cnt1]);
        }
      }
    }

    return dp1[m][n];
  }
};

475. Heaters $\star$

476. Number Complement $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  int findComplement(int num) {
    unsigned int mask = ~0;

    while (num & mask) mask <<= 1;

    return ~num ^ mask;
  }
};

477. Total Hamming Distance $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int totalHammingDistance(vector<int>& nums) {
    int ans = 0;
    int mask = 1;

    for (int i = 0; i < 30; ++i) {
      int onesCount = 0;
      for (int num : nums)
        if (num & mask) ++onesCount;
      ans += (nums.size() - onesCount) * onesCount;
      mask = mask << 1;
    }

    return ans;
  }
};

478. Generate Random Point in a Circle $\star\star$

479. Largest Palindrome Product $\star\star\star$

480. Sliding Window Median $\star\star\star$