Leetcode个人解题总结

题目形容给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 因为返回类型是整数，后果只保留 整数局部 ，小数局部将被 舍去 。 留神： 不容许应用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1： 输出： x = 4输入： 2示例 2： 输出： x = 8输入： 2解释： 8 的算术平方根是 2.82842..., 因为返回类型是整数，小数局部将被舍去。提醒： 0 <= x <= 231 - 1力扣原题目地址：https://leetcode.cn/problems/...思路解法剖析求一个数的平方根的值，由数学常识知，那么这个值，肯定是小于等于这个数的，如：0的平方根为0，等于01的平方根为1，等于12的平方根约为1.414，小于23的平方根约为1.732，小于34的平方根为2，小于4......x的平方根为m，m小于等于x所以x的平方根的值，肯定是介于0和x之间的一个数所以，咱们能够应用双指针的形式，定义两个指针，右边指针为0，左边指针为x，而后通过中位数的积，去与x的值进行判断，等于阐明间接找到了；大于x那就把右侧指针往左挪动，即减小减一；小于x那就把左侧指针往右挪动，即增大加一； 如下代码： 实现形式一（耗时略长）var mySqrt = function (x) { let left = 0 // 左侧指针初始为0 let right = x // 右侧指针初始为x自身 while (left <= right) { // 只有left小于等于right就始终执行，直至大于才进行 // 保留整数局部，以9为例，中位数4.5保留4即可 let middle = Math.floor((left + right) / 2) if (middle * middle == x) { // 若等于则是刚好找到 return middle // 刚好找到则间接返回即可 } else if (middle * middle > x) { // 若大于超过了 right = right - 1 // 那就减小一些 } else if (middle * middle < x) { // 若小于为达到 left = left + 1 // 那就增大一些 } } return right // 返回指针值即为平方根（四舍五入）};提交截图（超出工夫限度）写完当前，咱们间接提交LeetCode，发现：超时了！！！ ...

要求Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. ExamplesInput: nums = [1,2,3,1]Output: trueInput: nums = [1,2,3,4]Output: falseInput: nums = [1,1,1,3,3,4,3,2,4,2]Output: true输出值范畴1 <= nums.length <= 105-109 <= nums[i] <= 109解答class Solution { public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for(int i = 1;i<nums.length;i++){ if(nums[i] == nums[i-1]){ return true; } } return false; }}先排序，如果一个数字呈现了n次，那阐明至多呈现两次，则肯定在遍历时遍历到后一个数等于前一个数，间接返回true。如果没有遍历到此状况，则阐明没有反复，返回false。

