Leetcode: 0061-0070题速览

Leetcode: 0061-0070题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

61. 旋转链表

题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

 

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

难度：中等

标签：链表,双指针

解法

方法一：快慢指针 + 链表拼接

我们先判断链表节点数是否小于 $2$，如果是，直接返回 $head$ 即可。

否则，我们先统计链表节点数 $n$，然后将 $k$ 对 $n$ 取模，得到 $k$ 的有效值。

如果 $k$ 的有效值为 $0$，说明链表不需要旋转，直接返回 $head$ 即可。

否则，我们用快慢指针，让快指针先走 $k$ 步，然后快慢指针同时走，直到快指针走到链表尾部，此时慢指针的下一个节点就是新的链表头节点。

最后，我们将链表拼接起来即可。

时间复杂度 $O(n)$，其中 $n$ 是链表节点数，空间复杂度 $O(1)$。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:if head is None or head.next is None:return headcur, n = head, 0while cur:n += 1cur = cur.nextk %= nif k == 0:return headfast = slow = headfor _ in range(k):fast = fast.nextwhile fast.next:fast, slow = fast.next, slow.nextans = slow.nextslow.next = Nonefast.next = headreturn ans

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null) {return head;}ListNode cur = head;int n = 0;for (; cur != null; cur = cur.next) {n++;}k %= n;if (k == 0) {return head;}ListNode fast = head;ListNode slow = head;while (k-- > 0) {fast = fast.next;}while (fast.next != null) {fast = fast.next;slow = slow.next;}ListNode ans = slow.next;slow.next = null;fast.next = head;return ans;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (!head || !head->next) {return head;}ListNode* cur = head;int n = 0;while (cur) {++n;cur = cur->next;}k %= n;if (k == 0) {return head;}ListNode* fast = head;ListNode* slow = head;while (k--) {fast = fast->next;}while (fast->next) {fast = fast->next;slow = slow->next;}ListNode* ans = slow->next;slow->next = nullptr;fast->next = head;return ans;}
};

---

62. 不同路径

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

 

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

 

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

难度：中等

标签：数学,动态规划,组合数学

解法

方法一：动态规划

我们定义 $f[i][j]$ 表示从左上角走到 $(i,j)$ 的路径数量，初始时 $f[0][0]=1$，答案为 $f[m-1][n-1]$。

考虑 $f[i][j]$：

• 如果 $i>0$，那么 $f[i][j]$ 可以从 $f[i-1][j]$ 走一步到达，因此 $f[i][j]=f[i][j]+f[i-1][j]$；
• 如果 $j>0$，那么 $f[i][j]$ 可以从 $f[i][j-1]$ 走一步到达，因此 $f[i][j]=f[i][j]+f[i][j-1]$。

因此，我们有如下的状态转移方程：

$$f[i][j]=\{\begin{array}{ll}1& i=0,j=0\\ f[i-1][j]+f[i][j-1]& \text{otherwise}\end{array}$$

最终的答案即为 $f[m-1][n-1]$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是网格的行数和列数。

我们注意到 $f[i][j]$ 仅与 $f[i-1][j]$ 和 $f[i][j-1]$ 有关，因此我们优化掉第一维空间，仅保留第二维空间，得到时间复杂度 $O(m\times n)$，空间复杂度 $O(n)$ 的实现。

Python3

class Solution:def uniquePaths(self, m: int, n: int) -> int:f = [[0] * n for _ in range(m)]f[0][0] = 1for i in range(m):for j in range(n):if i:f[i][j] += f[i - 1][j]if j:f[i][j] += f[i][j - 1]return f[-1][-1]

Java

class Solution {public int uniquePaths(int m, int n) {var f = new int[m][n];f[0][0] = 1;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (i > 0) {f[i][j] += f[i - 1][j];}if (j > 0) {f[i][j] += f[i][j - 1];}}}return f[m - 1][n - 1];}
}

C++

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> f(m, vector<int>(n));f[0][0] = 1;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (i) {f[i][j] += f[i - 1][j];}if (j) {f[i][j] += f[i][j - 1];}}}return f[m - 1][n - 1];}
};

---

63. 不同路径 II

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

 

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

 

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

难度：中等

标签：数组,动态规划,矩阵

解法

方法一：记忆化搜索

我们设计一个函数 $dfs(i,j)$ 表示从网格 $(i,j)$ 到网格 $(m-1,n-1)$ 的路径数。其中 $m$ 和 $n$ 分别是网格的行数和列数。

