0071-0080

71. Simplify Path $\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:
  string simplifyPath(string path) {
    string ans;
    string temp;
    stringstream ss(path);
    vector<string> stack;

    while (getline(ss, temp, '/')) {
      if (temp == "" || temp == ".") continue;
      if (temp == "..") {
        if (!stack.empty()) stack.pop_back();
      } else {
        stack.push_back(temp);
      }
    }

    for (auto str : stack) ans += "/" + str;

    return ans.empty() ? "/" : ans;
  }
};

72. Edit Distance $\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
class Solution {
 public:
  int minDistance(string word1, string word2) {
    const int m = word1.length();
    const int n = word2.length();

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

    for (int i = 0; i <= m; ++i)
      for (int j = 0; j <= n; ++j) {
        if (i == 0)
          dp[i][j] = j;
        else if (j == 0)
          dp[i][j] = i;
        else
          dp[i][j] =
              min(dp[i - 1][j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 1),
                  min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
      }

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

73. Set Matrix 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
class Solution {
 public:
  void setZeroes(vector<vector<int>>& matrix) {
    const int m = matrix.size();
    const int n = matrix[0].size();

    bool isFirstRow = false;
    bool isFirstCol = false;

    for (int j = 0; j < n; ++j)
      if (matrix[0][j] == 0) isFirstRow = true;

    for (int i = 0; i < m; ++i)
      if (matrix[i][0] == 0) isFirstCol = true;

    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j)
        if (matrix[i][j] == 0) {
          matrix[i][0] = 0;
          matrix[0][j] = 0;
        }

    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j)
        if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;

    if (isFirstRow)
      for (int j = 0; j < n; ++j) matrix[0][j] = 0;

    if (isFirstCol)
      for (int i = 0; i < m; ++i) matrix[i][0] = 0;
  }
};

74. Search a 2D Matrix $\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:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty()) return false;

    const int m = matrix.size();
    const int n = matrix[0].size();

    int l = 0;
    int r = m * n;

    while (l < r) {
      int mid = l + (r - l) / 2;
      int i = mid / n;
      int j = mid % n;
      if (matrix[i][j] == target) return true;
      if (matrix[i][j] < target)
        l = mid + 1;
      else
        r = mid;
    }

    return false;
  }
};

75. Sort Colors $\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:
  void sortColors(vector<int>& nums) {
    int zero = -1;
    int one = -1;
    int two = -1;

    for (int num : nums) {
      if (num == 0) {
        nums[++two] = 2;
        nums[++one] = 1;
        nums[++zero] = 0;
      } else if (num == 1) {
        nums[++two] = 2;
        nums[++one] = 1;
      } else {
        nums[++two] = 2;
      }
    }
  }
};

76. Minimum Window Substring $\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
class Solution {
 public:
  string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";

    unordered_map<char, int> map;
    for (char c : t) ++map[c];

    int l = 0;
    int r = 0;
    int bestLeft = 0;
    int bestRight = 0;
    int required = map.size();
    int windowLength = s.length() + 1;

    for (int r = 0; r < s.length(); ++r) {
      if (map.count(s[r]))
        if (--map[s[r]] == 0) --required;

      while (required == 0 && l <= r) {
        if (r - l + 1 < windowLength) {
          windowLength = r - l + 1;
          bestLeft = l;
          bestRight = r;
        }

        if (map.count(s[l]))
          if (++map[s[l]] > 0) ++required;

        ++l;
      }
    }

    return windowLength == s.length() + 1 ? ""
                                          : s.substr(bestLeft, windowLength);
  }
};

77. Combinations $\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:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> path;

    dfs(n, k, 1, path, ans);

    return ans;
  }

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

    for (int i = s; i <= n; ++i) {
      path.push_back(i);
      dfs(n, k - 1, i + 1, path, ans);
      path.pop_back();
    }
  }
};

78. Subsets $\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:
  vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> path;

    dfs(nums, 0, path, ans);

    return ans;
  }

 private:
  void dfs(vector<int>& nums, int s, vector<int>& path,
           vector<vector<int>>& ans) {
    ans.push_back(path);
    if (s == nums.size()) return;

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

79. Word Search $\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:
  bool exist(vector<vector<char>>& board, string word) {
    if (board.empty()) return false;

    for (int i = 0; i < board.size(); ++i)
      for (int j = 0; j < board[0].size(); ++j)
        if (dfs(board, word, i, j, 0)) return true;

    return false;
  }

 private:
  bool dfs(vector<vector<char>>& board, string& word, int i, int j, int pos) {
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
        board[i][j] != word[pos] || board[i][j] == '*')
      return false;
    if (pos == word.length() - 1) return true;

    char c = board[i][j];
    board[i][j] = '*';
    bool flag = dfs(board, word, i + 1, j, pos + 1) ||
                dfs(board, word, i - 1, j, pos + 1) ||
                dfs(board, word, i, j + 1, pos + 1) ||
                dfs(board, word, i, j - 1, pos + 1);
    board[i][j] = c;

    return flag;
  }
};

80. Remove Duplicates from Sorted Array II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  int removeDuplicates(vector<int>& nums) {
    int i = 0;
    for (int num : nums)
      if (i < 2 || num != nums[i - 2]) nums[i++] = num;

    return i;
  }
};