动静布局的几个前提条件：最优子结构性质无后向性子问题的重叠性 显然这道题是满足动静布局的解题条件的每个门路的长度取决于之前门路的值求解最大门路的过程中须要屡次用到之前求出的子门路的长度易得状态转移方程为 当 i>0 且 j>0 时，当i或j有一个等于0时，则无需思考子门路的抉择，即为 代码 func minPathSum(grid [][]int) int { //构建一个二维数组 m,n:=len(grid),len(grid[0]) order:=make([][]int,m) for i:=range order{ order[i]=make([]int,n) } //计算门路长度 order[0][0]=grid[0][0] for i:=1;i<n;i++{ order[0][i]=order[0][i-1]+grid[0][i] } for i:=1;i<m;i++{ order[i][0]=order[i-1][0]+grid[i][0] } for i:=1;i<m;i++{ for j:=1;j<n;j++{ order[i][j]=grid[i][j]+min(order[i-1][j],order[i][j-1]) } } return order[m-1][n-1]}func min(a int,b int)int{ if a<b {return a} return b}成果 此时工夫复杂度：O(mn)，其中 m 和 n 别离是网格的行数和列数。须要对整个网格遍历一次，计算 dp 的每个元素的值。 空间复杂度：O(mn)，其中 m 和 n 别离是网格的行数和列数。创立一个二维数组 dp，和网格大小雷同。 空间复杂度能够优化，例如每次只存储上一行的 \textit{dp}dp 值，则能够将空间复杂度优化到 O(n)O(n) 代码 func minPathSum(grid [][]int) int { //构建一个二维数组 m,n:=len(grid),len(grid[0]) last:=make([]int,n) now:=make([]int,n) last[0]=grid[0][0] for i:=1;i<n;i++{ last[i]=last[i-1]+grid[0][i] } now=last for i:=1;i<m;i++{ now[0]=last[0]+grid[i][0] for j:=1;j<n;j++{ now[j]=grid[i][j]+min(last[j],now[j-1]) } last=now } return now[n-1]}func min(a int,b int)int{ if a<b {return a} return b}成果 ...

题目形容如下 要找到最大容量首先确定公式area=（右左标点-左坐标点）*min（height[左],height[右]） 首先能想到的当然是简略粗犷的暴力解法 func maxArea(height []int) int { max:=0 for i:=1;i<len(height);i++{ for j:=0;j<i;j++{ area:=(i-j)*minNum(height[i],height[j]) max=maxNum(max,area) } } return max}func minNum(a int,b int)int{ if(a<b){return a} return b}func maxNum(a int,b int)int{ if(a>b){return a} return b}让咱们看看提交后果尽管通过了样例，但在提交时因为超出事件限度，不予通过显然，这道中等难度的题不容许咱们用O（n^2）这样辣鸡的算法来解决 要将其优化，我思考过动静布局，分治法，然而显然实现难度都较大而，双指针，这个神奇的工具，再一次展现出了他神奇的魅力 上代码 func maxArea(height []int) int { max:=0 left,right:=0,len(height)-1 for left<right{ area:=(right-left)*minNum(height[left],height[right]) max=maxNum(max,area) if height[left]<height[right]{ left++ }else { right-- } } return max}func minNum(a int,b int)int{ if(a<b){return a} return b}func maxNum(a int,b int)int{ if(a>b){return a} return b}首先，先将初始状态设置为容器底部最大的状态，同时双指针开始挪动，底部逐步放大，寻找最大容积 ...

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（146）LRU 缓存一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。哈希法”。// 技巧：遇到 O(1) 的get、put操作，优先思考 哈希表（JS里的Map数据结构）。/** * @param {number} capacity */var LRUCache = function(capacity) { this.capacity = capacity; this.curCapacity = 0; // 注：越是最近应用的key，就越往 map 的前面放！ this.map = new Map();};/** * @param {number} key * @return {number} */LRUCache.prototype.get = function(key) { const {map} = this; let resVal = -1; // 边界1：get操作，若 曾经有该key， // 则 先删该key、接着把该key放到map的最初 —— 示意最近应用过该key！ if (map.has(key)) { resVal = map.get(key); map.delete(key); map.set(key, resVal); } return resVal;};/** * @param {number} key * @param {number} value * @return {void} */LRUCache.prototype.put = function(key, value) { const {capacity, curCapacity, map} = this; // 边界2：put操作，若 曾经有该key， // 则 先删该key、接着把该key放到map的最初 —— 示意最近应用过该key！ if (map.has(key)) { map.delete(key); map.set(key, value); return; } // 边界3：put操作，若 以后曾经放不下了（即 curCapacity >= capacity ）， // 则 删除map的第一个key 且 将新key放到map的最初 —— 示意最近应用过该key！ if (curCapacity >= capacity) { for (const [key, val] of map) { map.delete(key); break; } map.set(key, value); } // 边界4：put操作，若 以后放得下（即 curCapacity < capacity ）， // 则 间接将新key放到map的最初 —— 示意最近应用过该key 且 this.curCapacity++ 。 else { map.set(key, value); this.curCapacity++; } // 注：以上 5行 ，能够合并成如下 2行 （但为了可读性，可分拆为 if、else 2分支）： // } // map.set(key, value);};2 计划21)代码： ...

题目形容 要害思维日程列表中依照程序排序：不便大小比拟 首先进行大略的区间判断：通过二分查找初步确认应该插入的地位(index)判断插入日程是否与(index)相邻日程重叠，若无重叠则增加返回true，重叠则插入失败返回false。能够插入的几种状况：状况一：index为0，也就是说插入日程后面没有日程了，若插入日程的完结日期比日程表第一个日程开始工夫还早：end<=schedule[0][0]状况二：index不为0，若插入日程的开始日期比前一个日程的完结日期晚，并且插入日程的完结日期比下一个日程的开始日期早：start>=schedule[index][1]&&end<=this.schedule[index+1][0]（因为左开右闭）状况三：index不为0，若插入日程的开始日期比前一个日程的完结日期晚，并且前面没有日程了，能够直接插入:start>=schedule[index][1]&&index+1>=len代码实现var MyCalendar = function() { this.schedule = [];};/** * @param {number} start * @param {number} end * @return {boolean} */MyCalendar.prototype.book = function(start, end) { const len=this.schedule.length; //如果此时日程表中无日程，则间接增加日程 if (len === 0) { this.schedule.push([start, end]); return true; } //1.二分查找 let r=len; let l=0; while(l<r){ let mid = l + ((r - l) >> 1); if(this.schedule[mid][1] <= start){ l=mid+1; }else{ r=mid; } } //2.判断日程是否能插入 let index=l-1;//二分查找初步定的插入地位 let insertIndex;//最终的插入地位 if(index===-1){ if(this.schedule[0][0]>=end){ insertIndex=0; } }else{ if(start>=this.schedule[index][1]&&(index+1>=len||end<=this.schedule[index+1][0])){ insertIndex=index+1; } } //3.插入操作 if(insertIndex!==undefined){ this.schedule.splice(insertIndex,0,[start,end]); return true } return false };一些细节和纳闷在二分查找中寻找两头数：判断条件的程序问题：为什么index=l-1：

前缀树前缀树次要用来解决与字符串查找相干的问题。如果字符串的长度为k，因为在前缀树中查找一个字符串相当于顺着前缀树的门路查找字符串的每个字符，因而工夫复杂度是O（k）。 在哈希表中，只有输出残缺的字符串能力进行查找操作，在前缀树中就没有这个限度。例如，能够只输出字符串的后面若干字符，即前缀，查找以这个前缀结尾的所有字符串。如果要求依据字符串的前缀进行查找，那么正当利用前缀树可能是解决这个问题的要害。 实现前缀树/** * Initialize your data structure here. */var Trie = function() { this.children = {}; };/** * Inserts a word into the trie. * @param {string} word * @return {void} */Trie.prototype.insert = function(word) { let node = this.children; for (const ch of word) { if (!node[ch]) { node[ch] = {}; } node = node[ch]; } node.isEnd = true;};Trie.prototype.searchPrefix = function(prefix) { let node = this.children; for (const ch of prefix) { if(!node[ch]) { return false } node = node[ch] } return node;}/** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */Trie.prototype.search = function(word) { const node = this.searchPrefix(word) return node !== undefined && node.isEnd !== undefined;};/** * Returns if there is any word in the trie that starts with the given prefix. * @param {string} prefix * @return {boolean} */Trie.prototype.startsWith = function(prefix) { return this.searchPrefix(prefix);};替换单词英语中有一个概念叫词根。在词根前面加上若干字符就能拼出更长的单词。例如，"an"是一个词根，在它前面加上"other"就能失去另一个单词"another"。当初给定一个由词根组成的字典和一个英语句子，如果句子中的单词在字典中有它的词根，则用它的词根替换该单词；如果单词没有词根，则保留该单词。请输入替换后的句子。例如，如果词根字典蕴含字符串["cat"，"bat"，"rat"]，英语句子为"the cattle was rattled by the battery"，则替换之后的句子是"the cat was rat by the bat"。/** * @param {string[]} dictionary * @param {string} sentence * @return {string} */var replaceWords = function(dictionary, sentence) { let children = {} // 构建前缀树 for(let word of dictionary) { let node = children; for(let ch of word) { if(!node[ch]) { node[ch] = {} } node = node[ch] } node.isEnd = true } return sentence.split(' ').map(word => { let node = children, tmp = '' for (let w of word) { node = node[w] tmp += w if (!node || node.isEnd) break } return node && node.isEnd ? tmp : word }).join(' ')};神奇的字典题目：请实现有如下两个操作的神奇字典。● 函数buildDict，输出单词数组用来创立一个字典● 函数search，输出一个单词，判断是否批改该单词中的一个字符，使批改之后的单词是字典中的一个单词。/** * Initialize your data structure here. */var MagicDictionary = function() { this.dictionary = []};/** * @param {string[]} dictionary * @return {void} */MagicDictionary.prototype.buildDict = function(dictionary) { this.dictionary = dictionary};/** * @param {string} searchWord * @return {boolean} */MagicDictionary.prototype.search = function(searchWord) { for (const dict of this.dictionary) { if (dict.length == searchWord.length) { let diff = 0 for (let i = 0; i < dict.length; i++) { if (dict[i] != searchWord[i]) diff++ if (diff > 1) break } if (diff == 1) return true } } return false};最短的单词编码单词数组 words 的 无效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：words.length == indices.length助记字符串 s 以 '#' 字符结尾对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符完结（但不包含 '#'）的 子字符串 恰好与 words[i] 相等/** * @param {string[]} words * @return {number} */var minimumLengthEncoding = function(words) { const set = new Set(words) for (const word of set) { for (let i = 1; i < word.length; i++) set.delete(word.substring(i)) } let sum = 0 for (const word of set) { sum += word.length + 1 } return sum};单词之和/** * Initialize your data structure here. */var MapSum = function() { this.map = new Map(); this.prefixmap = new Map();};/** * @param {string} key * @param {number} val * @return {void} */MapSum.prototype.insert = function(key, val) { // 防止反复 const delta = val - (this.map.get(key) || 0); this.map.set(key, val); for (let i = 1; i <= key.length; ++i) { const currprefix = key.substring(0, i); this.prefixmap.set(currprefix, (this.prefixmap.get(currprefix) || 0) + delta); }};/** * @param {string} prefix * @return {number} */MapSum.prototype.sum = function(prefix) { return this.prefixmap.get(prefix) || 0;};最大的异或这个是真的难，思路转换很微妙 ...

题目：在一个 n * m 的二维数组中，每一行都依照从左到右递增的程序排序，每一列都依照从上到下递增的程序排序。请实现一个高效的函数，输出这样的一个二维数组和一个整数，判断数组中是否含有该整数。 链接： 力扣Leetcode—剑指Offer—数组—04.二维数组中的查找. 示例 1： 现有矩阵 matrix 如下：[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 target = 5，返回 true。给定 target = 20，返回 false。思路：从矩阵左下角开始查找，因为矩阵有 每行的元素从左到右升序排列 和 每列的元素从上到下升序排列 的个性。如果以后地位小于target，往右挪动，如果以后大于target，往上挪动。所以咱们先查找到须要的那一行，而后再往列一个个找过来，就能找到须要的那个数存在不。 Go代码如下： package mainimport "fmt"func findNumberIn2DArray(matrix [][]int, target int) bool { // m 行 m := len(matrix) if m == 0 { return false } // n 列 n := len(matrix[0]) if n == 0 { return false } //从左下角开始遍历 i := m - 1 j := 0 for i >= 0 && j < n { // 等于target就输入 if matrix[i][j] == target { return true } else if matrix[i][j] < target { // 如果小于target，列+1 j++ } else { // 剩下大于target状况，行-1 i-- } } return false}func main() { a := [][]int{{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}} fmt.Println(findNumberIn2DArray(a, 5))}提交截图： ...

22. 括号生成题目： 数字 n 代表生成括号的对数，请你设计一个函数，用于可能生成所有可能的并且 无效的 括号组合。 示例 1：输出：n = 3输入：["((()))","(()())","(())()","()(())","()()()"]示例 2：输出：n = 1输入：["()"] 提醒：1 <= n <= 8 思路：对于括号的生成能够看成是对于左括号或者右括号的抉择。这样就能够转化为二叉树。如下图所示。只是并不是每一条分支都是最终的后果。须要恪守肯定的规定：1.以做括号结尾（第一位是左括号）2.左括号数量和右括号相等时，只能退出做括号。3.左括号和右括号数量都等于n时，退出数组。 代码如下： /** * @param {number} n * @return {string[]} */var generateParenthesis = function(n) { // 寄存后果的数组 let res = []; // 遍历函数 /** * @param string val 结点累计值 * @param int left 以后节点的残余左括号数 * @param int right 以后节点的残余右括号数 */ function tranverse(val, left, right) { // 左右括号用完就是后果，退出数组 if(left === 0 && right === 0) { res.push(val); } else if(left === 0 && right > 0) { // 左括号用完，只能退出右括号 tranverse(val+')',left,right-1); } else if(left === right) { // 曾经存在的左右括号数相等，然而没有达到n,只能退出左括号 tranverse(val+'(',left-1,right); } else if (left < right) { // 失常走两个分支 tranverse(val+'(',left-1,right); tranverse(val+')',left,right-1); } } tranverse('(', n-1, n); return res;};```

第一题 3的幂题目给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x   示例 1： 输出：n = 27输入：true示例 2： 输出：n = 0输入：false示例 3： 输出：n = 9输入：true示例 4： 输出：n = 45输入：false  提醒： -231 <= n <= 231 - 1  进阶：你能不应用循环或者递归来实现本题吗？ 相干标签递归数学 解题思路其中1162261467来自于 代码func isPowerOfThree(n int) bool { return n > 0 && 1162261467%n == 0}第二题 罗马数字转整数题目 解题思路 代码var symbolValues = map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}func romanToInt(s string) (ans int) { n := len(s) for i := range s { value := symbolValues[s[i]] if i < n-1 && value < symbolValues[s[i+1]] { ans -= value } else { ans += value } } return}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/roman-to-integer/solution/luo-ma-shu-zi-zhuan-zheng-shu-by-leetcod-w55p/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

第一题 Fizz Buzz题目信息 解题思路先赋i再找3的倍数赋Fizz再找5的倍数赋Buzz，其中如果遇到15的倍数就赋FizzBuzz 代码func fizzBuzz(n int) []string { s:=make([]string,n) for i:=0;i<n;i++{ s[i]=strconv.Itoa(i+1) } if n<3 {return s} for i:=2;i<n;i+=3{ s[i]="Fizz" } if n<5{return s} for i:=4;i<n;i+=5{ if (i+1)%15!=0{ s[i]="Buzz" }else{s[i]="FizzBuzz"} } return s}优化这种办法须要在每次赋值的时候写一个新的字符串退出数组能够应用官解的字符串拼接使效率失去晋升对于字符串拼接能够看这个：https://www.cnblogs.com/apoce... func fizzBuzz(n int) (ans []string) { for i := 1; i <= n; i++ { sb := &strings.Builder{} if i%3 == 0 { sb.WriteString("Fizz") } if i%5 == 0 { sb.WriteString("Buzz") } if sb.Len() == 0 { sb.WriteString(strconv.Itoa(i)) } ans = append(ans, sb.String()) } return}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/fizz-buzz/solution/fizz-buzz-by-leetcode-solution-s0s5/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析工夫复杂度：O(n)。须要遍历从 1 到 n 的每个整数，对于每个整数 i，生成 answer[i] 的工夫复杂度是 O(1)。 ...

什么是动静布局https://zhuanlan.zhihu.com/p/... 第一题 最大子序和题目信息 解题思路一开始在思考的时候走错了方向直到看到这条评论失去了启发 错误代码如下正确代码如下 func maxSubArray(nums []int) int { max := nums[0] for i := 1; i < len(nums); i++ { if nums[i] + nums[i-1] > nums[i] { nums[i] += nums[i-1] } if nums[i] > max { max = nums[i] } } return max}第二题 打家劫舍题目信息 解题思路同样为多决策问题，动静布局能够疾速的解决 代码func rob(nums []int) int { if len(nums) == 0 { return 0 } if len(nums) == 1 { return nums[0] } dp := make([]int, len(nums)) dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i := 2; i < len(nums); i++ { dp[i] = max(dp[i-2] + nums[i], dp[i-1]) } return dp[len(nums)-1]}func max(x, y int) int { if x > y { return x } return y}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

第一题 爬楼梯题目信息 解题思路对于n阶台阶每次的抉择为一阶或者两阶残余的台阶数别离为n-1和n-2咱们只须要别离求出n-1和n-2别离有多少种计划再将其相加，便失去了n阶台阶的计划 然而很惋惜运行的工夫太长了，通过不了 思考一下这个思路咱们会发现在求n阶的计划时，咱们须要别离求n-1和n-2的计划求n-1的计划时，咱们需要求n-2和n-3的计划如此除了求n阶计划之外，每个计划都求了两遍以上咱们能够很显著的留神到这个数列的实质理论为斐波那契数列咱们能够将其从递归调用转换为循环叠加这样，咱们就失去了官解的第一种解法 代码func climbStairs(n int) int { p, q, r := 0, 0, 1 for i := 1; i <= n; i++ { p = q q = r r = p + q } return r}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析工夫复杂度：循环执行 n 次，每次破费常数的工夫代价，故渐进工夫复杂度为 O(n)。空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。 优化 第二题 交易股票的最佳时机题目信息 解题思路 代码func maxProfit(prices []int) int { minPrice :=10000 maxProfit :=0 for i:= 0; i < len(prices); i++ { if prices[i] < minPrice { minPrice = prices[i] }else if (prices[i] - minPrice) > maxProfit { maxProfit = prices[i] - minPrice } } return maxProfit }

第一题 合并两个有序数组题目信息、 解题思路由题可知，咱们须要将第二个数组的元素合并到第一个数组之后返回 两个数组都是有序的，因而对于每个想要插入数组的元素，咱们只有找到首个大于这个元素的数，将其插入到这个数的后方即可 代码func merge(nums1 []int, m int, nums2 []int, n int) { k:=0 for i:=0;i<n;i++{ for nums1[k]<=nums2[i]{ if(k==m) {break} k++ } copy(nums1[k+1:m+1],nums1[k:m]) m++ nums1[k]=nums2[i] }}复杂度剖析工夫复杂度：O（m+n）执行的循环次数为数组二的个数n，也就是插入数组一的元素个数，再加上指针搜寻插入地位的挪动长度，最坏状况等于数组一的长度m空间复杂度：O（1），常数次空间 另一种解法此计划缩小了插入时的复制元素数量，效率失去了肯定的晋升 第二题 第一个谬误的版本题目信息 解题思路尽量减少调用的次数显然二分查找能最快的定位到第一个谬误版本每次将n个版本一分为二 取两头n/2的版本如果他是正确的版本，那么显然后面的局部都是正确的，谬误的版本就在前面的一半中如果他的谬误的版本，那么显然前面的局部都是谬误的，正确的版本就在后面的一半中持续进行二分搜寻，直到长度为一，那么他就是第一个谬误的版本 二分查找实用于有序的查找定位，能将O（n）的工夫复杂度升高到O（logn） 代码func firstBadVersion(n int) int { first:=1var mid intmid=(first+n)/2for mid!=first{ if isBadVersion(mid){ n=mid mid=(first+n)/2 }else { first = mid mid = (first + n) / 2 }}if isBadVersion(mid){return mid}return mid+1} 官解调用了sort包的search函数search函数的源码如下 复杂度剖析复杂度剖析 工夫复杂度：O(logn)，其中 n 是给定版本的数量。 空间复杂度：O(1)。咱们只须要常数的空间保留若干变量。

第一题 删除链表的倒数第N个节点题目信息给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 解题思路1.想要删除第n个节点，咱们只须要设一个指针，将其定位到n的前一个节点，而后将其next指针改为指向n的下一个节点便可实现操作。2.思考到链表长度可能为1，无奈定位到前一节点，咱们引入一个新的概念 代码如下func getLength(head *ListNode) (length int) { for ; head != nil; head = head.Next { length++ } return}func removeNthFromEnd(head *ListNode, n int) *ListNode { length := getLength(head) dummy := &ListNode{0, head} cur := dummy for i := 0; i < length-n; i++ { cur = cur.Next } cur.Next = cur.Next.Next return dummy.Next}复杂度剖析工夫复杂度：O(L+n)，其中 L 是链表的长度。 空间复杂度：O(1)。 另一种办法 先后指针 func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{0, head} first, second := head, dummy for i := 0; i < n; i++ { first = first.Next } for ; first != nil; first = first.Next { second = second.Next } second.Next = second.Next.Next return dummy.Next}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。双指针是一种很酷很弱小也很常见的解题工具 ...

title: 每日一练（8）：二进制中1的个数 categories:[剑指offer] tags:[每日一练] date: 2022/01/21 每日一练（8）：二进制中1的个数编写一个函数，输出是一个无符号整数（以二进制串的模式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明分量).）。 提醒： 请留神，在某些语言（如 Java）中，没有无符号整数类型。在这种状况下，输出和输入都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其外部的二进制示意模式都是雷同的。 在 Java 中，编译器应用 二进制补码 记法来示意有符号整数。因而，在下面的 示例 3 中，输出示意有符号整数 -3。 示例 1： 输出：n = 11 (控制台输出 00000000000000000000000000001011) 输入：3 解释：输出的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。 示例 2： 输出：n = 128 (控制台输出 00000000000000000000000010000000) 输入：1 解释：输出的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。 示例 3： 输出：n = 4294967293 (控制台输出 11111111111111111111111111111101，局部语言中 n = -3） 输入：31 解释：输出的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。 提醒： 输出必须是长度为 32 的 二进制串 。 起源：力扣（LeetCode） ...

大厂算法面试之leetcode精讲17.栈视频解说（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 Stack的特点：先进后出（FILO）应用场景：十进制转2进制 函数调用堆栈js里没有栈，然而能够用数组模仿 42/2 42%2=021/2 21%2=110/2 10%2=05/2 5%2=12/2 2%2=01/2 1%2=1stack: [0,1,0,1,0,1]res: 1 0 1 0 1 0fn1(){ fn2()}fn2(){ fn3() }fn3(){}fn1()stack:[fn1,fn2,fn3]栈的工夫复杂度：入栈和出栈O(1)，查找O(n) 20. 无效的括号 (easy)办法1.栈 思路：首先如果字符串能组成无效的括号，则长度肯定是偶数，咱们能够遍历字符串，遇到左括号则暂存，期待前面有右括号能够和它匹配，如果遇到右括号则查看是否能和最晚暂存的做括号匹配。这就和栈这种数据结构先进后出的个性相吻合了。所以咱们能够筹备一个栈寄存括号对，遍历字符串的时候，如果遇到左括号入栈，遇到右括号则判断右括号是否能和栈顶元素匹配，在循环完结的时候还要判断栈是否为空，如果不为空，则不是无效括号匹配的字符串复杂度剖析：工夫复杂度O(n)，空间复杂度O(n)，n为字符串的长度js: var isValid = function(s) { const n = s.length; if (n % 2 === 1) {//如果字符串能组成无效的括号，则长度肯定是偶数 return false; } const pairs = new Map([//用栈存储括号对 [')', '('], [']', '['], ['}', '{'] ]); const stk = []; for (let ch of s){//循环字符串 if (pairs.has(ch)) { //遇到右括号则判断右括号是否能和栈顶元素匹配 if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) { return false; } stk.pop(); } else { stk.push(ch);//如果遇到左括号入栈 } }; return !stk.length;//循环完结的时候还要判断栈是否为空};Java: ...

大厂算法面试之leetcode精讲13.枯燥栈视频解说（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 239. 滑动窗口最大值 (hard)办法1.优先队列动画过大，点击查看 思路：最大值问题咱们能够采纳大顶堆，具体就是保护一个大顶堆，初始的时候将0～k-1的元素退出堆中，存入的是值和索引的键值队，而后滑动窗口从从索引为k的元素开始遍历，将新进入滑动窗口的元素加堆中，当堆顶元素不在滑动窗口中的时候，一直删除堆顶堆元素，直到最大值在滑动窗口里。复杂度剖析：工夫复杂度O(nlogn)，n是nums的长度，将一个元素退出优先队列的工夫复杂度是logn，最坏的状况下所有元素都要入队，所以复杂度是nlogn。空间复杂度是O(n)，最坏的状况下，所有元素都在队列中，所以是O(n)js: class Heap { constructor(comparator = (a, b) => a - b, data = []) { this.data = data; this.comparator = comparator;//比拟器 this.heapify();//堆化 } heapify() { if (this.size() < 2) return; for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) { this.bubbleDown(i);//bubbleDown操作 } } peek() { if (this.size() === 0) return null; return this.data[0];//查看堆顶 } offer(value) { this.data.push(value);//退出数组 this.bubbleUp(this.size() - 1);//调整退出的元素在小顶堆中的地位 } poll() { if (this.size() === 0) { return null; } const result = this.data[0]; const last = this.data.pop(); if (this.size() !== 0) { this.data[0] = last;//替换第一个元素和最初一个元素 this.bubbleDown(0);//bubbleDown操作 } return result; } bubbleUp(index) { while (index > 0) { const parentIndex = (index - 1) >> 1;//父节点的地位 //如果以后元素比父节点的元素小，就替换以后节点和父节点的地位 if (this.comparator(this.data[index], this.data[parentIndex]) < 0) { this.swap(index, parentIndex);//替换本人和父节点的地位 index = parentIndex;//一直向上取父节点进行比拟 } else { break;//如果以后元素比父节点的元素大，不须要解决 } } } bubbleDown(index) { const lastIndex = this.size() - 1;//最初一个节点的地位 while (true) { const leftIndex = index * 2 + 1;//左节点的地位 const rightIndex = index * 2 + 2;//右节点的地位 let findIndex = index;//bubbleDown节点的地位 //找出左右节点中value小的节点 if ( leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 ) { findIndex = leftIndex; } if ( rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 ) { findIndex = rightIndex; } if (index !== findIndex) { this.swap(index, findIndex);//替换以后元素和左右节点中value小的 index = findIndex; } else { break; } } } swap(index1, index2) {//替换堆中两个元素的地位 [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]]; } size() { return this.data.length; }}var maxSlidingWindow = function(nums, k) { let ans = []; let heap = new Heap((a, b) => b.val - a.val);//大顶堆 for(let i=0;i<k-1;i++) heap.offer({val: nums[i], index: i});//初始的时候将0～k-1的元素退出堆中 for(let i=k-1; i<nums.length; i++){//滑动窗口从从索引为k-1的元素开始遍历 heap.offer({val: nums[i], index: i});//将新进入滑动窗口的元素加堆中 //当堆顶元素不在滑动窗口中的时候，一直删除堆顶堆元素，直到最大值在滑动窗口里。 while(heap.peek().index<=i-k) heap.poll(); ans.push(heap.peek().val);//将在滑动窗口里的最大值退出ans } return ans;}java: ...

大厂算法面试之leetcode精讲12.堆视频解说（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 延长：满二叉树：除叶子节点外，所有的节点都有两个子节点，这类二叉树称作满二叉树（Full Binarry Tree)，如下图： 齐全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左间断缺若干结点，这就是齐全二叉树。 堆是一个齐全二叉树，所以咱们能够采纳数组实现，不会节约太多空间，堆中的每个节点的值总是不大于或不小于其父节点的值，堆分为大顶堆和小顶堆，大顶堆堆顶是元素中最大的一个，小顶堆堆顶是最小的，在向堆中退出元素的时候，能动静调整堆内元素的程序，始终保持堆的性质。 堆的特点：外部数据是有序的能够弹出堆顶的元素，大顶堆就是弹出最大值，小顶堆就是弹出最小值每次退出新元素或者弹出堆顶元素后，调整堆使之从新有序仅须要O(logn)的工夫堆的实现用数组实现，堆从上到下，从左到右一一对应数组中的元素节点父节点索引 parentIndex = [(index - 1) / 2]，左节点索引leftIndex = index * 2 + 1，右节点索引 rightIndex = index * 2 + 2第一个非叶子节点是[size / 2]向堆中增加元素把新数据增加到树的最初一个元素，也就是数组的开端把开端节点向上调整，即bubbleUp工夫复杂度O(logn)动画过大，点击查看 弹出堆中的元素替换根节点与最初一个节点的值删除最初一个节点把根节点向下调整工夫复杂度O(logn)动画过大，点击查看 从一个数组中取出最小值的复杂度： 残缺代码class Heap { constructor(comparator = (a, b) => a - b, data = []) { this.data = data; this.comparator = comparator;//比拟器 this.heapify();//堆化 } heapify() { if (this.size() < 2) return; for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) { this.bubbleDown(i);//bubbleDown操作 } } peek() { if (this.size() === 0) return null; return this.data[0];//查看堆顶 } offer(value) { this.data.push(value);//退出数组 this.bubbleUp(this.size() - 1);//调整退出的元素在小顶堆中的地位 } poll() { if (this.size() === 0) { return null; } const result = this.data[0]; const last = this.data.pop(); if (this.size() !== 0) { this.data[0] = last;//替换第一个元素和最初一个元素 this.bubbleDown(0);//bubbleDown操作 } return result; } bubbleUp(index) { while (index > 0) { const parentIndex = (index - 1) >> 1;//父节点的地位 //如果以后元素比父节点的元素小，就替换以后节点和父节点的地位 if (this.comparator(this.data[index], this.data[parentIndex]) < 0) { this.swap(index, parentIndex);//替换本人和父节点的地位 index = parentIndex;//一直向上取父节点进行比拟 } else { break;//如果以后元素比父节点的元素大，不须要解决 } } } bubbleDown(index) { const lastIndex = this.size() - 1;//最初一个节点的地位 while (true) { const leftIndex = index * 2 + 1;//左节点的地位 const rightIndex = index * 2 + 2;//右节点的地位 let findIndex = index;//bubbleDown节点的地位 //找出左右节点中value小的节点 if ( leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 ) { findIndex = leftIndex; } if ( rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 ) { findIndex = rightIndex; } if (index !== findIndex) { this.swap(index, findIndex);//替换以后元素和左右节点中value小的 index = findIndex; } else { break; } } } swap(index1, index2) {//替换堆中两个元素的地位 [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]]; } size() { return this.data.length; }}

大厂算法面试之leetcode精讲10.递归&分治视频教程（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 递归三要素递归函数以及参数递归终止条件递归单层搜寻逻辑递归伪代码模版： function recursion(level, param1, param2, ...) { //递归终止条件 if (level > MAX_LEVEL) { // output result return; } //解决以后层 process_data(level, data, ...); //进入下一层 recursion(level + 1, p1, ...); //重置状态 reverse_state(level);}什么是分治：分治会将大问题拆解成小问题，拆解到最小问题之后，开始一直合并后果，递归是分治实现的一种模式或者是分治实现的一部分，分治包含三分局部，合成、计算、合并。分治的场景很多，例如疾速排序，归并排序。 分治伪代码模版： function divide_conquer(problem, param1, param2, ...){ if(problem === null){ // return result } //宰割问题 subproblem = split_problem(problem, data) //计算子问题 subResult1 = divide_conquer(subproblem[0], p1, ...) subResult2 = divide_conquer(subproblem[1], p1, ...) subResult3 = divide_conquer(subproblem[2], p1, ...) ... result = process_resule(subResult1, subResult2, subResult3,...)}举例计算n! n! = 1 * 2 * 3... * n ...

大厂算法面试之leetcode精讲9.位运算视频教程（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 位运算根底：程序中所有的数载计算机内存中都是以二进制存储的，位运算就是间接对整数在内存中的二进制进行操作，因为间接在内存中进行操作，不须要转成十进制，因而处理速度十分快 常见位运算 x & 1 === 0 //判断奇偶x & (x - 1) //革除最左边的1x & -x //失去最左边的1 191. 位1的个数 （easy） 办法1：循环每个二进制位思路：间接循环二进制中的每一位，判断是否为1，统计1的个数复杂度剖析：工夫复杂度O(k)，k=32。空间复杂度为O(1)Js: var hammingWeight = function(n) { let ret = 0; for (let i = 0; i < 32; i++) { if ((n & (1 << i)) !== 0) {//让1一直左移 判断该位是否为1 ret++; } } return ret;};Java: ...

搞定大厂算法面试之leetcode精讲4.贪婪视频教程（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 什么是贪婪算法贪婪法，又称贪婪算法，贪心算法，在对问题求解时，总是做出在以后看来最好的抉择，冀望通过每个阶段的部分最优抉择达到全局最优，但后果不肯定最优 实用场景：简略的说，问题可能分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪婪算法的到最初的最优解，这种子问题最优解称为最优子结构 贪婪算法与动静布局的不同点在于它对每个子问题的解决方案都做出以后的最优抉择，不能回退，而动静布局会保留之前的运算后果，并依据之前的后果进行抉择，有回退的性能，贪婪是动静布局的理想化的状况。 122. 交易股票的最佳时机 II（medium）办法1.动静布局 思路：依据题意只能持有一只股票，不限度交易次数，咱们能够用动静布局来做，首先定义状态，题中有两个状态，一个是天数，一个是是否持有股票，所以咱们定义dp[i][0]示意第 i天交易完后手里没有股票的最大利润，dp[i][1] 示意第 i天交易完后手里持有一支股票的最大利润，接下来就是定义状态转移方程： 如果以后的状态是dp[i][0]，示意手中没股票，则可由前一天的两种状况转移过去，第一种是dp[i-1][0]，示意前一天手里没股票，而且明天没做任何操作。第二种是dp[i-1][1]，示意前一天持有股票，然而明天卖了，所以收益是dp[i-1][1]+prices[i]，咱们需要求出这两种状况下的最大值就是最大利润，状态转移方程就是： dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); 如果以后的状态是dp[i][1]，示意手中有股票，则可由前一天的两种状况转移过去，第一种是dp[i−1][1]，示意前一天手中有股票，即是明天没做任何操作。第二种是dp[i−1][0]，示意前一天没有股票，然而明天买进了，所以收益是dp[i-1][1]-prices[i]，咱们需要求出这两种状况下的最大值就是最大利润，状态转移方程就是： dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); 由下面的状态转移方程咱们晓得，以后天的最大收益，只与前一天的状态相干，所以咱们能够不必定义二维数组来寄存状态，只须要将dp[i - 1][0]，dp[i - 1][1]寄存在变量中。 复杂度剖析：工夫复杂度：O(n)，n是数组长度，每天有持有股票或者没持有两种状态，一共2n的状态转移次数，工夫复杂度就是O(2n)，工夫复杂度和常系数无关，所以工夫复杂度就是O(n)。空间复杂度O(n)，因为要开拓n的空间寄存状态，尽管是二维数组，然而第二维是常数。如果进行了状态压缩，空间复杂度能够优化到O(1)js: var maxProfit = function (prices) { const n = prices.length; const dp = new Array(n).fill(0).map((v) => new Array(2).fill(0)); //初始化状态数组 (dp[0][0] = 0), (dp[0][1] = -prices[0]); //3.定义初始值 for (let i = 1; i < n; ++i) { //1.确定状态 //2.推导状态转移方程 //以后没持有股票，可由前一天的两种状态转移过了， //1是前一天没持有，明天不动，2是前一天持有，明天卖掉，求这两种状况的较大值 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); //以后持有股票，可由前一天的两种状态转移过了， //1是前一天持有，明天不动，2是前一天没持有，明天买入，求这两种状况的较大值 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } //4.确定输入值 return dp[n - 1][0]; //返回第n-1天的最大值};//空间压缩var maxProfit = function (prices) { const n = prices.length; let dp0 = 0, dp1 = -prices[0]; for (let i = 1; i < n; ++i) { let newDp0 = Math.max(dp0, dp1 + prices[i]); let newDp1 = Math.max(dp1, dp0 - prices[i]); dp0 = newDp0; dp1 = newDp1; } return dp0;};Java: ...

搞定大厂算法面试之leetcode精讲1.开篇介绍视频教程（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 为什么要学习数据结构和算法面试须要：大家都晓得，国内外的一二线互联网公司都须要面试算法，像google、fb或者像阿里、字节这样的公司，都喜爱在面试的最初环节让候选人手写一段代码解决某个问题，甚至是须要白板编程，没有任何编辑器的提醒，这就须要候选者有扎实的数据结构和算法的功力，而且对编码习惯、代码格调、设计模式都有较高的要求。不论是前端、后端、不论用什么语言，这些编程思维和解决问题的形式都是统一的。那么为什么这么多公司都喜爱考查数据结构和算法呢？这是因为啊，面试短短的1、2个小时，面试官很难判断候选人的能力，就算是考查我的项目教训和以往的开发教训，因为面试官没有参加过你开发过我的项目或者研发方向，也很难了解候选人面临的问题和挑战。而考查数据结构和算法，既是对编程根底的考查，又能很好的考量解决问题的能力、思考问题的形式和门路，以及编码的习惯和格调。 不晓得大家有没有这样的感觉，就是面试了很多公司，一到面试算法的局部总是掉链子，刷了很多题，然而仍然写不好，总是挂在手写题上，或者明明有能力但面试的时候却说不进去，究其原因就是短少正确的刷题形式和办法、以及刻意的练习。 外围能力的晋升： 数据结构和算法是程序员最外围的能力，不论负责什么业务，是前端还是后端还是人工智能畛域的工程师、这项能力都是一个必备的最根底的能力。为什么数据结构和算法这么重要呢。 咱们日常开发用到的大量的框架、库，都是以数据结构和算法为根底设计进去的，举个例子，react源码中就用到了大量的链表，还有小顶堆这些数据结构，作为应用了react多年的工程师，如果对日常应用的框架的底层原理和运行逻辑没有一个大略的意识，怎么能设计好技术计划，做好选型以及我的项目优化改良呢。数据结构和算法就好比武侠小说里的内力，而大家学的框架、库都是招式，框架常常会变，而数据结构和算法却是最根底也是最外围的能力，招式用的好不好，打进去的成果怎么，都须要弱小的内功来撑持。 千万不要说这些数据结构和算法我平时工作用不到啊，其实恰恰相反，如果想深挖技术，想要用算法晋升程序运行的效率，或者进步本人的编码能力，学习数据结构和算法是一个十分好的形式，这也是咱们的外围竞争力之一 晋升职业生涯的高度： 不晓得大家有没有遇见过一些技术很厉害的程序员，不论在哪家公司，他们总能找到本人的地位，随着工夫的推移，独立lead一个我的项目或者带团队都是迟早的事，为什么这些人职业生涯会走的更远呢？援用乔布斯的一句话，“Stay hungry，Stay foolish”。 要想职业生涯走的更高更远就须要一直精进本人的技术和能力，比方程序员最外围的数据结构和算法的能力，当然，如果走向了技术管理层，还须要技术的前瞻性和治理能力，这些都是须要办法和刻意练习。时刻放弃危机感，不要只停留在某个技术的应用层面，只有这样能抉择机会才会更多。 这里我分享一些集体的教训，不要置信所谓的35岁危机，实质就是到了相应的年龄就需更高的能力，不要做有效的内卷，然而根底的数据结构和算法却是必须的。底层能力能力决定咱们走多远。 怎么学习数据结构和算法理解根底的数据结构：比方链表、栈、队列、树等等，能够借助博客，书籍，课程进行学习，书籍比方「javascript数据结构与算法」，以及其余语言的数据结构和算法的书籍，不举荐「算法导论」，因为推理和证实性的内容很多。依照类别刻意练习：依照leetcode上的分类进行刷题，比方依照动静布局、分治、回溯等分类练习，leetcode题目尽管多，但如果按类别来刷，其实也没多少，很多题目都是相似的套路和延长，把握其中面试热门的一百多道就足够应酬面试了。如何刷题:切碎知识点：对每个类型的题目造成一套解题思路和模版，比方解动静布局的步骤有 依据重叠子问题定义状态寻找最优子结构推导状态转移方程确定dp初始状态确定输入值刻意练习：要练习缺点的、弱的中央，那些写起来不难受、不爽、干燥的题目就是薄弱点，不要只练习相熟类型的题反馈：在leetcode上寻找他人的解题思路，包含评论区的探讨，还有程序的运行工夫和占用内存的数据，顺便提一句，leetcode的运行工夫和占用内存状况的数据不精确，就当个参考就好，不要太在意运行工夫的排名。多写：重复练习，增强记忆，三分学，七分练。总结法则；将刷题的套路总结成本人办法，比方拆解问题、找根本的子问题、问题的组装、数学演绎等等。最初这些办法落实到代码层面无非是if else，for while、递归等，总结了这些法则，能力在题目变动的时候还能找到正确的解题门路。题目做多了也会有相应的感觉，有时从题目要求中也能显著的感觉到该用什么算法，比方题中提到了用O(logn)的复杂度来解，那很有可能要用到二分法，提到了O(nlogn)，那可能是用归并或者快排的思维解题。面试时如何做一道题明确题意：有不分明的中央要和面试官明确题目的意思，包含程序的非凡数据输出，数据量，边界条件的解决等等。可能的解：要尽可能的列出你晓得的办法，比照他们的优劣势，抉择你认为最好的办法进行编码。不要小看暴力解法，它往往是题目思考和优化的终点。写完之后进行复杂度剖析：包含工夫和空间复杂度剖析。 面试官往往是考查思考和解决问题的形式，咱们要尽量的让面试官看到咱们思考的门路和过程，即便最初的运行后果不太正确，也不肯定会影响最初的录用，可能也就是因为某个条件或者返回值呈现了问题。 在面试的过程中，如果齐全没有思路，也能够向面试官寻求提醒和帮忙，人无完人，就算是在平时的工作中咱们也会遇到困难，这不丢人，踊跃寻找帮忙也是推动我的项目后退的形式，没有问题有时候才是最大的问题。如果确定这道题是你齐全没有遇到过的，能够要求面试官更换一道题，与其浪费时间思考，不如间接换一道，兴许换了之后就是相熟的题目了，知识点和题目这么多，每个人都有本人的常识盲区。不要想着面试官是监考的老师，而是将来的共事，面试不是考试，大多数题都没有标准答案，有时候只有体现的比其余候选人更好一点就能够了。 课程特色leetcode分类解说：对leetcode高频面试题进行分类解说，讲到对应的题目时，会介绍对应的数据结构，它有什么特点，以及它的实现，比方堆的实现、字典树的实现等，而后会介绍这道题相应的算法，比方递归，回溯、贪婪、动静布局等。思考门路和套路：每道题都会列出尽可能多的解题形式，以及复杂度剖析，而后解说思考的门路，同类型的题总结相应的套路，比方二分法，双指针，动静布局，dfs，bfs等的模版。题目量和难度达到面试的要求：目前课程包涵174道高频面试题，后续会不定时减少新的面试题，其余同类型的题目根本都是这些问题的变种和延长，hard题22道，medium题83道，easy题69道，每道题都有具体的正文，前面还会更新更多大厂高频面试题节省时间：难题了解艰难，解法看不懂，花了大量工夫刷题还是刷不会，这可能是大家最头疼的问题了，这门课程会解说必要的前置常识，相应的解题套路，大量的图解配合视频解说，不多废话，做到通俗易懂，节俭大家的了解和刷题老本。在面试前几天疾速进入做题的状态。解题语言：这门课次要次要的用JavaScript来解题，也会附上Java的解题代码，数据结构和算法与相应的实现语言没有太大关系，不论用python还是Go，其实了解了逻辑和办法，只须要相应的改一下if else，for while，数组和对象的申明等等，就能够用对应的语言来解题了。适宜人群应届校招生：校招门槛水涨船高，对同学们的能力要求也越来越高，当然薪资必定也是一年比一年高，做到提前准备，提前刷题，对于处于行将毕业的计算机学科的同学来说还是很必要的。算法单薄退职工程师：社招的同学如果是想进入bat、美团、字节这样的公司，算法的考查根本是必考的，就算是一些中型的公司，当初也越来越多的考查同学们的根底能力了，对算法的考查也是十分重要的一个环节。课程纲要和目录

1.leetCode第20题https://leetcode-cn.com/probl... 给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否无效。无效字符串需满足：左括号必须用雷同类型的右括号闭合。左括号必须以正确的程序闭合。示例 1：输出：s = "()"输入：true示例 2：输出：s = "()[]{}"输入：true示例 3：输出：s = "(]"输入：false示例 4：输出：s = "([)]"输入：false示例 5：输出：s = "{[]}"输入：true括号是具备对称性的 比方'()'咱们就能够提前做一个映射表{'(':')'}，当检测到左括号时咱们将映射表相应的值放到栈中，持续遍历下一个字节是')'，那么咱们须要判断一下他是不是和咱们栈顶的元素一样 如果一样那就是非法的 function print(s) { //因为上题说了只校验这三种括号 建设关系表 let map = {"{": "}","[": "]","(": ")",}; let stack = []; for (let i = 0; i < s.length; i++) { if (s[i] == "{" || s[i] == "[" || s[i] == "(") { stack.push(map[s[i]]); } else { if (s[i] !== stack.pop()) { return false; } } } return !stack.length; }2.leetCode第21题https://leetcode-cn.com/probl... ...

543. 二叉树的直径要点：根节点要做的事件是：把左子树和右子树的高度相加，再加1即可失去该节点所形成的一条直径长度，用一个两头变量max记录最长直径，最终max就是后果。计算直径：1.获得左子树高度 2.获得右子树高度 3.加一，即把根节点也加进去，因而本题本质就是后续遍历，只是在后续遍历过程顺便计算每个子节点的高度。 class Solution { int max = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { height(root); return max - 1; } public int height(TreeNode root){ if(root == null) return 0; int left = height(root.left); int right = height(root.right); max = Math.max(left + right + 1,max); return Math.max(left,right) + 1; }}

Leetcode: 543. 二叉树的直径要点：二叉树的直径就是左右子树和根节点形成的最长节点数量减一。设置一个两头变量max，每次寻找左右子树和根节点所形成的节点数量与max比拟大小，较大的用max保留，直到最初所有左右子树和根节点形成的最长节点门路就是max，最初用max-1就是最大直径。该题的实质还是求树的深度。 class Solution { int max = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { depth(root); return max - 1; } public int depth(TreeNode root){ if(root == null) return 0; int l = depth(root.left); int r = depth(root.right); max = Math.max(max,l + r + 1); return Math.max(l,r) + 1; }}

Leetcode：110. 均衡二叉树 要点：本题的实质还是求二叉树的深度。编写一个函数depth用于求子树的深度，得出的左右子树之差的绝对值如果大于1，那么这棵树不是均衡二叉树，否则该树为均衡二叉树。 class Solution { boolean result = true; public boolean isBalanced(TreeNode root) { depth(root); return result; } public int depth(TreeNode root){ if(root == null) return 0; int l = depth(root.left); int r = depth(root.right); if(Math.abs(l - r) > 1) result = false; return Math.max(l , r) + 1; }}

Leetcode：104. 二叉树的最大深度 要点：利用递归，只看一个头节点须要做哪些事。本题中，头节点只需看它的左子树和右子树哪个的深度最大，取其中最大的深度，再在最大深度根底上+1就是本节点的最大深度。 class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; int l = maxDepth(root.left); int r = maxDepth(root.right); return Math.max(l,r) + 1; }}

Leetcode：725. 分隔链表 class Solution { public ListNode[] splitListToParts(ListNode head, int k) { int len = 0; ListNode temp = head; while(temp != null){ len++; temp = temp.next; } ListNode cur = head; int size = len / k; int mode = len % k; ListNode[] res = new ListNode[k]; for(int i = 0;i < k;i++){ res[i] = cur; int count = mode-- > 0 ? 1 : 0; for(int j = 0;j < size + count - 1;j++){ if(cur != null) cur = cur.next; } if(cur != null){ ListNode curTemp = cur.next; cur.next = null; cur = curTemp; } } return res; }}

Leetcode: 328. 奇偶链表 解法：设置一个标记位isOdd，因为开始从链表第一个元素遍历，因而isOdd初始值设为true，每遍历一个元素，isOdd=!isOdd，当isOdd为true，遍历到的元素插入到奇链表的尾部，当isOdd为false，元素插入到偶链表尾部，最终失去一个奇链表和偶链表，将奇链表的尾元素的下一个地位指向even.next。留神：偶链表的最初一个元素的next要设置为null，否则会呈现循环链表。 class Solution { public ListNode oddEvenList(ListNode head) { ListNode odd = new ListNode(-1),oddTail = odd; ListNode even = new ListNode(-1),evenTail = even; boolean isOdd = true; while(head != null){ if(isOdd == true){ oddTail.next = head; oddTail = oddTail.next; }else{ evenTail.next = head; evenTail = evenTail.next; } head = head.next; isOdd = !isOdd; } evenTail.next = null; oddTail.next = even.next; return odd.next; } }

11. 盛最多水的容器给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点别离为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴独特形成的容器能够包容最多的水。阐明：你不能歪斜容器。 示例 1：输出：[1,8,6,2,5,4,8,3,7]输入：49 解释：图中垂直线代表输出数组 [1,8,6,2,5,4,8,3,7]。在此状况下，容器可能包容水（示意为蓝色局部）的最大值为 49。 提醒：n = height.length2 <= n <= 3 * 1040 <= height[i] <= 3 * 104 My Answer: /** * @param {number[]} height * @return {number} *//** 最大值不仅与高无关，还与宽有关系（即横坐标差）， 因而在找值最大的两个点时，还应思考让横坐标差最大。 用两个指针left和right别离记录两个端点的坐标， left从左向右挪动，right从右向左挪动， 当 left所指向的点的高 小于 right所指向的点的高 时： left向右挪动，否则，right向右挪动。 */var maxArea = function(height) { let left=0; let right=height.length-1; let maxValue=0; while(left<right){ if(((right-left)*(height[left]>height[right]?height[right]:height[left]))>maxValue){ maxValue=(right-left)*(height[left]>height[right]?height[right]:height[left]) } if(height[left]<height[right]){ left++; } else{ right--; } } return maxValue;};12. 整数转罗马数字罗马数字蕴含以下七种字符： I， V， X， L，C，D 和 M。 ...

Leetcode：234. 回文链表 解法：先把链表中的元素值放入arrayList中，再判断arrayList的值是否回文来判断是否为回文链表。留神：不要把元素值放入int[]类型的数组，因为须要计算链表长度能力确定要开拓多大的int空间，消耗性能。 class Solution { public boolean isPalindrome(ListNode head) { ArrayList<Integer> arr = new ArrayList<Integer>(); while(head != null){ arr.add(head.val); head = head.next; } int first = 0; int last = arr.size() -1; while(first <= last){ if(arr.get(first) != arr.get(last)) return false; first++; last--; } return true; }}

Leetcode：445. 两数相加 II 解法：加法运算从低位开始运算，但低位数字在链表的开端，因而能够借助栈的后入先出个性来解决。首先把两链表中的元素别离压入两个栈st1和st2，而后弹出两栈的栈顶元素和进位三数相加失去和sum（进位carry初始值为0），取和sum%10作为低位数，用链表节点保留，从头插入链表结尾，取carry=sum/10作为下一个高位数的进位。只有两栈任意一个不为空或者carry大于0，都进行位数加法操作，并把保留后果得节点插入到结尾。 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> st1 = new Stack<>(); Stack<Integer> st2 = new Stack<>(); ListNode pre = new ListNode(-1,null); while(l1 != null){ st1.push(l1.val); l1 = l1.next; } while(l2 != null){ st2.push(l2.val); l2 = l2.next; } int carry = 0; while(carry > 0 || !st1.isEmpty() || !st2.isEmpty()){ int sum = 0; sum += carry; sum += st1.isEmpty()?0 : st1.pop(); sum += st2.isEmpty()?0 : st2.pop(); carry = sum / 10; ListNode node = new ListNode(sum % 10); node.next = pre.next; pre.next = node; } return pre.next; }}

24. 两两替换链表中的节点 1.双指针法 class Solution { public ListNode swapPairs(ListNode head) { ListNode pre = new ListNode(-1,head),temp = pre; while(temp.next != null && temp.next.next != null){ ListNode first = temp.next; ListNode second = temp.next.next; first.next = second.next; second.next = first; temp.next = second; temp = first; } return pre.next; }}

Leetcode：19. 删除链表的倒数第 N 个结点 1.双指针法 首先设置一个虚构头节点pre,目标是当删除的元素是第一个时，用pre头节点删除第一个节点操作很不便。指针first和second开始都指向虚构头节点pre。而后将second向后挪动n+1个节点，这样first和second就有n+1个节点。first和second指针每次往后挪动一个节点，这样当second指向链表尾部null时，first指针此时的地位为倒数第n+1个节点，因而first.next = first.next.next就删除了倒数第n个节点，最初返回pre.next即可。 class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(n <= 0) return null; ListNode pre = new ListNode(-1,head); ListNode first = pre,second = pre; for(int i = 0;i <= n;i++){ if(second == null) return null; second = second.next; } while(second != null){ first = first.next; second = second.next; } first.next = first.next.next; return pre.next; }2.栈 设置一个虚构头节点pre,目标是当删除的元素是第一个时，用pre头节点删除第一个节点操作很不便.将所有节点从头到尾全副压进栈中，包含虚构头节点。而后从栈中弹出n个节点，弹出n个节点后栈顶的元素就是n的前一个节点，假如为preNode，将preNode.next = preNode.next.next，最初返回pre.next即可。 class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(n <= 0) return null; ListNode pre = new ListNode(-1,head),temp = pre; Stack<ListNode> st = new Stack<>(); while(temp != null){ st.push(temp); temp = temp.next; } for(int i = 0;i < n && st.isEmpty() != true;i++){ st.pop(); } if(st.isEmpty()) return null; ListNode preNode = st.peek(); preNode.next = preNode.next.next; return pre.next; } }

5. 最长回文子串给你一个字符串 s，找到 s 中最长的回文子串。 示例 1：输出：s = "babad"输入："bab"解释："aba" 同样是合乎题意的答案。 提醒：1 <= s.length <= 1000s 仅由数字和英文字母（大写和/或小写）组成 My Answer: /** * @param {string} s * @return {string} *//** 依据回文对称的个性，从两头向两边进行判断，例如 aba 是回文，那么在此基础上判断 cabac 时，看最右边和最左边是否相等； 因而从长度为2到长度为n的字串顺次判断（长度为1肯定是回文）， 判断过程中应用矩阵 isPalindrome 进行记录 isPalindrome[i][j]值为1，示意原字符串的第i为到第j为字符串为回文字符串。 */var longestPalindrome = function(s) { // 字串长度 let subLength; // 解决数组 let arr=s.split(''); // 字串最大长度 let maxLength=1; // 返回后果字串 let resString=arr[0]; let isPalindrome=Array(arr.length).fill(0).map(x=>Array(arr.length).fill(0)); // 长度为1的字串为回文 if(arr.length<=1){ return resString; } for(let i=0;i<arr.length;i++){ isPalindrome[i][i]=1; } for(subLength=2;subLength<=arr.length;subLength++){ for(let i=0;i<=arr.length-subLength;i++){ let j=i+subLength-1; if(subLength===2 && arr[i]===arr[j]){ isPalindrome[i][j]=1; if(arr.slice(i,j+1).length>maxLength){ maxLength=arr.slice(i,j+1).length; resString=arr.slice(i,j+1).join(''); } } if(arr[i]===arr[j] && isPalindrome[i+1][j-1]){ isPalindrome[i][j]=1; if(arr.slice(i,j+1).length>maxLength){ maxLength=arr.slice(i,j+1).length; resString=arr.slice(i,j+1).join(''); } } } } return resString;};6. Z 字形变换将一个给定字符串 s 依据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。 ...

83. 删除排序链表中的反复元素 双指针法：定义两个指针temp和cur，开始时，temp指向head，cur指向head.next。遍历链表，如果temp.val = cur.val，temp指向cur的下个节点，cur指针往后移一个节点，这时cur指向的节点为新节点，因而temp指针无需挪动，如果temp.val != cur.val，temp和cur都各往后挪动一个节点，晓得遍历完链表。 class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode temp = head,cur = head; while(cur != null){ if(temp.val == cur.val){ temp.next = cur.next; cur = temp.next; }else{ temp = temp.next; cur = cur.next; } } return head; }}

Leetcode：21. 合并两个有序链表 解法：定义一个虚构头节点pre和一个永远指向链表尾部节点的指针temp，如果两链表都不为空，比拟两链表以后节点的值，较小的节点加链表尾部，以此类推，直到退出循环。退出循环时，如果两链表之前就不为空，则退出while肯定还有一个链表不为空，因为每个链表都是有序的，因而间接将没遍历完的链表增加到总链表尾部即可。在遍历的过程中，temp始终保持在链表的尾部，用于在尾部增加节点。 class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode pre = new ListNode(); ListNode temp = pre; while(l1 != null && l2 != null){ if(l1.val < l2.val){ temp.next = l1; l1 = l1.next; }else{ temp.next = l2; l2 = l2.next; } temp = temp.next; } if(l1 != null) temp.next = l1; if(l2 != null) temp.next = l2; return pre.next; }}