函数 $dfs(i,j)$ 的执行过程如下：

• 如果 $i\ge m$ 或者 $j\ge n$，或者 $obstacleGrid[i][j]=1$，则路径数为 $0$；
• 如果 $i=m-1$ 且 $j=n-1$，则路径数为 $1$；
• 否则，路径数为 $dfs(i+1,j)+dfs(i,j+1)$。

为了避免重复计算，我们可以使用记忆化搜索的方法。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是网格的行数和列数。

Python3

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:@cachedef dfs(i: int, j: int) -> int:if i >= m or j >= n or obstacleGrid[i][j]:return 0if i == m - 1 and j == n - 1:return 1return dfs(i + 1, j) + dfs(i, j + 1)m, n = len(obstacleGrid), len(obstacleGrid[0])return dfs(0, 0)

Java

class Solution {private Integer[][] f;private int[][] obstacleGrid;private int m;private int n;public int uniquePathsWithObstacles(int[][] obstacleGrid) {m = obstacleGrid.length;n = obstacleGrid[0].length;this.obstacleGrid = obstacleGrid;f = new Integer[m][n];return dfs(0, 0);}private int dfs(int i, int j) {if (i >= m || j >= n || obstacleGrid[i][j] == 1) {return 0;}if (i == m - 1 && j == n - 1) {return 1;}if (f[i][j] == null) {f[i][j] = dfs(i + 1, j) + dfs(i, j + 1);}return f[i][j];}
}

C++

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();int f[m][n];memset(f, -1, sizeof(f));function<int(int, int)> dfs = [&](int i, int j) {if (i >= m || j >= n || obstacleGrid[i][j]) {return 0;}if (i == m - 1 && j == n - 1) {return 1;}if (f[i][j] == -1) {f[i][j] = dfs(i + 1, j) + dfs(i, j + 1);}return f[i][j];};return dfs(0, 0);}
};

---

64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

 

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

难度：中等

标签：数组,动态规划,矩阵

解法

方法一：动态规划

我们定义 $f[i][j]$ 表示从左上角走到 $(i,j)$ 位置的最小路径和。初始时 $f[0][0]=grid[0][0]$，答案为 $f[m-1][n-1]$。

考虑 $f[i][j]$：

• 如果 $j=0$，那么 $f[i][j]=f[i-1][j]+grid[i][j]$；
• 如果 $i=0$，那么 $f[i][j]=f[i][j-1]+grid[i][j]$；
• 如果 $i>0$ 且 $j>0$，那么 $f[i][j]=\min (f[i-1][j],f[i][j-1])+grid[i][j]$。

最后返回 $f[m-1][n-1]$ 即可。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是网格的行数和列数。

Python3

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])f = [[0] * n for _ in range(m)]f[0][0] = grid[0][0]for i in range(1, m):f[i][0] = f[i - 1][0] + grid[i][0]for j in range(1, n):f[0][j] = f[0][j - 1] + grid[0][j]for i in range(1, m):for j in range(1, n):f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]return f[-1][-1]

Java

class Solution {public int minPathSum(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] f = new int[m][n];f[0][0] = grid[0][0];for (int i = 1; i < m; ++i) {f[i][0] = f[i - 1][0] + grid[i][0];}for (int j = 1; j < n; ++j) {f[0][j] = f[0][j - 1] + grid[0][j];}for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];}}return f[m - 1][n - 1];}
}

C++

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();int f[m][n];f[0][0] = grid[0][0];for (int i = 1; i < m; ++i) {f[i][0] = f[i - 1][0] + grid[i][0];}for (int j = 1; j < n; ++j) {f[0][j] = f[0][j - 1] + grid[0][j];}for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];}}return f[m - 1][n - 1];}
};

---

65. 有效数字

题目描述

给定一个字符串 s ，返回 s 是否是一个 有效数字。

例如，下面的都是有效数字："2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"，而接下来的不是："abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"。

一般的，一个 有效数字 可以用以下的规则之一定义：

1. 一个 整数 后面跟着一个 可选指数。
2. 一个 十进制数 后面跟着一个 可选指数。

一个 整数 定义为一个 可选符号 '-' 或 '+' 后面跟着 数字。

一个 十进制数 定义为一个 可选符号 '-' 或 '+' 后面跟着下述规则：

1. 数字 后跟着一个 小数点 .。
2. 数字 后跟着一个 小数点 . 再跟着 数位。
3. 一个 小数点 . 后跟着 数位。

