Leetcode

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（200）岛屿数量一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。模仿 - 标记法”。// 思路：// 1）状态初始化：m = grid.length, n = grid[0].length; 。// tempMap = new Map(), resMap = getMapByGrid(), resCount = 0; 。// 2）外围：循环解决 —— 条件为 存在未被拜访过的海洋 。// 3）返回后果 resCount 。var numIslands = function(grid) { const getMapByGrid = () => { let resMap = new Map(); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === '1') { const tempVal = `${i}#${j}`; resMap.set(tempVal, 1); } } } return resMap; }; // 1）状态初始化：m = grid.length, n = grid[0].length; 。 // tempMap = new Map(), resMap = getMapByGrid(), resCount = 0; 。 const m = grid.length, n = grid[0].length; let // tempMap：目前已被拜访过的海洋。 tempMap = new Map(), resMap = getMapByGrid(), resCount = 0; // 2）外围：循环解决 —— 条件为 存在未被拜访过的海洋 。 while (resMap.size !== 0) { for (const [key, val] of resMap) { if (!tempMap.has(key)) { tempMap.set(key, 1); let tempQueue = [key]; while (tempQueue.length !== 0) { const key = tempQueue.shift(), [tempI, tempJ] = key.split('#').map(v => parseInt(v)); // 标记为已被拜访。 resMap.delete(key); // 4个方向的拜访。 // 上 if (tempI - 1 >= 0 && grid[tempI - 1][tempJ] === '1') { const key = `${tempI - 1}#${tempJ}`; if (!tempMap.has(key)) { tempQueue.push(key); tempMap.set(key, 1); } } // 下 if (tempI + 1 < m && grid[tempI + 1][tempJ] === '1') { const key = `${tempI + 1}#${tempJ}`; if (!tempMap.has(key)) { tempQueue.push(key); tempMap.set(key, 1); } } // 左 if (tempJ - 1 >= 0 && grid[tempI][tempJ - 1] === '1') { const key = `${tempI}#${tempJ - 1}`; if (!tempMap.has(key)) { tempQueue.push(key); tempMap.set(key, 1); } } // 右 if (tempJ + 1 < n && grid[tempI][tempJ + 1] === '1') { const key = `${tempI}#${tempJ + 1}`; if (!tempMap.has(key)) { tempQueue.push(key); tempMap.set(key, 1); } } } // 以后岛屿无奈再次连贯到任何海洋了。 resCount++; } break; } } // 3）返回后果 resCount 。 return resCount;};2 计划21)代码： ...

leetcode912排序数组给你一个整数数组 nums，请你将该数组升序排列。 示例 1： 输出：nums = [5,2,3,1]输入：[1,2,3,5] 示例 2： 输出：nums = [5,1,1,2,0,0]输入：[0,0,1,1,2,5] 提醒： 1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104归并排序（重点）基本思路：借助额定空间，合并两个有序数组，失去更长的有序数组。例如：「力扣」第 88 题：合并两个有序数组。算法思维：分而治之（分治思维）。「分而治之」思维的形象了解是「曹冲称象」、MapReduce，在肯定状况下能够并行化。集体倡议：「归并排序」是了解「递归思维」的十分好的学习材料，大家能够通过了解：递归实现当前，合并两个有序数组的这一步骤，想分明程序的执行流程。即「递归函数执行实现当前，咱们还能够做点事件」。因而，「归并排序」我集体感觉十分重要，肯定要把握。 class Solution { //归并排序 public int[] sortArray(int[] nums) { return mergeSort(nums, 0, nums.length-1); } public int[] mergeSort(int[] nums, int left, int right){ //递归退出条件 //如果左指针大于右指针，就退出循环 //通过左右拆分，数组元素造成单个元素的树 if(left >=right){ return nums; } //数组中的中位数 int mid = (right+left)/2; //数组左拆分 mergeSort(nums, left, mid); //数组右拆分 mergeSort(nums, mid+1, right); //数组合并，将单个元素进行合并 return merge(nums, left, mid, right); } public int[] merge(int[] nums, int left, int mid, int right){ //定义一个长期数组，存储排序好的元素 int[] temp = new int[right-left+1]; //左排序的元素数组的左指针 int i = left; //右排序的元素数组的左指针 int j = mid+1; //定义一个指向长期数组的左指针 int t = 0; //循环判断条件 //左数组到mid，右数组到right //左右数组都有元素的时候，进行比拟 while(i<=mid&&j<=right){ //取左右数组中较小的元素，填入长期数组中 //并将较小元素所在数组的左指针和长期数组的左指针都一起右移 if(nums[i]<=nums[j]){ temp[t++] = nums[i++]; }else{ temp[t++] = nums[j++]; } } //当左右数组其中一个数组没有元素的时候 //如果左数组中还有残余元素，就将残余元素全副退出到长期数组中 while(i<=mid){ temp[t++]=nums[i++]; } //如果有数组中还有元素，就将残余元素全副退出到长期数组中 while(j<=right){ temp[t++] = nums[j++]; } //将长期数组的元素复制到原数组中去 for(int k = 0; k<temp.length;k++){ //特地留神这便nums数组起始地位要从 k+left开始 //起因在加右数组的时候，起始地位要加left //这里不了解，间接把它记住。 nums[left+k]=temp[k]; } //返回原数组 return nums; }}优化 1：在「小区间」里转向应用「插入排序」，Java 源码外面也有相似这种操作，「小区间」的长度是个超参数，须要测试决定，我这里参考了 JDK 源码；优化 2： 在「两个数组」自身就是有序的状况下，无需合并；优化 3：全程应用一份长期数组进行「合并两个有序数组」的操作，防止创立长期数组和销毁的耗费，防止计算下标偏移量。留神：实现归并排序的时候，要特地留神，不要把这个算法实现成非稳固排序，区别就在 <= 和 < ，已在代码中注明。「归并排序」比「疾速排序」好的一点是，它借助了额定空间，能够实现「稳固排序」，Java 里对于「对象数组」的排序工作，就是应用归并排序（的升级版 TimSort，在这里就不多做介绍）。 ...

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/word-ladder-ii 按字典 wordList 实现从单词 beginWord 到单词 endWord 转化，一个示意此过程的 转换序列 是模式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足： 每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。留神，beginWord 不用是字典 wordList 中的单词。sk == endWord给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的模式返回。 示例 1： 输出：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]输入：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]解释：存在 2 种最短的转换序列："hit" -> "hot" -> "dot" -> "dog" -> "cog""hit" -> "hot" -> "lot" -> "log" -> "cog"示例 2： ...

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/shortest-bridge 在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 造成的一个最大组。） 当初，咱们能够将 0 变为 1，以使两座岛连接起来，变成一座岛。 返回必须翻转的 0 的最小数目。（能够保障答案至多是 1 。） 示例 1： 输出：A = [[0,1],[1,0]]输入：1示例 2： 输出：A = [[0,1,0],[0,0,0],[0,0,1]]输入：2示例 3： 输出：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]输入：1提醒： 2 <= A.length == A[0].length <= 100Ai == 0 或 Ai == 1 二、解题思路给一个二维的矩阵，0示意陆地1示意海洋，下面一共有两个小岛，由竖连贯着的1组成的。当初填多少格子让两个小岛连在一起。这道题能够看成多终点多起点的最短门路问题。这种状况咱们能够应用BFS（广度优先搜寻），把终点全副push到队列外面去，下一步走到起点上的放就找到门路了，就是一个BFS找最短门路的问题。前提是晓得哪局部是终点，哪局部是起点。终点咱们能够应用DFS来找，找到小岛后标记成2。而后往外扩大，每次往外扩一层，直到碰到1为止。 以题目中的示例2为例，如上图左上角第二个。应用DFS找到第1个小岛后标记成2，放到queue里去，这是终点。而后用BFS去扩大，使小岛面积一直的扩充，每次往外扩一层，直到碰到1为止。上图当扩大到第3步即第3层的时候碰到1了，阐明找到了门路了，即两个岛的最短距离为3-1=2。 三、解题办法3.1 Java实现public class Solution { public int shortestBridge(int[][] grid) { // 用来存入第一个岛屿的坐标 Queue<Pair> queue = new LinkedList(); boolean found = false; for (int i = 0; !found && i < grid.length; i++) { for (int j = 0; !found && j < grid[0].length; j++) { if (grid[i][j] == 1) { dfs(grid, j, i, queue); found = true; } } } int steps = 0; int[] dirs = new int[]{0, 1, 0, -1, 0}; while (!queue.isEmpty()) { int size = queue.size(); while (size-- != 0) { Pair p = queue.poll(); int x = p.x; int y = p.y; for (int i = 0; i < 4; i++) { int tx = x + dirs[i]; int ty = y + dirs[i + 1]; if (tx < 0 || ty < 0 || tx >= grid[0].length || ty >= grid.length || grid[ty][tx] == 2) { continue; } if (grid[ty][tx] == 1) { return steps; } grid[ty][tx] = 2; queue.add(new Pair(tx, ty)); } } steps++; } return -1; } private void dfs(int[][] grid, int x, int y, Queue<Pair> queue) { if (x < 0 || y < 0 || x >= grid[0].length || y >= grid.length || grid[y][x] != 1) { return; } grid[y][x] = 2; queue.add(new Pair(x, y)); dfs(grid, x - 1, y, queue); dfs(grid, x, y - 1, queue); dfs(grid, x + 1, y, queue); dfs(grid, x, y + 1, queue); } class Pair { int x; int y; public Pair(int x, int y) { this.x = x; this.y = y; } }}四、总结小记2022/6/7 要总结一些模板

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/n-queens 依照国际象棋的规定，皇后能够攻打与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 钻研的是如何将 n 个皇后搁置在 n×n 的棋盘上，并且使皇后彼此之间不能互相攻打。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法蕴含一个不同的 n 皇后问题 的棋子搁置计划，该计划中 'Q' 和 '.' 别离代表了皇后和空位。 示例 1： 输出：n = 4输入：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2： 输出：n = 1输入：[["Q"]]提醒： 1 <= n <= 9 二、解题思路经典的递归入门题目，在N*N的棋盘下面放上N个皇后，而后使得任意两个皇后不能互相攻打，没有玩的国际象棋，皇后的攻打范畴是整个一行一列以及对角线攻打，以N=8为例，问题就是摆放8个皇后，皇后之间不能互相攻打。先看一个最要害的个性，因为每个皇后会攻打一行或一列，一个最根本的要求是每行只有一个皇后，每列也只有一个皇后，每条对角线也只有一个皇后，这道题是用递归进行搜寻，依据这个个性能够减去不须要的判断。 皇后的攻打范畴是行、列、对角线，如上图，棋盘是11是有1个解棋盘是22与33是无解，8皇后是92个解，棋盘是对称的，fundamental是根本解，高低对称、左右对称、对角线对称。解的增长是很快的，当棋盘是2424时解基本上就是天文数字了，题目给出N的范畴是1-9每一行只能放一个皇后，用递归的办法，以后行找一个地位放皇后，下一行再找一个地位放皇后，每搁置一个皇后将它所有的攻打范畴标记成不能走，下一行皇后搁置的地位范畴就少了，这就是递归的过程。 它的对角线的特点，8皇后，正对角线和反对角线别离有15条，对应的公式为2*n-1。搁置一个皇后后能够将以后地位的对角线设置为不可走，然而这样会节约很多工夫和空间，其实咱们能够用一个变量来形容这一行、一列、一个对角线。最小单位就是一行、一列、一个对角线，对角线从左上角到右下角标记成0...14，咱们就能够用这15个变量来形容这15条对角线，对角线的索引和格子的xy有什么关系呢？红色对角线的索引idx = x + y，蓝色对角线的索引idx = x - y + (n - 1)，这样在递归搜寻的时候就能够缩小判断了。看伪代码，按行来搜寻，所以就不用来记录第几行间接用y来示意。因为不能放到之前的行数中去，比方递归到第4行的时候，后面3行曾经搁置了3个皇后，当初要在第4行中找一个适合的地位搁置第4行的皇后，所以行数就不必数组来形容它是否曾经被占据了，从0到y-1的行数曾经被占据了，是不能搁置皇后的。当y == n的时候，示意超过棋盘了，即曾经搁置了n个皇后了，找到解了，即把以后的棋盘追加到返回后果中，返回，递归完结。对于第y行来说，要循环这个列，x从0到n开始循环，先判断以后格局是否能走，能走的话将皇后搁置在这个地位并持续下一层递归，递归完之后要将这一行清空，示意这一行没有皇后，并将这行的地位置为可走。available判断是否可走的实现：判断列是否可走，正对角线是否可走，反对角线是否可走。 三、解题办法3.1 Java实现public class Solution { public List<List<String>> solveNQueens(int n) { board = new ArrayList<>(); for (int i = 0; i < n; i++) { // jdk11 // board.add(".".repeat(n)); board.add(".".repeat(n).toCharArray()); } cols = new boolean[n]; diag1 = new boolean[2 * n - 1]; diag2 = new boolean[2 * n - 1]; sols = new ArrayList<>(); nqueens(n, 0); return sols; } /** * 记录棋盘 */ private List<char[]> board; /** * 记录第x列是否有皇后 */ private boolean[] cols; /** * 记录第x条正对角线上是否有皇后 */ private boolean[] diag1; /** * 记录第x条反对角线上是否有皇后 */ private boolean[] diag2; /** * 记录解 */ private List<List<String>> sols; boolean available(int x, int y, int n) { return !cols[x] && !diag1[x + y] && !diag2[x - y + n - 1]; } /** * 更新棋盘 * * @param x * @param y * @param n * @param put */ void updateBoard(int x, int y, int n, boolean put) { cols[x] = put; diag1[x + y] = put; diag2[x - y + n - 1] = put; board.get(y)[x] = put ? 'Q' : '.'; } void nqueens(int n, int y) { if (y == n) { List<String> tmp = board.stream().map(t -> String.valueOf(t)).collect(Collectors.toList()); sols.add(tmp); return; } for (int x = 0; x < n; x++) { if (!available(x, y, n)) { continue; } // 更新棋盘 updateBoard(x, y, n, true); nqueens(n, y + 1); // 将棋盘还原 updateBoard(x, y, n, false); } }}四、总结小记2022/6/6 回溯+递归来解决八皇后问题

两头结点定义1->2->3->4 两头结点为31->2->3->4->5 两头结点为3 ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow;}链表从两头断开但有的题须要从链表两头结点断开，例如1->2->3->4->NULL断开为1->2->NULL和3->4->NULL两条链表，此时咱们须要找两头结点的前一结点(2)。但链表节点数为奇数，则无区别。例如1->2->3->4->5->NULL断开为1->2->3->NULL和4->5->NULL 办法1： ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow;}办法2：当然也能够不批改while条件，而在while中先走fast，而后到尾就退出，此时slow少走一步即为两头结点前一结点。 while(fast != nullptr && fast->next != nullptr) { fast=fast->next->next; if(fast == nullptr || fast->next == nullptr) brk = slow; //找到两头的地位 slow = slow->next;}brk->next = nullptr; // 将链表切开

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/word-search 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须依照字母程序，通过相邻的单元格内的字母形成，其中“相邻”单元格是那些程度相邻或垂直相邻的单元格。同一个单元格内的字母不容许被重复使用。 示例 1： 输出：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输入：true示例 2： 输出：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"输入：true示例 3： 输出：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"输入：false提醒： m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board 和 word 仅由大小写英文字母组成进阶：你能够应用搜寻剪枝的技术来优化解决方案，使其在 board 更大的状况下能够更快解决问题？ 二、解题思路还是用回溯法，定义一个二维数组存储拜访标记，在对任意地位进行深度优先搜寻时，先将以后地位为已拜访，以防止反复遍历，在所有的可能都搜寻实现后，再改回以后地位为未拜访，避免烦扰其它地位搜寻以后地位。 三、解题办法3.1 Java实现public class Solution { boolean find = false; public boolean exist(char[][] board, String word) { if (board.length == 0) { return false; } int m = board.length; int n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { backTracking(i, j, board, word, visited, 0); } } return find; } void backTracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos) { if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) { return; } if (visited[i][j] || find || board[i][j] != word.charAt(pos)) { return; } if (pos == word.length() - 1) { find = true; return; } visited[i][j] = true; backTracking(i + 1, j, board, word, visited, pos + 1); backTracking(i - 1, j, board, word, visited, pos + 1); backTracking(i, j + 1, board, word, visited, pos + 1); backTracking(i, j - 1, board, word, visited, pos + 1); visited[i][j] = false; }}四、总结小记2021/6/5 明天假日最初一天

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（236）二叉树的最近公共先人一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。递归-存储所有门路法”。// 思路：// 1）状态初始化：resList = [], curPpath = []; 。// 2）调用递归函数。// 3）外围：顺次从底下往上找 p、q 的公共先人。var lowestCommonAncestor = function(curRoot, p, q) { // 递归函数 var dfs = function(curPath, curRroot){ const {left, right} = curRroot; curPath.push(curRroot); // 1）递归进口。 if (left === null && right === null) { resList.push(curPath.slice()); return; } // 2）递归主体。 if (left === null && right !== null) { dfs(curPath, right); curPath.pop(); } else if (left !== null && right === null) { dfs(curPath, left); curPath.pop(); } else { dfs(curPath, left); curPath.pop(); dfs(curPath, right); curPath.pop(); } } // 1）状态初始化：resList = [], curPpath = []; 。 let resList = [], curPath = []; // 2）调用递归函数。 dfs(curPath, curRoot); // 3）外围：顺次从底下往上找 p、q 的公共先人。 let p_path = resList.filter(item => item.includes(p))[0], q_path = resList.filter(item => item.includes(q))[0]; for(let i = p_path.indexOf(p); i >= 0; i--){ if(q_path.slice(0, q_path.indexOf(q) + 1).includes(p_path[i])){ return p_path[i]; } }};2 计划21)代码： ...

LRU 策略详解和实现关注 TA [ labuladongL6 ](https://leetcode.cn/u/labulad...)公布于 2019-07-06130.3kC++Javacpp 读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目： 146. LRU缓存机制（中等） ----------- LRU 算法就是一种缓存淘汰策略，原理不难，然而面试中写出没有 bug 的算法比拟有技巧，须要对数据结构进行层层形象和拆解，本文就带你写一手丑陋的代码。 计算机的缓存容量无限，如果缓存满了就要删除一些内容，给新内容腾地位。但问题是，删除哪些内容呢？咱们必定心愿删掉哪些没什么用的缓存，而把有用的数据持续留在缓存里，不便之后持续应用。那么，什么样的数据，咱们断定为「有用的」的数据呢？ LRU 缓存淘汰算法就是一种罕用策略。LRU 的全称是 Least Recently Used，也就是说咱们认为最近应用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。 举个简略的例子，安卓手机都能够把软件放到后盾运行，比方我先后关上了「设置」「手机管家」「日历」，那么当初他们在后盾排列的程序是这样的： 然而这时候如果我拜访了一下「设置」界面，那么「设置」就会被提前到第一个，变成这样： 假如我的手机只容许我同时开 3 个应用程序，当初曾经满了。那么如果我新开了一个利用「时钟」，就必须敞开一个利用为「时钟」腾出一个地位，关那个呢？ 依照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未应用的，而后把新开的利用放到最下面： 当初你应该了解 LRU（Least Recently Used）策略了。当然还有其余缓存淘汰策略，比方不要按拜访的时序来淘汰，而是按拜访频率（LFU 策略）来淘汰等等，各有利用场景。本文解说 LRU 算法策略。 [](#)一、LRU 算法形容力扣第 146 题「LRU缓存机制」就是让你设计数据结构： 首先要接管一个 capacity 参数作为缓存的最大容量，而后实现两个 API，一个是 put(key, val) 办法存入键值对，另一个是 get(key) 办法获取 key 对应的 val，如果 key 不存在则返回 -1。 留神哦，get 和 put 办法必须都是 O(1) 的工夫复杂度，咱们举个具体例子来看看 LRU 算法怎么工作。 ...

D137 27. Remove Element题目链接27. Remove Element 题目剖析给定一个数组和一个数字，从该数组中移除该数字，并返回剩下的元素个数。 因为数组传的是援用型的，所以不必返回数组。 解题思路这道题换作是C/C++的话，考查的是指针吧。 PHP的话，判断是否相等，而后间接unset就能够了。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @param Integer $val * @return Integer */ function removeElement(&$nums, $val) { $remain = 0; foreach($nums as $key => $num){ if($num == $val){ unset($nums[$key]); } $remain++; } return $remain; }}若感觉本文章对你有用，欢送用爱发电赞助。

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/combinations 给定两个整数 n 和 k，返回范畴 [1, n] 中所有可能的 k 个数的组合。 你能够按 任何程序 返回答案。 示例 1： 输出：n = 4, k = 2输入：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]示例 2： 输出：n = 1, k = 1输入：[[1]]提醒： 1 <= n <= 201 <= k <= n 二、解题思路用回溯办法解决组合问题，相似排列，排列回溯的是替换的地位，而组合回溯的是否把以后的数字退出后果中。 三、解题办法3.1 Java实现public class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> ans = new ArrayList<>(); backTracking(ans, new int[k], 0, 1, n, k); return ans; } void backTracking(List<List<Integer>> ans, int[] comb, int count, int pos, int n, int k) { if (count == k) { ans.add(Arrays.stream(comb).boxed().collect(Collectors.toList())); return; } for (int i = pos; i <= n; i++) { // 批改以后节点状态 comb[count++] = i; // 递归子节点 backTracking(ans, comb, count, i + 1, n, k); // 回改以后节点状态 count--; } }}四、总结小记2022/6/4 好吃的货色很多，要克服

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/permutations 给定一个不含反复数字的数组 nums ，返回其 所有可能的全排列 。你能够 按任意程序 返回答案。示例 1： 输出：nums = [1,2,3]输入：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2： 输出：nums = [0,1]输入：[[0,1],[1,0]]示例 3： 输出：nums = [1]输入：[[1]]提醒： 1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不雷同 二、解题思路应用回溯法解决此问题，对于每一个以后地位i，咱们能够将其与之后的任意地位替换，而后持续解决地位i+1，直到解决到最初一位。为了避免咱们每次遍历时都要新建一个子数组贮存地位i之前曾经替换好的数字，咱们就利用回溯法，只对原数组进行批改，在递归实现后再批改回来。 三、解题办法3.1 Java实现public class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); backTracking(nums, 0, ans); return ans; } void backTracking(int[] nums, int level, List<List<Integer>> ans) { if (level == nums.length - 1) { ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList())); return; } for (int i = level; i < nums.length; i++) { // 批改以后节点状态 swap(nums, i, level); // 递归子节点 backTracking(nums, level + 1, ans); // 回改以后节点状态 swap(nums, i, level); } } void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }}四、总结小记2022/6/3 在这天完结的时候实现

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/pacific-atlantic-water-flow 有一个 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.lengthn == heights[r].length1 <= m, n <= 2000 <= heightsr <= 105 二、解题思路了解题意：了解题意很重要，大海之中有一块四四方方的海洋且有高有低，地位都编上码，地位处的数字代表海拔，海洋左上方是太平洋，右下方是大西洋，水往低解决流，问哪些地方的水能同时流向太平洋和大西洋。解题思路：逆向思维，假如淡水落潮的时候，太平洋和大西洋的水能漫到海洋的最高点是多少，别离记录下来。假如水在达到最高点后不在持续漫了。这时别离记录下太平洋和大西洋的水能达到的地位。再取他们公共的局部就是答案了。 三、解题办法3.1 Java实现public class Solution { public List<List<Integer>> pacificAtlantic(int[][] heights) { this.heights = heights; this.M = heights.length; this.N = heights[0].length; boolean[][] reachsP = new boolean[M][N]; boolean[][] reachsA = new boolean[M][N]; int[] leftDir = new int[]{-1, 0}; int[] rightDir = new int[]{1, 0}; int[] upDir = new int[]{0, -1}; int[] downDir = new int[]{0, 1}; for (int i = 0; i < M; i++) { dfs(reachsP, i, 0); dfs(reachsA, i, N - 1); } for (int j = 0; j < N; j++) { dfs(reachsP, 0, j); dfs(reachsA, M - 1, j); } List<List<Integer>> ans = new ArrayList<>(); for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (reachsA[i][j] && reachsP[i][j]) { ans.add(Arrays.asList(i, j)); } } } return ans; } private int[][] heights; private int M; private int N; private int[][] dirs = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; private void dfs(boolean[][] reachs, int i, int j) { reachs[i][j] = true; for (int[] dir : dirs) { int x = i + dir[0]; int y = j + dir[1]; if (x >= 0 && x < M && y >= 0 && y < N && !reachs[x][y] && heights[x][y] >= heights[i][j]) { dfs(reachs, x, y); } } }}四、总结小记2022/6/1 要放端午了

