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;
};视频解说：传送门