0031-0040

31. Next Permutation $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    int i;
    for (i = nums.size() - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1]) break;

    if (i >= 0) {
      int j;
      for (j = nums.size() - 1; j >= 0; --j)
        if (nums[j] > nums[i]) break;
      swap(nums[i], nums[j]);
    }

    reverse(nums, i + 1, nums.size() - 1);
  }

 private:
  void reverse(vector<int>& nums, int l, int r) {
    while (l < r) swap(nums[l++], nums[r--]);
  }
};

32. Longest Valid Parentheses $\star\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
class Solution {
 public:
  int longestValidParentheses(string s) {
    int ans = 0;
    int l = 0;
    int r = 0;

    for (int i = 0; i < s.length(); ++i) {
      if (s[i] == '(')
        ++l;
      else
        ++r;
      if (l == r)
        ans = max(ans, 2 * r);
      else if (r > l) {
        l = 0;
        r = 0;
      }
    }

    l = 0;
    r = 0;

    for (int i = s.length() - 1; i >= 0; --i) {
      if (s[i] == '(')
        ++l;
      else
        ++r;
      if (l == r)
        ans = max(ans, 2 * l);
      else if (l > r) {
        l = 0;
        r = 0;
      }
    }

    return ans;
  }
};

33. Search in Rotated Sorted Array $\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
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size() - 1;

    while (l <= r) {
      int m = l + (r - l) / 2;
      if (nums[m] == target) return m;
      if (nums[l] <= nums[m]) {
        if (nums[l] <= target && target < nums[m])
          r = m - 1;
        else
          l = m + 1;
      } else {
        if (nums[m] < target && target <= nums[r])
          l = m + 1;
        else
          r = m - 1;
      }
    }

    return -1;
  }
};

34. Find First and Last Position of Element in Sorted Array $\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
class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    int leftIndex = find(nums, target, true);

    if (leftIndex == nums.size() || nums[leftIndex] != target) return {-1, -1};

    return {leftIndex, find(nums, target, false) - 1};
  }

 private:
  int find(vector<int>& nums, int target, bool isLeft) {
    int l = 0;
    int r = nums.size();

    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] > target || (isLeft && nums[m] == target))
        r = m;
      else
        l = m + 1;
    }

    return l;
  }
};

35. Search Insert Position $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int searchInsert(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size();

    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] == target) return m;
      if (nums[m] < target)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }
};

36. Valid Sudoku $\star\star$

37. Sudoku Solver $\star\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
class Solution {
 public:
  void solveSudoku(vector<vector<char>>& board) { dfs(0, board); }

 private:
  bool dfs(int s, vector<vector<char>>& board) {
    if (s == 81) return true;

    int i = s / 9;
    int j = s % 9;

    if (board[i][j] != '.') return dfs(s + 1, board);

    for (char c = '1'; c <= '9'; ++c)
      if (isValid(i, j, c, board)) {
        board[i][j] = c;
        if (dfs(s + 1, board)) return true;
        board[i][j] = '.';
      }

    return false;
  }

  bool isValid(int row, int col, char c, vector<vector<char>>& board) {
    for (int i = 0; i < 9; ++i) {
      if (board[i][col] != '.' && board[i][col] == c) return false;
      if (board[row][i] != '.' && board[row][i] == c) return false;
      if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&
          board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
        return false;
    }
    return true;
  }
};

38. Count and Say $\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 Solution {
 public:
  string countAndSay(int n) {
    unordered_map<int, string> map = {
        {1, "1"}, {2, "11"}, {3, "21"}, {4, "1211"}, {5, "111221"}};

    if (n <= 5) return map[n];

    for (int i = 6; i < n + 1; ++i) {
      string s;
      int j = 0;
      while (j <= map[i - 1].size() - 2) {
        int count = 1;
        while (j <= map[i - 1].size() - 2 &&
               map[i - 1][j] == map[i - 1][j + 1]) {
          ++count;
          ++j;
        }
        s += to_string(count) + map[i - 1][j];
        ++j;
      }
      if (j == map[i - 1].size() - 1) s += to_string(1) + map[i - 1][j];
      map[i] = s;
    }

    return map[n];
  }
};

39. Combination 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
class Solution {
 public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    vector<int> path;

    sort(candidates.begin(), candidates.end());
    dfs(candidates, target, 0, path, ans);

    return ans;
  }

 private:
  void dfs(vector<int>& candidates, int target, int s, vector<int>& path,
           vector<vector<int>>& ans) {
    if (target < 0) return;
    if (target == 0) {
      ans.push_back(path);
      return;
    }

    for (int i = s; i < candidates.size(); ++i) {
      path.push_back(candidates[i]);
      dfs(candidates, target - candidates[i], i, path, ans);
      path.pop_back();
    }
  }
};

40. Combination Sum II $\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
class Solution {
 public:
  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    vector<int> path;

    sort(candidates.begin(), candidates.end());
    dfs(candidates, target, 0, path, ans);

    return ans;
  }

 private:
  void dfs(vector<int>& candidates, int target, int s, vector<int>& path,
           vector<vector<int>>& ans) {
    if (target < 0) return;
    if (target == 0) {
      ans.push_back(path);
      return;
    }

    for (int i = s; i < candidates.size(); ++i) {
      if (i > s && candidates[i] == candidates[i - 1]) continue;
      path.push_back(candidates[i]);
      dfs(candidates, target - candidates[i], i + 1, path, ans);
      path.pop_back();
    }
  }
};