一、题目粗心标签:搜寻 https://leetcode.cn/problems/number-of-provinces 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 间接相连，且城市 b 与城市 c 间接相连，那么城市 a 与城市 c 间接相连。 省份 是一组间接或间接相连的城市，组内不含其余没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnectedi = 1 示意第 i 个城市和第 j 个城市间接相连，而 isConnectedi = 0 示意二者不间接相连。 返回矩阵中 省份 的数量。 示例 1： 输出：isConnected = [[1,1,0],[1,1,0],[0,0,1]]输入：2示例 2： 输出：isConnected = [[1,0,0],[0,1,0],[0,0,1]]输入：3提醒： 1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnectedi 为 1 或 0isConnectedi == 1isConnectedi == isConnectedj二、解题思路每个人看作是一个点，每个人与别人的分割看作是一条线，即n条线，包含本人与本人的关系。这样每个节点最多n条边起码1条边。 三、解题办法3.1 Java实现public class Solution { public int findCircleNum(int[][] isConnected) { int M = isConnected.length; int num = 0; boolean[] visited = new boolean[M]; for (int i = 0; i < M; i++) { if (!visited[i]) { dfs(isConnected, i, visited); num++; } } return num; } private void dfs(int[][] isConnected, int i, boolean[] visited) { visited[i] = true; for (int j = 0; j < isConnected[0].length; j++) { if (isConnected[i][j] == 1 && !visited[j]) { dfs(isConnected, j, visited); } } }}四、总结小记2022/6/1 白天越来越长，四川雅安连发地震 最大6.1级。。。

一、题目粗心标签: 搜寻 https://leetcode.cn/problems/max-area-of-island 给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 形成的组合，这里的「相邻」要求两个 1 必须在 程度或者竖直的四个方向上 相邻。你能够假如 grid 的四个边缘都被 0（代表水）突围着。 岛屿的面积是岛上值为 1 的单元格的数目。 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。 示例 1： 输出：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]输入：6解释：答案不应该是 11 ，因为岛屿只能蕴含程度或垂直这四个方向上的 1 。示例 2： 输出：grid = [[0,0,0,0,0,0,0,0]]输入：0提醒： m == grid.lengthn == grid[i].length1 <= m, n <= 50gridi 为 0 或 1 二、解题思路搜寻类的题，这题能够用深度优先搜寻，定义一个主函数和一个辅函数，主函数用于遍历所有的搜寻地位，判断是否能够开始搜寻，辅函数则负责深度优先搜寻的递归调用。 三、解题办法3.1 Java实现public class Solution { public int maxAreaOfIsland(int[][] grid) { this.GRID = grid; this.M = grid.length; this.N = grid[0].length; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (GRID[i][j] == 1) { dfs(i, j); max = Math.max(max, island); island = 0; } } } return max; } private int[][] GRID; private int M; private int N; private int[][] dirs = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; private int island = 0; private int max = 0; private void dfs(int i, int j) { // 此处保障GRID[i][j] == 1 GRID[i][j] = 0; island++; for (int[] dir : dirs) { int x = i + dir[0]; int y = j + dir[1]; if (x >= 0 && x < M && y >= 0 && y < N && GRID[x][y] == 1) { dfs(x, y); } } }}四、总结小记2022/5/31 5月最初一天啦

一、题目粗心标签: 查找 https://leetcode.cn/problems/median-of-two-sorted-arrays 给定两个大小别离为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的工夫复杂度应该为 O(log (m+n)) 。 示例 1： 输出：nums1 = [1,3], nums2 = [2]输入：2.00000解释：合并数组 = [1,2,3] ，中位数 2示例 2： 输出：nums1 = [1,2], nums2 = [3,4]输入：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5提醒： nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106二、解题思路号称leetcode守门员的题。中位数能够来自于同一个数组，也能够来自于两个数组，能够是一个数，也能够是两个数。实现思路（参考花花酱的解说）分类：思路：假如n1,n2是两个数组的元素，那么k=(n1+n2+1)/2就示意左中位数或中位数的索引，假如从nums1中取m1个元素，从nums2中取m2个元素，那么m1+m2 = k。咱们要求的中位数就是从max(nums[m1-1], nums[m2-1])和min(nums[m1], nums[m2])。 ...

一、题目粗心标签: 查找 https://leetcode.cn/problems/single-element-in-a-sorted-array 给你一个仅由整数组成的有序数组，其中每个元素都会呈现两次，唯有一个数只会呈现一次。请你找出并返回只呈现一次的那个数。你设计的解决方案必须满足 O(log n) 工夫复杂度和 O(1) 空间复杂度。 示例 1: 输出: nums = [1,1,2,3,3,4,4,8,8]输入: 2示例 2: 输出: nums = [3,3,7,7,10,11,11]输入: 10提醒: 1 <= nums.length <= 1050 <= nums[i] <= 105 二、解题思路题目中是有序数组，每个元素呈现2次，假如数组索引i是偶数，如果nums[i] == nums[i+1]，阐明那个独自呈现的元素在i的左边；反之在i的右边 三、解题办法3.1 Java实现public class Solution { public int singleNonDuplicate(int[] nums) { int l = 0; int r = nums.length - 1; while (l < r) { int mid = l + (r - l) / 2; // 保障mid是偶数 mid = mid / 2 * 2; if (nums[mid] == nums[mid + 1]) { l = mid + 2; } else { r = mid; } } // 针对只有一个元素的数组，题目中曾经给出数组最小长度为1 return nums[l]; }}四、总结小记2022/5/29 周末也要保持每日一道

一、题目粗心标签: 查找 https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array 已知一个长度为 n 的数组，事后依照升序排列，经由 1 到 n 次 旋转 后，失去输出数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变动后可能失去：若旋转 4 次，则能够失去 [4,5,6,7,0,1,2]若旋转 7 次，则能够失去 [0,1,2,4,5,6,7]留神，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的后果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个元素值 互不雷同 的数组 nums ，它原来是一个升序排列的数组，并按上述情景进行了屡次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个工夫复杂度为 O(log n) 的算法解决此问题。 示例 1： 输出：nums = [3,4,5,1,2]输入：1解释：原数组为 [1,2,3,4,5] ，旋转 3 次失去输出数组。示例 2： 输出：nums = [4,5,6,7,0,1,2]输入：0解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次失去输出数组。示例 3： 输出：nums = [11,13,15,17]输入：11解释：原数组为 [11,13,15,17] ，旋转 4 次失去输出数组。提醒： ...

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（53）最大子数组和一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 解法1 “本人。贪婪法”。// 思路：// 1）状态初始化 l = nums.length; sum = 0, resMaxVal = Number.NEGATIVE_INFINITY; 。// 2）外围：遍历数组。// 2.1）外围：若 此时 sum < 0，阐明我还不如从0开始 —— 即重置sum为0。// 2.2）sum 加上以后值 num[i] 。// 2.3）依据 sum 状况，更新 resMaxVal 值。// 3）返回后果 resMaxVal 。var maxSubArray = function(nums) { // 1）状态初始化 l = nums.length; sum = 0, resMaxVal = Number.NEGATIVE_INFINITY; 。 const l = nums.length; let sum = 0, resMaxVal = Number.NEGATIVE_INFINITY; // 2）外围：遍历数组。 for (let i = 0; i < l; i++) { const tempVal = nums[i]; // 2.1）外围：若 此时 sum < 0，阐明我还不如从0开始 —— 即重置sum为0。 if (sum < 0) { sum = 0; } // 2.2）sum 加上以后值 num[i] 。 sum += tempVal; // 2.3）依据 sum 状况，更新 resMaxVal 值。 resMaxVal = Math.max(resMaxVal, sum); } // 3）返回后果 resMaxVal 。 return resMaxVal;}2 计划21)代码： ...

单词间隔单次——双指针 func findClosest(words []string, word1, word2 string) int { ans := len(words) index1, index2 := -1, -1 for i, word := range words { if word == word1 { index1 = i } else if word == word2 { index2 = i } if index1 >= 0 && index2 >= 0 { ans = min(ans, abs(index1-index2)) } } return ans}func abs(x int) int { if x < 0 { return -x } return x}func min(a, b int) int { if a > b { return b } return a}工夫复杂度：O(n)，其中 n 是数组words 的长度。须要遍历数组一次计算 word 1和word 2的最短距离，每次更新下标和更新最短距离的工夫都是 O(1)。这里将字符串的长度视为常数。 ...

一、题目粗心标签: 查找 https://leetcode.cn/problems/search-in-rotated-sorted-array-ii 已知存在一个按非降序排列的整数数组 nums ，数组中的值不用互不雷同。 在传递给函数之前，nums 在事后未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。 给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。 你必须尽可能减少整个操作步骤。 示例 1： 输出：nums = [2,5,6,0,0,1,2], target = 0输入：true示例 2： 输出：nums = [2,5,6,0,0,1,2], target = 3输入：false提醒： 1 <= nums.length <= 5000-104 <= nums[i] <= 104题目数据保障 nums 在事后未知的某个下标上进行了旋转-104 <= target <= 104进阶： ...