206. 反转链表 有三种解法：利用栈的个性来解，头插法和双指针法 1.利用栈 利用栈后入先出的个性，先把链表的元素全副压入栈中，而后出栈，把每一个出栈的元素插在链表尾部，即可实现反转，能够利用虚构头节点来辅助，指针temp始终指向链表尾部节点，便于尾部插入元素。留神：在尾部插入最初一个元素时，肯定记得在尾部加上null，不然最初元素的next指向倒数第二个元素，呈现循环链表。 class Solution { public ListNode reverseList(ListNode head) { if(head == null) return null; ListNode pre = new ListNode(-1),temp = pre; Stack<ListNode> st = new Stack<>(); while(head != null){ st.push(head); head = head.next; } while(!st.isEmpty()){ temp.next = st.pop(); temp = temp.next; } temp.next = null; return pre.next; }}2.头插法 如果head为空或者只有一个节点，则返回head即可。设置一个虚构头节点pre，而后将链表从头到尾遍历，每遍历一个元素，将该元素插入在pre和第一个元素之间，须要留神的是，在遍历过程中要用两头变量temp来保留以后元素的下一个节点，以防失落。 class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode pre = new ListNode(-1,null); while(head != null){ ListNode temp = head.next; head.next = pre.next; pre.next = head; head = temp; } return pre.next; }}3.双指针法 ...

