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， 99var 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 2evar 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][c];//返回下一个状态 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][c] = 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][c] ) { 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][c] && flow2[r][c]) { 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;};视频解说：传送门