0411-0420

411. Minimum Unique Word Abbreviation $\star\star\star$

412. Fizz Buzz $\star$

413. Arithmetic Slices $\star\star$

414. Third Maximum Number $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int thirdMax(vector<int>& nums) {
    priority_queue<int, vector<int>, compare> pq;
    unordered_set<int> set;

    for (int num : nums)
      if (!set.count(num)) {
        set.insert(num);
        pq.push(num);
        if (pq.size() > 3) pq.pop();
      }

    if (pq.size() == 2) pq.pop();

    return pq.top();
  }

 private:
  struct compare {
    bool operator()(const int a, const int b) { return a > b; }
  };
};

415. Add Strings $\star$

416. Partition Equal Subset Sum $\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
68
69
70
71
72
73
74
75
76
func canPartition(nums []int) bool {
    // return func1(nums);
    return func2(nums);
}
/* pack[i][v] means:
 * 1. The i-th item, weight=nums[i-1]
 * 2. The v capacity package
 */
func func1(nums []int) bool {
    sum := 0;
    for i := 0; i < len(nums); i++ {
        sum += nums[i];
    }
    if sum % 2 != 0 {
        return false;
    }

    vol := sum / 2;
    N := len(nums);

    pack := make([][]bool, N + 1);
    for i := 0; i <= N; i++ {
        pack[i] = make([]bool, vol + 1);
    }
    pack[0][0] = true;

    for i := 1; i <= N; i++ {
        curr_v := nums[i-1];
        for v := vol; v >= 0; v-- {
            if v >= curr_v {
                pack[i][v] = pack[i-1][v] || pack[i-1][v-curr_v];
            } else {
                pack[i][v] = pack[i-1][v];
            }
        }
    }

    for i := 0; i <= N; i++ {
        if pack[i][vol] == true {
            return true
        }
    }
    return false
}

func func2(nums []int) bool {
    sum := 0;
    for i := 0; i < len(nums); i++ {
        sum += nums[i];
    }
    if sum % 2 != 0 {
        return false;
    }

    vol := sum / 2;
    N := len(nums);

    pack := make([]bool, vol + 1);
    pack[0] = true;

    for i := 1; i <= N; i++ {
        curr_v := nums[i-1];
        for v := vol; v >= 0; v-- {
            if v >= curr_v {
                pack[v] = pack[v] || pack[v-curr_v];
            } else {
                pack[v] = pack[v];
            }
        }
        if pack[vol] == true {
            return true;
        }
    }

    return false
}

417. Pacific Atlantic Water Flow $\star\star$

418. Sentence Screen Fitting $\star\star$

419. Battleships in a Board $\star\star$

420. Strong Password Checker $\star\star\star$