Leetcode: 160. 相交链表两种解法：双指针法和哈希表法。 1.双指针法 思路：链表A和B同时登程，链表A走到开端，跳到B的结尾持续走，B走到开端，同样跳到A持续走，如果A，B不相等，继续执行，如果A，B相等，有两种可能：①A=B=null，A和B都来到了各自的开端，A，B无交点。②A=B=链表交点，该状况A，B存在交点，这时返回A，B任一节点即可。因而如果两个链表相交，返回的值是两链表第一个交点，如果不相交，返回的是null。 //双指针法public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headA == null) return null; ListNode A = headA,B = headB; while(A!= B){ A = A == null?headA:A.next; B = B == null?headB:B.next; } return A; }}2.哈希表法 （1）如果指向链表的指针A或者B任何一个为空，则没有交点，返回null（2）把链表A所有节点退出先hashset（3）遍历链表B，在遍历过程中的节点如果在hashset中存在，则阐明该节点为公共节点，如果最终遍历完没有节点存在hashset中，两链表不相交，则返回空。 //哈希表法public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; HashSet<ListNode> set = new HashSet<ListNode>(); while(headA != null){ set.add(headA); headA = headA.next; } while(headB != null){ if(set.contains(headB)){ return headB; } headB = headB.next; } return null; }}