指数 定义为指数符号 'e' 或 'E'，后面跟着一个 整数。

数字 定义为一个或多个数位。

 

示例 1：

输出：true

示例 2：

输出：false

示例 3：

输出：false

 

提示：

• 1 <= s.length <= 20
• s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

难度：困难

标签：字符串

解法

方法一：分情况讨论

首先，我们判断字符串是否以正负号开头，如果是，将指针 $i$ 向后移动一位。如果此时指针 $i$ 已经到达字符串末尾，说明字符串只有一个正负号，返回 false。

如果当前指针 $i$ 指向的字符是小数点，并且小数点后面没有数字，或者小数点后是一个 e 或 E，返回 false。

接着，我们用两个变量 $dot$ 和 $e$ 分别记录小数点和 e 或 E 的个数。

用指针 $j$ 指向当前字符：

• 如果当前字符是小数点，并且此前出现过小数点或者 e 或 E，返回 false。否则，我们将 $dot$ 加一；
• 如果当前字符是 e 或 E，并且此前出现过 e 或 E，或者当前字符是开头或结尾，返回 false。否则，我们将 $e$ 加一；然后判断下一个字符是否是正负号，如果是，将指针 $j$ 向后移动一位。如果此时指针 $j$ 已经到达字符串末尾，返回 false；
• 如果当前字符不是数字，返回 false。

遍历完字符串后，返回 true。

时间复杂度 $O(n)$，其中 $n$ 为字符串长度。空间复杂度 $O(1)$。

Python3

class Solution:def isNumber(self, s: str) -> bool:n = len(s)i = 0if s[i] in '+-':i += 1if i == n:return Falseif s[i] == '.' and (i + 1 == n or s[i + 1] in 'eE'):return Falsedot = e = 0j = iwhile j < n:if s[j] == '.':if e or dot:return Falsedot += 1elif s[j] in 'eE':if e or j == i or j == n - 1:return Falsee += 1if s[j + 1] in '+-':j += 1if j == n - 1:return Falseelif not s[j].isnumeric():return Falsej += 1return True

Java

class Solution {public boolean isNumber(String s) {int n = s.length();int i = 0;if (s.charAt(i) == '+' || s.charAt(i) == '-') {++i;}if (i == n) {return false;}if (s.charAt(i) == '.'&& (i + 1 == n || s.charAt(i + 1) == 'e' || s.charAt(i + 1) == 'E')) {return false;}int dot = 0, e = 0;for (int j = i; j < n; ++j) {if (s.charAt(j) == '.') {if (e > 0 || dot > 0) {return false;}++dot;} else if (s.charAt(j) == 'e' || s.charAt(j) == 'E') {if (e > 0 || j == i || j == n - 1) {return false;}++e;if (s.charAt(j + 1) == '+' || s.charAt(j + 1) == '-') {if (++j == n - 1) {return false;}}} else if (s.charAt(j) < '0' || s.charAt(j) > '9') {return false;}}return true;}
}

C++

class Solution {
public:bool isNumber(string s) {int n = s.size();int i = 0;if (s[i] == '+' || s[i] == '-') ++i;if (i == n) return false;if (s[i] == '.' && (i + 1 == n || s[i + 1] == 'e' || s[i + 1] == 'E')) return false;int dot = 0, e = 0;for (int j = i; j < n; ++j) {if (s[j] == '.') {if (e || dot) return false;++dot;} else if (s[j] == 'e' || s[j] == 'E') {if (e || j == i || j == n - 1) return false;++e;if (s[j + 1] == '+' || s[j + 1] == '-') {if (++j == n - 1) return false;}} else if (s[j] < '0' || s[j] > '9')return false;}return true;}
};

---

66. 加一

题目描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

难度：简单

标签：数组,数学

解法

方法一：模拟

我们从数组的最后一个元素开始遍历，将当前元素加一，然后对 $10$ 取模，如果取模后的结果不为 $0$，说明当前元素没有进位，直接返回数组即可。否则，当前元素为 $0$，需要进位，继续遍历前一个元素，重复上述操作。如果遍历完数组后，仍然没有返回，说明数组中所有元素都为 $0$，需要在数组的头部插入一个 $1$。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

Python3

class Solution:def plusOne(self, digits: List[int]) -> List[int]:n = len(digits)for i in range(n - 1, -1, -1):digits[i] += 1digits[i] %= 10if digits[i] != 0:return digitsreturn [1] + digits

