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$

 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
func findMaxForm(strs []string, m int, n int) int {
    // return func1(strs, m, n);
    return func2(strs, m, n);
}

// O(len*m*n) time, 2*O(m*n) space
func func1(strs []string, m int, n int) int {
    dp1 := make([][]int, m+1);
    dp2 := make([][]int, m+1);
    for i := 0; i < m+1; i++ {
        dp1[i] = make([]int, n+1);
        dp2[i] = make([]int, n+1);
    }

    for i := 1; i <= len(strs); i++ {
        cnt0, cnt1 := count01(strs[i-1]);
        for j0 := cnt0; j0 <= m; j0++ {
            for j1 := cnt1; j1 <= n; j1++ {
                dp2[j0][j1] = max(dp1[j0][j1], 1 + dp1[j0-cnt0][j1-cnt1]);
            }
        }
        for j0 := 0; j0 <= m; j0++ {
            for j1 := 0; j1 <= n; j1++ {
                dp1[j0][j1] = dp2[j0][j1];
            }
        }
    }
    return dp2[m][n];
}

// O(len*m*n) time, O(m*n) space
func func2(strs []string, m int, n int) int {
    dp1 := make([][]int, m+1);
    for i := 0; i < m+1; i++ {
        dp1[i] = make([]int, n+1);
    }

    for i := 1; i <= len(strs); i++ {
        cnt0, cnt1 := count01(strs[i-1]);
        for j0 := m; j0 >= cnt0; j0-- {
            for j1 := n; j1 >= cnt1; j1-- {
                dp1[j0][j1] = max(dp1[j0][j1], 1 + dp1[j0-cnt0][j1-cnt1]);
            }
        }
    }
    return dp1[m][n];
}

func count01(str string) (int, int) {
    cnt0 := 0;
    cnt1 := 0;
    for _, s := range str {
        if s == '0' {
            cnt0++;
        }
        if s == '1' {
            cnt1++;
        }
    }
    return cnt0, cnt1;
}
func max(a int, b int) int {
    if a > b {
        return a;
    }
    return b;
}

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$