0061-0070

61. Rotate List $\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:
  ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;

    int length = 0;
    for (auto curr = head; curr; curr = curr->next) ++length;

    k %= length;
    if (k == 0) return head;

    auto slow = head;
    auto fast = head;

    while (k--) fast = fast->next;

    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next;
    }

    auto ans = slow->next;
    slow->next = NULL;
    fast->next = head;

    return ans;
  }
};

62. Unique Paths $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);

    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j) dp[j] += dp[j - 1];

    return dp[n - 1];
  }
};

63. Unique Paths II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    const int m = obstacleGrid.size();
    const int n = obstacleGrid[0].size();

    vector<long> dp(n, 0);
    dp[0] = 1;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        if (obstacleGrid[i][j])
          dp[j] = 0;
        else if (j > 0)
          dp[j] += dp[j - 1];
      }

    return dp[n - 1];
  }
};

64. Minimum Path Sum $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int minPathSum(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();

    for (int i = 1; i < m; ++i) grid[i][0] += grid[i - 1][0];
    for (int j = 1; j < n; ++j) grid[0][j] += grid[0][j - 1];
    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j)
        grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);

    return grid[m - 1][n - 1];
  }
};

65. Valid Number $\star\star\star$

66. Plus One $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  vector<int> plusOne(vector<int>& digits) {
    const int n = digits.size();

    for (int i = n - 1; i >= 0; --i) {
      if (digits[i] < 9) {
        ++digits[i];
        return digits;
      }

      digits[i] = 0;
    }

    vector<int> ans(n + 1);
    ans[0] = 1;

    return ans;
  }
};

67. Add Binary $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  string addBinary(string a, string b) {
    string ans;
    int carry = 0;
    int i = a.length() - 1;
    int j = b.length() - 1;

    while (i >= 0 || j >= 0 || carry == 1) {
      if (i >= 0) carry += a[i--] - '0';
      if (j >= 0) carry += b[j--] - '0';
      ans = char(carry % 2 + '0') + ans;
      carry >>= 1;
    }

    return ans;
  }
};

68. Text Justification $\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
40
class Solution {
 public:
  vector<string> fullJustify(vector<string>& words, int maxWidth) {
    vector<string> ans;
    vector<string> curr;
    int numOfLetters = 0;

    for (string& word : words) {
      if (numOfLetters + (int)curr.size() + (int)word.length() > maxWidth) {
        for (int i = 0; i < maxWidth - numOfLetters; ++i) {
          curr.size() - 1 == 0 ? curr[0].append(" ")
                               : curr[i % (curr.size() - 1)].append(" ");
        }
        ans.push_back(join(curr, ""));
        curr.clear();
        numOfLetters = 0;
      }
      curr.push_back(word);
      numOfLetters += word.length();
    }
    ans.push_back(ljust(join(curr, " "), maxWidth));

    return ans;
  }

 private:
  string join(vector<string>& v, string c) {
    string s;
    for (auto p = v.begin(); p != v.end(); ++p) {
      s += *p;
      if (p != v.end() - 1) s += c;
    }
    return s;
  }

  string ljust(string s, int width) {
    for (int i = 0; i < s.length() - width; ++i) s += " ";
    return s;
  }
};

69. Sqrt(x) $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int mySqrt(int x) {
    unsigned l = 1;
    unsigned r = x + 1u;

    while (l < r) {
      unsigned m = (l + r) >> 1;
      if (m > x / m)
        r = m;
      else
        l = m + 1;
    }

    return l - 1;
  }
};

70. Climbing Stairs $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int climbStairs(int n) {
    if (n == 1) return 1;

    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2];

    return dp[n];
  }
};