Java

class Solution {public int[] plusOne(int[] digits) {int n = digits.length;for (int i = n - 1; i >= 0; --i) {++digits[i];digits[i] %= 10;if (digits[i] != 0) {return digits;}}digits = new int[n + 1];digits[0] = 1;return digits;}
}

C++

class Solution {
public:vector<int> plusOne(vector<int>& digits) {for (int i = digits.size() - 1; i >= 0; --i) {++digits[i];digits[i] %= 10;if (digits[i] != 0) return digits;}digits.insert(digits.begin(), 1);return digits;}
};

---

67. 二进制求和

题目描述

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

 

示例 1：

输入:a = “11”, b = “1”
输出：“100”

示例 2：

输入：a = “1010”, b = “1011”
输出：“10101”

 

提示：

• 1 <= a.length, b.length <= 104
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

难度：简单

标签：位运算,数学,字符串,模拟

解法

方法一：模拟

我们用一个变量 $carry$ 记录当前的进位，用两个指针 $i$ 和 $j$ 分别指向 $a$ 和 $b$ 的末尾，从末尾到开头逐位相加即可。

时间复杂度 $O(\max (m,n))$，其中 $m$ 和 $n$ 分别为字符串 $a$ 和 $b$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:def addBinary(self, a: str, b: str) -> str:return bin(int(a, 2) + int(b, 2))[2:]

Java

class Solution {public String addBinary(String a, String b) {var sb = new StringBuilder();int i = a.length() - 1, j = b.length() - 1;for (int carry = 0; i >= 0 || j >= 0 || carry > 0; --i, --j) {carry += (i >= 0 ? a.charAt(i) - '0' : 0) + (j >= 0 ? b.charAt(j) - '0' : 0);sb.append(carry % 2);carry /= 2;}return sb.reverse().toString();}
}

C++

class Solution {
public:string addBinary(string a, string b) {string ans;int i = a.size() - 1, j = b.size() - 1;for (int carry = 0; i >= 0 || j >= 0 || carry; --i, --j) {carry += (i >= 0 ? a[i] - '0' : 0) + (j >= 0 ? b[j] - '0' : 0);ans.push_back((carry % 2) + '0');carry /= 2;}reverse(ans.begin(), ans.end());return ans;}
};

---

68. 文本左右对齐

题目描述

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

 

示例 1:

输入: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
输出:
[
   “This    is    an”,
   “example  of text”,
   "justification.  "
]

示例 2:

输入:words = [“What”,“must”,“be”,“acknowledgment”,“shall”,“be”], maxWidth = 16
输出:
[
  “What   must   be”,
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 “shall be”,
  因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:words = [“Science”,“is”,“what”,“we”,“understand”,“well”,“enough”,“to”,“explain”,“to”,“a”,“computer.”,“Art”,“is”,“everything”,“else”,“we”,“do”]，maxWidth = 20
输出:
[
  “Science  is  what we”,
“understand      well”,
  “enough to explain to”,
  “a  computer.  Art is”,
  “everything  else  we”,
  "do                  "
]

 

提示:

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] 由小写英文字母和符号组成
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

难度：困难

标签：数组,字符串,模拟

解法

方法一：模拟

根据题意模拟即可，注意，如果是最后一行，或者这一行只有一个单词，那么要左对齐，否则要均匀分配空格。

时间复杂度 $O(L)$，空间复杂度 $O(L)$。其中 $L$ 为所有单词的长度之和。

Python3

class Solution:def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:ans = []i, n = 0, len(words)while i < n:t = []cnt = len(words[i])t.append(words[i])i += 1while i < n and cnt + 1 + len(words[i]) <= maxWidth:cnt += 1 + len(words[i])t.append(words[i])i += 1if i == n or len(t) == 1:left = ' '.join(t)right = ' ' * (maxWidth - len(left))ans.append(left + right)continuespace_width = maxWidth - (cnt - len(t) + 1)w, m = divmod(space_width, len(t) - 1)row = []for j, s in enumerate(t[:-1]):row.append(s)row.append(' ' * (w + (1 if j < m else 0)))row.append(t[-1])ans.append(''.join(row))return ans

Java

