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
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
func uniquePaths(m int, n int) int {
    // return func1(m-1, n-1, 0, 0);
    // return func2(m, n);
    return func4(m, n);
}

//  1. recursive
func func1(m int, n int, i int, j int) int {
    if i < 0 || m < i || j < 0 || n < j {
        return 0;
    }
    if m == i && n == j {
        return 1;
    }

    return func1(m, n, i+1, j) + func1(m, n, i, j+1);
}

//  2. recursive + memo
func func2(m int, n int) int {
    memo := make([][]int, m);
    for i := 0; i < m; i++ {
        memo[i] = make([]int, n);
        for j := 0; j < n; j++ {
            memo[i][j] = -1;
        }
    }

    return helper2(m-1, n-1, 0, 0, memo);

}
func helper2(m int, n int, i int, j int, memo [][]int) int {
    if i < 0 || m < i || j < 0 || n < j {
        return 0;
    }
    if m == i && n == j {
        return 1;
    }

    if memo[i][j] != -1 {
        return memo[i][j];
    }

    memo[i][j] = helper2(m, n, i+1, j, memo) + helper2(m, n, i, j+1, memo);
    return memo[i][j];
}

//  3. iterative + memo, pass
//  4. iterative + 2N variables
func func4(m int, n int) int {
    memo := make([][]int, 2);
    for i := 0; i < 2; i++ {
        memo[i] = make([]int, n);
        for j := 0; j < n; j++ {
            memo[i][j] = 0;
        }
    }
    memo[(m-1)%2][n-1] = 1;

    for i := m-1; i >= 0; i-- {
        for j := n-1; j >= 0; j-- {
            if i == m-1 && j == n-1 {
                continue;
            }
            memo[i%2][j] = 0;
            if j+1 < n {
                memo[i%2][j] += memo[i%2][j+1];
            }
            if i+1 < m {
                memo[i%2][j] += memo[(i+1)%2][j];
            }
        }
    }
    // for i := 0; i < 2; i++ {
    //  for j := 0; j < n; j++ {
    //      fmt.Println(i, j, memo[i][j]);
    //  }
    // }
    return memo[0][0];
}

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    return func4(obstacleGrid, m, n)
}

//  3. iterative + memo, pass
//  4. iterative + 2N variables
func func4(obstacleGrid [][]int, m int, n int) int {
    memo := make([][]int, 2)
    for i := 0; i < 2; i++ {
        memo[i] = make([]int, n)
        for j := 0; j < n; j++ {
            memo[i][j] = 0
        }
    }

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if i == m-1 && j == n-1 {
                if obstacleGrid[m-1][n-1] == 1 {
                    memo[(m-1)%2][n-1] = 0
                } else {
                    memo[(m-1)%2][n-1] = 1
                }
                continue
            }

            memo[i%2][j] = 0
            if obstacleGrid[i][j] == 1 {
                continue
            }
            if j+1 < n {
                memo[i%2][j] += memo[i%2][j+1]
            }
            if i+1 < m {
                memo[i%2][j] += memo[(i+1)%2][j]
            }
        }
    }
    return memo[0][0]
}

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];
  }
};