共计 9354 个字符,预计需要花费 24 分钟才能阅读完成。
73. 矩阵置零(medium)
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请应用 原地 算法。
示例 1:
输出:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输入:[[1,0,1],[0,0,0],[1,0,1]]
示例 2:输出:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输入:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]提醒:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrixi <= 231 – 1进阶:
一个直观的解决方案是应用 O(mn) 的额定空间,但这并不是一个好的解决方案。
一个简略的改良计划是应用 O(m + n) 的额定空间,但这依然不是最好的解决方案。
你能想出一个仅应用常量空间的解决方案吗?
- 思路: 用两个变量标记第一行和第一列是否有 0,接着循环一遍矩阵,如果遇见 0,将和这个网格雷同的第一行和第一列的元素标记成 0,在循环矩阵,如果以后网格对应的第一行和第一列是 0,则将这个单元格置为 0。最初如果第一列有 0,则将这第一列全副置为 0, 如果第一行有 0,则将这第一行全副置为 0
- 复杂度:工夫复杂度
O(mn)
,m、n 为矩阵的行和列。空间复杂度O(1)
js:
var setZeroes = function(matrix) {const m = matrix.length, n = matrix[0].length;
let flagCol0 = false, flagRow0 = false;// 示意第一行和第一列有没有 0
for (let i = 0; i < m; i++) {// 寻找第一列是否存在 0
if (matrix[i][0] === 0) {flagCol0 = true;}
}
for (let j = 0; j < n; j++) {if (matrix[0][j] === 0) {flagRow0 = true;}
}
for (let i = 1; i < m; i++) {// 循环矩阵,如果遇见 0,将和这个网格雷同的第一行和第一列的元素标记成 0
for (let j = 1; j < n; j++) {if (matrix[i][j] === 0) {matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (let i = 1; i < m; i++) {// 循环矩阵,如果以后网格对应的第一行和第一列是 0,则将这个单元格置为 0
for (let j = 1; j < n; j++) {if (matrix[i][0] === 0 || matrix[0][j] === 0) {matrix[i][j] = 0;
}
}
}
if (flagCol0) {// 如果第一列有 0,则将这第一列全副置为 0
for (let i = 0; i < m; i++) {matrix[i][0] = 0;
}
}
if (flagRow0) {// 如果第一行有 0,则将这第一行全副置为 0
for (let j = 0; j < n; j++) {matrix[0][j] = 0;
}
}
};
133. 克隆图(medium)
给你无向 连通 图中一个节点的援用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都蕴含它的值 val(int)和其街坊的列表(list[Node])。
class Node {
public int val; public List<Node> neighbors;
}
测试用例格局:
简略起见,每个节点的值都和它的索引雷同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中应用邻接列表示意。
邻接列表 是用于示意无限图的无序列表的汇合。每个列表都形容了图中节点的街坊集。
给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的援用返回。
示例 1:
输出:adjList = [[2,4],[1,3],[2,4],[1,3]]
输入:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个街坊:节点 2 和 4。
节点 2 的值是 2,它有两个街坊:节点 1 和 3。
节点 3 的值是 3,它有两个街坊:节点 2 和 4。
节点 4 的值是 4,它有两个街坊:节点 1 和 3。
示例 2:输出:adjList = [[]]
输入:[[]]
解释:输出蕴含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何街坊。
示例 3:输出:adjList = []
输入:[]
解释:这个图是空的,它不含任何节点。
示例 4:输出:adjList = [[2],[1]]
输入:[[2],[1]]提醒:
节点数不超过 100。
每个节点值 Node.val 都是惟一的,1 <= Node.val <= 100。
无向图是一个简略图,这意味着图中没有反复的边,也没有自环。
因为图是无向的,如果节点 p 是节点 q 的街坊,那么节点 q 也必须是节点 p 的街坊。
图是连通图,你能够从给定节点拜访到所有节点。
办法 1:dfs
- 思路:深度优先遍历,递归新建每个节点和相邻节点的关系
- 复杂度:工夫复杂度
O(n)
,n 示意节点的数量。空间复杂度O(n)
,递归的深度
js:
var cloneGraph = function(node) {if(!node) return;
const visited = new Map();// 寄存遍历过的节点
const dfs = (n) => {const nCopy = new Node(n.val);// 拷贝节点
visited.set(n, nCopy);// 节点值和新建节点以键值对存入 visited
(n.neighbors || []).forEach(ne => {if(!visited.has(ne)) {dfs(ne);// 递归遍历相邻节点
}
nCopy.neighbors.push(visited.get(ne));// 复制相邻节点
})
}
dfs(node);// 深度优先遍历
return visited.get(node);// 返回 visited 中的新创建的节点
};
办法 1:bfs
- 思路:广度优先遍历每个节点,复制节点和节点间的关系
- 复杂度:工夫复杂度
O(n)
,n 示意节点的数量。空间复杂度O(n)
,队列的空间
js:
var cloneGraph = function(node) {if(!node) return;
const visited = new Map();
visited.set(node, new Node(node.val));// 节点值和新建节点以键值对存入 visited
const q = [node];
while(q.length) {const n = q.shift()// 出队
(n.neighbors || []).forEach(ne => {// 循环相邻节点
if(!visited.has(ne)) {// 没有拜访过就退出队列
q.push(ne);
visited.set(ne, new Node(ne.val));
}
visited.get(n).neighbors.push(visited.get(ne));// 复制相邻节点
})
}
return visited.get(node);
};
54. 螺旋矩阵(medium)
给你一个 m 行 n 列的矩阵 matrix,请依照 顺时针螺旋程序,返回矩阵中的所有元素。
示例 1:
输出:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输入:[1,2,3,6,9,8,7,4,5]
示例 2:输出:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输入:[1,2,3,4,8,12,11,10,9,5,6,7]提醒:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrixi <= 100
- 思路:模仿旋转的程序
- 复杂度:工夫复杂度
O(mn)
,空间复杂度O(1)
js:
var spiralOrder = function (matrix) {if (matrix.length == 0) return []
const res = []
let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1
while (top <= bottom && left <= right) {// 循环条件
for (let i = left; i <= right; i++) res.push(matrix[top][i])// 循环完下面一行 top++
top++
for (let i = top; i <= bottom; i++) res.push(matrix[i][right])// 循环左边一行 right--
right--
if (top > bottom || left > right) break
for (let i = right; i >= left; i--) res.push(matrix[bottom][i])
bottom--
for (let i = bottom; i >= top; i--) res.push(matrix[i][left])
left++
}
return res
};
48. 旋转图像(medium)
给定一个 n × n 的二维矩阵 matrix 示意一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你须要间接批改输出的二维矩阵。请不要 应用另一个矩阵来旋转图像。
示例 1:
输出:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输入:[[7,4,1],[8,5,2],[9,6,3]]
示例 2:输出:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输入:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]提醒:
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrixi <= 1000
- 思路:先沿程度中轴线翻转,而后在沿主对角线翻转.
- 复杂度:工夫复杂度
O(n^2)
,空间复杂度O(1)
js:
var rotate = function(matrix) {
const n = matrix.length;
// 程度中轴线翻转
for (let i = 0; i < Math.floor(n / 2); i++) {for (let j = 0; j < n; j++) {[matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]];
}
}
// 主对角线翻转
for (let i = 0; i < n; i++) {for (let j = 0; j < i; j++) {[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
};
836. 矩形重叠(easy)
矩形以列表 [x1, y1, x2, y2] 的模式示意,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴,左右边平行于 y 轴。
如果相交的面积为 正,则称两矩形重叠。须要明确的是,只在角或边接触的两个矩形不形成重叠。
给出两个矩形 rec1 和 rec2。如果它们重叠,返回 true;否则,返回 false。
示例 1:
输出:rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输入:true
示例 2:输出:rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输入:false
示例 3:输出:rec1 = [0,0,1,1], rec2 = [2,2,3,3]
输入:false提醒:
rect1.length == 4
rect2.length == 4
-109 <= rec1[i], rec2[i] <= 109
rec1 和 rec2 示意一个面积不为零的无效矩形
- 复杂度:工夫复杂度
O(1)
,空间复杂度O(1)
js:
var isRectangleOverlap = function(rec1, rec2) {const [x1, y1, x2, y2] = rec1;
const [x3, y3, x4, y4] = rec2;
return !(x1 >= x4 || x3 >= x2 || y3 >= y2 || y1 >= y4);
};
89. 格雷编码(medium)
n 位格雷码序列 是一个由 2n 个整数组成的序列,其中:
每个整数都在范畴 [0, 2n – 1] 内(含 0 和 2n – 1)
第一个整数是 0
一个整数在序列中呈现 不超过一次
每对 相邻 整数的二进制示意 恰好一位不同,且
第一个 和 最初一个 整数的二进制示意 恰好一位不同
给你一个整数 n,返回任一无效的 n 位格雷码序列。示例 1:
输出:n = 2
输入:[0,1,3,2]
解释:
[0,1,3,2] 的二进制示意是 [00,01,11,10]。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个无效的格雷码序列,其二进制示意是 [00,10,11,01]。- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
示例 2:输出:n = 1
输入:[0,1]提醒:
1 <= n <= 16
- 思路:变量 pre 初始为 1,一直左移,ans 寄存后果,每次循环之前数,在后面加上 pre
- 复杂度:工夫复杂度
O(n^2)
。空间复杂度O(1)
js:
var grayCode = function(n) {let ans = [0];
let pre = 1;
for(let i = 0;i<n;i++){for(let j = ans.length - 1;j>=0;j--){ans.push(pre + ans[j]);
}
pre <<= 1;
}
return ans;
};
66. 加一(easy)
给定一个由 整数 组成的 非空 数组所示意的非负整数,在该数的根底上加一。
最高位数字寄存在数组的首位,数组中每个元素只存储单个数字。
你能够假如除了整数 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
- 思路:如果
digits[i] %= 10
不为 0,则间接返回 digits,循环过程中没有 reutrn 掉阐明始终进位到最大地位。 - 复杂度:工夫复杂度
O(n)
,空间复杂度O(1)
js:
// 例子:12,19,99
var plusOne = function(digits) {
const len = digits.length;
for(let i = len - 1; i >= 0; i--) {digits[i]++;
digits[i] %= 10;// 求余 10,笼罩以后地位
if(digits[i]!=0)// 没有进位就间接返回这个数
return digits;
}
digits = [...Array(len + 1)].map(_=>0);// 循环没有 return 掉 解决始终进位到最大地位
//[1,0,0]
digits[0] = 1;
return digits;
};
65. 有效数字(hard)
有效数字(按程序)能够分成以下几个局部:
一个 小数 或者 整数
(可选)一个 ‘e’ 或 ‘E’,前面跟着一个 整数
小数(按程序)能够分成以下几个局部:(可选)一个符号字符(’+’ 或 ‘-‘)
下述格局之一:
至多一位数字,前面跟着一个点 ‘.’
至多一位数字,前面跟着一个点 ‘.’,前面再跟着至多一位数字
一个点 ‘.’,前面跟着至多一位数字
整数(按程序)能够分成以下几个局部:(可选)一个符号字符(’+’ 或 ‘-‘)
至多一位数字
局部有效数字列举如下:[“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”]
给你一个字符串 s,如果 s 是一个 有效数字,请返回 true。
示例 1:
输出:s = “0”
输入:true
示例 2:输出:s = “e”
输入:false
示例 3:输出:s = “.”
输入:false提醒:
1 <= s.length <= 20
s 仅含英文字母(大写和小写),数字(0-9),加号 ‘+’,减号 ‘-‘,或者点 ‘.’。
图是网络结构的形象模型,是一组由边连贯的节点
图能够辨识任何二元关系 比方路、航班
图的示意办法
- 邻接矩阵
- 邻接表
- 思路: 无限状态机,遍历字符串,一直转换状态,看最初的状态是是否是无效状态
- 复杂度:工夫复杂度
O(n)
,n 是字符串的长度,遍历 n 次,每次状态转移是O(1)
。空间复杂度O(1)
js:
//1.2 2e10
//--6 2e
var isNumber = function (s) {
const graph = {0: { 'black': 0, 'sign': 1, '.': 2, 'digit': 6},
1: {'digit': 6, '.': 2},
2: {'digit': 3},
3: {'digit': 3, 'e': 4, "E": 4},
4: {'digit': 5, 'sign': 7},
5: {'digit': 5},
6: {'digit': 6, '.': 3, 'e': 4, "E": 4},
7: {'digit': 5}
};
let state = 0;// 初始状态
for (let c of s.trim()) {// 循环字符串
if (c >= '0' && c <= '9') {c = 'digit';} else if (c === ' ') {c = 'blank';} else if (c === '+' || c === '-') {c = 'sign'}
state = graph[state];// 返回下一个状态
if (state === undefined) {// 状态转移之后不在临接表中 返回 false
return false;
}
}
if (state == 3 || state == 5 || state == 6) {// 状态是 3、5、6 中的一个阐明是有效数字
return true;
}
return false;
};
417. 太平洋大西洋水流问题(medium)
有一个 m × n 的矩形岛屿,与 太平洋 和 大西洋 相邻。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。
这个岛被宰割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights,heightsr 示意坐标 (r, c) 上单元格 高于海平面的高度。
岛上雨水较多,如果相邻单元格的高度 小于或等于 以后单元格的高度,雨水能够间接向北、南、东、西流向相邻单元格。水能够从陆地左近的任何单元格流入陆地。
返回网格坐标 result 的 2D 列表,其中 result[i] = [ri, ci] 示意雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋。
示例 1:
输出: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输入: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2:输出: heights = [[2,1],[1,2]]
输入: [[0,0],[0,1],[1,0],[1,1]]提醒:
m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heightsr <= 105
- 思路:筹备两个示意是否能流向某个海岸线的矩阵,沿着海岸线‘’逆流而上‘’,最初统计两个大洋都能流向的坐标
- 复杂度:工夫复杂度
O(m*n)
,m、n 别离是坐标矩阵的长宽。空间复杂度O(m * n)
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
js:
var pacificAtlantic = function(matrix) {if(!matrix || !matrix[0]) {return []; }
const m = matrix.length;
const n = matrix[0].length;
// 从太平洋或大西洋逆流而上是否能达到某个坐标的数组 ture 示意能流向某一个大洋
const flow1 = Array.from({length: m}, () => new Array(n).fill(false));
const flow2 = Array.from({length: m}, () => new Array(n).fill(false));
const dfs = (r, c, flow) => {flow[r] = true;
[[r-1, c], [r+1, c], [r, c-1], [r, c+1]].forEach(([nr, nc]) => {
if(
// 避免越界
nr >= 0 && nr < m &&
nc >= 0 && nc < n &&
// 只有未标记的坐标能力持续递归 避免死循环
!flow[nr][nc] &&
// 确保是逆流而上
matrix[nr][nc] >= matrix[r]
) {dfs(nr, nc, flow)
}
})
}
// 逆流而上
for(let r = 0; r<m; r+=1) {dfs(r, 0, flow1);
dfs(r, n-1, flow2)
}
for(let c = 0; c <n; c += 1) {dfs(0, c, flow1);
dfs(m-1, c, flow2)
}
// 统计两个大洋都能流向的坐标
const res = []
for(let r = 0; r < m; r += 1) {for(let c = 0; c < n; c += 1) {if(flow1[r] && flow2[r]) {res.push([r, c])
}
}
}
return res;
};
41. 缺失的第一个负数(hard)
给你一个未排序的整数数组 nums,请你找出其中没有呈现的最小的正整数。
请你实现工夫复杂度为 O(n) 并且只应用常数级别额定空间的解决方案。
示例 1:
输出:nums = [1,2,0]
输入:3
示例 2:输出:nums = [3,4,-1,1]
输入:2
示例 3:输出:nums = [7,8,9,11,12]
输入:1提醒:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 – 1
- 思路: 循环 nums,以后元素在
(0,nums.lenght]
之间,并且nums[nums[i]-1] != nums[i]
,则替换地位,而后循环替换地位之后的数组,判断第一个缺失的负数 - 复杂度:工夫复杂度
O(n)
,空间复杂度O(1)
js:
var firstMissingPositive = function(nums) {for(let i = 0; i < nums.length; i++){// 循环 nums,以后元素在 (0,nums.lenght] 之间,并且 nums[nums[i]-1] != nums[i],则替换地位
while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i] ){const temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
}
}
for(let i = 0; i < nums.length; i++){// 循环替换地位之后的数组,判断第一个缺失的负数
if(nums[i] != i+1){return i+1;}
}
// [1,2,3]
return nums.length + 1;
};
视频解说:传送门