class Solution {public List<String> fullJustify(String[] words, int maxWidth) {List<String> ans = new ArrayList<>();for (int i = 0, n = words.length; i < n;) {List<String> t = new ArrayList<>();t.add(words[i]);int cnt = words[i].length();++i;while (i < n && cnt + 1 + words[i].length() <= maxWidth) {cnt += 1 + words[i].length();t.add(words[i++]);}if (i == n || t.size() == 1) {String left = String.join(" ", t);String right = " ".repeat(maxWidth - left.length());ans.add(left + right);continue;}int spaceWidth = maxWidth - (cnt - t.size() + 1);int w = spaceWidth / (t.size() - 1);int m = spaceWidth % (t.size() - 1);StringBuilder row = new StringBuilder();for (int j = 0; j < t.size() - 1; ++j) {row.append(t.get(j));row.append(" ".repeat(w + (j < m ? 1 : 0)));}row.append(t.get(t.size() - 1));ans.add(row.toString());}return ans;}
}

C++

class Solution {
public:vector<string> fullJustify(vector<string>& words, int maxWidth) {vector<string> ans;for (int i = 0, n = words.size(); i < n;) {vector<string> t = {words[i]};int cnt = words[i].size();++i;while (i < n && cnt + 1 + words[i].size() <= maxWidth) {cnt += 1 + words[i].size();t.emplace_back(words[i++]);}if (i == n || t.size() == 1) {string left = t[0];for (int j = 1; j < t.size(); ++j) {left += " " + t[j];}string right = string(maxWidth - left.size(), ' ');ans.emplace_back(left + right);continue;}int spaceWidth = maxWidth - (cnt - t.size() + 1);int w = spaceWidth / (t.size() - 1);int m = spaceWidth % (t.size() - 1);string row;for (int j = 0; j < t.size() - 1; ++j) {row += t[j] + string(w + (j < m ? 1 : 0), ' ');}row += t.back();ans.emplace_back(row);}return ans;}
};

---

69. x 的平方根

题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

 

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

 

提示：

• 0 <= x <= 231 - 1

难度：简单

标签：数学,二分查找

解法

方法一：二分查找

我们定义二分查找的左边界 $l=0$，右边界 $r=x$，然后在 $[l,r]$ 范围内查找平方根。

在每一步查找中，我们找出中间值 $mid=(l+r+1)/2$，如果 $mid>x/mid$，说明平方根在 $[l,mid-1]$ 范围内，我们令 $r=mid-1$；否则说明平方根在 $[mid,r]$ 范围内，我们令 $l=mid$。

查找结束后，返回 $l$ 即可。

时间复杂度 $O(\log x)$，空间复杂度 $O(1)$。

Python3

class Solution:def mySqrt(self, x: int) -> int:l, r = 0, xwhile l < r:mid = (l + r + 1) >> 1if mid > x // mid:r = mid - 1else:l = midreturn l

Java

class Solution {public int mySqrt(int x) {int l = 0, r = x;while (l < r) {int mid = (l + r + 1) >>> 1;if (mid > x / mid) {r = mid - 1;} else {l = mid;}}return l;}
}

C++

class Solution {
public:int mySqrt(int x) {int l = 0, r = x;while (l < r) {int mid = (l + r + 1ll) >> 1;if (mid > x / mid) {r = mid - 1;} else {l = mid;}}return l;}
};

---

70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

 

提示：

• 1 <= n <= 45

难度：简单

标签：记忆化搜索,数学,动态规划

解法

方法一：递推

我们定义 $f[i]$ 表示爬到第 $i$ 阶楼梯的方法数，那么 $f[i]$ 可以由 $f[i-1]$ 和 $f[i-2]$ 转移而来，即：

$$f[i]=f[i-1]+f[i-2]$$

初始条件为 $f[0]=1$，$f[1]=1$，即爬到第 0 阶楼梯的方法数为 1，爬到第 1 阶楼梯的方法数也为 1。

答案即为 $f[n]$。

由于 $f[i]$ 只与 $f[i-1]$ 和 $f[i-2]$ 有关，因此我们可以只用两个变量 $a$ 和 $b$ 来维护当前的方法数，空间复杂度降低为 $O(1)$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

Python3

class Solution:def climbStairs(self, n: int) -> int:a, b = 0, 1for _ in range(n):a, b = b, a + breturn b

Java

class Solution {public int climbStairs(int n) {int a = 0, b = 1;for (int i = 0; i < n; ++i) {int c = a + b;a = b;b = c;}return b;}
}

C++

class Solution {
public:int climbStairs(int n) {int a = 0, b = 1;for (int i = 0; i < n; ++i) {int c = a + b;a = b;b = c;}return b;}
};

---