0041-0050

41. First Missing Positive $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int firstMissingPositive(vector<int>& nums) {
    if (nums.empty()) return 1;

    const int n = nums.size();

    for (int i = 0; i < nums.size(); ++i)
      while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
        swap(nums[i], nums[nums[i] - 1]);

    for (int i = 0; i < n; ++i)
      if (nums[i] != i + 1) return i + 1;

    return n + 1;
  }
};

42. Trapping Rain Water $\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
class Solution {
 public:
  int trap(vector<int>& height) {
    int ans = 0;
    int l = 0;
    int r = height.size() - 1;
    int maxLeft = 0;
    int maxRight = 0;

    while (l < r) {
      if (height[l] < height[r]) {
        maxLeft = max(maxLeft, height[l]);
        ans += maxLeft - height[l];
        ++l;
      } else {
        maxRight = max(maxRight, height[r]);
        ans += maxRight - height[r];
        --r;
      }
    }

    return ans;
  }
};

43. Multiply Strings $\star\star$

44. Wildcard Matching $\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
class Solution {
 public:
  bool isMatch(string s, string p) {
    const int m = s.length();
    const int n = p.length();

    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));

    for (int i = 0; i <= m; ++i)
      for (int j = 0; j <= n; ++j) {
        if (i == 0 && j == 0)
          dp[i][j] = true;
        else if (i == 0)
          dp[i][j] = dp[i][j - 1] && p[j - 1] == '*';
        else if (j == 0)
          dp[i][j] = dp[i - 1][j] && s[i - 1] == '*';
        else
          dp[i][j] =
              (dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1]) &&
                  (s[i - 1] == '*' || p[j - 1] == '*') ||
              (dp[i - 1][j - 1]) &&
                  (s[i - 1] == '?' || p[j - 1] == '?' || s[i - 1] == p[j - 1]);
      }

    return dp[m][n];
  }
};

45. Jump Game II $\star\star\star$

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

    for (int i = 0; i + 1 < nums.size(); ++i) {
      farthest = max(farthest, i + nums[i]);
      if (i == end) {
        ++ans;
        end = farthest;
      }
    }

    return ans;
  }
};

46. Permutations $\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
class Solution {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> used(nums.size(), false);

    dfs(nums, nums.size(), used, path, ans);

    return ans;
  }

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

    for (int i = 0; i < nums.size(); ++i) {
      if (used[i]) continue;
      used[i] = true;
      path.push_back(nums[i]);
      dfs(nums, target - 1, used, path, ans);
      path.pop_back();
      used[i] = false;
    }
  }
};

47. Permutations 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
30
31
class Solution {
 public:
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> used(nums.size(), false);

    sort(nums.begin(), nums.end());
    dfs(nums, nums.size(), used, path, ans);

    return ans;
  }

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

    for (int i = 0; i < nums.size(); ++i) {
      if (used[i] || i > 0 && used[i - 1] && nums[i] == nums[i - 1]) continue;
      used[i] = true;
      path.push_back(nums[i]);
      dfs(nums, target - 1, used, path, ans);
      path.pop_back();
      used[i] = false;
    }
  }
};

48. Rotate Image $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  void rotate(vector<vector<int>>& matrix) {
    for (int min = 0; min < matrix.size() / 2; ++min) {
      int max = matrix.size() - min - 1;
      for (int i = min; i < max; ++i) {
        int offset = i - min;
        int top = matrix[min][i];
        matrix[min][i] = matrix[max - offset][min];
        matrix[max - offset][min] = matrix[max][max - offset];
        matrix[max][max - offset] = matrix[i][max];
        matrix[i][max] = top;
      }
    }
  }
};

49. Group Anagrams $\star\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:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> ans;
    unordered_map<string, vector<string>> map;

    for (string& str : strs) {
      string s = str;
      sort(s.begin(), s.end());
      map[s].push_back(str);
    }

    for (auto& [key, value] : map) {
      vector<string> s = value;
      sort(s.begin(), s.end());
      ans.push_back(s);
    }

    return ans;
  }
};

50. Pow(x, n) $\star\star$

1
2
3
4
5
6
7
8
9
class Solution {
 public:
  double myPow(double x, long n) {
    if (n == 0) return 1;
    if (n < 0) return 1 / myPow(x, -n);
    if (n % 2) return x * myPow(x, n - 1);
    return myPow(x * x, n / 2);
  }
};