Leetcode：155. 最小栈 办法1: 关键点：定义两个栈st和stMin，st寄存所有元素，stMin寄存最小值。 压入： 行将入栈的元素如果val<stMin.peek()，则将val压入stMin，如果val>=stMin.peek()，将stMin栈顶元素再次压入stMin，无论什么状况都要把val压入st。 弹出： st和stMin别离弹出元素即可。 class MinStack { Stack<Integer> st; Stack<Integer> stMin; /** initialize your data structure here. */ public MinStack() { st = new Stack<Integer>(); stMin = new Stack<Integer>(); } public void push(int val) { st.push(val); if(stMin.isEmpty()){ stMin.push(val); }else if(val < getMin()){ stMin.push(val); }else{ stMin.push(stMin.peek()); } } public void pop() { if(st.isEmpty()){ return; }else{ st.pop(); stMin.pop(); } } public int top() { if(st.isEmpty()){ return -1; }else{ return st.peek(); } } public int getMin() { if(stMin.isEmpty()){ return -1; }else{ return stMin.peek(); } }}办法2: ...

Leetcode: 503. 下一个更大元素 II 关键点： 遍历数组nums时，用 for(int i = 0;i < nums.length * 2;i++) 对数组遍历两次，下标index为i对长度len取余，否则会越界。具体见下列代码。 class Solution { public int[] nextGreaterElements(int[] nums) { Stack<Integer> st = new Stack<Integer>(); int len = nums.length; int[] res = new int[len]; Arrays.fill(res,-1); for(int i = 0;i < len * 2;i++){ int index = i % len; while(!st.isEmpty() && nums[st.peek()] < nums[index]){ res[st.pop()] = nums[index]; } st.push(index); } return res; }}

