0671-0680

671. Second Minimum Node In a Binary Tree $\star$

672. Bulb Switcher II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  int flipLights(int n, int m) {
    n = min(n, 3);

    if (m == 0) return 1;
    if (m == 1) return n == 1 ? 2 : n == 2 ? 3 : 4;
    if (m == 2) return n == 1 ? 2 : n == 2 ? 4 : 7;

    return n == 1 ? 2 : n == 2 ? 4 : 8;
  }
};

673. Number of Longest Increasing Subsequence $\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
77
78
79
80
81
func findNumberOfLIS(nums []int) int {
    // return func1(nums);
    return func2(nums);
}

// iterative, from right to left
func func1(nums []int) int {
    n := len(nums);
    length := make([]int, n);
    count := make([]int, n);

    for i := 0; i < n; i++ {
        length[i] = 1;
        count[i] = 1;
    }

    maxLen := 1;
    for i := n-1; i >= 0; i-- {
        for j := i+1; j < n; j++ {
            if nums[i] < nums[j] {
                if length[j]+1 > length[i] {
                    length[i] = length[j]+1;
                    count[i] = count[j];
                } else if length[j]+1 == length[i] {
                    count[i] += count[j];
                }
            }
        }
        // fmt.Printf("i=%d, length=%d, count=%d\n", i, length[i], count[i]);
        if length[i] > maxLen {
            maxLen = length[i];
        }
    }

    ret := 0;
    for i := 0; i < n; i++ {
        if length[i] == maxLen {
            ret += count[i];
        }
    }

    return ret;
}

// iterative, from left to right
func func2(nums []int) int {
    n := len(nums);
    length := make([]int, n);
    count := make([]int, n);

    for i := 0; i < n; i++ {
        length[i] = 1;
        count[i] = 1;
    }

    maxLen := 1;
    for i := 0; i < n; i++ {
        for j := i-1; j >= 0; j-- {
            if nums[i] > nums[j] {
                if length[j]+1 > length[i] {
                    length[i] = length[j]+1;
                    count[i] = count[j]; 
                } else if length[j]+1 == length[i] {
                    count[i] += count[j];
                }
            }
        }
        if length[i] > maxLen {
            maxLen = length[i];
        }
    }

    ret := 0;
    for i := 0; i < n; i++ {
        if length[i] == maxLen {
            ret += count[i];
        }
    }

    return ret;
}

674. Longest Continuous Increasing Subsequence $\star$

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

    for (int i = 0, j = 0; i < nums.size(); ++i) {
      if (i > 0 && nums[i] <= nums[i - 1]) j = i;
      ans = max(ans, i - j + 1);
    }

    return ans;
  }
};

675. Cut Off Trees for Golf Event $\star\star\star$

676. Implement Magic Dictionary $\star\star$

677. Map Sum Pairs $\star\star$

678. Valid Parenthesis String $\star\star$

679. 24 Game $\star\star\star$

680. Valid Palindrome II $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool validPalindrome(string s) {
    const int n = s.length();

    for (int i = 0; i < n / 2; ++i)
      if (s[i] != s[n - 1 - i])
        return validPalindrome(s, i + 1, n - 1 - i) ||
               validPalindrome(s, i, n - 2 - i);

    return true;
  }

 private:
  bool validPalindrome(string& s, int l, int r) {
    for (int i = l; i <= l + (r - l) / 2; ++i)
      if (s[i] != s[r - i + l]) return false;

    return true;
  }
};