一、题目粗心标签: 查找 https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array 给定一个依照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始地位和完结地位。如果数组中不存在目标值 target，返回 [-1, -1]。 进阶： 你能够设计并实现工夫复杂度为 O(log n) 的算法解决此问题吗？示例 1： 输出：nums = [5,7,7,8,8,10], target = 8输入：[3,4]示例 2： 输出：nums = [5,7,7,8,8,10], target = 6输入：[-1,-1]示例 3： 输出：nums = [], target = 0输入：[-1,-1]提醒： 0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递加数组-109 <= target <= 109 二、解题思路给定一个增序的整数数组和一个值，查找该值第一次和最初一次呈现的地位。应用二分查找找左右区间。lower_bound返回的是开始的第一个满足条件的地位，upper_bound返回的是第一个不满足条件的地位。所以当两个返回值相等的时候示意没有找到，找到了须要返回的是{left, right - 1} 三、解题办法3.1 Java实现public class Solution2 { public int[] searchRange(int[] nums, int target) { int left = lower_bound(nums, target); int right = upper_bound(nums, target); if (left == right) { return new int[]{-1, -1}; } return new int[]{left, right - 1}; } private int lower_bound(int[] nums, int target) { int left = 0; int right = nums.length; int mid; while (left < right) { mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; } private int upper_bound(int[] nums, int target) { int left = 0; int right = nums.length; int mid; while (left < right) { mid = left + (right - left) / 2; if (nums[mid] > target) { right = mid; } else { left = mid + 1; } } return left; }}四、总结小记2022/5/26 二分查找l工夫复杂度O(logn)

一、题目粗心https://leetcode.cn/problems/sqrtx标签: 查找 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 因为返回类型是整数，后果只保留 整数局部 ，小数局部将被 舍去 。 留神：不容许应用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1：  输出：x = 4输入：2示例 2： 输出：x = 8输入：2解释：8 的算术平方根是 2.82842..., 因为返回类型是整数，小数局部将被舍去。提醒：  0 <= x <= 231 - 1 二、解题思路两个思路：二分法：sqrt = a / mid，判断sqrt == mid牛顿迭代法：x = (x x/a)/2，判断xx > a 三、解题办法3.1 Java实现-二分法public class Solution2 { public int mySqrt(int a) { // 留神：独自思考0，避免除以0的状况 if (a == 0) { return 0; } int left = 1; int right = a; int mid; int sqrt; // 留神：条件是 <= while (left <= right) { // 留神：这样写能够避免溢出 mid = left + (right - left) / 2; sqrt = a / mid; if (sqrt == mid) { // 间接返回，mid就是平方根 return mid; } else if (mid > sqrt) { right = mid - 1; } else { left = mid + 1; } } return right; }}3.2 Java实现-牛顿迭代法public class Solution { public int mySqrt(int a) { // 避免int越界，用long来存储乘法后果 long x = a; while (x * x > a) { x = (x + a / x) / 2; } return (int) x; }}四、总结小记2022/5/25 保持一天一道题，明天阴天

大家好，我是散步coding, 最近在整顿2022年LeetCode高频算法面试题 ,感觉好的, 能够点赞、珍藏哈。同时有补充的也欢送大家给出反馈。本文首发于公众号: 散步coding https://manbucoding.com/trave... 题目来源于 LeetCode 上第 1 号问题：两数之和。题目难度为 Easy。 题目形容给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你能够假如每种输出只会对应一个答案。然而，你不能反复利用这个数组中同样的元素。 题目难度: ★ 示例: 给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]示例 2： 输出：nums = [3,2,4], target = 6输入：[1,2]示例 3： 输出：nums = [3,3], target = 6输入：[0,1]题目解析应用查找表来解决该问题。 设置一个 map 容器 record 用来记录元素的值与索引，而后遍历数组 nums。 每次遍历时应用长期变量 complement 用来保留目标值与以后值的差值在此次遍历中查找 record ，查看是否有与 complement 统一的值，如果查找胜利则返回查找值的索引值与以后变量的值 i如果未找到，则在 record 保留该元素与索引值 i代码实现tips: 以下代码是应用Go代码实现的不同解法, 文章最初能够看C++、C、Java、Python实现1、暴力解法最容易想到的办法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。 ...

记录刷LeedCode过程

In software development process what is the meaning of debugging? How can you make sure that your code is both safe and fast? Name two tools which are used for keeping track of software requirements? Describe the architecture of your current project and how deployment is configured? Diff between abstract and interface Java program find the intersection of two rectangles https://blog.csdn.net/xia1500... RESTful API What do you think makes a good HTTP API? ...

D136 26. Remove Duplicates from Sorted Array题目链接26. Remove Duplicates from Sorted Array 题目剖析给定一个曾经排好序的数组，其中的整数会呈现反复。须要在不减少内存的状况下移除反复的元素。即不要新建数组。 留神，最初须要返回的是不反复的元素个数。 留神2，参数是以援用型传过来的。 解题思路一一遍历元素，先间接把以后元素从数组中移除。 当以后元素和前一个元素不雷同时，做3件事件： 在原数组中插入这个不反复的元素。记录以后数字，即最初呈现的数字。把下次要插入数字的下标标记为以后下标+1最终代码<?phpclass Solution { /** * @param Integer[] $nums * @return Integer */ function removeDuplicates(&$nums) { $index = 0; $prev = NULL; foreach($nums as $key => $num){ unset($nums[$key]); if($num !== $prev){ $nums[$index] = $num; $prev = $num; $index = $key + 1; } } return $index; }}若感觉本文章对你有用，欢送用爱发电赞助。

title: 每日一练（47）：找不同 categories:[剑指offer] tags:[每日一练] date: 2022/04/22 每日一练（47）：找不同给定两个字符串 s 和 t ，它们只蕴含小写字母。字符串 t 由字符串 s 随机重排，而后在随机地位增加一个字母。请找出在 t 中被增加的字母。 示例 1： 输出：s = "abcd", t = "abcde" 输入："e" 解释：'e' 是那个被增加的字母。 示例 2： 输出：s = "", t = "y" 输入："y" 提醒： 0 <= s.length <= 1000 t.length == s.length + 1 s 和 t 只蕴含小写字母 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：求和思路剖析本题是只增加一个字符，求 s 字符串的ASCII值和 t 的ASCII值 再 t - s 的ASCII值得到的就是增加的字符的ASCII值 char findTheDifference(string s, string t) { int as = 0, at = 0; for (auto ch : s) { as += ch; } for (auto ch : t) { at += ch; } return at - as;}办法二：位运算思路剖析如果将两个字符串拼接成一个字符串，则问题转换成求字符串中呈现奇数次的字符 ...

title: 每日一练（46）：两个数组的交加 categories:[剑指offer] tags:[每日一练] date: 2022/04/21 每日一练（46）：两个数组的交加给定一个蕴含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范畴内没有呈现在数组中的那个数。 示例 1： 输出：nums = [3,0,1] 输入：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范畴 [0,3] 内。2 是失落的数字，因为它没有呈现在 nums 中。 示例 2： 输出：nums = [0,1] 输入：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范畴 [0,2] 内。2 是失落的数字，因为它没有呈现在 nums 中。 示例 3： 输出：nums = [9,6,4,2,3,5,7,0,1] 输入：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范畴 [0,9] 内。8 是失落的数字，因为它没有呈现在 nums 中。 示例 4： 输出：nums = [0] ...

title: 每日一练（45）：长度最小的子数组 categories:[剑指offer] tags:[每日一练] date: 2022/04/19 每日一练（45）：长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 间断子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 示例 1： 输出：target = 7, nums = [2,3,1,2,4,3] 输入：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2： 输出：target = 4, nums = [1,4,4] 输入：1 示例 3： 输出：target = 11, nums = [1,1,1,1,1,1,1,1] 输入：0 提醒： 1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105 起源：力扣（LeetCode） ...

title: 每日一练（44）：无效的字母异位词 categories:[剑指offer] tags:[每日一练] date: 2022/04/18 每日一练（44）：无效的字母异位词给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 留神：若 s 和 t 中每个字符呈现的次数都雷同，则称 s 和 t 互为字母异位词。 示例 1: 输出: s = "anagram", t = "nagaram" 输入: true 示例 2: 输出: s = "rat", t = "car" 输入: false 提醒: 1 <= s.length, t.length <= 5 * 104 s 和 t 仅蕴含小写字母 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：排序思路剖析t 是 s 的异位词等价于「两个字符串排序后相等」。因而咱们能够对字符串 s 和 t 别离排序，看排序后的字符串是否相等即可判断。此外，如果 s 和 t 的长度 ...

title: 每日一练（43）：同构字符串 categories:[剑指offer] tags:[每日一练] date: 2022/04/15 每日一练（43）：同构字符串给定两个字符串 s 和 t ，判断它们是否是同构的。 如果 s 中的字符能够按某种映射关系替换失去 t ，那么这两个字符串是同构的。 每个呈现的字符都该当映射到另一个字符，同时不扭转字符的程序。不同字符不能映射到同一个字符上，雷同字符只能映射到同一个字符上，字符能够映射到本人自身。 示例 1: 输出：s = "egg", t = "add" 输入：true 示例 2： 输出：s = "foo", t = "bar" 输入：false 示例 3： 输出：s = "paper", t = "title" 输入：true 提醒： 1 <= s.length <= 5 * 104 t.length == s.length s 和 t 由任意无效的 ASCII 字符组成 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一思路剖析t.length == s.length 所以无需思考长度 雷同的字符用find找到的index肯定是一样的 利用这点咱们能够利用find来验证是否pattern雷同 ...

title: 每日一练（42）：Excel表序号 categories:[剑指offer] tags:[每日一练] date: 2022/04/14 每日一练（42）：Excel表序号给你一个字符串 columnTitle ，示意 Excel 表格中的列名称。返回 该列名称对应的列序号 。 例如： A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ... 示例 1: 输出: columnTitle = "A" 输入: 1 示例 2: 输出: columnTitle = "AB" 输入: 28 示例 3: 输出: columnTitle = "ZY" 输入: 701 提醒： 1 <= columnTitle.length <= 7 columnTitle 仅由大写英文组成 columnTitle 在范畴 ["A", "FXSHRXW"] 内 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一： 进制转换（从前到后）思路剖析这道题要求将 Excel 表中的列名称转换成绝对应的列序号。因为 Excel 表的列名称由大写字母组成，大写字母共有 26 个，因而列名称的 ...

title: 每日一练（41）：Excel表列名称 categories:[剑指offer] tags:[每日一练] date: 2022/04/13 每日一练（41）：Excel表列名称给你一个整数 columnNumber ，返回它在 Excel 表中绝对应的列名称。 例如： A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ... 示例 1： 输出：columnNumber = 1 输入："A" 示例 2： 输出：columnNumber = 28 输入："AB" 示例 3： 输出：columnNumber = 701 输入："ZY" 示例 4： 输出：columnNumber = 2147483647 输入："FXSHRXW" 提醒： 1 <= columnNumber <= 231 - 1 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一： 从1开始的26进制转换思路剖析失常的26进制显示数字应该是0-25，而本题是1-26，那么在解决每一位之前进行减一，即可变成失常进制转换操作。 string convertToTitle(int columnNumber) { string ans; do { columnNumber--; ans = char(columnNumber % 26 + 'A') + ans;//失去字符列名称 columnNumber /= 26; } while(columnNumber > 0); return ans;}办法二：取余+反转思路剖析当余数为0时，咱们不能取@而是应该取Z ...

题目： 给你一个有序数组 nums ，请你 原地 删除反复呈现的元素，使每个元素 最多呈现两次 ，返回删除后数组的新长度。 不要应用额定的数组空间，你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。 1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums 已按升序排列题解： 首先，这是一道数组类的简略算法题。咱们明确循环不变式（loop invariant）的概念，即一组在循环体内、每次迭代均放弃为真的性质。 先贴代码：（GO语言） func removeDuplicates(nums []int) int { n := len(nums) if n < 3 { return n } slow, fast := 2, 2 for fast < n { if nums[slow-2] != nums[fast] { nums[slow] = nums[fast] slow++ } fast++ } return slow}咱们设置的循环不变式：slow指针之前的数组元素（不蕴含目前所指元素）最多有两个反复。同时应用快慢指针的形式。 初始slow设为2，即nums[2]之前的元素不反复，因为nums[2]之前最多有两个元素，肯定不会呈现两个以上的反复，所以slow地位满足不变式要求。接下来的循环中，如果nums[fast]与nums[slow-2]不雷同，则将nums[fast]赋值给nums[slow]后后移slow，完结本次循环。如果nums[fast]与nums[slow-2]雷同，则间接完结本次循环。每次循环，slow地位均满足不变式要求。最终fast指针遍历完数组元素后，完结整个循环，slow地位满足不变式要求。因而在循环完结后，slow左侧元素最多只有两个反复元素，合乎算法要求。 复杂度剖析： ...

题目： 给你一个 升序排列 的数组 nums ，请你 原地 删除反复呈现的元素，使每个元素 只呈现一次 ，返回删除后数组的新长度。元素的 绝对程序 应该放弃 统一 。 因为在某些语言中不能扭转数组的长度，所以必须将后果放在数组nums的第一局部。更标准地说，如果在删除反复项之后有 k 个元素，那么 nums 的前 k 个元素应该保留最终后果。 将最终后果插入 nums 的前 k 个地位后返回 k 。 不要应用额定的空间，你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。 0 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums 已按 升序 排列题解： 首先，这是一道数组类的简略算法题。咱们明确循环不变式（loop invariant）的概念，即一组在循环体内、每次迭代均放弃为真的性质。 先贴代码：（GO语言） func removeDuplicates(nums []int) int { n := len(nums) if n < 2 { return n } slow, fast := 1, 1 for fast < n { if nums[fast-1] != nums[fast] { nums[slow] = nums[fast] slow++ } fast++ } return slow咱们设置的循环不变式：slow指针之前的数组元素（不蕴含目前所指元素）不反复。同时应用快慢指针的形式。 ...

题目： 给你一个数组 nums 和一个值 val，你须要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要应用额定的数组空间，你必须仅应用 O(1) 额定空间并 原地 批改输出数组。 元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素 0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100题解： 首先，这是一道数组类的简略算法题。咱们明确循环不变式（loop invariant）的概念，即一组在循环体内、每次迭代均放弃为真的性质。 先贴代码：（GO语言） func removeElement(nums []int, val int) int { left, right, n := 0, 0, len(nums) for right < n { if nums[right] != val { nums[left] = nums[right] left++ } right++ } return left}咱们设置的循环不变式：left指针之前的数组元素（不蕴含目前所指元素）不为val。 初始left设为0，即nums[0]之前的元素不为val，因为nums[0]之前没有元素，left地位满足不变式要求。接下来的循环中，如果nums[right]不为val，则将nums[right]赋值给nums[left]后后移left，完结本次循环。如果nums[right]为val，则间接完结本次循环。每次循环，left地位均满足不变式要求。最终right指针遍历完数组元素后，完结整个循环，left地位满足不变式要求。因而在循环完结后，left左侧元素均为非val元素，合乎算法要求。 复杂度剖析： 工夫复杂度：O(n)，其中n为序列长度。每个地位至少被遍历两次。空间复杂度：O(1)。只须要常数的空间寄存若干变量。优化：咱们留神到，题目中还有一个阐明，“元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素”，也就是说，咱们能够通过放弃原数组元素的地位不变来缩小赋值次数。当val非常少的时候，原办法会呈现大量的冗余赋值，缩小赋值次数是对性能的一个大的晋升。 先贴代码：（GO语言） func removeElement(nums []int, val int) int { left, right := 0, len(nums)-1 for right >= left { if nums[right] != val { nums[left], nums[right] = nums[right], nums[left] left++ } else { right-- } } return left}同样，咱们的循环不变量放弃不变，即left指针之前的数组元素（不蕴含目前所指元素）不为val。设置数组首尾指针，循环终止条件为right >= left以保障所有元素均被遍历过一次。循环中保护不变式，最终后果满足题目要求。 ...

title: 每日一练（40）：验证回文串 categories:[剑指offer] tags:[每日一练] date: 2022/04/12 每日一练（40）：验证回文串给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。 阐明：本题中，咱们将空字符串定义为无效的回文串。 示例 1: 输出: "A man, a plan, a canal: Panama" 输入: true 解释："amanaplanacanalpanama" 是回文串 示例 2: 输出: "race a car" 输入: false 解释："raceacar" 不是回文串 提醒： 1 <= s.length <= 2 * 105 字符串 s 由 ASCII 字符组成 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：字符串预处理 + 双指针思路剖析isalnum：判断字符变量c是否为字母或数字，若是则返回非零，否则返回零。 tolower：把字母字符转换成小写，非字母字符不做出解决 1.先把字符串s做解决 2.双指针判断，左指针指向第一个地位，右指针指向最初一个地位，顺次判断是否雷同 bool isPalindrome(string s) { string str; for (const char &ch : s) { if (isalnum(ch)) { str.push_back(tolower(ch));// 将数字和字母保留在 str 中，大写字母转换成小写 } } // 左指针指向第一个地位，右指针指向最初一个地位 // 顺次比拟是否雷同 int l = 0, r = str.size() - 1; while (l < r) { if (str[l] != str[r]) { return false; } l++; r--; } return true;}办法二：筛选 + 判断思路剖析对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样咱们只须要判断 sgood 是否是一 ...

title: 每日一练（39）：二进制求和 categories:[剑指offer] tags:[每日一练] date: 2022/04/11 每日一练（39）：二进制求和给你两个二进制字符串，返回它们的和（用二进制示意）。 输出为 非空 字符串且只蕴含数字 1 和 0。 示例 1: 输出: a = "11", b = "1" 输入: "100" 示例 2: 输出: a = "1010", b = "1011" 输入: "10101" 提醒： 每个字符串仅由字符 '0' 或 '1' 组成。 1 <= a.length, b.length <= 10^4 字符串如果不是 "0" ，就都不含前导零。 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：模仿运算思路剖析模仿间接计算，就是依照相似10进制计算形式，思考进位 string addBinary(string a, string b) { // 先倒序 reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int na = a.size(); int nb = b.size(); int n = max(na, nb); string res = ""; int curr = 0; for (int i = 0; i < n; ++i) { curr += i < na ? a[i] == '1' : 0; curr += i < nb ? b[i] == '1' : 0; res.push_back(curr % 2 ? '1' : '0'); curr /= 2; } if (curr) { res.push_back('1'); } reverse(res.begin(), res.end()); return res;}办法二：模仿运算优化（LeetCode英文网站大佬写法）思路剖析模仿间接计算，就是依照相似10进制计算形式，思考进位 ...

给定一个由 0 和 1 组成的非空二维数组 grid ，用来示意陆地岛屿地图。一个 岛屿 是由一些相邻的 1 (代表土地) 形成的组合，这里的「相邻」要求两个 1 必须在程度或者竖直方向上相邻。你能够假如 grid 的四个边缘都被 0（代表水）突围着。找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。 示例 1: 输出: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]输入: 6解释: 对于下面这个给定矩阵应返回 6。留神答案不应该是 11 ，因为岛屿只能蕴含程度或垂直的四个方向的 1 。 示例 2: 输出: grid = [[0,0,0,0,0,0,0,0]]输入: 0 提醒： m == grid.length n == grid[i].length 1 <= m, n <= 50 grid[i][j] is either 0 or 1解题思路遍历记录拜访过和未拜访过的岛屿；如果为岛屿则将状态置为已拜访；别离向上下左右进行遍历，记录岛屿的数量，并且置以后岛屿为已拜访；依据大的岛屿，更新岛屿记录解题代码及其正文/** * @param {number[][]} grid * @return {number} */var maxAreaOfIsland = function (grid) { let col = grid.length,row = grid[0].length,max=0; //行、列 //未拜访过的岛屿为1，拜访过的岛屿为0 let matrix = [...Array(col)].fill(0).map(()=> [...Array(row)].fill(1)) let dfs = (i,j)=>{ //边界 if(i<0 || i>=col || j<0 || j>=row) return 0; let ret=0; let temp = matrix[i][j] //是否为岛屿 matrix[i][j] = 0 //拜访过的岛屿标记为 0 if(grid[i][j] && temp){ ret+=dfs(i+1,j) //下 ret+=dfs(i-1,j) //上 ret+=dfs(i,j+1) //右 ret+=dfs(i,j-1) //左 ret++ } return ret } for(let i=0;i<col;i++){ for(let j=0;j<row;j++){ if(grid[i][j]===1){ //更新岛屿记录 max = Math.max(max,dfs(i,j)) } } } return max};总结【DFS】深度优先搜索算法(Depth-First-Search):是一种用于遍历或搜寻树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜寻树的分支。当节点v的所在边都己被探寻过或者在搜查时结点不满足条件，搜寻将回溯到发现节点v的那条边的起始节点。整个过程重复进行直到所有节点都被拜访为止。深度优先搜寻是基于栈实现的,Stack 先入后出。 ...

title: 每日一练（38）：最初一个单词的长度 categories:[剑指offer] tags:[每日一练] date: 2022/04/09 每日一练（38）：最初一个单词的长度给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最初一个 单词的长度。 单词 是指仅由字母组成、不蕴含任何空格字符的最大子字符串。 示例 1： 输出：s = "Hello World" 输入：5 解释：最初一个单词是“World”，长度为5。 示例 2： 输出：s = " fly me to the moon " 输入：4 解释：最初一个单词是“moon”，长度为4。 示例 3： 输出：s = "luffy is still joyboy" 输入：6 解释：最初一个单词是长度为6的“joyboy”。 提醒： 1 <= s.length <= 104 s 仅有英文字母和空格 ' ' 组成 s 中至多存在一个单词 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：双指针法思路剖析定义两个指针指向字符串的开端，若字符串开端为空格，指针同时前移 i--; j--; 若遇到非空格，那么固定 j 不动，示意单词的开端地位，持续前移 i ,直到再次遇到空格，或者遍历完字符串； 最初，i 指向的地位是最初一个单词结尾的前一个地位， j - i 即为最初一个单词的长度。 ...

无反复字符的最长子串——滑动窗口+哈希 一刷：https://segmentfault.com/a/11... 二刷https://leetcode-cn.com/probl... func lengthOfLongestSubstring(s string) int { var n = len(s) if n <= 1 { return n } var maxLen = 1 var left, right, window = 0, 0, [128]int{} for right < n { var rightChar = s[right] var rightCharIndex = window[rightChar] if rightCharIndex > left { left = rightCharIndex } if right - left + 1 > maxLen { maxLen = right - left + 1 } window[rightChar] = right + 1 right++ } return maxLen}成果 ...

title: 每日一练（37）：实现 strStr() categories:[剑指offer] tags:[每日一练] date: 2022/03/21 每日一练（37）：实现 strStr()实现 strStr() 函数。 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串呈现的第一个地位（下标从 0 开始）。如果不存在，则返回 -1 。 阐明： 当 needle 是空字符串时，咱们该当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时咱们该当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 示例 1： 输出：haystack = "hello", needle = "ll" 输入：2 示例 2： 输出：haystack = "aaaaa", needle = "bba" 输入：-1 示例 3： 输出：haystack = "", needle = "" 输入：0 提醒： 0 <= haystack.length, needle.length <= 5 * 104 ...

题目：在字符串 s 中找出第一个只呈现一次的字符。如果没有，返回一个单空格。 s 只蕴含小写字母。 链接： 力扣Leetcode—剑指Offer—面试题50. 第一个只呈现一次的字符. 示例 1： 输出：s = "abaccdeff"输入：'b'示例 2: 输出：s = "" 输入：' '思路：用哈希表存储频数，遍历两次字符串，第一次遍历，用哈希映射统计出字符串中每个字符呈现的次数。第二次遍历，遍历到了一个只呈现一次的字符，那么就返回该字符，否则在遍历完结后返回空格。 Go代码： package mainimport "fmt"func firstUniqChar(s string) byte { var res [26]int for _, v := range s { res[v-'a']++ } for i, ch := range s { if res[ch-'a'] == 1 { //这里千万不能写成res[i]==1，因为res后面的元素程序对应为abcd，他们的值可能为1然而不肯定是在s中第一个呈现一次的字符 return s[i] } } return ' '}func main() { fmt.Println(firstUniqChar("abaccdeff"))}提交截图：

验证IP地址 分治strings.Split(string,byte)//字符串的拆分 对于 IPv4 地址，通过界定符 . 将地址分为四块；对于 IPv6 地址，通过界定符 : 将地址分为八块。对于 IPv4 地址的每一块，查看它们是否在 0 - 255 内，且没有前置零。对于 IPv6 地址的每一块，查看其长度是否为 1 - 4 位的十六进制数。 func validIPAddress(IP string) string { if validIPv4Address(IP) { return "IPv4" } if validIPv6Address(IP) { return "IPv6" } return "Neither"}func validIPv4Address(IP string) bool { strArr := strings.Split(IP, ".") if len(strArr) != 4 { return false } for _, str := range strArr { num, err := strconv.Atoi(str) if err != nil || num > 255 || num < 0 { //留神：err != nil return false } newStr := fmt.Sprint(num) if str != newStr { return false } } return true}func validIPv6Address(IP string) bool { strArr := strings.Split(IP, ":") if len(strArr) != 8 { return false } for _, str := range strArr { if len(str) == 0 || len(str) > 4 { return false } for i := 0; i < len(str); i++ { if !(str[i] >= '0' && str[i] <= '9') && !(str[i] >= 'a' && str[i] <= 'f') && !(str[i] >= 'A' && str[i] <= 'F') { return false } } } return true}正则需二刷 ...

春招季降临，大家陆续曾经开始筹备面试斩获心仪 offer。 这次 lucifer 就从面试官角度给大家分享一些面试技巧，让大家面试时少走弯路。这次分享偏重算法面试。 我负责公司的面试曾经有 5 年以上了，根本都是初面和二面，因而技术面试的层面比拟深，更多的是理解候选人的技术能力是否达标。在这几年工夫，我前前后后也面试了很多的候选人。这些人中有的技术能力不行，但也有些人很惋惜，技术能力是能够的，然而却没能通过我的面试，为什么呢？ 面试考查什么？首先，通常判断候选人是否能够通过面试有如下几个规范： 技能是否胜任沟通能力如何工作激情如何。。。 那么我面试的时候必定也是围绕下面开展的，只不过偏重考查不同罢了。 算法题和编程题实际上可能很好地测验以上信息，而不仅仅是测验能力是否胜任。前提是面试官不能太死板，比方间接扔一个网上原题，有的甚至本人都不太会就拿进去考，这必定是不行的。 有同学反馈算法题目做进去了，然而却挂了面试。这又是为什么呢？ 除了想当然的那种做的很好，实际上 corner case 没思考到或者不是最优解。还是有可能会被挂，为什么呢？ 其实你题目做的很好，仅仅能够证实能力能够胜任，这不意味着其余也满足要求，比方下面提到的沟通能力，工作激情等等。 那么如何更好地展现本人，给面试官留下更好的印象从而通过面试呢？除了进步本人的技术实力之外，办法也很重要。这里我就总结了几个技巧给大家。 算法面试根本步骤我在网上找到一份《Interview Cheat Sheet》，这个 PDF 列举了面试的模板步骤，具体批示了如何一步步实现面试。这个 pdf 结尾就提到了好的代码三个规范： 可读性工夫复杂度空间复杂度这写的太好了。 紧接着，列举了 15 算法面试的步骤。比方步骤一：当面试官发问完后，你须要先下来关键点（之后再上面写正文和代码） 看完我的感触就是，面试只有依照这个来做，成功率蹭蹭晋升。 pdf 地址 多问几次，确保题目了解正确。比方输入输出，corner case 等等。试想一个共事拿到需要不分青红皂白就去做，后果发现做进去的不对，多难堪？你会想和这样的共事一起共事么？ 比方你能够问： 须要思考正数么？后果的程序重要么？能够应用额定空间么？。。。先说思路，再写代码。尽管题目了解没问题，然而可能思路基本不对，或者面试官不想要这个解法。 试想你是面试官， 对面写了半天代码。思路基本就不对或者不是你想要的解法，是不是有点悲观？ 所以尽量先说思路，面试官感觉没问题再写，不要节约彼此的工夫。 比方你能够说： 奢侈的暴力的思路是：xxxx。而这么做的话工夫复杂度是 xxxx。奢侈的暴力算法的瓶颈在于 xxx，咱们能够应用 xxxx 算法进行优化，这样复杂度能够优化到 xxxx。上一步骤给面试官讲思路的时候，代入几个例子。corner case 和 normal case 都至多举一个来阐明。这样不仅让面试官感觉你沟通能力强，而且能够帮忙你进一步了解题目以及理清思路。 有点时候大家面试比拟缓和，通过代入例子解说紧张感会缓缓缩小。就如同我做技术分享，往往缓和的就是后面几分钟，前面就不会有缓和的感觉了。 比方你能够说： 当输出为 [1,2,3,4] 时， 咱们的先 xxxx， 这样就 xxxx，接下来计算出 xxxx ，最初 xxxx 。当输出为正数时，咱们能够间接返回 xxx。写代码要快，不要来来回回改，不然就会被扣上 coding 不行的帽子。其实有后面的铺垫，写快不难。因为后面其实讲思路，通过例子讲解法你曾经对算法很理解了才对。 ...

解题思路要验证一个数字是否是对称的，只须要将它的信息保留到一个能够实现翻转的数据类型就好了 步骤将数据类型转换成str验证生成的str是否对称原题链接欢送在我的博客摸索更多思路 代码class Solution(object): def isPalindrome(self, x): str_num=str(x) if str_num==str_num[::-1]: return True else: return False

字符串相加题目 官解-惯例解法func addStrings(num1 string, num2 string) string { add := 0 ans := "" for i, j := len(num1) - 1, len(num2) - 1; i >= 0 || j >= 0 || add != 0; i, j = i - 1, j - 1 { var x, y int if i >= 0 { x = int(num1[i] - '0') } if j >= 0 { y = int(num2[j] - '0') } result := x + y + add ans = strconv.Itoa(result%10) + ans add = result / 10 } return ans}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。成果 ...

解题思路设nums长度为n，区间[1,n+1]中，第一个未呈现在nums中的数即为题目所求 步骤将nums转换为set()遍历range(1,len(set_num)+1)，检测是否这些正整数存在于nums中（if i+1 in set工夫复杂度为O(1)）因为此处遍历set而不是list，所以速度更快原题链接欢送在我的博客轻松摸索更多思路 代码class Solution(object): def firstMissingPositive(self, nums): set_num=set(nums) for i in range(len(set_num)+1): if i+1 in set_num: continue else: return i+1 return 0

正则表达式匹配——基于字符串的高级动静布局/回溯/自动机1动静布局//不是很懂，等刷动静布局的时候再来二刷 https://leetcode-cn.com/probl...//这个如同讲得比官解好一些 func isMatch(s string, p string) bool { m, n := len(s), len(p) matches := func(i, j int) bool { if i == 0 { return false } if p[j-1] == '.' { return true } return s[i-1] == p[j-1] } f := make([][]bool, m + 1) for i := 0; i < len(f); i++ { f[i] = make([]bool, n + 1) } f[0][0] = true for i := 0; i <= m; i++ { for j := 1; j <= n; j++ { if p[j-1] == '*' { f[i][j] = f[i][j] || f[i][j-2] if matches(i, j - 1) { f[i][j] = f[i][j] || f[i-1][j] } } else if matches(i, j) { f[i][j] = f[i][j] || f[i-1][j-1] } } } return f[m][n]}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。2递归https://leetcode-cn.com/probl... ...

零 题目：算法（leetode，附思维导图 + 全副解法）300题之（2119）反转两次的数字一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “模拟法”。// 思路：// 1）通过 反转num 失去 reversed1 ，通过 反转reversed1 失去 reversed2 。// 2）return reversed2 === num 。var isSameAfterReversals = function(num) { // 1）通过 反转num 失去 reversed1 ，通过 反转reversed1 失去 reversed2 。 const reversed1 = parseInt(String(num).split('').reverse().join('')), reversed2 = parseInt(String(reversed1).split('').reverse().join('')); // 2）return reversed2 === num 。 return reversed2 === num;};2 计划21)代码： // 计划2 “察看、技巧（即数学法）法”。// 技巧：题干中、 “反转之后不保留前导零 ” --> 原始数不能开端为0（即 num % 10 !== 0 ） ，// 但留神 num = 0 时是符合条件的！var isSameAfterReversals = function(num) { return (num === 0) || (num % 10 !== 0);}四 资源分享 & 更多1 历史文章 - 总览 ...

翻转单词程序重点1.删除字符串中冗余的空格 2.字符串翻转函数 func reverseWords(s string) string { //1.应用双指针删除冗余的空格 slowIndex, fastIndex := 0, 0 b := []byte(s) //删除头部冗余空格 for len(b) > 0 && fastIndex < len(b) && b[fastIndex] == ' ' { fastIndex++ } //删除单词间冗余空格 for ; fastIndex < len(b); fastIndex++ { if fastIndex-1 > 0 && b[fastIndex-1] == b[fastIndex] && b[fastIndex] == ' ' { continue } b[slowIndex] = b[fastIndex] slowIndex++ } //删除尾部冗余空格 if slowIndex-1 > 0 && b[slowIndex-1] == ' ' { b = b[:slowIndex-1] } else { b = b[:slowIndex] } //2.反转整个字符串 reverse(&b, 0, len(b)-1) //3.反转单个单词 i单词开始地位，j单词完结地位 i := 0 for i < len(b) { j := i for ; j < len(b) && b[j] != ' '; j++ { } reverse(&b, i, j-1) i = j i++ } return string(b)}func reverse(b *[]byte, left, right int) { for left < right { (*b)[left], (*b)[right] = (*b)[right], (*b)[left] left++ right-- }}把字符串转换为整数——自动机/正则表达式/字符串——披着字符串皮的其余标签题 ...

第一次只呈现一次的字符——字符串的遍历&哈希表表存储字符呈现次数 func firstUniqChar(s string) byte { cnt := [26]int{} for _, ch := range s { cnt[ch-'a']++ } for i, ch := range s { if cnt[ch-'a'] == 1 { return s[i] } } return ' '}左旋转字符串——字符串解决在golang中能够间接对字符串的字符索引进行操作，相似于字符数组 func reverseLeftWords(s string, n int) string { s1:=s[:n] s2:=s[n:] return s2+s1}

替换空格——字符串的批改1.遍历字符串，用新的字符串返回后果 工夫，空间复杂化均为O（n） 代码如下 func replaceSpace(s string) string { var res string for _,v:=range s{ if v==' '{ res=res+"%20" }else{ res=res+string(v) } } return res}成果如下 2.占用内存空间较小的办法 golang中字符串是无奈批改的，要对字符串进行操作应将其转化为字符数组 例如 var str string = "hello"strBytes := []byte(str)strBytes[0] = 'H'str = string(strBytes)fmt.Println(str)题解 func replaceSpace(s string) string { b := []byte(s) length := len(b) spaceCount := 0 // 计算空格数量 for _, v := range b { if v == ' ' { spaceCount++ } } // 扩大原有切片 resizeCount := spaceCount * 2 tmp := make([]byte, resizeCount) b = append(b, tmp...) i := length - 1 j := len(b) - 1 for i >= 0 { if b[i] != ' ' { b[j] = b[i] i-- j-- } else { b[j] = '0' b[j-1] = '2' b[j-2] = '%' i-- j = j - 3 } } return string(b)}作者：carlsun-2链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/jian-zhi-offer-05-ti-huan-kong-ge-shuang-cgk3/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。成果 ...

title: 每日一练（36）：无效的括号 categories:[剑指offer] tags:[每日一练] date: 2022/03/15 每日一练（36）：无效的括号给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否无效。 无效字符串需满足： 左括号必须用雷同类型的右括号闭合。 左括号必须以正确的程序闭合。 示例 1： 输出：s = "()" 输入：true 示例 2： 输出：s = "()[]{}" 输入：true 示例 3： 输出：s = "(]" 输入：false 示例 4： 输出：s = "([)]" 输入：false 示例 5： 输出：s = "{[]}" 输入：true 提醒： 1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：栈+哈希表思路剖析无效括号字符串的长度，肯定是偶数！右括号后面，必须是绝对应的左括号，能力对消！右括号后面，不是对应的左括号，那么该字符串，肯定不是无效的括号！bool isValid(string s) { if (s.size() % 2) { return false; } unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; stack<char> stk; for (char ch : s) { if (pairs.count(ch)) { if (stk.empty() || stk.top() != pairs[ch]) { return false; } stk.pop(); } else { stk.push(ch); } } return stk.empty();}办法二：栈bool isValid(string s) { if (s.size() % 2) { return false; } stack<char> st; for (auto ss : s) { if (ss == '(') { st.push(')'); } else if (ss == '[') { st.push(']'); } else if (ss == '{') { st.push('}'); } else { if (st.empty() || st.top() != ss) { return false; } else { st.pop(); } } } return st.empty();}

解题思路因为[i,j,k]三元组中i的地位是惟一的，所以咱们能够固定i位对数组points进行遍历。由高中学的排列组合的常识咱们失去，以points[i]为i点、间隔为l的boomerang的个数等于x*（x-1）（也就是A（x,2）），其中x为与points[i]的间隔等于l的点的个数。咱们只有把这些x*（x-1）都加起来就能失去题目的答案步骤遍历数组points，将每个元素points[i]设置为[i,j,k]中的i点再次遍历数组points，计算从points[i]到其余点的间隔的平方（因为间隔的平方与间隔是一一对应的关系，这里应用间隔的平方以节俭计算工夫），将这些间隔的平方贮存在列表list_distance中应用计数器cnt计算list_distance中每个数字呈现的次数x将x*（x-1）累计入num_boomerang原题链接欢送在我的博客轻松摸索更多思路 代码class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int: from collections import Counter if len(points)==1: return 0 num_boomerang=0 for i in range(len(points)): list_distance=[] for j in range(len(points)): if j==i: continue else: list_distance.append(pow(points[i][0]-points[j][0],2)+pow(points[i][1]-points[j][1],2)) cnt=Counter(list_distance) for k in cnt: if cnt[k]>1: num_boomerang+=cnt[k]*(cnt[k]-1) return int(num_boomerang)

title: 每日一练（35）：最长公共前缀 categories:[剑指offer] tags:[每日一练] date: 2022/03/14 每日一练（35）：最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例 1： 输出：strs = ["flower","flow","flight"] 输入："fl" 示例 2： 输出：strs = ["dog","racecar","car"] 输入："" 解释：输出不存在公共前缀。 提醒： 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：逐字符比拟思路剖析先第一个和第二个比，保留公共前缀，再和第三个比，以此类推 string longestCommonPrefix(vector<string>& strs) { if (strs.size() == 0) { return ""; } string ans = strs[0];//先从strs[0]开始，与前面一个比拟 for (int i = 0; i < strs.size(); i++) { string s = ans;//保留上次的公共前缀 ans = ""; for (int j = 0; j < strs[i].size(); j++) { if (s[j] == strs[i][j]) { ans += s[j]; } else { //遇到不一样的就退出循环 break; } } if (ans == "") { break; } } return ans;}办法二：双指针算法流程： ...

原题链接https://leetcode-cn.com/probl... 解题思路遍历数组nums，因为num[:i]的值咱们已不再关怀，所以把这部分的空间用作备忘录遍历过后nums[i]处的值等于：1.以nums[i]结尾的2.子数组的3.最大和 欢送在我的博客轻松摸索更多思路 代码class Solution: def maxSubArray(self, nums: List[int]) -> int: if len(nums)==1: return nums[0] for i in range(1,len(nums)): if nums[i-1]>0: nums[i]+=nums[i-1] return max(nums)

题目：统计一个数字在排序数组中呈现的次数。 链接： 力扣Leetcode—剑指Offer—数组—53 - I. 在排序数组中查找数字 I. 示例 1： 输出: nums = [5,7,7,8,8,10], target = 8输入: 2示例 2: 输出: nums = [5,7,7,8,8,10], target = 6输入: 0思路： 法一：遍历数组，用哈希表存储每个数呈现的次数，再找出要的那个数呈现的次数即可法二：也是遍历，间接遇到和要求一样的数字，次数就加一法一Go代码： package mainimport "fmt"func search(nums []int, target int) int { m := make(map[int]int) var res int for _, v := range nums { m[v]++ } for key, v := range m { if key == target { res = v } } return res}func main() { a := []int{5, 7, 7, 8, 8, 10} fmt.Println(search(a, 8))}提交截图： ...

原文：https://dushusir.com/leetcode... 问题给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范畴 [1, n] 内，且每个整数呈现 一次 或 两次 。请你找出所有呈现 两次 的整数，并以数组模式返回。 你必须设计并实现一个工夫复杂度为 O(n) 且仅应用常量额定空间的算法解决此问题。 示例 1： 输出：nums = [4,3,2,7,8,2,3,1] 输入：[2,3] 示例 2： 输出：nums = [1,1,2] 输入：[1] 示例 3： 输出：nums = [1] 输入：[] 提醒： n == nums.length1 <= n <= 1051 <= nums[i] <= nnums 中的每个元素呈现 一次 或 两次解法一思路： 利用 Set 值惟一的个性，一直向一个空的 Set 外面增加 nums 中的数字，再应用 set.add办法，通过获取 set 长度是否减少来判断是否有反复数字呈现。 代码： /** * @param {number[]} nums * @return {number[]} */var findDuplicates = function(nums) { const set = new Set() // 惟一值测验 const result = [] // 后果数组 nums.forEach(n => { const preSize = set.size // 应用 set.add 办法，通过获取 set 长度是否减少来判断是否有反复数字呈现 set.add(n) // 发现反复数字 if(preSize === set.size){ result.push(n) } }) return result};解法二思路： ...

题目：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有肯定的价值（价值大于 0）。你能够从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下挪动一格、直到达到棋盘的右下角。给定一个棋盘及其下面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 链接： 力扣Leetcode—剑指Offer—数组—47.礼物的最大价值. 示例 1： 输出: [ [1,3,1], [1,5,1], [4,2,1]]输入: 12解释: 门路 1→3→5→2→1 能够拿到最多价值的礼物思路：用前缀和的形式解决，用双重for循环，如下： 外层for从第2行开始，最初1行完结内层for从第2列开始，最初1列完结比拟左方和上方的值，并取其中较大者，加到以后地位的值上返回最右下角的值就拿上面的例子来讲： [1,3,1][1,5,1][4,2,1]把 第1行 和 第1列 别离用前缀和的形式解决，失去： [1,4,5][2,5,1][6,2,1]再遍历残余地位，也就是从第二行第二列开始，取以后地位的上边和右边中的较大者，加到以后地位的值上： [1,4,5][2,5,1][6,2,1]加粗局部为所要遍历的地位 先从加粗的5开始(第2行，第2列)取右边(2)和上边(4)的较大者(4)加到以后地位的值(5)上失去第2行，第2列： [1,4,5][2,9,1][6,2,1]反复上述步骤，顺次失去: 已解决第2行，第3列 (1 + max(9, 5) = 1 + 9 = 10)： [1,4,5][2,9,10][6,2,1]已解决第3行，第2列 (2 + max(9, 6) = 2 + 9 = 11)： [1,4,5][2,9,10][6,11,1]已解决第3行，第3列 (1 + max(11, 10) = 1 + 11 = 12)： [1,4,5][2,9,10][6,11,12]全副处理完毕，返回最右下角的值(12) Go代码如下： package mainimport ( "fmt")func max(a, b int) int { if a >= b { return a } return b}func maxValue(grid [][]int) int { row := len(grid) - 1 // 列 col := len(grid[0]) - 1 // 行 for i := 0; i <= row; i++ { for j := 0; j <= col; j++ { //把第1行 和 第1列 别离用前缀和的形式解决 if i == 0 && j == 0 { continue } if i == 0 { grid[i][j] += grid[i][j-1] continue } if j == 0 { grid[i][j] += grid[i-1][j] continue } //遍历残余地位，取以后地位的上边和右边中的较大者，加到以后地位的值上 grid[i][j] += max(grid[i-1][j], grid[i][j-1]) } } //最初一位为累计最大值 return grid[row][col]}func main() { a := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}} fmt.Println(maxValue(a))}提交截图： ...

title: 每日一练（34）：不必加减乘除做加法 categories:[剑指offer] tags:[每日一练] date: 2022/03/09 每日一练（34）：不必加减乘除做加法写一个函数，求两个整数之和，要求在函数体内不得应用 “+”、“-”、“*”、“/” 四则运算符号。 示例: 输出: a = 1, b = 1 输入: 2 提醒： a, b 均可能是正数或 0 后果不会溢出 32 位整数 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：位运算算法流程： a ^ b 计算出2个加数二进制下每一位的本位 a & b 计算出2个加数二进制下每一位的进位 (a & b) << 1 进位做进位逻辑，也就是 * 2 int add(int a, int b) { while (b != 0) { int carry = a & b ; // 计算 进位 a ^= b; // 计算 本位 b = (unsigned)c << 1; } return a;}办法二：递归加法=进位+非进位局部 ...

title: 每日一练（31）：翻转单词程序 categories:[剑指offer] tags:[每日一练] date: 2022/03/05 每日一练（31）：翻转单词程序输出一个英文句子，翻转句子中单词的程序，但单词内字符的程序不变。为简略起见，标点符号和一般字母一样解决。例如输出字符串"I am a student. "，则输入"student. a am I"。 示例 1： 输出: "the sky is blue" 输入: "blue is sky the" 示例 2： 输出: " hello world! " 输入: "world! hello" 解释: 输出字符串能够在后面或者前面蕴含多余的空格，然而反转后的字符不能包含。 示例 3： 输出: "a good example" 输入: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格缩小到只含一个。 阐明： 无空格字符形成一个单词。 输出字符串能够在后面或者前面蕴含多余的空格，然而反转后的字符不能包含。 如果两个单词间有多余的空格，将反转后单词间的空格缩小到只含一个。 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：模板代码办法出处：https://leetcode-cn.com/probl... 思路剖析这类题目我的惯常做法，也是核心思想，就是先把句子中所有字符串取出放入字符串数组，再对数组中的字符串进行操作后从新连贯即可，具体问题具体细节还需 要按题目要求剖析 而遍历句子取字符串的思路，就是遇到字符把它放入长期字符串，遇到空格或者标点(如果有标点)，就把长期字符串输入，并且清空 模板代码须要留神的是：这类题目能够分为两类，一类是有前置或者后置空格的，另一类是没有前置和后置空格的。 模板1、如果有前后置空格，那么必须判断长期字符串非空能力输入，否则会输入空串 s += " "; //这里在最初一个字符地位加上空格，这样最初一个字符串就不会脱漏string temp = ""; //长期字符串vector<string> res; //寄存字符串的数组for (char ch : s) { //遍历字符句子 if (ch == ' ') {//遇到空格 if (!temp.empty()) { //有前后置空格，须要判断长期字符串非空，反之能够去掉此判断 res.push_back(temp); temp.clear(); //清空长期字符串 } } else { temp += ch; }}模板2、没有前后置的空格不须要判断空串 ...

title: 每日一练（30）：和为s的间断负数序列 categories:[剑指offer] tags:[每日一练] date: 2022/03/04 每日一练（30）：和为s的间断负数序列输出一个正整数 target ，输入所有和为 target 的间断正整数序列（至多含有两个数）。 序列内的数字由小到大排列，不同序列依照首个数字从小到大排列。 示例 1： 输出：target = 9 输入：[[2,3,4],[4,5]] 示例 2： 输出：target = 15 输入：[[1,2,3,4,5],[4,5,6],[7,8]] 限度： 1 <= target <= 10^5 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：暴力求和公式vector<vector<int>> findContinuousSequence(int target) { if (target < 3) { return {}; } int left = 1; double right = 2.0; vector<vector<int>> res; while (left < right) { right = (-1 + sqrt(1 + 4 * (2 * target + (long)left * left - left))) / 2; if (left < right && right == (int) right) { vector<int> ans; for (int i = left; i <= (int)right; i++) { ans.push_back(i); } res.push_back(ans); } left++; } return res;}办法二：滑动窗口算法流程：1.初始化： 左边界 left = ，右边界 right = 2 ，元素和 sum = 3 ，后果列表 res ； ...

title: 每日一练（29）：和为s的两个数字 categories:[剑指offer] tags:[每日一练] date: 2022/03/02 每日一练（29）：和为s的两个数字输出一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输入任意一对即可。 示例 1： 输出：nums = [2,7,11,15], target = 9 输入：[2,7] 或者 [7,2] 示例 2： 输出：nums = [10,26,30,31,47,60], target = 40 输入：[10,30] 或者 [30,10] 限度： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^6 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：哈希思路： 创立哈希表遍历数组若哈希表中存在元素与以后遍历到的元素之和为 target 则返回后果即可没有满足条件的元素，返回空vector<int> twoSum(vector<int>& nums, int target) { // 创立哈希表 unordered_set<int> s; // 遍历数组 for (int x : nums) { // 若哈希表中存在元素与以后遍历到的元素之和为target // 则返回后果即可 if (s.count(target - x)) { return vector<int>{x, target - x}; } // 插入以后遍历到的元素 s.insert(x); } // 没有满足条件的元素，返回空 return {};}办法二：双指针充分利用递增数组的性质，双指针从头尾开始遍历，两数和小于指标，则left++；大于指标，则right--。 ...

title: 每日一练（28）：均衡二叉树 categories:[剑指offer] tags:[每日一练] date: 2022/03/01 每日一练（28）：均衡二叉树输出一棵二叉树的根节点，判断该树是不是均衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵均衡二叉树。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3/ \9 20/ \15 7返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \3 3 / \4 4返回 false 。 限度： 0 <= 树的结点个数 <= 10000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：后序遍历（DFS）dfs计算思路： 对于空结点，深度为0以后深度是左右子树深度的最大值+1， 无效状况间接返回深度一旦发现左右子树的深度差别超过1，则认为有效，返回-1一旦发现返回是-1， 间接返回-1bool isBalanced(TreeNode* root) { return (dfs(root) != -1);}int dfs(TreeNode* node) { if (node == nullptr) { return 0; } int left = dfs(node->left); if (left == -1) { return -1; } int right = dfs(node->right); if (right == -1) { return -1; } return abs(left - right) > 1 ? -1 : max(left, right) + 1;//以后深度是左右子树深度的最大值+1， 无效状况间接返回深度}办法二：前序遍历对于以后遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 11，再别离递归地遍历左右子节点，并判断左子树和右子树是否均衡。这 ...

零 题目：算法（leetode，附思维导图 + 全副解法）300题之（2120）执行所有后缀指令一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “模拟法”。// 思路：// 1）状态初始化：resList（寄存后果的） = [] 。// 2）外围1：遍历 指令字符串 s 。// 2.1）计算在以后的 后缀指令字符串 tempStr = s.slice(i) 下，能执行多少条指令数目 resCount 。// 2.2）走到这，阐明曾经无奈再执行命令，将 resCount 放入 数组 resList 中。// 3）返回后果 resList 。var executeInstructions = function(n, startPos, s) { // 1）状态初始化：resList（寄存后果的） = [] 。 const l = s.length; let resList = []; // 2）外围1：遍历 指令字符串 s 。 for (let i = 0; i < l; i++) { // 2.1）计算在以后的 后缀指令字符串 tempStr = s.slice(i) 下，能执行多少条指令数目 resCount 。 const tempStr = s.slice(i), tempL = tempStr.length; let [row, col] = startPos, resCount = 0 ; for (let j = 0; j < tempL; j++) { if (tempStr[j] === 'U' && (row - 1) >= 0) { row--; resCount++; } else if (tempStr[j] === 'D' && (row + 1) < n) { row++; resCount++; } else if (tempStr[j] === 'L' && (col - 1) >= 0) { col--; resCount++; } else if (tempStr[j] === 'R' && (col + 1) < n) { col++; resCount++; } else { break; } } // 2.2）走到这，阐明曾经无奈再执行命令，将 resCount 放入 数组 resList 中。 resList.push(resCount); } // 3）返回后果 resList 。 return resList;};四 资源分享 & 更多1 历史文章 - 总览 ...

title: 每日一练（27）：二叉树的深度 categories:[剑指offer] tags:[每日一练] date: 2022/02/26 每日一练（27）：二叉树的深度输出一棵二叉树的根节点，求该树的深度。从根节点到叶节点顺次通过的节点（含根、叶节点）造成树的一条门路，最长门路的长度为树的深度。 例如： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。 提醒： 节点总数 <= 10000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：递归后续遍历： 依照递归三部曲，来看看如何来写。 1.确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。代码如下： int getDepth(TreeNode* node)2.确定终止条件：如果为空节点的话，就返回0，示意高度为0。代码如下： if (node == NULL) return 0;3.确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最初取左右深度最大的数值 再+1 （加1是因为算上以后两头节点）就是目前节点为根节点的树的深度。 int leftDepth = getDepth(node->left); // 左int rightDepth = getDepth(node->right); // 右int depth = 1 + max(leftDepth, rightDepth); // 中return depth;//1简化前int getDepth(TreeNode *root) { if (root == NULL) { return 0; } int leftDepth = getDepth(node->left); // 左 int rightDepth = getDepth(node->right); // 右 int depth = 1 + max(leftDepth, rightDepth); // 中 return depth;}int maxDepth(TreeNode* root) { return getDepth(root);}//2简化后int maxDepth(TreeNode* root) { return (root == NULL) ? 0 : 1 + max(maxDepth(root->left), maxDepth(root->right));}办法二：迭代法(BFS)应用迭代法的话，应用层序遍历是最为适合的，因为最大的深度就是二叉树的层数，和层序遍历的形式极其吻合 ...

动静布局最近在猛刷动静布局题，正好 leetcode 中国有“学习打算” 的性能，每天给我调配几道题的工作。 总结出了一套做动静布局的小模板。以“跳跃游戏”这道题为例 defmodule Solution do @spec can_jump(nums :: [integer]) :: boolean def can_jump([x]), do: true def can_jump([h | _] = nums) do # 首先结构初始状态，因为 List 的拜访工夫是 O(n) 的，咱们先将其转换为 Map state = %{0 => h, nums: nums |> Enum.with_index() |> Enum.into(%{}, fn {v, k} -> {k, v} end)} # 用一个 Agent 来保留状态，因为 elixir 外面个别不应用全局变量 Agent.start(fn -> state end, name: __MODULE__) r = dp(length(nums) - 1) # 完结后须要进行 Agent，否则状态会保留到下一个测试 Agent.stop(__MODULE__) !!r end # dp 主逻辑 defp dp(i) do find_and_store(i, fn %{nums: nums} -> nums[i] end, fn step -> case dp(i - 1) do false -> false j -> if j >= i do max(j, i + step) else false end end end) end # 通用函数，计算并存储最新状态。fget 函数是在 Agent 里执行，再返回后果。 # fdp 是状态转换的函数，其输出是 fget 的后果。 defp find_and_store(i, fget, fdp) do case Agent.get(__MODULE__, fn m -> m[i] end) do nil -> x = Agent.get(__MODULE__, fget) |> fdp.() Agent.update(__MODULE__, fn m -> Map.put(m, i, x) end) x x -> x end endend大家可能会说，你这样乱递归，不会爆栈吗？其实我也是战战兢兢的，惟恐不必尾递归会导致爆栈，但目前还没有遇到这种状况。可能是 beam 的优化很好吧。 ...

title: 每日一练（26）：二叉搜寻树的第k大节点 categories:[剑指offer] tags:[每日一练] date: 2022/02/25 每日一练（26）：二叉搜寻树的第k大节点给定一棵二叉搜寻树，请找出其中第 k 大的节点的值。 示例 1: 输出: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输入: 4 示例 2: 输出: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1输入: 4 限度： 1 ≤ k ≤ 二叉搜寻树元素个数 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：vector递归class Solution {public: vector<int> ans; void dfs(TreeNode* root) { if (!root) { return; } dfs(root->left); ans.push_back(root->val); dfs(root->right); } int kthLargest(TreeNode* root, int k) { dfs(root); return ans[ans.size() - k]; }};办法二：变量递归把本来是 “左中右” 的中序遍历改成 “右中左” 的反向中序遍历 ...

title: 每日一练（25）： 0～n-1中缺失的数字 categories:[剑指offer] tags:[每日一练] date: 2022/02/24 每日一练（25）： 0～n-1中缺失的数字一个长度为n-1的递增排序数组中的所有数字都是惟一的，并且每个数字都在范畴0～n-1之内。在范畴0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例 1: 输出: [0,1,3] 输入: 2 示例 2: 输出: [0,1,2,3,4,5,6,7,9] 输入: 8 限度： 1 <= 数组长度 <= 10000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：二分查找二分求边界，其实就是求数组中等于target的元素的范畴边界，如果数组中不存在等于target的元素，那求得的左右边界的值就是一样的。 int missingNumber(vector<int>& nums) { int l = 0; int r = nums.size(); int m = 0; while (l < r) { //二分查找 m = (l + r) / 2; if (nums[m] == m) { l = m + 1; } else { r = m; //失去缺失的那个数 } } return r;}办法二：数学法（等差数列）数组有n个数，但0到n有n+1个数，依据等差数列求和可得sum = (0+n)*(n+1)/2而后总和减去数组所有数，就是缺失的那个数 ...

title: 每日一练（24）：在排序数组中查找数字 categories:[剑指offer] tags:[每日一练] date: 2022/02/23 每日一练（24）：在排序数组中查找数字统计一个数字在排序数组中呈现的次数。 示例 1: 输出: nums = [5,7,7,8,8,10], target = 8 输入: 2 示例 2: 输出: nums = [5,7,7,8,8,10], target = 6 输入: 0 提醒： 0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递加数组 -109 <= target <= 109 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：STL（一行搞定）count函数能够用来统计字符串中某个字符的个数 应用办法是count(ivec.begin() , ivec.end() , searchValue)，其中begin指的是起始地址，end指的是完结地址，第三个参数指的是须要查找的字符。 int search(vector<int>& nums, int target) { return count(nums.begin(),nums.end(),target);}办法二：暴力解法间接for循环遍历查找指标并计数 int search(vector<int>& nums, int target) { if (nums.size() == 0) { return 0; } if (nums.size() == 1) { if (nums[0] == target) { return 1; } else { return 0; } } int count = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == target) { count++; //循环计数 } } return count;}办法三：二分查找二分模板： ...

title: 每日一练（23）：第一个只呈现一次的字符 categories:[剑指offer] tags:[每日一练] date: 2022/02/22 每日一练（23）：第一个只呈现一次的字符在字符串 s 中找出第一个只呈现一次的字符。如果没有，返回一个单空格。 s 只蕴含小写字母。 示例 1: 输出：s = "abaccdeff" 输入：'b' 示例 2: 输出：s = "" 输入：' ' 限度： 0 <= s 的长度 <= 50000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：哈希表思路1.对字符串进行两次遍历。 遍历字符串 s ，应用哈希表统计 “各字符数量是否 >1 ”。再遍历字符串 s ，在哈希表中找到首个 “数量为 1 的字符”，并返回。算法1.字符统计： 遍历字符串 s 中的每个字符 c ； 若 dic 中 不蕴含 键(key) c ：则向 dic 中增加键值对 (c, True) ，代表字符 c 的数量为 1 ；若 dic 中 蕴含 键(key) c ：则批改键 c 的键值对为 (c, False) ，代表字符 c 的数量 >1 。2.查找数量为 1 的字符： 遍历字符串 s 中的每个字符 c ； ...

title: 每日一练（22）：间断子数组的最大和 categories:[剑指offer] tags:[每日一练] date: 2022/02/21 每日一练（22）：间断子数组的最大和输出一个整型数组，数组中的一个或间断多个整数组成一个子数组。求所有子数组的和的最大值。 要求工夫复杂度为O(n)。 示例1: 输出: nums = [-2,1,-3,4,-1,2,1,-5,4] 输入: 6 解释: 间断子数组 [4,-1,2,1] 的和最大，为 6。 提醒： 1 <= arr.length <= 10^5 -100 <= arr[i] <= 100 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：前缀和思路和算法都是正数的状况下 每次都是sum为以后值，顺次与maxsum比拟取其中最大的。失常状况下（有正有负）累计前缀和，只有sum大于0 （还有存在价值），就加上来，判断与后面的maxsum谁大，取较大值；以后和变小到0时（阐明后面的正数对消了，前面来的数不论是正是负，后面累计的和0都没价值了），则从新从以后数开始，同时保障子数组的连续性。留神不是遇到正数就从新赋值。另外须要不停的判断以后和是不是最大的。int maxSubArray(vector<int>& nums) { int maxSum = nums[0]; //默认第一个数为最大值 int sum = 0; for (int i = 0; i < nums.size(); i++) { sum = sum <= 0 ? nums[i] : sum + nums[i];// 以后和不大于0时，阐明后面对消了，从新开始累计和;同样的如果都是正数时，则顺次比拟哪个最大，赋值给maxSum maxSum = sum > maxSum ? sum : maxSum; // 不停比拟更新maxSum } return maxSum;}办法二：动静布局（DP方程）思路和算法最原始的动静布局 ...

title: 每日一练（21）：最小的k个数 categories:[剑指offer] tags:[每日一练] date: 2022/02/17 每日一练（21）：最小的k个数输出整数数组 arr ，找出其中最小的 k 个数。例如，输出4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： 输出：arr = [3,2,1], k = 2 输入：[1,2] 或者 [2,1] 示例 2： 输出：arr = [0,1,2,1], k = 1 输入：[0] 限度： 0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：sort排序思路和算法对原数组从小到大排序后取出前 k 个数即可。 复杂度剖析工夫复杂度：O(n logn)，其中 n 是数组 arr 的长度。算法的工夫复杂度即排序的工夫复杂度。空间复杂度：O(logn)，排序所需额定的空间复杂度为 O(logn)。vector<int> getLeastNumbers(vector<int>& arr, int k) { vector<int> ans(k, 0); if (arr.size() == 0 || k == 0) { return ans; } sort(arr.begin(), arr.end()); //排序 for (int i = 0; i < k; i++) { ans.push_back(arr[i]); //增加到指标vector } return ans;}办法二：堆思路和算法咱们用一个大根堆实时保护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果以后遍历到的数比大根堆的堆顶的数要小，就把 ...

题目：给定一个字符串 s ，请你找出其中不含有反复字符的 最长子串 的长度。 链接： 力扣Leetcode—中级算法—数组和字符串—无反复字符的最长子串. 示例 1: 输出: s = "abcabcbb"输入: 3 解释: 因为无反复字符的最长子串是 "abc"，所以其长度为 3。示例 2: 输出: s = "bbbbb"输入: 1解释: 因为无反复字符的最长子串是 "b"，所以其长度为 1。示例 3: 输出: s = "pwwkew"输入: 3解释: 因为无反复字符的最长子串是 "wke"，所以其长度为 3。 请留神，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。标签：哈希表、字符串、滑动窗口 思路：利用首字符的递归解决问题。看成子问题： 蕴含s[0]的最长无反复子串lengthOfLongestSubstring(s[1:n])次要Go代码如下： package mainimport "fmt"func lengthOfLongestSubstring(s string) int { n := len(s) // 字符串长度不大于1 if n <= 1 { return n } // 全局的字符串，用于保留 var mp = make(map[byte]int) var i int for i = 0; i < n; i++ { if _, ok := mp[s[i]]; ok { // 找到反复的，间接退出 break } else { // 没找到反复的，加上这个子串 mp[s[i]] = i } } length := lengthOfLongestSubstring(s[1:]) if i > length { return i } return length}func main() { fmt.Println(lengthOfLongestSubstring("abcabcbb"))}提交截图： ...

赎金信哈希映射 建设一个哈希表 lettersPool, 用于寄存 magazine 中呈现的 字母 以及 对应数量 /** * @param {string} ransomNote * @param {string} magazine * @return {boolean} */var canConstruct = function(ransomNote, magazine) { const lettersPool = new Map(); for(let letter of magazine) { if(lettersPool.has(letter)) { lettersPool.set(letter, lettersPool.get(letter) + 1); } else { lettersPool.set(letter, 1); } } for(let letter of ransomNote) { if(lettersPool.has(letter)) { const rest = lettersPool.get(letter); if(rest === 0) return false; lettersPool.set(letter, lettersPool.get(letter) - 1); } else { return false; } } return true;};无效的字母异位词排序比拟 ...

title: 每日一练（20）：数组中呈现次数超过一半的数字 categories:[剑指offer] tags:[每日一练] date: 2022/02/16 每日一练（20）：数组中呈现次数超过一半的数字数组中有一个数字呈现的次数超过数组长度的一半，请找出这个数字。 你能够假如数组是非空的，并且给定的数组总是存在少数元素。 示例 1: 输出: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输入: 2 限度： 1 <= 数组长度 <= 50000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：哈希表思路咱们晓得呈现次数最多的元素大于n/2次，所以能够用哈希表来疾速统计每个元素呈现的次数。 算法咱们应用哈希映射（HashMap）来存储每个元素以及呈现的次数。对于哈希映射中的每个键值对，键示意一个元素，值示意该元素呈现的次数。 咱们用一个循环遍历数组 nums 并将数组中的每个元素退出哈希映射中。在这之后，咱们遍历哈希映射中的所有键值对，返回值最大的键。咱们同样也能够在遍历数组 nums 时候应用打擂台的办法，保护最大的值，这样省去了最初对哈希映射的遍历。 复杂度剖析工夫复杂度：O(n)，其中 n 是数组 nums 的长度。咱们遍历数组 nums 一次，对于 nums 中的每一个元素，将其插入哈希表都只须要常数工夫。如果在遍历时没有保护最大值，在遍历完结后还须要对哈希表进行遍历，因为哈希表中占用的空间为 O(n)（可参考下文的空间复杂度剖析），那么遍历的工夫不会超过 O(n)。因而总工夫复杂度为 O(n)。空间复杂度：O(n)。哈希表最多蕴含 n - n/2个键值对，所以占用的空间为 O(n)。这是因为任意一个长度为 n 的数组最多只能蕴含 n 个不同的值，但题中保障 nums 肯定有一个众数，会占用（起码）n/2 + 1 个数字。因而最多有n - (n/2 +1)个不同的其余数字，所以最多有 n - n/2个不同的元素。int majorityElement(vector<int>& nums) { unordered_map<int, int> counts; int majority = 0, cnt = 0; for (int num : nums) { ++counts[num]; if (counts[num] > cnt) { majority = num; cnt = counts[num]; } } return majority;}办法二：排序思路如果将数组 nums 中的所有元素依照枯燥递增或枯燥递加的程序排序，那么下标为 n/2 的元素（下标从 0 开始）肯定是众数。 ...

休了个不短不长的年假，题解系列持续动工~ 本专题旨在分享刷Leecode过程发现的一些思路乏味或者有价值的题目。 题目相干原题地址: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/]题目形容： 输出一个正整数 target ，输入所有和为 target 的间断正整数序列（至多含有两个数）。序列内的数字由小到大排列，不同序列依照首个数字从小到大排列。 示例 1：输出：target = 9输入：[[2,3,4],[4,5]]示例 2：输出：target = 15输入：[[1,2,3,4,5],[4,5,6],[7,8]]限度：1 <= target <= 10^5思路解析暴力破解题目的含意比拟清晰，需要求出和为特定值的 间断正整数序列。 首先，这道题的很间接的也会想到一个 -- 暴力破解: 具体思路： 首先寻找是否存在满足要求的，以1为结尾的序列，所以初始化一个序列为 [ 1 ]顺次往序列里增加间断的正整数，让序列变成 [1, 2, 3..i. target]， 并且每次增加完一个整数时，比照以后序列所有整数之和sum，与目标值target的关系： 如果sum < target，则持续往序列里增加下一个数；如果曾经满足sum = target，那么存储以后序列，并且阐明以1开始的序列寻找能够进行了；如果间接到sum > target，那么阐明以1开始的序列寻找能够进行了（不存在以1为结尾并且满足要求的序列）；反复上述步骤，别离寻找以2，3, ... target结尾且满足题意的序列； 下面这种思路的话 最坏的状况下，须要外层循环（外层循环也就是遍历以1..n结尾的序列）n次，内层循环n次（内层循环就是寻找以后结尾固定时，不同结尾的序列），那么总的复杂度就是O(n^2)，因为 1 <= target <= 10^5 , 所以O(n^2)显著超时; 红色区域示意序列，它的左边界和右边界有个特点，都只向右侧挪动，而整个遍历的过程，其实就像是一个推拉窗的挪动过程，这个算法也就由此得名。 滑动窗口从上述过程能够看到，暴力破解的问题在于工夫复杂度太高，而之所以高，是因为在遍历过程存在一些能够跳过的过程, 为了便于了解，咱们带入一个题设中的示例1，target = 9的状况来进行演示。依照暴力破解思路： 首先序列为 [1] , 序列之和 sum = 1 , 1 < 9 持续循环;序列为 [1, 2] , 序列之和 sum = 3 , 3 < 9 持续循环;序列为 [1, 2，3] , 序列之和 sum = 6 , 6 < 9 持续循环;序列为 [1, 2, 3 ,4] , 序列之和 sum = 12 , 12 > 9 ,那 Stop!; 到此阐明不存在以1为结尾切满足要求的序列，那么依照后面的思路，接下来是要寻找以2结尾且满足题意的序列，那么当初问题来了： ...

title: 每日一练（19）：从上到下打印二叉树 categories:[剑指offer] tags:[每日一练] date: 2022/02/15 每日一练（19）：从上到下打印二叉树从上到下按层打印二叉树，同一层的节点按从左到右的程序打印，每一层打印到一行。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3/ \9 20/ \15 7返回其档次遍历后果： [ [3], [9,20], [15,7]]提醒： 节点总数 <= 1000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 留神的是要把每一层放到一起，须要保护一个level进行保留。 DFS记得应用援用&，不然就得保护一个全局变量了。 办法一：BFS/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; q.push(root); vector<vector<int>> res; while (q.size()) { int size = q.size(); vector<int> level; for (int i=0;i<size;i++) { TreeNode* rt = q.front(); q.pop(); if (!rt) { continue; } level.push_back(rt->val); if (rt->left) { q.push(rt->left); } if (rt->right) { q.push(rt->right); } } if (level.size()!=NULL) { res.push_back(level); } } return res; }};办法二：DFS/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; dfs(root, res, 0); return res; } void dfs(TreeNode* root,vector<vector<int>>& res,int level) { if (!root) { return; } if (level >= res.size()) { res.emplace_back(vector<int>()); } res[level].emplace_back(root->val); dfs(root->left, res, level+1); dfs(root->right, res, level+1); }};

老铁们是否据说过 https://adventofcode.com/ 这个网站，在每天的圣诞前夕，它就会开始间断25天公布编程谜题，吸引了有数人参加。从我开始学编程那会儿，就有用这里的题目来锤炼本人的编程能力。 2021年的题目的难度是逐步加深的，越往后越艰巨，我保持做完了前23天的题目，直到看到第24天的题目，死磕了很久，还是想不进去。 题目大略是这样：有一种计算单元，具备w,x,y,z四个寄存器，反对以下几种指令： inp a（读取用户输出的数字，保留于寄存器a）add a b (a与b之和保留于a。b能够是数字或寄存器）mul a b (...乘积...)mod a b (...余数...)div a b (...整除...)eql a b (如果 a 等于 b，为 1，否则为0。后果保留于a。b能够是数字或寄存器）而后给定一串指令，令用户输出一串1~9的数字，使寄存器z的后果等于0. 求用户输出的数字按程序组成的十进制数的最大和最小值。 尝试解题一开始我千方百计优化给定的指令，比方 add a 0，mul a 1能够间接省略，最初发现优化完了还是很长一串，没什么卵用。 再起初想到 div a b 时如果 a < b 则为 0。加上咱们晓得单个输出的范畴是 1..9，往后能够依据数字的范畴来进行优化，最初失去 z 的范畴。 卡在这里没方法停顿上来了，一个月之后，我终于忍不了了，在 reddit 上查看了一下大家分享的解题办法。次要的办法是逆向剖析给定的指令，从而得出对于输出值的限度条件。看到这里我有点悲观，尽管逆向剖析也很酷，然而 AOC 之前的题目很少有对输出做假如的，我更心愿应用一种通用的解法，可能实用于任意的指令列表。 终于，我看到了某位大神的解法，完满满足了我的需要。 解法次要的思路和我之前是一样的，即剖析每一次计算的后果的最大和最小值。最牛的中央是大神不是只剖析一次，而是每一次 inp a 指令读取完一个用户输出的值，就再从新剖析一次计算结果的范畴。设 i(n) 是第n个 inp 指令读取的用户输出。例如，当咱们没有给定 i(1) 的值时，i(1)的范畴是 {1, 9}，最初剖析进去 z 的范畴可能就是一个很大的区间。但咱们给定 i(1) 为一个常数，最初剖析进去的 z 的范畴就有可能会小很多。 ...

title: 每日一练（18）：蕴含min函数的栈 categories:[剑指offer] tags:[每日一练] date: 2022/02/14 每日一练（18）：蕴含min函数的栈定义栈的数据结构，请在该类型中实现一个可能失去栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的工夫复杂度都是 O(1)。 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2. 提醒： 各函数的调用总次数不超过 20000 次 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法：栈一个栈用于寄存全副元素，另一个栈用于寄存不断更新最小值 pop出栈是如果检测到两栈top相等，即同时出栈 min即返回最小栈的top class MinStack {public: /** initialize your data structure here. */ stack<int>a,b; //b栈用于寄存不断更新的最小值 MinStack() { } void push(int x) { a.push(x); if (b.empty() || x <= b.top()) { b.push(x); } } void pop() { if (a.top() == b.top()) { b.pop(); } a.pop(); } int top() { return a.top(); } int min() { return b.top(); }};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->min(); */

题目：给你一个字符串数组，请你将 字母异位词 组合在一起。能够按任意程序返回后果列表。          字母异位词 是由重新排列源单词的字母失去的一个新单词，所有源单词中的字母通常恰好只用一次。 链接： 力扣Leetcode—中级算法—数组和字符串—字母异位词分组. 示例 1: 输出: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输入: [["bat"],["nat","tan"],["ate","eat","tea"]]示例 2: 输出: strs = [""]输入: [[""]]示例 3: 输出: strs = ["a"]输入: [["a"]]标签：哈希表、字符串、排序 思路：因为字母异位词指字母雷同，排列程序不同的字符串。因而咱们能够对每一个字符串的字母进行升序或者降序排序，如果升序之后的字符串相等，那么它们就是一组的。 全副Go代码如下： package mainimport ( "fmt" "sort" "strings")func groupAnagrams(strs []string) [][]string { wordMap := map[string][]string{} for _, str := range strs { key := SortString(str) // 为切片增加元素 wordMap[key] = append(wordMap[key], str) fmt.Println(wordMap) } ans := make([][]string, 0, len(wordMap)) for _, v := range wordMap { ans = append(ans, v) } return ans}func SortString(s string) string { // strings.Split 将指定的分隔符切割字符串，并返回切割后的字符串切片。 ret := strings.Split(s, "") // sort 包来实现切片内字母升序排序 sort.Strings(ret) // strings.Join 将字符串切片中存在的所有元素连贯为单个字符串 return strings.Join(ret, "")}func main() { var a = []string{"eat", "tea", "tan", "ate", "nat", "bat"} fmt.Println(groupAnagrams(a))}提交截图： ...

title: 每日一练（17）：顺时针打印矩阵 categories:[剑指offer] tags:[每日一练] date: 2022/02/12 每日一练（17）：顺时针打印矩阵输出一个矩阵，依照从内向里以顺时针的程序顺次打印出每一个数字。 示例 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] 限度： 0 <= matrix.length <= 100 0 <= matrix[i].length <= 100 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法：设定边界依据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输入 [1,2,3,6,9,8,7,4,5] 能够发现，顺时针打印矩阵的程序是 “从左向右、从上向下、从右向左、从下向上” 循环。 因而，思考设定矩阵的“左、上、右、下”四个边界，模仿以上矩阵遍历程序。 算法流程： 1.空值解决： 当 matrix 为空时，间接返回空列表 [] 即可。 2.初始化： 矩阵 左、右、上、下 四个边界 l , r , t , b ，用于打印的后果列表 res 。 3.循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环，每个方向打印中做以下三件事 （各方向的具体信息见下表） ； 1.依据边界打印，行将元素按程序增加至列表 res 尾部；2.边界向内膨胀 11 （代表已被打印）；3.判断是否打印结束（边界是否相遇），若打印结束则跳出。4.返回值： 返回 res 即可。 ...

title: 每日一练（16）：对称的二叉树 categories:[剑指offer] tags:[每日一练] date: 2022/02/11 每日一练（16）：对称二叉树请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \3 4 4 3然而上面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \2 2 \ \ 3 3示例 1： 输出：root = [1,2,2,3,4,4,3] 输入：true 示例 2： 输出：root = [1,2,2,null,3,null,3] 输入：false 限度： 0 <= 节点个数 <= 1000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法出处： 代码随想录 办法一：递归递归三部曲确定递归函数的参数和返回值因为咱们要比拟的是根节点的两个子树是否是互相翻转的，进而判断这个树是不是对称树，所以要比拟的是两个树，参数天然也是左子树节点和右子树节点。 返回值天然是bool类型。 代码： bool compare(TreeNode *left, TreeNode *right)确定终止条件要比拟两个节点数值相不雷同，首先要把两个节点为空的状况弄清楚！否则前面比拟数值的时候就会操作空指针了。 节点为空的状况有： 左节点为空，右节点不为空，不对称，return false左不为空，右为空，不对称 return false左右都为空，对称，返回true此时曾经排除掉了节点为空的状况，那么剩下的就是左右节点不为空： 左右都不为空，比拟节点数值，不雷同就return false此时左右节点不为空，且数值也不雷同的状况咱们也解决了。 ...

题目：给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否无效。 提醒：无效字符串需满足： 左括号必须用雷同类型的右括号闭合。左括号必须以正确的程序闭合。链接： 力扣Leetcode—高级算法—其余—无效的括号. 示例1 ： 输出：s = "()"输入：true示例2 ： 输出：s = "()[]{}"输入：true示例 3： 输出：s = "(]"输入：false示例 4： 输出：s = "([)]"输入：false示例 5： 输出：s = "{[]}"输入：true标签：栈、字符串 思路：要让所有的括号匹配，最容易想到的办法就是栈。遍历字符串，每读到一个左括号，便将其入栈；若呈现右括号，则匹配栈内的左括号，删除匹配过的左括号；当没有与右括相匹配的左括号，则该字符串不非法。如果读完字符串之后栈内仍有元素，阐明有多余的左括号，该字符串也不非法。 次要Go代码如下： package mainimport "fmt"func isValid(s string) bool { var n = len(s) // 字符串的匹配，单字符类型为byte myDick := map[byte]byte{ ']': '[', ')': '(', '}': '{', } // 如果字符串为空则返回true if n == 0 { return true } // 创立切片充当栈 var stack []byte // 遍历字符串中的元素 for i := 0; i < n; i++ { // 如果以后字符是左括号，则存入栈内 if (s[i] == '[') || (s[i] == '{') || (s[i] == '(') { stack = append(stack, s[i]) // 若呈现右括号，则匹配栈内的左括号 } else if len(stack) > 0 && stack[len(stack)-1] == myDick[s[i]] { // 删除匹配过的左括号 stack = stack[:len(stack)-1] } else { // 以上状况都不存在时则len(stack)==0 || 没有与右括相匹配的左括号，则该字符串不非法 return false } } // 最初判断栈内是否还有空余字符，若有阐明有残余的左括号，该字符串也不非法 return len(stack) == 0}func main() { result := isValid("{[}}") fmt.Println(result)}提交截图： ...

零 题目：算法（leetode，附思维导图 + 全副解法）300题之（2126）捣毁小行星一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “排序、模拟法（实质：贪婪法）”。// 技巧：“相似打怪降级，优先战胜小怪物、降级，前面再去挑战血量更厚的怪物！”。// 思路：// 1）状态初始化，resBool = true 。// 2）外围1：对 asteroids 进行升序排序。// 3）外围2：遍历 asteroids ，依据状况别离去更新 mass、resBool 值。// 3.1）若 mass >= asteroids[i] （阐明行星 能捣毁该小行星），// 则 mass += asteroids[i] （取得该小行星的品质）。// 3.2）若 mass < asteroids[i] （阐明行星 不能捣毁该小行星），// 则 resBool = false 并 跳出循环 。// 4）返回后果 resBool 。var asteroidsDestroyed = function(mass, asteroids) { // 1）状态初始化，resBool = true 。 const l = asteroids.length; let resBool = true; // 2）外围1：对 asteroids 进行升序排序。 asteroids = asteroids.sort((a, b) => a - b); // 3）外围2：遍历 asteroids ，依据状况别离去更新 mass、resBool 值。 for (let i = 0; i < l; i++) { // 3.1）若 mass >= asteroids[i] （阐明行星 能捣毁该小行星）， // 则 mass += asteroids[i] （取得该小行星的品质）。 if (mass >= asteroids[i]) { mass += asteroids[i]; } // 3.2）若 mass < asteroids[i] （阐明行星 不能捣毁该小行星）， // 则 resBool = false 并 跳出循环 。 else { resBool = false; break; } } // 4）返回后果 resBool 。 return resBool;};2 计划21)代码： ...

题目：统计所有小于非负整数 n 的质数的数量。 链接： 力扣Leetcode—高级算法—数学—计数质数. 示例1 ： 输出：n = 10输入：4解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。示例2 ： 输出：n = 0输入：0示例3 ： 输出：n = 1输入：0标签：数组、数学、枚举、数论 思路：如果用暴力破解，那么毫无疑问会超时，咱们能够用厄拉多塞筛法（Eratosthenes）：即从2开始，2的倍数全副去掉；接下来3是质数，3的倍数全副去掉，如此上来，留下的都是质数。 咱们首先定义一个长度为n的bool数组，用来标识某个数是否是素数，如果不是素数就将数组中对应的地位置为true首先，0和1必定不是质数，所以数组前两个元素的值置为true数组中初始化的时候每个元素对应的值都是false，从2开始，如果对应数组中的值还是false，那么阐明了这个数肯定是质数所以2是质数，那么将2翻倍的数肯定不是质数，所以咱们将2始终这样翻倍翻下去，直到某一个倍数超过n，那么数组中就没有对应的地位了，咱们在这个过程中，将翻倍失去的数字在数组中对应的地位置为true而后遍历2的下一个数，首先看这个数在数组中对应地位的值是true还是false，如果是true阐明了这个地位是由后面某个数翻倍失去的，阐明他是合数，所以跳过，如果是false，阐明了这个数不能由后面的数翻倍失去，那么他必定是质数始终反复上述过程，直到这个2变成了最初的n次要Go代码如下： package mainimport "fmt"func countPrimes(n int) int { list := make([]bool, n) sum := 0 for i := 2; i < n; i++ { if list[i] == false { sum++ } for j := i + i; j < n; j += i { list[j] = true } } return sum}func main() { var n int fmt.Scanf("%d", &n) fmt.Println(countPrimes(n))}提交截图： ...

题目：给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 示意，并用字符串数组 answer（下标从 1 开始）返回后果，其中：    answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。     answer[i] == "Fizz" 如果 i是 3 的倍数。     answer[i] == "Buzz" 如果 i 是 5 的倍数。     answer[i] == i（以字符串模式）如果上述条件全不满足。 链接： 力扣Leetcode—高级算法—数学—Fizz Buzz. 示例1 ： 输出：n = 3输入：["1","2","Fizz"]示例2 ： 输出：n = 5输入：["1","2","Fizz","4","Buzz"]示例3 ： 输出：n = 15输入：["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]标签：数学、字符串、模仿 思路：定义一个字符串数组，从1开始遍历，用append在数组后顺次增加字符串。遇到同时是 3 和 5 的倍数，增加字符串FizzBuzz；遇到是3的倍数，增加字符串Fizz；遇到是5的倍数，增加字符串Buzz；其余就把int类型转换为string类型，要应用到strconve.Itoa(i)函数 次要Go代码如下： package mainimport ( "fmt" "strconv")func fizzBuzz(n int) []string { var list []string for i := 1; i <= n; i++ { if i%3 == 0 && i%5 == 0 { list = append(list, "FizzBuzz") } else if i%3 == 0 { list = append(list, "Fizz") } else if i%5 == 0 { list = append(list, "Buzz") } else { list = append(list, strconv.Itoa(i)) } } return list}func main() { var a int fmt.Scanf("%d", &a) fmt.Println(fizzBuzz(a))}提交截图： ...

以终为始在日常生活中指的是先确定指标，再做好打算。之前读管理学的书的时候，学到了这个概念。 而在算法中，以终为始指的是从后果反向推，直到问题的初始状态。 那么什么时候适宜反向思考呢？一个很简略的准则就是： 正向思考的状况比拟多代码比拟难写或者算法简单度过高这个时候咱们能够思考反向操作。 我的习惯是如果间接求解很难，我会优先思考应用能力检测二分，如果不行我则会思考反向思考。 对于能力检测二分，能够在我的公众号中找到，大家能够在《力扣加加》回复二分获取。明天西法通过三道题来给大家聊聊到底怎么在写算法题的时候使用以终为始思维。 机器人跳跃问题这道题来自于牛客网。地址：nowcoder.com/question/next?pid=16516564&qid=362295&tid=36905981 题目形容工夫限度：C/C++ 1秒，其余语言2秒空间限度：C/C++ 32M，其余语言64M机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座修建——从0到N编号，从左到右排列。编号为0的修建高度为0个单位，编号为i的修建的高度为H(i)个单位。起初， 机器人在编号为0的修建处。每一步，它跳到下一个（左边）修建。假如机器人在第k个修建，且它当初的能量值是E, 下一步它将跳到第个k+1修建。它将会失去或者失去反比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将失去 E - H(k+1) 的能量值。游戏指标是达到第个N修建，在这个过程中，能量值不能为正数个单位。当初的问题是机器人以多少能量值开始游戏，才能够保障胜利实现游戏？输出形容:第一行输出，示意一共有 N 组数据.第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度输入形容:输入一个独自的数示意实现游戏所需的起码单位的初始能量输出例子1:53 4 3 2 4输入例子1:4输出例子2:34 4 4输入例子2:4输出例子3:31 6 4输入例子3:3思路题目要求初始状况下至多须要多少能量。正向求解会比拟艰难，因而我的想法是： 能力检测二分。比方能量 x 是否能够，如果 x 能够，那么大于 x 的能量都能够。依此咱们不难写出代码。反向思考。 尽管咱们不晓得最开始的能量是多少，然而咱们晓得最初的能量是 0 才最优，基于此咱们也能够写出代码。这里咱们应用第二种办法。 具体来说：咱们从后往前思考。达到最初一级的能量起码是 0 。而因为: next = pre + (pre - H[i])因而： pre = (next + H[i]) / 2因为除以 2 可能会呈现小数的状况，因而须要 ceil。 ...

title: 每日一练（15）：二叉树的镜像 categories:[剑指offer] tags:[每日一练] date: 2022/01/28 每日一练（15）：二叉树的镜像请实现一个函数，输出一个二叉树，该函数输入它的镜像。 例如输出： 4 / \ 2 7/ \ / \1 3 6 9镜像输入： 4 / \ 7 2 / \ / \9 6 3 1示例 1： 输出：root = [4,2,7,1,3,6,9] 输入：[4,7,2,9,6,3,1] 限度： 0 <= 节点个数 <= 1000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：递归思路与算法 这是一道很经典的二叉树问题。显然，咱们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转失去镜像。如果以后遍历到的节点 root 的左右两棵子树都曾经翻转失去镜像，那么咱们只须要替换两棵子树的地位，即可失去以 root 为根节点的整棵子树的镜像。 //1TreeNode* mirrorTree(TreeNode* root) { if (root == nullptr) { return nullptr; } TreeNode *left = mirrorTree(root->left); TreeNode *right = mirrorTree(root->right); root->left = right; root->right = left; return root;}//2TreeNode* mirrorTree(TreeNode* root) { if (root == nullptr) { return nullptr; } swap(root->left, root->right);//替换左右节点 mirrorTree(root->left);//对右节点递归 mirrorTree(root->right);//对左节点递归 return root;}办法二：迭代（栈/队列）利用栈（或队列）遍历树的所有节点 node ，并替换每个 node 的左 / 右子节点。 ...

题目：你是一个业余的小偷，打算偷窃沿街的屋宇。每间房内都藏有肯定的现金，影响你偷窃的惟一制约因素就是相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。给定一个代表每个屋宇寄存金额的非负整数数组，计算你 不触动警报安装的状况下 ，一夜之内可能偷窃到的最高金额。 链接： 力扣Leetcode—高级算法—动静布局—打家劫舍. 示例1 ： 输出：[1,2,3,1]输入：4解释：偷窃 1 号屋宇 (金额 = 1) ，而后偷窃 3 号屋宇 (金额 = 3)。            偷窃到的最高金额 = 1 + 3 = 4 。示例2 ： 输出：[2,7,9,3,1]输入：12解释：偷窃 1 号屋宇 (金额 = 2), 偷窃 3 号屋宇 (金额 = 9)，接着偷窃 5 号屋宇 (金额 = 1)。            偷窃到的最高金额 = 2 + 9 + 1 = 12 。标签：数组、动静布局 思路： 遍历到第一个数，这是第一家，以他家作为完结，那就把他偷了遍历到第二个数，咱们须要斟酌，如果第二家的财产更多就偷第二家，否则偷第一家遍历到第三个数，咱们须要分对第三家是偷还是不偷     偷第三家：那么第二家咱们就不能偷，所以咱们将第三家偷到的财产加上以第一家作为完结的最大财产，失去在截至第三家偷到所得的累加的总财产     不偷第三家：那么咱们截至在第三家盗窃所得的总财产其实就是截至到第二家盗窃所得的总财产。     比拟下面两种形式的大小，能够失去截至第三家累加的最大收益遍历后续数组，每次只须要截至前两家的财产就能够计算出截至到以后家的最大收益最初返回截至到最初一家的盗窃的收益次要Go代码如下： package mainimport "fmt"func rob(nums []int) int { n := len(nums) if n == 0 { return 0 } if n == 1 { return nums[0] } if n > 1 { // 如果第一家大于第二家，那么就偷第一家，否则就偷第二家 if nums[1] < nums[0] { nums[1] = nums[0] } if n > 2 { for i := 2; i < n; i++ { // 偷第i家 if nums[i]+nums[i-2] >= nums[i-1] { nums[i] += nums[i-2] } else { // 不偷第i家 nums[i] = nums[i-1] } } } } return nums[n-1]}func main() { a := []int{2, 7, 9, 3, 1} fmt.Println(rob(a))}提交截图： ...

本专题旨在分享刷Leecode过程发现的一些思路乏味或者有价值的题目。【当然是基于js进行解答】。 动静布局一样是leetcode 中等难度习题的重点类型之一，同时可能也是面试热点之一，所以重要性显而易见。 题目相干原题地址: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/题目形容： 示例1：输出: [7,1,5,3,6,4]输入: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 （留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格。） - 示例2：输出: [7,6,4,3,1]输入: 0解释: 在这种状况下, 没有交易实现, 所以最大利润为 0。- 限度：<= 数组长度 <= 10^5思路解析暴力破解首先有一部分同学喜爱上来就来一波暴力破解，间接计算出所有可能的组合状况: 找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）, 那么所有的组合状况就是n*(n-1)/2，复杂度是O(n^2),毫无疑问，在题目给定的0 <= 数组长度 <= 10^5下，妥妥超时； 而且面试如果暴力破解的话，预计也要被暴力pass了。 动静布局（这个名字一听就很迷信！） 其实晚期具体写过动静布局的根底思路：https://segmentfault.com/a/11... 倡议不相熟的同学能够先去看看这一篇。 而所谓动静布局，外围就是就是把多阶段过程，转化为一系列单阶段问题；把问题一直拆解为子问题去求解。 如果看过根底篇的同学应该晓得，这里说的拆解，其实更直白一些就是找到第i个子问题与前i个子问题的关系。 带入本道题其实就是 把求解n天里交易股票最高利润的问题，先转化为先求解第n天卖出股票时的最高利润，而后从中找出最大值即可。 以输出 [7,1,5,3,6,4] 为例： 第1天卖出的话，最高利润是0，等于是无交易；第2天卖出的话，最高利润是0，因为第二天价格是1，高出第1天，也不会交易；第3天卖出的话，的最高利润是4，也就是第二天买入，第三天卖出；以此类推...来察看计算求解第i天卖出股票时，所能失去的最高利润的外围，只有已知目前为止的历史最低价，那么前i天的最高利润其实就是 用第i天的价格减去这个历史最低价即可，那么思路不就来了？ var maxProfit = function(prices) { const profit = []; // profit[i] 示意第i天卖出时的最大利润 let historyMinPrice = Infinity; for(let i = 0; i <= prices.length; i++) { // 放弃更新迄今为止的历史最低价 if(prices[i] < historyMinPrice) { historyMinPrice = prices[i]; } profit[i] = prices[i] - historyMinPrice; } // 未完待续 // ... };那么，有了这个price数组之后， 只有获取其中的最大值，其实也就是题目所要求的输入了。 这个想必难不倒大家，能够间接循环比对一次取得，然而其实思考下，并没必要再进行一次循环，因为在原来的循环过程，咱们其实就能够沿用历史最低价的思路， 另外维持一个目前为止的最大利润变量。 也就是 ...

本专题旨在分享刷Leecode过程发现的一些思路乏味或者有价值的题目。【当然是基于js进行解答】。 递归算法始终是leetcode 中等难度习题的重点类型之一，所以关键性显而易见。 题目相干原题地址: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/题目形容： 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。  1   / \  2   2 / \ / \3  4 4  3 然而上面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:     1   / \  2   2   \   \   3    3Tips思考某些同学可能比拟少用js来刷leetcode，咱们在这里简略介绍下,对于树类型的数据输出,在js里的示意。 形如上题中的内容，给定二叉树的输出，其实并非一个数组，而应该是如下所示: 每个节点是一个object:  const root = {      val: 3,      left: { // left示意以后节点的左侧子节点        val: 9,        left: null, // 对照上图能够看到 节点9没有左右子节点        right: null,      },      right: {        val: 20,        left: {          val: 15, // 对照上图能够看到 节点15没有左右子节点          left: null,           right: null,        },         right: {          val: 7, // 对照上图能够看到 节点7没有左右子节点          left: null,           right: null,        },      }    }思路解析首先这道题是显著的递归类题目， 而递归类的题目个别就是以下几个步骤： ...

题目：假如你正在爬楼梯。须要 n 阶你能力达到楼顶。每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？ 链接： 力扣Leetcode—高级算法—动静布局—爬楼梯. 示例1 ： 输出：n = 2输入：2解释：有两种办法能够爬到楼顶。(1) 1 阶 + 1 阶(2) 2 阶示例2 ： 输出：n = 3输入：3解释：有三种办法能够爬到楼顶。(1) 1 阶 + 1 阶 + 1 阶(2) 1 阶 + 2 阶(3) 2 阶 + 1 阶标签：记忆化搜寻、数学、动静布局 思路：咱们先来画一个表格，这样能够更容易的看出解题思路 n办法总和11121+1   2231+1+1   1+2   2+1341+1+1+1   1+2+1   1+1+2   2+1+1   2+2551+1+1+1+1   1+2+1+1   1+1+2+1   1+1+1+2   2+1+1+1   1+2+2   2+1+2   2+2+18.........从表格看出其实是一个斐波那契数列，须要走 n 阶你能力达到楼顶，每次只能爬 1 或 2 个台阶，不同的办法总数就等于 [(n-1阶总办法数)+(n-2阶总办法数)] ，那么代码就很简略了，先定义切片寄存 n =1，2，3的时候的总办法数，再从 3 开始，遍历到总台阶数为 n ，用append办法始终给切片（slice）追加元素，追加到 sli[i-1]+sli[i-2] ，返回 len(sli)-1 就是不同办法数的总和。 次要Go代码如下： package mainimport "fmt"// fibonacci数列（斐波那契数列）func climbStairs(n int) int { sli := []int{1, 2, 3} if n <= 3 { return sli[n-1] } for i := 3; i < n; i++ { sli = append(sli, sli[i-1]+sli[i-2]) } return sli[len(sli)-1]}func main() { n := 5 fmt.Println(climbStairs(n))}提交截图： ...

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。 你只能抉择 某一天 买入这只股票，并抉择在 将来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 假如你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个谬误的版本。 你能够通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个谬误的版本。你应该尽量减少对调用 API 的次数。 链接： 力扣Leetcode—高级算法—动静布局—交易股票的最佳时机. 示例1 ： 输出：[7,1,5,3,6,4]输入：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。示例2 ： 输出：prices = [7,6,4,3,1]输入：0解释：在这种状况下, 没有交易实现, 所以最大利润为 0标签：数组、动静布局 思路：本题应用动静布局的形式，先遍历一遍数组，首先买进和卖出都指向第一天的价格，而后到了后一天，后一天的价格有三种模式：1. 价格比之前的卖出价格高，那么更新卖出价格。2. 价格在之前的卖出价格与买进价格之间，那么不做解决，间接期待新的一天到来。3. 价格比之前的买进价格低，那么将之前的卖出价格与买进价格作差，这个差值就是收益，将这个收益与之前保留的最大作比拟，如果这个收益更大，就更新存储的最大收益，而后将买进和卖出的价格都指向以后这个更低的买进价格。 次要Go代码如下： package mainimport "fmt"func maxProfit(prices []int) int { // 买进和卖出都指向第一天的价格 max := prices[0] min := prices[0] sum := max - min n := len(prices) if n == 0 { return 0 } for index, value := range prices { if value >= max { max = value } if value < min { // 保留之前的最大值 if sum < (max - min) { sum = max - min } max, min = value, value } // 到了数组最初,看最大收益是否须要更新 if index == len(prices)-1 { if sum < (max - min) { sum = max - min } } } return sum}func main() { var balance = []int{7, 1, 5, 3, 6, 4} fmt.Println(maxProfit(balance))}提交截图： ...

title: 每日一练（14）：合并两个排序的链表 categories:[剑指offer] tags:[每日一练] date: 2022/01/27 每日一练（14）：合并两个排序的链表输出两个递增排序的链表，合并这两个链表并使新链表中的节点依然是递增排序的。 示例1： 输出：1->2->4, 1->3->4 输入：1->1->2->3->4->4 限度： 0 <= 链表长度 <= 1000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：迭代咱们的目标是将两个有序链表合并成一个有序链表，因而，咱们的每次操作都是获取 l1 指向的结点和 l2 指向的结点中，值较小的结点。迭代和递归都是如此。 应用迭代的时候 为了将第一个结点与其余结点对立解决，个别会定义一个头结点。应用递归的时候 咱们往往能够利用递归函数的返回值，将解决好的链表的第一个结点，作为返回值返回到上一级。上一级函数则间接将失去的返回值，链接在以后结点的 next 即可。迭代 定义头结点若 l1 指向的结点值 < l2 指向的结点值，则将 l1 链接到头结点的 next 地位否则将 l2 链接到头结点的 next 地位循环进行，直至 l1 或 l2 为 NULL最初，将 l1 或 l2 中剩下的局部，链接到头结点前面ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *head = new ListNode(0); ListNode *ret = head; while (l1 != NULL && l2 != NULL) { if (l1->val < l2-> val) { head->next = l1; l1 = l1->next; } else { head->next = l2; l2 = l2->next; } head = head->next; } head->next = l1 == NULL ? l2 : l1; return ret->next;}办法二：递归编写递归的第一步，该当是明确以后函数该当实现的性能。 ...

题目：你是产品经理，目前正在率领一个团队开发新的产品。可怜的是，你的产品的最新版本没有通过品质检测。因为每个版本都是基于之前的版本开发的，所以谬误的版本之后的所有版本都是错的。 假如你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个谬误的版本。 你能够通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个谬误的版本。你应该尽量减少对调用 API 的次数。 链接： 力扣Leetcode—高级算法—排序和搜寻—第一个谬误的版本. 示例1 ： 输出：n = 5, bad = 4输入：4解释：调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true所以，4 是第一个谬误的版本。示例2 ： 输出：n = 1, bad = 1输入：1标签：二分查找、交互 思路：使用二分查找，先取两头mid，如为ture，可能刚好在或者曾经超过第一个谬误的版本，取mid=max，再在min<max的前提下持续二分查找；如果false，证实第一个谬误的版本在mid之后，取mid=min，再在min<max的前提下持续二分查找。在查找的时候留神边界。 次要Go代码如下： /** * Forward declaration of isBadVersion API. * @param version your guess about first bad version * @return true if current version is bad * false if current version is good * func isBadVersion(version int) bool; */func firstBadVersion(n int) int { min := 0 max := n for min < max { mid := min + (max - min) / 2 if isBadVersion(mid) { max = mid // ture 刚好在或者曾经超过第一个谬误的版本 } else { min = mid + 1 // false 没超过第一个谬误的版本 } } return max}提交截图： ...

title: 每日一练（13）：反转链表 categories:[剑指offer] tags:[每日一练] date: 2022/01/26 每日一练（13）：反转链表定义一个函数，输出一个链表的头节点，反转该链表并输入反转后链表的头节点。 示例: 输出: 1->2->3->4->5->NULL输入: 5->4->3->2->1->NULL 限度： 0 <= 节点个数 <= 5000 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 办法一：双指针具体过程如下： 假如链表为 1→2→3→∅，咱们想要把它改成∅←1←2←3。 在遍历链表时，将以后节点的 next 指针改为指向前一个节点。因为节点没有援用其前一个节点，因而必须当时存储其前一个节点。在更改援用之前，还须要存储后一个节点。最初返回新的头援用。 复杂度剖析 工夫复杂度：O(n)，其中 n 是链表的长度。须要遍历链表一次。空间复杂度：O(1)。ListNode* reverseList(ListNode* head) { if (head == nullptr) { return nullptr; } ListNode *prev = nullptr; ListNode *curr = head;//双指针解法 while (curr) { ListNode *next = curr->next; //保留一下 cur的下一个节点，因为接下来要扭转cur->next curr->next = prev; //翻转操作 prev = curr; //更新pre 和 cur指针 curr = next; } return prev;}办法二：递归复杂度剖析 ...

本专题旨在分享刷Leecode过程发现的一些思路乏味或者有价值的题目。【当然是基于js进行解答】。（这道题应该算是二叉树的根底题，倡议还是学一下，不难且经典） 题目相干原题地址: https://leetcode-cn.com/probl...题目形容: 从上到下按层打印二叉树，同一层的节点按从左到右的程序打印，每一层打印到一行，例如，给定二叉树: [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回其档次遍历后果： [ [3], [9,20], [15,7]]Tips思考某些同学可能比拟少用js来刷leetcode，咱们在这里简略介绍下,对于树类型的数据输出,在js里的示意。 形如上题中的内容，给定二叉树的输出，其实并非一个数组，而应该是如下所示: 每个节点是一个object const input = { val: 3, left: { // left示意以后节点的左侧子节点 val: 9, left: null, // 对照上图能够看到 节点9没有左右子节点 right: null, }, right: { val: 20, left: { val: 15, // 对照上图能够看到 节点15没有左右子节点 left: null, right: null, }, right: { val: 7, // 对照上图能够看到 节点7没有左右子节点 left: null, right: null, }, } }思路解析这道题比拟根底，其实考的是BFS+层序遍历，怎么说呢？ ...