Leetcode: 739. 每日温度 要点： 把数组下标压进栈，行将进栈的下标元素对应的温度如果比栈顶元素对应的温度高，则该元素为左边第一个比栈顶元素对应温度高的温度下标，该元素与栈顶元素下标之差即为须要期待的天数，其余元素采纳雷同做法，最终后果放在数组res中。 class Solution { public int[] dailyTemperatures(int[] T) { Stack<Integer> st = new Stack<Integer>(); int len = T.length; int[] res = new int[len]; Arrays.fill(res,0); for(int i = 0;i < len;i++){ while(!st.isEmpty() && T[st.peek()] < T[i]){ int index = st.peek(); int day = i - st.pop(); res[index] = day; } st.push(i); } return res; }}

Leetcode: 20 无效的括号 关键点： 遍历到左括号"{","[","("时，入栈；遍历到右括号"}","]",")"时，判断栈顶是否为相应的左括号，如果是，则将栈顶元素出栈，如果不是或栈为空，则返回false。遍历字符完之后还要判断栈是否为空，目标是避免只有左括号，如“[[,{[”，如栈为空，则返回true，否则返回false。代码如下： class Solution { Stack<Character> st = new Stack<Character>(); HashMap<Character,Character> map = new HashMap<Character,Character>(); public boolean isValid(String s) { //留神: '}':'{',而不是'{':'}' map.put('}','{'); map.put(')','('); map.put(']','['); for(char ch:s.toCharArray()){ if(map.containsKey(ch)){ if(!st.isEmpty() && st.peek() == map.get(ch)) st.pop(); else return false; } else st.push(ch); } //避免只有左括号，如”[[,{[” return st.isEmpty(); }}

Leetcode：剑指 Offer 59 - II. 队列的最大值双端队列queue为主队列，寄存全副元素，help用于寄存主队列的最大值。 1.入队： queue：把元素value直接插入queue后即可。help：把help前面的小于value用help.pollLast()删除，再把value用help.addLast()退出。 2.出队： queue：用queue.pollFirst（）把元素出队。help：如果pollFirst（）的元素等于help的左端头元素的值，用help.pollFirst()把元素出队。 class MaxQueue { LinkedList<Integer> queue; LinkedList<Integer> help; public MaxQueue() { queue = new LinkedList<Integer>(); help = new LinkedList<Integer>(); } public int max_value() { if(help.isEmpty()) return -1; return help.peekFirst(); } public void push_back(int value) { queue.addLast(value); while(!help.isEmpty() && value > help.peekLast()){ help.pollLast(); } help.addLast(value); } public int pop_front() { if(queue.isEmpty()) return -1; int value = queue.pollFirst(); if(value == help.peekFirst()){ help.pollFirst(); } return value; }}

Leetcode ： 用队列实现栈要害：元素入队后，把元素x前的其余元素从新出队，再入队，这样x就在队头了，其余元素采纳同样办法入队。 class MyStack { Queue<Integer> queue; /** Initialize your data structure here. */ public MyStack() { queue = new LinkedList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { //获取入队前的元素个数 int length = queue.size(); queue.offer(x); //将x前的元素从新入队再出队，最终x排在队头 for (int i = 0;i < length;i++){ queue.offer(queue.poll()); } } /** Removes the element on top of the stack and returns that element. */ public int pop() { if(empty()){ return -1; }else{ return queue.poll(); } } /** Get the top element. */ public int top() { if(empty()){ return -1; }else{ return queue.peek(); } } /** Returns whether the stack is empty. */ public boolean empty() { if(queue.isEmpty()){ return true; }else{ return false; } }}

精选 100 道力扣（LeetCode）上最热门的题目，本篇文章只有 easy 级别的，适宜初识算法与数据结构的老手和想要在短时间内高效晋升的人。 1.两数之和https://leetcode-cn.com/probl... 办法一/** * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function (nums, target) { for (let i = 0; i < nums.length; i++) { let diff = target - nums[i] for (let j = i + 1; j < nums.length; j++) { if (diff == nums[j]) { return [i, j] } } }}办法二/** * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function (nums, target) { var temp = [] for (var i = 0; i < nums.length; i++) { var dif = target - nums[i] if (temp[dif] != undefined) { return [temp[dif], i] } temp[nums[i]] = i }}14.最长公共前缀https://leetcode-cn.com/probl... ...

题目起源：力扣（LeetCode）链接：https://leetcode-cn.com/probl...题目形容 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。你能够按任意程序返回答案算法思维 结余每种输出只会对于一个答案，只须要思考第一个呈现的符合要求的答案就好了。采纳两层for循环，进行暴力遍历。代码展现 class Solution { public int[] twoSum(int[] nums, int target) { int[] result=new int[2] ; for(int i = 0;i < nums.length-1;i++){ for(int j = i+1;j < nums.length;j++){ if(nums[i]+nums[j]==target){ result[0]=i; result[1]=j; return result; } } } return null; }}感触（启发） 第一次在LeetCode刷题，作为一个程序员，始终都是据说过，胆怯本人做不进去就不敢入手。当我开始做时，只管想不到甚至看不懂大佬那些奇妙的办法，对于那些哈希形式只是晓得实践而写不进去。正是这样，我能力更快提高，并理解到该学些什么。今后，每天都要写一份笔记。愿大四秋招能顺利进入大厂。数组初始化以及在函数中的传递。这是本次我曾经想分明如何应用蛮力法却仍旧调试了一个多小时的起因。 数组的初始化分为动态初始化和动静初始化，上面为例子 1. int[] result = new int[]{0,1}；//动态初始化 // 动态初始化：程序员决定数组元素的初始值，零碎决定长度。 2. int[] result = new int[2];//动静初始化 // 动静初始化：程序员只决定数组元素的长度，零碎调配元素初始值. PS:int（初始值为0)，float（初始值为0.0），char（初始值为‘\u0000’），boolean（初始值为false）对于数组的传递，间接用回传的是a[0]的地址地位，间接写a就行了函数标准化。间接只是要求实现性能并没有思考标准接口以及多态（适宜多种状况），当初要规范化。对于一些模块化的函数还是要纯熟利用。比方明天题目里的String[]转换成int []是提供好的。如果本人写的话，齐全写不进去。 明天例子如下 public static int[] stringToIntegerArray(String input) { input = input.trim(); input = input.substring(1, input.length() - 1); if (input.length() == 0) { return new int[0]; } String[] parts = input.split(","); int[] output = new int[parts.length]; for(int index = 0; index < parts.length; index++) { String part = parts[index].trim(); output[index] = Integer.parseInt(part); } return output; } public static String integerArrayToString(int[] nums, int length) { if (length == 0) { return "[]"; } String result = ""; for(int index = 0; index < length; index++) { int number = nums[index]; result += Integer.toString(number) + ", "; } return "[" + result.substring(0, result.length() - 2) + "]"; } public static String integerArrayToString(int[] nums) { return integerArrayToString(nums, nums.length); }