Leetcode: 0061-0070题速览
Leetcode: 0061-0070题速览
本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer(第 2 版)》、《程序员面试金典(第 6 版)》题解
遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证
研一在读备战就业,制此集合便于空闲时间浏览,有任何疑惑问题欢迎讨论,共同进步
目录
- Leetcode: 0061-0070题速览
- [61. 旋转链表](https://leetcode.cn/problems/rotate-list)
- 题目描述
- 解法
- 方法一:快慢指针 + 链表拼接
- Python3
- Java
- C++
- [62. 不同路径](https://leetcode.cn/problems/unique-paths)
- 题目描述
- 解法
- 方法一:动态规划
- Python3
- Java
- C++
- [63. 不同路径 II](https://leetcode.cn/problems/unique-paths-ii)
- 题目描述
- 解法
- 方法一:记忆化搜索
- Python3
- Java
- C++
- [64. 最小路径和](https://leetcode.cn/problems/minimum-path-sum)
- 题目描述
- 解法
- 方法一:动态规划
- Python3
- Java
- C++
- [65. 有效数字](https://leetcode.cn/problems/valid-number)
- 题目描述
- 解法
- 方法一:分情况讨论
- Python3
- Java
- C++
- [66. 加一](https://leetcode.cn/problems/plus-one)
- 题目描述
- 解法
- 方法一:模拟
- Python3
- Java
- C++
- [67. 二进制求和](https://leetcode.cn/problems/add-binary)
- 题目描述
- 解法
- 方法一:模拟
- Python3
- Java
- C++
- [68. 文本左右对齐](https://leetcode.cn/problems/text-justification)
- 题目描述
- 解法
- 方法一:模拟
- Python3
- Java
- C++
- [69. x 的平方根](https://leetcode.cn/problems/sqrtx)
- 题目描述
- 解法
- 方法一:二分查找
- Python3
- Java
- C++
- [70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs)
- 题目描述
- 解法
- 方法一:递推
- Python3
- Java
- C++
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 2 2,如果是,直接返回 h e a d head head 即可。
否则,我们先统计链表节点数 n n n,然后将 k k k 对 n n n 取模,得到 k k k 的有效值。
如果 k k k 的有效值为 0 0 0,说明链表不需要旋转,直接返回 h e a d head head 即可。
否则,我们用快慢指针,让快指针先走 k k k 步,然后快慢指针同时走,直到快指针走到链表尾部,此时慢指针的下一个节点就是新的链表头节点。
最后,我们将链表拼接起来即可。
时间复杂度 O ( n ) O(n) O(n),其中 n n n 是链表节点数,空间复杂度 O ( 1 ) O(1) 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 head
cur, n = head, 0
while cur:
n += 1
cur = cur.next
k %= n
if k == 0:
return head
fast = slow = head
for _ in range(k):
fast = fast.next
while fast.next:
fast, slow = fast.next, slow.next
ans = slow.next
slow.next = None
fast.next = head
return 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 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3:
输入:m = 7, n = 3
输出:28
示例 4:
输入:m = 3, n = 3
输出:6
提示:
1 <= m, n <= 100
- 题目数据保证答案小于等于
2 * 109
难度:中等
标签:数学,动态规划,组合数学
解法
方法一:动态规划
我们定义 f [ i ] [ j ] f[i][j] f[i][j] 表示从左上角走到 ( i , j ) (i, j) (i,j) 的路径数量,初始时 f [ 0 ] [ 0 ] = 1 f[0][0] = 1 f[0][0]=1,答案为 f [ m − 1 ] [ n − 1 ] f[m - 1][n - 1] f[m−1][n−1]。
考虑 f [ i ] [ j ] f[i][j] f[i][j]:
- 如果 i > 0 i \gt 0 i>0,那么 f [ i ] [ j ] f[i][j] f[i][j] 可以从 f [ i − 1 ] [ j ] f[i - 1][j] f[i−1][j] 走一步到达,因此 f [ i ] [ j ] = f [ i ] [ j ] + f [ i − 1 ] [ j ] f[i][j] = f[i][j] + f[i - 1][j] f[i][j]=f[i][j]+f[i−1][j];
- 如果 j > 0 j \gt 0 j>0,那么 f [ i ] [ j ] f[i][j] f[i][j] 可以从 f [ i ] [ j − 1 ] f[i][j - 1] f[i][j−1] 走一步到达,因此 f [ i ] [ j ] = f [ i ] [ j ] + f [ i ] [ j − 1 ] f[i][j] = f[i][j] + f[i][j - 1] f[i][j]=f[i][j]+f[i][j−1]。
因此,我们有如下的状态转移方程:
f [ i ] [ j ] = { 1 i = 0 , j = 0 f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] otherwise f[i][j] = \begin{cases} 1 & i = 0, j = 0 \\ f[i - 1][j] + f[i][j - 1] & \textit{otherwise} \end{cases} f[i][j]={1f[i−1][j]+f[i][j−1]i=0,j=0otherwise
最终的答案即为 f [ m − 1 ] [ n − 1 ] f[m - 1][n - 1] f[m−1][n−1]。
时间复杂度 O ( m × n ) O(m \times n) O(m×n),空间复杂度 O ( m × n ) O(m \times n) O(m×n)。其中 m m m 和 n n n 分别是网格的行数和列数。
我们注意到 f [ i ] [ j ] f[i][j] f[i][j] 仅与 f [ i − 1 ] [ j ] f[i - 1][j] f[i−1][j] 和 f [ i ] [ j − 1 ] f[i][j - 1] f[i][j−1] 有关,因此我们优化掉第一维空间,仅保留第二维空间,得到时间复杂度 O ( m × n ) O(m \times n) O(m×n),空间复杂度 O ( n ) O(n) O(n) 的实现。
Python3
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [[0] * n for _ in range(m)]
f[0][0] = 1
for 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
条不同的路径:
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j]
为0
或1
难度:中等
标签:数组,动态规划,矩阵
解法
方法一:记忆化搜索
我们设计一个函数 d f s ( i , j ) dfs(i, j) dfs(i,j) 表示从网格 ( i , j ) (i, j) (i,j) 到网格 ( m − 1 , n − 1 ) (m - 1, n - 1) (m−1,n−1) 的路径数。其中 m m m 和 n n n 分别是网格的行数和列数。
函数 d f s ( i , j ) dfs(i, j) dfs(i,j) 的执行过程如下:
- 如果 i ≥ m i \ge m i≥m 或者 j ≥ n j \ge n j≥n,或者 o b s t a c l e G r i d [ i ] [ j ] = 1 obstacleGrid[i][j] = 1 obstacleGrid[i][j]=1,则路径数为 0 0 0;
- 如果 i = m − 1 i = m - 1 i=m−1 且 j = n − 1 j = n - 1 j=n−1,则路径数为 1 1 1;
- 否则,路径数为 d f s ( i + 1 , j ) + d f s ( i , j + 1 ) dfs(i + 1, j) + dfs(i, j + 1) dfs(i+1,j)+dfs(i,j+1)。
为了避免重复计算,我们可以使用记忆化搜索的方法。
时间复杂度 O ( m × n ) O(m \times n) O(m×n),空间复杂度 O ( m × n ) O(m \times n) O(m×n)。其中 m m m 和 n n n 分别是网格的行数和列数。
Python3
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= m or j >= n or obstacleGrid[i][j]:
return 0
if i == m - 1 and j == n - 1:
return 1
return 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 ] f[i][j] f[i][j] 表示从左上角走到 ( i , j ) (i, j) (i,j) 位置的最小路径和。初始时 f [ 0 ] [ 0 ] = g r i d [ 0 ] [ 0 ] f[0][0] = grid[0][0] f[0][0]=grid[0][0],答案为 f [ m − 1 ] [ n − 1 ] f[m - 1][n - 1] f[m−1][n−1]。
考虑 f [ i ] [ j ] f[i][j] f[i][j]:
- 如果 j = 0 j = 0 j=0,那么 f [ i ] [ j ] = f [ i − 1 ] [ j ] + g r i d [ i ] [ j ] f[i][j] = f[i - 1][j] + grid[i][j] f[i][j]=f[i−1][j]+grid[i][j];
- 如果 i = 0 i = 0 i=0,那么 f [ i ] [ j ] = f [ i ] [ j − 1 ] + g r i d [ i ] [ j ] f[i][j] = f[i][j - 1] + grid[i][j] f[i][j]=f[i][j−1]+grid[i][j];
- 如果 i > 0 i \gt 0 i>0 且 j > 0 j \gt 0 j>0,那么 f [ i ] [ j ] = min ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) + g r i d [ i ] [ j ] f[i][j] = \min(f[i - 1][j], f[i][j - 1]) + grid[i][j] f[i][j]=min(f[i−1][j],f[i][j−1])+grid[i][j]。
最后返回 f [ m − 1 ] [ n − 1 ] f[m - 1][n - 1] f[m−1][n−1] 即可。
时间复杂度 O ( m × n ) O(m \times n) O(m×n),空间复杂度 O ( m × n ) O(m \times n) O(m×n)。其中 m m m 和 n n 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"
。
一般的,一个 有效数字 可以用以下的规则之一定义:
- 一个 整数 后面跟着一个 可选指数。
- 一个 十进制数 后面跟着一个 可选指数。
一个 整数 定义为一个 可选符号 '-'
或 '+'
后面跟着 数字。
一个 十进制数 定义为一个 可选符号 '-'
或 '+'
后面跟着下述规则:
- 数字 后跟着一个 小数点
.
。 - 数字 后跟着一个 小数点
.
再跟着 数位。 - 一个 小数点
.
后跟着 数位。
指数 定义为指数符号 'e'
或 'E'
,后面跟着一个 整数。
数字 定义为一个或多个数位。
示例 1:
输入:s = "0"
输出:true
示例 2:
输入:s = "e"
输出:false
示例 3:
输入:s = "."
输出:false
提示:
1 <= s.length <= 20
s
仅含英文字母(大写和小写),数字(0-9
),加号'+'
,减号'-'
,或者点'.'
。
难度:困难
标签:字符串
解法
方法一:分情况讨论
首先,我们判断字符串是否以正负号开头,如果是,将指针
i
i
i 向后移动一位。如果此时指针
i
i
i 已经到达字符串末尾,说明字符串只有一个正负号,返回 false
。
如果当前指针
i
i
i 指向的字符是小数点,并且小数点后面没有数字,或者小数点后是一个 e
或 E
,返回 false
。
接着,我们用两个变量
d
o
t
dot
dot 和
e
e
e 分别记录小数点和 e
或 E
的个数。
用指针 j j j 指向当前字符:
- 如果当前字符是小数点,并且此前出现过小数点或者
e
或E
,返回false
。否则,我们将 d o t dot dot 加一; - 如果当前字符是
e
或E
,并且此前出现过e
或E
,或者当前字符是开头或结尾,返回false
。否则,我们将 e e e 加一;然后判断下一个字符是否是正负号,如果是,将指针 j j j 向后移动一位。如果此时指针 j j j 已经到达字符串末尾,返回false
; - 如果当前字符不是数字,返回
false
。
遍历完字符串后,返回 true
。
时间复杂度 O ( n ) O(n) O(n),其中 n n n 为字符串长度。空间复杂度 O ( 1 ) O(1) O(1)。
Python3
class Solution:
def isNumber(self, s: str) -> bool:
n = len(s)
i = 0
if s[i] in '+-':
i += 1
if i == n:
return False
if s[i] == '.' and (i + 1 == n or s[i + 1] in 'eE'):
return False
dot = e = 0
j = i
while j < n:
if s[j] == '.':
if e or dot:
return False
dot += 1
elif s[j] in 'eE':
if e or j == i or j == n - 1:
return False
e += 1
if s[j + 1] in '+-':
j += 1
if j == n - 1:
return False
elif not s[j].isnumeric():
return False
j += 1
return 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 10 10 取模,如果取模后的结果不为 0 0 0,说明当前元素没有进位,直接返回数组即可。否则,当前元素为 0 0 0,需要进位,继续遍历前一个元素,重复上述操作。如果遍历完数组后,仍然没有返回,说明数组中所有元素都为 0 0 0,需要在数组的头部插入一个 1 1 1。
时间复杂度 O ( n ) O(n) O(n),其中 n n n 是数组的长度。忽略答案的空间消耗,空间复杂度 O ( 1 ) O(1) 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] += 1
digits[i] %= 10
if digits[i] != 0:
return digits
return [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"
,就不含前导零
难度:简单
标签:位运算,数学,字符串,模拟
解法
方法一:模拟
我们用一个变量 c a r r y carry carry 记录当前的进位,用两个指针 i i i 和 j j j 分别指向 a a a 和 b b b 的末尾,从末尾到开头逐位相加即可。
时间复杂度 O ( max ( m , n ) ) O(\max(m, n)) O(max(m,n)),其中 m m m 和 n n n 分别为字符串 a a a 和 b b b 的长度。空间复杂度 O ( 1 ) O(1) 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) O(L),空间复杂度 O ( L ) O(L) O(L)。其中 L 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 += 1
while i < n and cnt + 1 + len(words[i]) <= maxWidth:
cnt += 1 + len(words[i])
t.append(words[i])
i += 1
if i == n or len(t) == 1:
left = ' '.join(t)
right = ' ' * (maxWidth - len(left))
ans.append(left + right)
continue
space_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 l = 0 l=0,右边界 r = x r = x r=x,然后在 [ l , r ] [l, r] [l,r] 范围内查找平方根。
在每一步查找中,我们找出中间值 m i d = ( l + r + 1 ) / 2 mid = (l + r + 1) / 2 mid=(l+r+1)/2,如果 m i d > x / m i d mid > x / mid mid>x/mid,说明平方根在 [ l , m i d − 1 ] [l, mid - 1] [l,mid−1] 范围内,我们令 r = m i d − 1 r = mid - 1 r=mid−1;否则说明平方根在 [ m i d , r ] [mid, r] [mid,r] 范围内,我们令 l = m i d l = mid l=mid。
查找结束后,返回 l l l 即可。
时间复杂度 O ( log x ) O(\log x) O(logx),空间复杂度 O ( 1 ) O(1) O(1)。
Python3
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 0, x
while l < r:
mid = (l + r + 1) >> 1
if mid > x // mid:
r = mid - 1
else:
l = mid
return 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 阶
- 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示:
1 <= n <= 45
难度:简单
标签:记忆化搜索,数学,动态规划
解法
方法一:递推
我们定义 f [ i ] f[i] f[i] 表示爬到第 i i i 阶楼梯的方法数,那么 f [ i ] f[i] f[i] 可以由 f [ i − 1 ] f[i - 1] f[i−1] 和 f [ i − 2 ] f[i - 2] f[i−2] 转移而来,即:
f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i] = f[i - 1] + f[i - 2] f[i]=f[i−1]+f[i−2]
初始条件为 f [ 0 ] = 1 f[0] = 1 f[0]=1, f [ 1 ] = 1 f[1] = 1 f[1]=1,即爬到第 0 阶楼梯的方法数为 1,爬到第 1 阶楼梯的方法数也为 1。
答案即为 f [ n ] f[n] f[n]。
由于 f [ i ] f[i] f[i] 只与 f [ i − 1 ] f[i - 1] f[i−1] 和 f [ i − 2 ] f[i - 2] f[i−2] 有关,因此我们可以只用两个变量 a a a 和 b b b 来维护当前的方法数,空间复杂度降低为 O ( 1 ) O(1) O(1)。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1)。
Python3
class Solution:
def climbStairs(self, n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return 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;
}
};