Leetcode

题目要求： 思路： 画一个表格可以求出数组中所有元素的和为5，所以画一个（5*2+1）len(nums)的表格（也就是一个二维数组）-5~5表示把这个数组每一个元素加上或减去得到结果值的所有可能从[-1 -1 -1 -1 -1]到[+1 +1 +1 +1 +1]的所有可能遍历数组，当遍历到数组下标为0的元素时，也就是第一个1，它与加号减号的组合有两种：1 和 -1，所以得到-1的方法有1种，得到1的方法也有一种当遍历到数组下标为1的元素时，前面已经得到的可能的结果值为-1和1，那么在这个基础上，新加入新的1与加号减号的组合，可能得到-2（-1-1），可能得到0（-1+1或+1-1），可能得到2（+1+1），所以在-2的位置有一种方法，在0的位置有2种，在1的位置有1种依次遍历，遍历到最后，找到目标值所对应的列的最后一行，也就是3所对应的有5中方法，返回5即可要特殊注意： 当数组的第一个元素为0时，应初始化0的位置方法为2，因为0+0=0，0-0=0核心代码：dp = [[0 for i in range(2 * total + 1)] for j in range(len(nums))]# 如果数组的第一个元素为0，那么+0或是-0，结果都为0if nums[0] == 0: dp[0][total] = 2else: # total是数组元素的和，也是dp的行中，元素值为0的元素的下标 dp[0][total + nums[0]] = 1 dp[0][total - nums[0]] = 1for i in range(1, len(dp)): for j in range(len(dp[0])): # 注意边界 # 在第一个图中，dp[4][0]的当前元素值是1，对应的目标值是-5，那么-5加上或减去1可能是上一行得到的值，但是要注意-5-1也就是-6不在考虑范围内 # left和right都初始化为0，是因为在表格也就是二维数组中，0所在的列所对应的目标值是给定数组的所有元素可能得到的最小值，是一个极值，所以不到最后一行，也就是不遍历到最后一个数组元素是得不到这个值的，也就是，所有行的下标为0的位置（所有行的起始位置）的方法数一定是0，所以当left或right越界了，没有被赋新的值时，不会影响计算方法数 left, right = 0, 0 if j - nums[i] >= 0: left = j - nums[i] if j + nums[i] < 2 * total + 1: right = j + nums[i] dp[i][j] = dp[i - 1][left] + dp[i - 1][right]return dp[-1][total + S]完整代码：class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: total = sum(nums) if total < S: return 0 dp = [[0 for i in range(2 * total + 1)] for j in range(len(nums))] if nums[0] == 0: dp[0][total] = 2 else: dp[0][total + nums[0]] = 1 dp[0][total - nums[0]] = 1 for i in range(1, len(dp)): for j in range(len(dp[0])): left, right = 0, 0 if j - nums[i] >= 0: left = j - nums[i] if j + nums[i] < 2 * total + 1: right = j + nums[i] dp[i][j] = dp[i - 1][left] + dp[i - 1][right] return dp[-1][total + S]

题目要求： 思路： 得分为A[i] + A[j] + i - j，可以分为(A[i] + i)和(A[j] - j)，最高分为两个之和所以遍历数组，维护两个值，一个是A[i] + i的最大值，另一个是A[i] + i + A[j] - j的最大值第二个值维护的不是A[j] - j的最大值是因为最大值还与i - j有关，所以要根据i - j保存最大值核心代码：res , localmax = 0 , 0for index , value in enumerate(A): # 先保存全局的结果，因为localmax保存的是A[i] + i，如果先改变localmax，说明当前的A[i] - i最大，那么res就变成A[i] + i + A[i] - i，没有意义了 res = max(res, localmax - index + value) localmax = max(localmax, index + value)return res完整代码：class Solution: def maxScoreSightseeingPair(self, A: List[int]) -> int: res , localmax = 0 , 0 for index , value in enumerate(A): res = max(res, localmax - index + value) localmax = max(localmax, index + value) return res 直观一些：class Solution: def maxScoreSightseeingPair(self, A: List[int]) -> int: res, localmax = 0, 0 for i in range(len(A)): res = max(res, localmax - i + A[i]) localmax = max(localmax, A[i] + i) return res更直观：class Solution: def maxScoreSightseeingPair(self, A: List[int]) -> int: res, localmax = 0, 0 for i in range(len(A)): j = i res = max(res, localmax + A[j] - j) localmax = max(localmax, A[i] + i) return res

题目要求： 思路： 动态规划上当前的楼梯花费的体力最小值为，前一个楼梯和前面两个楼梯中较小的那一个加上当前楼梯需要花费的体力值维护一个数组dp用来保存上所有台阶需要花费的体力值，初始化前两个元素，第一个元素为0，第二个元素为上第一个台阶需要花费的体力值遍历数组，从下标位置为1开始遍历，因为下标位置为0的元素，也就是上第一个台阶所要花费的体力值已经保存在数组中了遍历结束后，数组dp的末尾两个元素中较小的就是花费最小的，因为从dp[-1]的那个元素可以一步走到阶梯顶，dp[-2]的元素也可以一步走到阶梯顶。核心代码：dp = [0, cost[0]]for i in range(1, len(cost)): dp.append(min(dp[i] + cost[i], dp[i - 1] + cost[i]))return min(dp[-1], dp[-2])完整代码：class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: if not cost: return 0 dp = [0, cost[0]] for i in range(1, len(cost)): dp.append(min(dp[i] + cost[i], dp[i - 1] + cost[i])) return min(dp[-1], dp[-2])因为只需要前一个台阶和前两个台阶，所以可以不用数组，维护两个值即可：class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: if not cost: return 0 pre, cur = 0, cost[0] dp = [0, cost[0]] for i in range(1, len(cost)): pre, cur = cur, min(pre + cost[i], cur + cost[i]) return min(pre, cur)

题目要求： 思路： 先将字符串分割为列表，分隔符为空格遍历这个数组，如果当前的元素长度小于给定的检索词，直接遍历下一个如果当前的元素长度等于或大于给定的检索词，遍历检索词，把这个元素和检索词逐个对比，如果不一致，直接break，如果一致，且当前的下标为检索词长度-1，说明当前的这个单词前面的几个字符正是检索词，返回这个单词的下标+1遍历结束返回-1，说明没有检索词作为前缀核心代码：nums = sentence.split(" ")for i in range(len(nums)): if len(nums[i]) >= len(searchWord): for j in range(len(searchWord)): if nums[i][j] == searchWord[j]: if j == len(searchWord) - 1: return i + 1 else: breakreturn -1完整代码：class Solution: def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: nums = sentence.split(" ") for i in range(len(nums)): if len(nums[i]) >= len(searchWord): for j in range(len(searchWord)): if nums[i][j] == searchWord[j]: if j == len(searchWord) - 1: return i + 1 else: break return -1

题目要求： 思路： 两个字符串逐个匹配，会遇到三种情况情况1：字符相等，或字符模式p中的字符为"?"，那么可以比对下一位情况2：字符不等，但字符模式p中的字符为星号（*）! 这种情况下，用一个prestar来标记遇到星号的下标，prestar初始化为-1将字符模式p的指针移到下一个位置并将s指针的当前指向的下标保存下来，用来标记当前对比过了情况3：字符不等，但是prestar不为-1，也就是在这之前出现过星号 那么把s字符串的指针移到之前对比过的下一个位置，再进行比对，把match也更改到下一个位置如果不为上述三种情况，也就是当前的两个字符不相同，之前也没有出现过星号，说明两个字符串真的不相同，返回False核心代码：i, j, prestar, match = 0, 0, -1, -1while i < len(pre): if j < len(cur) and (pre[i] == cur[j] or cur[j] == "?" ): i += 1 j += 1 elif j < len(cur) and cur[j] == "*": prestar = j j += 1 match = i elif prestar != -1: j = prestar + 1 i = match + 1 match = i else: return False完整代码：class Solution: def isMatch(self, pre: str, cur: str) -> bool: i, j, prestar, match = 0, 0, -1, -1 while i < len(pre): if j < len(cur) and (pre[i] == cur[j] or cur[j] == "?" ): i += 1 j += 1 elif j < len(cur) and cur[j] == "*": prestar = j j += 1 match = i elif prestar != -1: j = prestar + 1 i = match + 1 match = i else: return False # 上一段代码只跟踪了字符串s，也就是pre，如果字符模式p字符串后面还有字符，如果后面的字符是*，那么可以继续看下一个字符 while j < len(cur) and cur[j] == "*": j += 1 # 如果当前位置不为字符串p的长度，说明做字符串p的*后面（如果有），还有未匹配的字符，说明两个字符串不完全匹配 return j == len(cur)

题目要求： 思路： 创建一个二维数组，用来保存每个格子能取到的礼物的最大价值遍历数组，取到当前的礼物的最大价值是这个礼物的(上一格，或左面一格)两个中最大的价值+当前礼物的价值，把这个值存在二维数组中。最后返回二维数组的最后一个值就是最大的价值。核心代码：dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]for i in range(len(grid)): for j in range(len(grid[0])): # 处理了一下边界问题，如果当前礼物是第一个格子，那么它的最大价值就是它本身的最大价值 if i == 0 and j == 0: dp[i][j] = grid[0][0] # 如果当前的格子是在第一行，而且不是第一行的第一个，也就是说它没有上一行格子，那么它的价值是它本身加上它左面的格子 elif i == 0 and j != 0: dp[i][j] = dp[i][j-1] + grid[i][j] # 如果当前格子是在第一列，而且不是第一列的第一个，也就是说它没有左边的格子，那么它的价值是它本身加上它上面的格子 elif j == 0 and i != 0: dp[i][j] = dp[i - 1][j] + grid[i][j] else: dp[i][j] = max(dp[i - 1][j], dp[i][j-1]) + grid[i][j]return dp[-1][-1]完整代码：class Solution: def maxValue(self, grid: List[List[int]]) -> int: dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))] for i in range(len(grid)): for j in range(len(grid[0])): if i == 0 and j == 0: dp[i][j] = grid[0][0] elif i == 0 and j != 0: dp[i][j] = dp[i][j-1] + grid[i][j] elif j == 0 and i != 0: dp[i][j] = dp[i - 1][j] + grid[i][j] else: dp[i][j] = max(dp[i - 1][j], dp[i][j-1]) + grid[i][j] return dp[-1][-1]

题目要求： 思路： 上第一个台阶有一种方法：（1）1上第二个台阶有两种方法：（1）1+1（2）2上第三个台阶有四种方法：（1）1+1+1（2）1+2（3）2+1（4）3所以从上第四个台阶开始，就可以依据前面的数据进行计算，比如上第四个台阶，可以从第一个台阶一次走三步上来，也可以从第二个台阶一次走两步上来，也可以第三个台阶一次走一步上来，所以走第四个台阶的方法总数是（台阶1的方法+台阶2的方法+台阶3的方法）从台阶4开始的每一个台阶，都可以根据当前台阶的前三个台阶的方法数和求来，所以只需要维护当前台阶的前三个台阶数即可核心代码：if n <= 2: return nstep1, step2, step3 = 1, 2, 4for i in range(3, n): step1, step2, step3 = step2 % 1000000007, step3 % 1000000007, (step1 + step2 + step3) % 1000000007return step3完整代码：class Solution: def waysToStep(self, n: int) -> int: if n <= 2: return n step1, step2, step3 = 1, 2, 4 for i in range(3, n): step1, step2, step3 = step2 % 1000000007, step3 % 1000000007, (step1 + step2 + step3) % 1000000007 return step3

题目要求： 思路： 定义一个flag用来表示当前公共字符串的长度，flag初始化为str[0]的长度遍历数组，当前的flag为（当前的字符串和flag）中最小的一个，例如，数组为 ["flower","flow","flight"]，遍历到flower时，flag为6，遍历到flow时，最长的公共前缀长度最长可能为4，也就是flow的长度，然后嵌套遍历，逐个比较str[0]和当前字符串的每个字符，遍历范围为flag，例如flower和flow，只需要比较range(len("flow"))即可。遍历到如果有不相同的，把当前的位数赋给flag，例如flower和flight，遍历到下标为2时，“o”和“i”不同，所以把2赋给flag。如果在遍历过程中，flag变为0，那么直接返回空字符串即可。最后返回str0核心代码：flag = len(strs[0])for i in range(len(strs)): flag = min(flag,len(strs[i])) if flag == 0: return "" for j in range(flag): if strs[0][j] != strs[i][j]: flag = j breakreturn strs[0][:flag]完整代码：class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" flag = len(strs[0]) for i in range(len(strs)): flag = min(flag,len(strs[i])) if flag == 0: return "" for j in range(flag): if strs[0][j] != strs[i][j]: flag = j break return strs[0][:flag]

题目要求： 思路： 维护一个tmp，用来保存临时的最大值维护一个res，用来保存全局最大值，也就是结果遍历数组，如果当前的tmp小于0，那么把当前的值赋给tmp，如果当前的值大于0，把当前的值加上tmp的值的和赋给tmp把res和tmp最大的那个赋给res循环结束，返回res核心代码：# res的初始值为数组当中的随机一个元素即可，初始不能为0，因为有可能数组中所有的元素都小于0res = nums[-1]tmp = 0for i in nums: if tmp < 0: tmp = i else: tmp += i res = max(res, tmp)return res完整代码：class Solution: def maxSubArray(self, nums: List[int]) -> int: res = nums[-1] tmp = 0 for i in nums: if tmp < 0: tmp = i else: tmp += i res = max(res, tmp) return res

题目要求： 思路： 每天都买卖股票，卖出前一天的，再买进当天的维护一个res用来保存总利润如果当天的股票价格比前一天的高，也就是有利润，把这个利润加到res中，如果没有利润，把res加0返回res核心代码：res = 0for i in range(1,len(prices)): res += max(0, prices[i] - prices[i - 1])return res完整代码：class Solution: def maxProfit(self, prices: List[int]) -> int: res = 0 for i in range(1,len(prices)): res += max(0, prices[i] - prices[i - 1]) return res

题目要求： 思路： 维护一个res用来保存结果集，维护一个mymin用来保存当前的最小值遍历数组，如果当前元素减掉mymin大于当前的res，把这个差值赋给res，如果当前的元素比mymin还小，把当前元素的值赋给mymin最后返回res核心代码：# 把第一个元素的值赋给mymin，作为初始最小值mymin = prices[0]# 用来保存结果res = 0# 遍历数组for i in range(len(prices)): # 如果当前元素减去前面的最小值大于res if prices[i] - mymin > res: # 把这个值赋给res res = prices[i] - mymin # 如果当前元素比之前遇到的所有元素的值都小，把这个值赋给mymin if prices[i] < mymin: mymin = prices[i]# 返回结果return res完整代码： class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 mymin = prices[0] res = 0 for i in range(len(prices)): if prices[i] - mymin > res: res = prices[i] - mymin if prices[i] < mymin: mymin = prices[i] return res

ARTSARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。 每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。本周内容本周的 ARTS 你将看到： 经典题「树中节点的最低公共祖先」一个 Golang 多队列的 worker-dispatcher 原型关于编程的方法论Algorithm这周的算法题是「树中节点的最低公共祖先」。[235. Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems...[236. Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems... 这两道题相同之处都是需要求公共祖先，但不同的是「二叉树」还是「二叉查找树」的最低公共祖先。对于二叉树，只能通过后序遍历来求。但是如果给出的两个节点如果互为父子的话，就无法通过简单的后序遍历来判断了，需要单独判断。这种方法对于任何的二叉树都是适用的，当然也包含二叉查找树 BST. 如果对 BST 的公共祖先也是用这种方式的话，因为没有利用 BST 本身的排序特性，必然时间复杂度上会吃亏。话不多说，直接上代码吧，欢迎拍砖。 先是普通二叉树节点的最低公共祖先代码。 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { // dfs 函数里的逻辑没办法包含 p q 互为父子的情况 // 这里只能单独判断 if isAcst(p, q) { return p } if isAcst(q, p) { return q } var ans *TreeNode var dfs func(node, p, q *TreeNode) (bool, bool) dfs = func(node, p, q *TreeNode) (bool, bool) { if node == nil { return false, false } leftFoundP, leftFoundQ := dfs(node.Left, p, q) rightFoundP, rightFoundQ := dfs(node.Right, p, q) foundP, foundQ := leftFoundP || rightFoundP, leftFoundQ || rightFoundQ // 因为是后序遍历，暂时想不到很好的剪枝办法 if ans == nil && (foundP && foundQ) { ans = node return true, true } if node == p { foundP = true } if node == q { foundQ = true } return foundP, foundQ } fp, fq := dfs(root, p, q) if ans == nil && (fp && fq) { ans = root } return ans}// return p if p is ancestor of qfunc isAcst(p, q *TreeNode) bool { var found bool var find func(node *TreeNode) find = func(node *TreeNode) { if node == nil { return } if found { return } if node == q { found = true return } find(node.Left) find(node.Right) } find(p) return found}然后是 BST 中节点的最低公共祖先。 ...

题目要求： 思路： 维护一个小根堆（父节点的值小于或等于子节点的值），小根堆拥有的节点数量是k，保持小根堆始终有k个元素。遍历数组，把当前元素加入到堆中，加入后判断堆的节点数量，如果大于k，把最小的元素取出，从堆中删除，这样保持堆中剩余的始终是最大的k个元素，堆顶是这些数字中最小的，也就是第k大的元素。Python heapq参考： https://docs.python.org/zh-tw...核心代码：# 小根堆用数组代替res = []# 遍历数组for i in nums: # 把当前元素添加到堆中，保持小根堆 heapq.heappush(res,i) # 如果堆中的元素数量，也就是数组的长度大于k if len(res) > k: # 把堆顶元素取出，也就是把最小的元素取出堆 heapq.heappop(res)# 如果res不为空，就返回res[0],如果res为空，说明最开始的数组就为空，返回Nonereturn res[0] if res else None完整代码：class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: res = [] for i in nums: heapq.heappush(res,i) if len(res) > k: heapq.heappop(res) return res[0] if res else None

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 demo01输入: s = "anagram", t = "nagaram"输出: truedemo02输入: s = "rat", t = "car"输出: false说明:你可以假设字符串只包含小写字母。 题解关键词：map 首先判断两个字符串长度是否相等，不相等则直接返回 false遍历串s为map赋值，组成字母为key，字母出现次数为value遍历串t，判断字母是否在map中，若在，map值减1，若不在，返回false算法完成，返回truevar isAnagram = function(s, t) { if (s.length !== t.length) { return false; } let obj = {}; for (let i = 0; i < s.length; i ++) { let char = s.charAt(i); obj[char] = obj[char] ? obj[char] + 1 : 1 } for (let i = 0; i < t.length; i++) { let char = t.charAt(i); if (!obj[char]) { return false; } if (obj[char] > 0 ) { obj[char] --; } } return true;};leetcode优秀题解guanpengchn 画解算法关键词：哈希映射 ...

力扣第169、171、189、198、202题169、多数元素 代码：class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; }}171、Excel表的序列号解题思路：标签：字符串遍历，进制转换初始化结果ans = 0，遍历时将每个字母与A做减法，因为A表示1，所以减法后需要每个数加1，计算其代表数值num = 字母 - ‘A’ + 1因为有26个字母，所以相当于26进制，每26个数则向前进一位所以每遍历一位则ans = ans * 26 + num以ZY为例，Z的值为26，Y的值为25，则结果为26 * 26 + 25=701时间复杂度：O(n)代码：class Solution { public int titleToNumber(String s) { int ans = 0; for(int i=0;i<s.length();i++) { int num = s.charAt(i) - 'A' + 1; ans = ans * 26 + num; } return ans; }}189、转转数组 解题思路一：最简单的方法是旋转 k 次，每次将数组旋转 1 个元素。 ...

41. 缺失的第一个正数题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/first-missing-positive 题目给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0]输出: 3示例 2: 输入: [3,4,-1,1]输出: 2示例 3: 输入: [7,8,9,11,12]输出: 1提示： 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。解题思路思路：交换 因为题目中要求【算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间】。 如果没有这样的限制，那么可以使用哈希表的方法： 将数组元素存入哈希表，从头遍历，判断是否在哈希表中（但是这种方法的时间复杂度虽然为 O(n)，但是空间复杂度也为 O(n)，不符合前提）但是仔细审题之后，会发现，因为题目所给的数组是没有经过排序的。那么如果将所给的数组进行恢复，到时候遍历查看即能找到缺失的正数。 在给定的数组中，我们需要找的整数一定是落在 [1, n+1] (n 表示数组长度) 这个区间。但是 n + 1 并不用求，因为当前面 n 个数不满足时，要求的自然就是 n+1。 我们看示例 2： 输入: [3,4,-1,1]输出: 2在这个例子当中，我们将其恢复，那么数组最终是这样的：[1, -1, 3, 4]，这样我们就可以发现，数组中缺失的就是就是数字 2。 那么现在的问题即是如何进行恢复。大致的思路是这样的：将 1 放到索引为 0 的位置上，2 放到索引为 1 的位置上，依次类推。 也即是说，设当前遍历的元素为 a，也就是说 a = nums[i]，如果 a 落在 [1, n]，根据上面的思路，那么 a 应该落在索引为 a-1 的位置。这个时候，交换 nums[i] 和 nums[a-1]，那么 a 就会落在正确的位置。但是这里交换位置后的元素如果还在 [1, n] 的范围内，还需要继续进行交换操作，直到 a 不再落在 [1, n]。具体的过程如下图所示： ...

题目要求： 思路： 开一个字典用来去重开一个新的链表用来返回遍历链表，如果当前值已经在字典中，直接遍历下一个，如果不在字典中，那么把这个值加到字典中后，加到新的链表中核心代码：# 新建一个链表节点作为返回链表的头n = ListNode(0)# 新建字典用来去重mydict = {}# 把新链表的头赋给tmp用来插入新节点tmp = n# cur用来保存遍历给定链表所到的节点cur = head# 遍历链表while cur: # 如果这个值已经在字典中，遍历下一个节点 if cur.val in mydict: cur = cur.next # 如果这个值不在字典中，把这个值添加到字典中，把这个节点添加到新链表中 else: mydict[cur.val] = True tmp.next = ListNode(cur.val) cur = cur.next tmp = tmp.next# 返回新链表头的下一个return n.next完整代码# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def removeDuplicateNodes(self, head: ListNode) -> ListNode: n = ListNode(0) mydict = {} tmp = n cur = head while cur: if cur.val in mydict: cur = cur.next else: mydict[cur.val] = True tmp.next = ListNode(cur.val) cur = cur.next tmp = tmp.next return n.next

题目要求： 思路： 把数组排序，遍历数组，遍历时用双指针寻找当前元素后面的所有元素中，与当前元素和最接近目标值target的两个元素，把三数之和作为res返回核心代码：# 把数组排序nums.sort()# 结果初始化为数组的前三个元素之和res = nums[0] + nums[1] + nums[2]# 遍历数组for i in range(len(nums)-2): left = i + 1 right = len(nums) - 1 while left < right: tmp = nums[i] + nums[left] + nums[right] # 如果当前的三个元素之和更接近目标值，把当前的三个元素之和赋给结果res if abs(tmp - target) < abs(res - target): res = tmp if tmp < target: left += 1 else: right -= 1return res完整代码：class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: if len(nums) < 3: return 0 nums.sort() res = nums[0] + nums[1] + nums[2] for i in range(len(nums)-2): left = i + 1 right = len(nums) - 1 while left < right: tmp = nums[i] + nums[left] + nums[right] if abs(tmp - target) < abs(res - target): res = tmp if tmp < target: left += 1 else: right -= 1 return res

最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列，有的则会换个说法，但最终考察的还是最长上升子序列。那么问题来了，它穿上衣服你还看得出来是么？ 如果你完全看不出来了，说明抽象思维还不到火候。经常看我的题解的同学应该会知道，我经常强调抽象思维。没有抽象思维，所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题，那你做的题意义何在？ 虽然抽象思维很难练成，但是幸好算法套路是有限的，经常考察的题型更是有限的。从这些入手，或许可以让你轻松一些。本文就从一个经典到不行的题型《最长上升子序列》，来帮你进一步理解抽象思维。 注意。 本文是帮助你识别套路，从横向上理清解题的思维框架，并没有采用最优解，所有的题目给的解法都不是最优的，但是都可以通过所有的测试用例。如果你想看最优解，可以直接去讨论区看。或者期待我的深入剖析系列。300. 最长上升子序列题目地址https://leetcode-cn.com/probl... 题目描述给定一个无序的整数数组，找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]输出: 4解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?思路美团和华为都考了这个题。题目的意思是让我们从给定数组中挑选若干数字，这些数字满足： 如果 i < j 则 nums[i] < nums[j]。问：一次可以挑选最多满足条件的数字是多少个。 这种子序列求极值的题目，应该要考虑到贪心或者动态规划。这道题贪心是不可以的，我们考虑动态规划。 按照动态规划定义状态的套路，我们有两种常见的定义状态的方式： dp[i] : 以 i 结尾（一定包括 i）所能形成的最长上升子序列长度, 答案是 max(dp[i])，其中 i = 0,1,2, ..., n - 1dp[i] : 以 i 结尾（可能包括 i）所能形成的最长上升子序列长度，答案是 dp[-1] （-1 表示最后一个元素）容易看出第二种定义方式由于无需比较不同的 dp[i] 就可以获得答案，因此更加方便。但是想了下，状态转移方程会很不好写，因为 dp[i] 的末尾数字（最大的）可能是 任意 j < i 的位置。 第一种定义方式虽然需要比较不同的 dp[i] 从而获得结果，但是我们可以在循环的时候顺便得出，对复杂度不会有影响，只是代码多了一点而已。因此我们选择第一种建模方式。 由于 dp[j] 中一定会包括 j，且以 j 结尾， 那么 nums[j] 一定是其所形成的序列中最大的元素，那么如果位于其后（意味着 i > j）的 nums[i] > nums[j]，那么 nums[i] 一定能够融入 dp[j] 从而形成更大的序列，这个序列的长度是 dp[j] + 1。因此状态转移方程就有了：dp[i] = dp[j] + 1 (其中 i > j, nums[i] > nums[j]) ...

1028. 从先序遍历还原二叉树题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal 题目我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。 如果节点只有一个子节点，那么保证该子节点为左子节点。 给出遍历输出 S，还原树并返回其根节点 root。 示例 1： 输入："1-2--3--4-5--6--7"输出：[1,2,5,3,4,6,7]示例 2： 输入："1-2--3---4-5--6---7"输出：[1,2,5,3,null,6,null,4,null,7]示例 3： 输入："1-401--349---90--88"输出：[1,401,null,349,88,90]提示： 原始树中的节点数介于 1 和 1000 之间。每个节点的值介于 1 和 10 ^ 9 之间。解题思路思路：栈 + 迭代 根据题意，结合示例和图例，我们可以得到如下信息： 遍历字符串时，读取 - 字符，直至遇到非 - 字符。此时我们可以通过 - 的个数判断当前节点的深度。（也印证题目中所说【在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度）】）；读取数字（这里注意示例 3，数字不仅是个位数），直到遇到非数字。这些数字则是节点的值。在题目中提及【如果节点只有一个子节点，那么保证该子节点为左子节点。】，根据这个前提开始进行分析。假设当前节点为 A，上一个节点为 B，那么这里可能出现的就是两种情况： A 是 B 的左子节点；A 不是 B 的左子节点；第一种情况就不解释了，这个相当于考虑前面的前提，因为当节点只有一个子节点，这个节点优先考虑是左子节点。所以这里先构建左子树。 因为本篇幅使用栈来辅助解决问题，栈存储的是等待构建子树的节点，当子树构建完成时，出栈。 如果当前节点的深度 < 栈的 size 时，这就表明上一个节点并不是当前节点的左子节点，也就是第二种所述的情况，（根据前面题目所提及的，如果节点只有一个子节点，这个子节点是左子节点）那么此时的 A 节点就是根节点到 B 节点（除 B 节点）这条路径的某个节点的右子节点。（这里考虑栈的 size 和当前节点的深度。） ...

297. 二叉树的序列化与反序列化题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree 题目序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 示例: 你可以将以下二叉树： 1 / \ 2 3 / \ 4 5序列化为 "[1,2,3,null,null,4,5]"提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。 解题思路思路：深度优先搜索 根据题目，我们可以了解到。其实二叉树序列化，是将二叉树按照某种遍历方式以某种格式保存为字符串。在本篇幅当中，我们使用的方法是使用深度优先搜索来达到这个目的。 在这里，我们使用的深度优先搜索的思路，用递归实现，在此过程中，我们使用先序遍历的方式来进行解决。 我们使用递归的时候，只需要关注单个节点，剩下就交给递归实现。使用先序遍历的是因为：先序遍历的访问顺序是先访问根节点，然后遍历左子树，最后遍历右子树。这样在我们首先反序列化的时候能够直接定位到根节点。 这里有个需要注意的地方，当遇到 null 节点的时候，要进行标识。这样在反序列化的时候才能够分辨出这里是 null 节点。 下面使用先序遍历的方式，借助示例 1，用图解的形式说明序列化的过程： 在上面的图示中，根据先序遍历的访问顺序，从根节点 1 开始，序列化字符为 1。然后遍历左子树，此时左子树的根节点为 2，序列化字符为 1, 2, 。这个时候从 2 开始，访问左节点 (1, 2, null, )，右节点 (1, 2, null, null)。在这里 null，就是前面所说标记 null 的符号。这个回到根节点，访问右子树。同样是按照先序遍历的访问顺序，最终序列化字符串的结果是： 1, 2, null, null, 3, 4, null, null, 5, null, null, 。 ...

297. 二叉树的序列化与反序列化题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree 题目序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 示例: 你可以将以下二叉树： 1 / \ 2 3 / \ 4 5序列化为 "[1,2,3,null,null,4,5]"提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。 解题思路思路：深度优先搜索 根据题目，我们可以了解到。其实二叉树序列化，是将二叉树按照某种遍历方式以某种格式保存为字符串。在本篇幅当中，我们使用的方法是使用深度优先搜索来达到这个目的。 在这里，我们使用的深度优先搜索的思路，用递归实现，在此过程中，我们使用先序遍历的方式来进行解决。 我们使用递归的时候，只需要关注单个节点，剩下就交给递归实现。使用先序遍历的是因为：先序遍历的访问顺序是先访问根节点，然后遍历左子树，最后遍历右子树。这样在我们首先反序列化的时候能够直接定位到根节点。 这里有个需要注意的地方，当遇到 null 节点的时候，要进行标识。这样在反序列化的时候才能够分辨出这里是 null 节点。 下面使用先序遍历的方式，借助示例 1，用图解的形式说明序列化的过程： 在上面的图示中，根据先序遍历的访问顺序，从根节点 1 开始，序列化字符为 1。然后遍历左子树，此时左子树的根节点为 2，序列化字符为 1, 2, 。这个时候从 2 开始，访问左节点 (1, 2, null, )，右节点 (1, 2, null, null)。在这里 null，就是前面所说标记 null 的符号。这个回到根节点，访问右子树。同样是按照先序遍历的访问顺序，最终序列化字符串的结果是： 1, 2, null, null, 3, 4, null, null, 5, null, null, 。 ...

30. 串联所有单词的子串题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words 题目给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。 示例 1： 输入： s = "barfoothefoobarman", words = ["foo","bar"]输出：[0,9]解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。示例 2： 输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]解题思路思路：滑动窗口 先用最简单的思路去尝试看能否解决问题。题目中说明要我们找到子串与 words 的单词完全匹配。那么最简单的思路就是判断子串是否符合，符合就将索引放到列表中，最后返回。 具体的做法如上图，循环遍历索引，判断子串是否符合。这里主要的问题是如何判断子串是否符合？ 题目中有个提示【注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。】，也就是说题目中并不要求子串完全按照顺序，只需要对应个数相等且中间连接部分不会有其他字符。这样就算匹配。 这里，我们可以借助哈希表解决。一个哈希表存储 words 的信息，键存储的是单词，值存储的是单词出现的个数。另外一个哈希表同样键存储的是单词，值存储单词出现的个数，这个哈希表在遍历字符串的同时进行维护，然后与前面的哈希表中的值进行比对。这里会出现如下情况： 当遍历存储的值大于存储 words 的哈希表中的 value 值时，显然是不成立的。进行判断下一个子串当小于的时候，接着进行判断。当子串完全符合的情况，那么这就是要找的子串，将其索引存入列表中，最后返回。但这里其实不必移动 1 个字符去匹配。题目有提及【一些长度相同的单词 words】，也就是说 words 中的单词的长度都是一样的。这样，每次移动就可以移动的偏移量就是单词的长度。 那么对单词使用滑动窗口，步长就是单词的长度 word_len。那么在 0 ~ word_len 的范围内，这里每个都作为滑动窗口的起点，进行滑动，就能覆盖所有字符串的组合。 ...

题目要求： 思路1： 定义数组num，长度为给定的n的长度如果n大于1，num[0]赋为1，因为走上第一个台阶只有一种方法，也就是迈一步如果n大于2，num[1]赋为2，也就是走上第二个台阶有两种方法，第一种是走一步，再走一步，第二种是直接走两步然后for循环遍历数组，从下标位置为2开始遍历，也就是上第三个台阶，可以是第二个台阶走一步，也可以是从第一个台阶走一步上来，那么第三个台阶的方法就是第二个台阶的方法加上第一个台阶的方法，也就是num[i]的台阶的方法数为num[i-1]与num[i-2]的和。最后返回数组最后一位元素的值即可核心代码：# 初始化数组，可以为0，可以为Nonenum = [0] * n# 如果 n 大于等于1，那么走第一个台阶的方法有一个，就是走一步if n >= 1: num[0] = 1 # 如果台阶数大于等于2，走第二个台阶的方法有两种 if n >= 2: num[1] = 2 # 第二个台阶之后的台阶就可以通过这个台阶的前两个台阶的方法数的和求来 for i in range(2,n): num[i] = num[i-1] + num[i-2]# 返回结果return num[-1]完整代码：class Solution: def climbStairs(self, n: int) -> int: num = [0] * n if n >= 1: num[0] = 1 if n >= 2: num[1] = 2 for i in range(2,n): num[i] = num[i-1] + num[i-2] return num[-1]思路2： ...

题目要求： 思路1： 定义数组num，长度为给定的n的长度如果n大于1，num[0]赋为1，因为走上第一个台阶只有一种方法，也就是迈一步如果n大于2，num[1]赋为2，也就是走上第二个台阶有两种方法，第一种是走一步，再走一步，第二种是直接走两步然后for循环遍历数组，从下标位置为2开始遍历，也就是上第三个台阶，可以是第二个台阶走一步，也可以是从第一个台阶走一步上来，那么第三个台阶的方法就是第二个台阶的方法加上第一个台阶的方法，也就是num[i]的台阶的方法数为num[i-1]与num[i-2]的和。最后返回数组最后一位元素的值即可核心代码：# 初始化数组，可以为0，可以为Nonenum = [0] * n# 如果 n 大于等于1，那么走第一个台阶的方法有一个，就是走一步if n >= 1: num[0] = 1 # 如果台阶数大于等于2，走第二个台阶的方法有两种 if n >= 2: num[1] = 2 # 第二个台阶之后的台阶就可以通过这个台阶的前两个台阶的方法数的和求来 for i in range(2,n): num[i] = num[i-1] + num[i-2]# 返回结果return num[-1]完整代码：class Solution: def climbStairs(self, n: int) -> int: num = [0] * n if n >= 1: num[0] = 1 if n >= 2: num[1] = 2 for i in range(2,n): num[i] = num[i-1] + num[i-2] return num[-1]思路2： ...

题目要求： 思路1（把str转换为list） 先判断数字是否小于0，小于0返回False判断数字是否小于10，如果小于10，返回True，因为个位数是回文数如果上述两项都不符合，把字符串转换为list，用双指针遍历数组，一个指针指向list头，一个指针指向list尾，相向遍历，挨个比对，是否相同，相同则遍历下一个，不同则返回False，注意这个遍历的范围从0到数组的一半即可思路2（不把str转换为list） 先判断数字是否小于0，小于0返回False判断数字是否小于10，如果小于10，返回True，因为个位数是回文数如果上述两项都不符合，定义一个res，使其等于给定的x，再定义一个tmp，把res的每一位数逆序保存到tmp中，最后返回tmp==x核心代码：if x < 0: return Falseif x < 10: return Trueres = xtmp = 0# 当res不为0时，说明res的每一位还没都保存到tmp中，继续循环while res != 0: # 把上一次循环的到的tmp乘10，加上当前的res的个位 tmp = tmp * 10 + res % 10 # 去掉res的个位 res //= 10# 循环结束，返回tmp是否等于xreturn tmp == x完整代码：class Solution: def isPalindrome(self, x: int) -> bool: if x < 0: return False if x < 10: return True res = x tmp = 0 while res != 0: tmp = tmp * 10 + res % 10 res //= 10 return tmp == x

题目要求 思路 创建一个数组mylist，长度为n，数组初始化所有元素为True创建另一个数组res，用来保存质数数组的0下标位置赋值为Fals，表示1不是质数遍历数组下标1~n，也就是遍历数字2-n，如果当前位置为True，把当前的元素append到结果集里，并把数组mylist中，所有当前元素的倍数都置为False，如果当前位置为False，xountine继续下一次循环最后返回res的长度核心代码：# 初始化标记数组mylist = [True]*n# res用来保存质数res = []# 因为1不是质数，所以数组下标为0的位置置为Falsemylist[0] = False# 遍历数字1~nfor i in range(1,n): # 如果标记数字是否为质数的值为False，说明它是某个数的倍数，直接continue进入下一次循环 if mylist[i-1] is False: continue # 如果为True else: # 把当前的数字append到结果集中 res.append(i) # 遍历从当前数字开始到结束的数字，步长为当前数组，也就是把当前数字所有的倍数找到，然后把它的数组的标记位置置为False for j in range(i,n,i): mylist[j-1] = False# 返回保存质数结果数组的长度return len(res)完整代码： 加上了判断给定的n值是否小于等于1class Solution: def countPrimes(self, n: int) -> int: if n <= 1: return 0 mylist = [True]*n res = [] mylist[0] = False for i in range(1,n): if mylist[i-1] is False: continue else: res.append(i) for j in range(i,n,i): mylist[j-1] = False return len(res)

ARTSARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。 每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。本周内容这周的 ARTS 你将看到： 动态规划典型中的典型，最长上升子序列。你对编程的热爱都用十年吗？这些 defer 的坑让你大呼卧槽。本周没有灵光一闪。Algorithm本周的算法题是经典题目：最长上升子序列。 LeetCode 1143. Longest Increasing Subsequence 这道题即是经典的动态规划题，也是经典面试题。但是因为前一段时间做了太多回溯相关的题，所以这道题我偏要用 DFS 来 AC，但没想到这真的挺坑。话不多说，直接贴 DFS 代码。 // 这是一次 DFS 的超低空飞行，危险刺激但是能 ACfunc lengthOfLIS_DFS(nums []int) int { var dfs func(s, prev, count int) int // 直接递归会超时，必须加记忆 // key 表示 nums 字符起始位置 // value 表示从 key 代表的位置开始到 nums 结尾 LIS 的长度增量 mem := make(map[int]int, 0) // s 正在处理的子串起始下标 // prev 递归树中上一个层级已构成的上升序列最大值（最后一个元素值） // count nums[s] 加入到递归分支的 LIS 之后 LIS 的长度 // 这样之所以可以记忆中间结果是因为 // 不同的递归求解 LIS 的过程可能会经过相同的 nums[s] // 只要当前到达的 nums[s] 相同的话，后续能将上升序列长度增加多少 // 完全取取决于 nums[s] 之后的子数组构成 // 这种记忆方式已经无限接近 DP 了 dfs = func(s, prev, count int) int { if _, ok := mem[s]; ok { return count+mem[s] } var ret int flag := false for i := s; i < len(nums); i++ { if nums[i] > prev { flag = true ret = max(dfs(i+1, nums[i], count+1), ret) } } if !flag { ret = count-1 } mem[s] = ret - count return ret } return dfs(0, -1<<31, 1)}func max(a, b int) int { if a < b { return b } return a}DFS 代码没有变量 mem 来记忆中间结果的话，肯定会超时，但是考虑如果做这个记忆的确花了很多时间。思考过程都在注释里了，下面是枯燥无味的 DP 解法。 ...

题目给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。示例 给定 nums = [2, 7, 11, 15]，target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回[0, 1]思考最简单、最直接的想法就是暴力的嵌套的双循环，遍历每个元素计算。空间复杂度虽然是O(1)，但是时间复杂度却是O($n^2$)，因为对于每个元素，都试图遍历它以外的所有元素来求解，这一次循环就耗费O(n)时间。所以对于长度越长的数组来说效率越低。所以需要一种更有效的方法来检查数组中是否存在所需的元素。如果存在，就返回它的索引。这里可以使用哈希表。通过牺牲空间换取时间。可以将查找时间从O(n)降底到O(1)，哈希表正是为此目的而构建，它支持以近似恒定的时间进行快速查找。之所以“近似”，是因为一旦出现冲突，查找时间可能退化到O(n)。只要仔细的挑选哈希函数，在哈希表中进行查找的用时应当被摊销为O(1)。使用哈希表的话，时间复杂度为O(n)，因为查找时间缩短到了O(1)。空间复杂度为O(n)。 解题思路关键点在于 nums[i] + nums[j] = target，即等于 nums[i] = target - nums[j]。可以做个哈希表，表里面存储以target - nums[j](目标元素)为键，当前索引为值。在迭代并将元素插入到表中的同时，进行检查表中是否已经存在当前元素所对应的目标元素。如果存在，即找到对应解，立即返回。 Python实现Python里面的字典就是利用哈希表存储的，可以拿来直接使用。 class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ if len(nums) <= 1: return [0, 0] d = dict() for i in range(len(nums)): if nums[i] in d: return [d[nums[i]], i] else: d[target - nums[i]] = i在LeetCode上跑了44ms ...

题目罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符 数值I 1V 5X 10L 50C 100D 500M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。 ...

题目编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。示例 1:输入: ["flower","flow","flight"]输出: "fl" 示例 2:输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。 说明:所有输入只包含小写字母 a-z 。 思考看见这个题目，我能想到的最简单最好理解的，就是先把所有的可能的公共前缀找出来，然后去一个一个比较。这个所有的公共前缀其实很简单，第一个字符串的的前1个字符，前2个字符，以此类推直到最后。这里只需要简单的双循环就能解决问题。 看了官解的解法，我自己的这个解法有点类似官解的水平扫描法，从左到右扫描。 解题思路把第一个字符串取出来，然后按照前1个字符，前2个字符，前3个字符，以此类推遍历一遍字符串，例如"flower"->["f","fl","flo","flow","flowe","flower"]然后就是简单的把上面得到的字符串，跟得到的需要比较的字符串全部遍历一遍如果找到了，那个字符串就是答案，没找到就返回空字符串Python实现class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if 0 == len(strs): return "" #分解第一个字符串 checkStrList = list() for i in range(len(strs[0])): checkStrList.append(strs[0][0:(i + 1)]) #排除比较第一个字符串 targetStrs = strs[1:] resStr = "" for checkStr in checkStrList: bForceEnd = False for targetStr in targetStrs: if not targetStr.startswith(checkStr): bForceEnd = True break if bForceEnd: break resStr = checkStr return resStr执行用时 :48 ms, 在所有 Python3 提交中击败了85.61%的用户，内存消耗 :14 MB, 在所有 Python3 提交中击败了5.53%的用户 ...

题目给出一个32位的有符号整数，你需要将这个整数中每位上的数字进行反装。示例1 输入：123输出：321示例2输出：-123输出：-321注意假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [-(2^31), 2^31 - 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。思考还是最简单的用数学方法加循环，取模和除法。 解题思路首先，循环倒序求出每一位数字。然后叠加到最后结果上，最后需要判断不要超出32位的有符号整数的表示范围。 Python实现class Solution: def reverse(self, x): """ :type x: int :rtype: int """ tempX = x bNegative = False intMax = (pow(2, 31) - 1) intMin = -(pow(2, 31)) if(tempX < 0): tempX = abs(tempX) bNegative = True res = 0 while(tempX != 0): num = tempX % 10 tempX = int(tempX / 10) res = res * 10 + num if(res >= intMax): return 0 elif(res <= intMin): return 0 if(bNegative): res *= -1 return res在LeetCode上跑了68ms ...

题目Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used: ...

背景记录一下，工作之所刷的 leetcode 题目。 01.twoSum/** * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function (nums, target) { for (var i = 1; i < nums.length; i++) { const idx = nums.indexOf(target - nums[i]); if (idx > -1 && idx !== i) { return [i, idx]; } } return [];};15.threeSum/** * @param {number[]} nums * @return {number[][]} */// Given array nums = [-1, 0, 1, 2, -1, -4],// A solution set is:// [// [-1, 0, 1],// [-1, -1, 2]// ]var threeSum = function (nums) { const result = []; const length = nums.length; if (length === 3) return [nums]; var sortedNums = num.sort((a, b) => a - b); for (let i = 0; i < l; i++) { if (i !== 0 && sortedNums[i] === sortedNums[i - 1]) continue; var j = i + 1; var k = l - 1; while (j < k) { var sum = temp[i] + temp[j] + temp[k]; if (sum === 0) { res.push([temp[i], temp[j], temp[k]]); while (j++ < k && temp[j - 1] === temp[j]) { /* do nothing*/ } while (k-- > j && temp[k] === temp[k + 1]) { /* do nothing*/ } } else if (sum < 0) { j++; } else { k--; } } } return result;};70.climbStairs/** * @param {number} n * @return {number} */var climbStairs = function (n) { const array = [0, 1, 2]; for (var i = 3; i <= n; i++) { array[i] = array[i - 1] + array[i - 2]; } return array[n];};283.moveZeroes/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */var moveZeroes = function (nums) { var validNumberCount = 0; for (var i = 0; i < nums.length; i++) { if (nums[i] !== 0) { nums[validNumberCount] = nums[i]; validNumberCount++; } } for (var j = validNumberCount; j < nums.length; j++) { nums[j] = 0; } return nums;};11.maxArea/** * @param {number[]} height * @return {number} */// solution 1: 暴力双循环var maxArea = function (height) { var max = 0; for (var i = 0; i < height.length; i++) { for (var j = i + 1; j < height.length; j++) { max = Math.max(max, (j - i) * Math.min(height[i], height[j])); } } return max;};// solution 1: 双指针var maxArea = function (height) { var max = 0; var left = 0, right = height.length - 1; while (left < right) { var area = (right - left) * Math.min(height[left], height[right]); max = Math.max(max, area); if (height[left] < height[right]) { left++; } else { right--; } } return max;};84.largestRectangleArea/** * @param {number[]} heights * @return {number} */// ## 柱状图中最大的矩形// solution1: 暴力循环var largestRectangleArea = function (heights) { var maxArea = 0; for (var i = 0; i < heights.length; i++) { for (j = i; j < heights.length; j++) { var minHeight = Number.MAX_VALUE; for (var k = i; k <= j; k++) { minHeight += Math.min(minHeight, heights[k]); } maxArea = Math.max(maxArea, minHeight * (j - i + 1)); } } return maxArea;};// solution2: 最小栈// TODO239.maxSlidingWindow/* * @lc app=leetcode.cn id=239 lang=javascript * * [239] 滑动窗口最大值 */// @lc code=start/** * @param {number[]} nums * @param {number} k * @return {number[]} */// 解法1: 暴力var maxSlidingWindow = function (nums, k) { var length = nums.length; if (!length) return []; var res = []; for (var i = 0; i < length - (k - 1); i++) { let max = Number.MIN_SAFE_INTEGER; for (j = i; j < i + k; j++) { max = Math.max(max, nums[j]); } res.push(max); } return res;};// @lc code=end289.rotateArray/** * @param {number[]} nums * @param {number} k * @return {void} Do not return anything, modify nums in-place instead. */// solution 1: 暴力, 每次移动一个var rotate = function (nums, k) { let previous; for (var i = 0; i < k; i++) { previous = nums[nums.length - 1]; for (var j = 0; j < nums.length; j++) { [previous, nums[j]] = [nums[j], previous]; } }};88.mergeTwoArray/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */// 解法1: 合并后排序var merge = function (nums1, m, nums2, n) { for (var i = 0; i < nums2.length; i++) { nums1[m + i] = nums2[i]; } nums1.sort((a, b) => a - b);};// 解法2: 判断元素大小, 直接插入var merge = function (nums1, m, nums2, n) { let length = m + n; while(n > 0) { if(m <= 0) { // num1中的元素已经排完， 剩下的nums直接放进来 nums1[--length] = nums2[--n]; continue; } nums1[--length] = nums1[m-1] > nums2[n-1] ? nums1[--m] : nums2[--n]; }};21.mergeTwoLists/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */var mergeTwoLists = function (l1, l2) { if (l1 === null) return l2; if (l2 === null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l2.next, l1); return l2; }};42.trap 接雨水/** * @param {number[]} height * @return {number} */var trap = function (height) { let capacity = 0; const stack = []; for (let i = 0; i < height.length; i++) { while (stack.length !== 0 && height[stack[stack.length - 1]] < height[i]) { let cur = stack[stack.length - 1]; stack.pop(); if (stack.length === 0) { break; } let l = stack[stack.length - 1]; let r = i; capacity += (Math.min(height[l], height[r]) - height[cur]) * (r - l - 1); } stack.push(i); } return capacity;};

[22].括号生成/* * @lc app=leetcode.cn id=22 lang=javascript * * [22] 括号生成 */// @lc code=start/** * @param {number} n * @return {string[]} */// solution: 回溯 + 剪枝var generateParenthesis = function (n) { var res = []; var initialPath = ''; dfs(res, n, n, initialPath); return res; function dfs(res, left, right, path) { if (left === 0 && right === 0) { res.push(path); return; } if (left > 0) { dfs(res, left - 1, right, path + '('); } if (left < right) { dfs(res, left, right - 1, path + ')'); } }};[01].两数之和/* * @lc app=leetcode.cn id=1 lang=javascript * * [1] 两数之和 */// @lc code=start/** * @param {number[]} nums * @param {number} target * @return {number[]} */// solution 1:var twoSum = function (nums, target) { for (var i = 1; i < nums.length; i++) { var idx = nums.indexOf(target - nums[i]); if (idx > -1 && idx !== i) { return [i, idx]; } } return [];};// solution 2:var twoSum = function (nums, target) { var dic = {}; for (var i = 0; i < nums.length; i++) { var complement = target - nums[i]; if (complement in dic) { return [dic[complement], i]; } dic[nums[i]] = i; }};// @lc code=end[40]. 最小的k个数/** * 40. 最小的k个数 * @param {number[]} arr * @param {number} k * @return {number[]} */var getLeastNumbers = function (arr, k) { var result = []; var nums = arr.sort((a, b) => a - b); for (var i = 0; i < k; i++) { result.push(nums[i]); } return result;};[49] 字母异位词分组/* * @lc app=leetcode.cn id=49 lang=javascript * * [49] 字母异位词分组 */// @lc code=start/** * @param {string[]} strs * @return {string[][]} */// 思路: 以排序后的 str 作为 key, values 为排序后为 key 的 str 集合.var groupAnagrams = function (strs) { const map = new Map(); for (var i = 0; i < strs.length; i++) { const sortedStr = strs[i].split('').sort().join(); if (map.has(sortedStr)) { let temp = map.get(sortedStr); temp.push(strs[i]); map.set(sortedStr, temp); } else { map.set(sortedStr, [strs[i]]); } } return [...map.values()];};// @lc code=end[94] 二叉树的中序遍历/* * @lc app=leetcode.cn id=94 lang=javascript * * [94] 二叉树的中序遍历 */// @lc code=start/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function (root) { var stack = []; function helper(node) { if (!node) return; node.left && helper(node.left); stack.push(node.val); node.right && helper(node.right); } helper(root); return stack;};// @lc code=end[242] 有效的字母异位词/* * @lc app=leetcode.cn id=242 lang=javascript * * [242] 有效的字母异位词 */// @lc code=start/** * @param {string} s * @param {string} t * @return {boolean} */// 方法1:var isAnagram = function (s, t) { return s.split('').sort().join('') == t.split('').sort().join('');};// 方法2: Setvar isAnagram = function(s, t) { if(s.length !== t.length) return false; var ary = new Array(26).fill(0); for(var i = 0; i < s.length; i++) { ary[s[i].charCodeAt(0) - 97]++; ary[t[i].charCodeAt(0) - 97]--; } for(var i = 0; i < ary.length; i++) { if(ary[i] !== 0) return false; } return true};// @lc code=end[347] 前 K 个高频元素/* * @lc app=leetcode.cn id=347 lang=javascript * * [347] 前 K 个高频元素 */// @lc code=start/** * @param {number[]} nums * @param {number} k * @return {number[]} */// 解法: 优先队列， 大顶堆var topKFrequent = function (nums, k) { var map = new Map(); var list = []; var result = []; for (var i = 0; i < nums.length; i++) { if (map.has(nums[i])) { let count = map.get(nums[i]); map.set(nums[i], count + 1); } else { map.set(nums[i], 1); } } for (let [key, value] of map.entries()) { list.push({ value, key }); } // 降序排列 list.sort((a, b) => b.value - a.value); for (let i = 0; i < k; i++) { result.push(parseInt(list[i].key, 10)); } return result;};// @lc code=end[429] N叉树的层序遍历/* * @lc app=leetcode.cn id=429 lang=javascript * * [429] N叉树的层序遍历 */// @lc code=start/** * // Definition for a Node. * function Node(val,children) { * this.val = val; * this.children = children; * }; *//** * @param {Node} root * @return {number[][]} */var levelOrder = function (root) { var initialLevel = 0; var stack = []; if (!root) return []; helper(root, initialLevel); return stack; function helper(node, level) { if (stack.length === level) { stack.push([]); } stack[level].push(node.val); for (var i = 0; i < node.children.length; i++) { helper(node.children[i], level + 1); } }};// @lc code=end[589] N叉树的前序遍历/* * @lc app=leetcode.cn id=589 lang=javascript * * [589] N叉树的前序遍历 */// @lc code=start/** * // Definition for a Node. * function Node(val, children) { * this.val = val; * this.children = children; * }; *//** * @param {Node} root * @return {number[]} */var preorder = function (root) { var stack = []; if (!root) return []; helper(root, stack); return stack; function helper(node, stack) { if (!node) return; stack.push(node.val); for (var i = 0; i < node.children.length; i++) { helper(node.children[i], stack); } }};// @lc code=end[590] N叉树的后序遍历/* * @lc app=leetcode.cn id=590 lang=javascript * * [590] N叉树的后序遍历 */// @lc code=start/** * // Definition for a Node. * function Node(val,children) { * this.val = val; * this.children = children; * }; *//** * @param {Node} root * @return {number[]} */var postorder = function (root) { var stack = []; if (!root) return []; helper(root, stack); return stack; function helper(node, stack) { if (!node) return; for (var i = 0; i < node.children.length; i++) { helper(node.children[i], stack); } stack.push(node.val); }};// @lc code=end

算法首先选一个基准 pivot，然后过一遍数组， 把小于 pivot 的都挪到 pivot 的左边，把大于 pivot 的都挪到 pivot 的右边。这样一来，这个 pivot 的位置就确定了，也就是排好了 1 个元素。 然后对 pivot 左边 ? 的数排序， 对 pivot 右边 ? 的数排序， 就完成了。 那怎么排左边和右边？ 答：同样的方法。 所以快排也是用的分治法的思想。 「分」选择一个 pivot，就把问题分成了 pivot 左边pivot 右边这两个问题。 「治」就是最开始描述的方法，直到每个区间内没有元素或者只剩一个元素就可以返回了。 「合」放在一起自然就是。 但是如何选择这个 pivot？ 取中间的？ 取第一个？ 取最后一个？ 举个例子：{5, 2, 1, 0, 3}.比如选最后一个，就是 3. 然后我们就需要把除了 3 之外的数分成「比 3 大」和「比 3 小」的两部分，这个过程叫做 partition（划分）。 这里我们仍然使用「挡板法」的思想，不用真的弄两个数组来存这两部分，而是用两个挡板，把区间划分好了。 我们用「两个指针」（就是挡板）把数组分成「三个区间」，那么 左边的区间用来放小于 pivot 的元素；右边的区间用来放大于 pivot 的元素；中间是未排序区间。 那么初始化时，我们要保证「未排序区间」能够包含除了 3 之外的所有元素，所以 ...

思路来源：https://leetcode-cn.com/probl... 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4func main(){ a := new(Node) a.Data = 1 a.Next = &Node{2, &Node{4, nil}} b := new(Node) b.Data = 1 b.Next = &Node{3, &Node{4, nil}} c := merge(a, b) for { fmt.Print(c.Data) if c.Next == nil { break } c = c.Next }}type Node struct { Data int Next *Node}func merge(a, b *Node) *Node { if a == nil { return b } if b == nil { return a } if a.Data < b.Data { a.Next = merge(a.Next, b) return a } b.Next = merge(a, b.Next) return b}

·解题思路来源https://github.com/azl3979858... package mainimport "container/list"import "fmt"func main(){ s := "{{}}" m := "{{[()}]}" l := "{[(())]}" fmt.Println(check(s)) fmt.Println(check(m)) fmt.Println(check(l))}func check(x string) bool { mapper := map[byte]byte{ '{':'}', '(':')', '[':']', } stack := list.New() //初始化栈 for _, v := range x { i := byte(v) if _, ok := mapper[i]; ok { //入栈 stack.PushFront(i) fmt.Println(i) } else { if stack.Len() == 0 { return false } l := stack.Remove(stack.Front()).(byte) r, ok := mapper[l] if !ok || r != i { return false } fmt.Printf("%s:%s", "S", string(i)) fmt.Printf("%s:%s", "L", string(l)) fmt.Printf("%s:%s", "R", string(r)) fmt.Println() } } if stack.Len() > 0 { return false } return true}

在解这道题之前需要了解一下什么是回溯法。 通俗来讲，回溯法就是：当前有多个选择，我们不知道具体要选哪个，就每个都需要尝试。每一个尝试的路径连接起来会得到一个树形解。 比如说上图坐标中的 [0,2] 这个位置，通过观察，我们可以知道这个位置可以放置的数字有：1、2、4，如果我们当前位置选择放置 1，则下一个位置能够选择放置的数字有：2、6，如果我们当前位置选择放置 2，则下一个位置能够选择放置的数字有：1、6 。通过分析可以画出树形解： 37. 解数独 题解 /** * @param {character[][]} board * @return {void} Do not return anything, modify board in-place instead. */var solveSudoku = function(board) { // 辅助函数，判断当前位置放置某个值是否可行 function isOk(i,j,val){ // 判断当前行是否已存在该数 for(let k = 0; k<9; k++){ if(board[i][k] == val) return false } // 判断当前列是否已存在该数 for(let k = 0; k<9; k++){ if(board[k][j] == val) return false } // 判断当前的3*3格中是否已存在该数 let l = Math.floor(j/3)*3, t = Math.floor(i/3)*3 for(let m = t; m < t+3; m++){ for(let n = l; n < l+3; n++){ if(board[m][n] == val) return false } } return true } function backTrace(i,j){ if(j === 9){ // 数独已结完，返回 true if(i === 8) return true // 否则进入下一行 i++ j = 0 } // 当前位置没有填数字 if(board[i][j] === '.'){ // 从 1-9 中选择满足条件的数填入 for(let val = 1; val<=9; val++){ // 如果当前数字满足条件，写入数独中 if(isOk(i,j,val)){ board[i][j] = val + '' // 这条路径上如果有解，则满足条件直接返回 if(backTrace(i,j+1)) return true } board[i][j] = '.' } }else{ // 当前位置有数字，直接进入下一格 return backTrace(i,j+1) } // 如果当前格既没有数字，也没有满足条件的数字能填入， // 说明这条路径不通 return false } backTrace(0,0)};

问题描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例：给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1] 解题思路：1.暴力法利用两层循环查找和为目标值的两个整数，并返回下标。 2.HashMap两层循环先将数组中的值和下标作为key和value存到HashMap中，然后遍历数组，计算差值是否在HashMap中，若存在，返回对应两个目标值的下标。 注意：有缺陷，对于数组中存在相同元素，得到的下标，有问题。例如[3, 3] 6 结果应为[0,0],实际为[1,1] 3.HashMap一次循环将数组元素和下标依次存到HashMap中，同时寻找当前元素的目标差值是否已经在HashMap中，若存在，则返回目标差值的下标和当前循环下标。 代码展示：Java版： import java.util.HashMap;/* * @lc app=leetcode.cn id=1 lang=java * * [1] 两数之和 */class Solution { //HashMap一次循环 public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for(int j = 0; j < nums.length; j++){ int sub = target - nums[j]; if(map.containsKey(sub)){ return new int[]{map.get(sub), j}; } map.put(nums[j], j); } return new int[2]; } //HashMap两次循环 public int[] twoSum1(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ map.put(nums[i], i); } for(int j = 0; j < nums.length; j++){ int sub = target - nums[j]; if(map.containsKey(sub) && sub != nums[j]){ return new int[]{map.get(sub), j}; } } return new int[2]; } //暴力法 public int[] twoSum2(int[] nums, int target){ for(int i = 0; i < nums.length; i++){ for(int j = i+1; j < nums.length; j++){ if(nums[i] + nums[j] == target){ return new int[]{i, j}; } } } return new int[2]; }}Go版： ...

首发于微信公众号《前端成长记》，写于 2019.11.05背景本文记录刷题过程中的整个思考过程，以供参考。主要内容涵盖： 题目分析设想编写代码验证查阅他人解法思考总结目录20.有效的括号21.合并两个有序链表26.删除排序数组中的重复项27.移除元素28.实现strStrEasy20.有效的括号题目地址 题目描述给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。 示例： 输入: "()"输出: true输入: "()[]{}"输出: true输入: "(]"输出: false输入: "([)]"输出: false输入: "{[]}"输出: true题目分析设想这道题从题面来看，仍然需要对字符串做遍历处理，找到相互匹配的括号，剔除后继续做处理即可。所以这道题我的解题想法是： 使用栈来记录，匹配的一对就出栈，最后判断栈是否为空有几点需要注意下，可以减少一些计算量： 题面说明了字符串只含有三种括号，所以长度为奇数，一定无效只要有一对不符合，则可判定一定无效堆栈长度超过字符串长度一半，则一定无效先找到右括号则一定无效编写代码验证Ⅰ.记录栈 代码： /** * @param {string} s * @return {boolean} */var isValid = function(s) { if (s === '') return true; if (s.length % 2) return false; // hash 表做好索引 const hash = { '(': ')', '[': ']', '{': '}' } let arr = [] for (let i = 0; i < s.length; i++) { if (!hash[s.charAt(i)]) { // 推入的是右括号 if (!arr.length || hash[arr[arr.length - 1]] !== s.charAt(i)) { return false } else { arr.pop() } } else { if (arr.length >= s / 2) { // 长度超过一半 return false } arr.push(s.charAt(i)) } } return !arr.length};结果： ...

概述我觉得自己的算法思维能力有些薄弱，所以基本上每天晚上都会抽空做1-2到 leetcode 算法题。这两天遇到一个排列的问题——Next Permutation。然后我去搜索了一下生成排列的算法。这里做一下总结。 算法目前，生成一个序列的排列常用的有以下几种算法： 暴力法（Brute Force）插入法（Insert）字典法（Lexicographic）SJT算法（Steinhaus-Johnson-Trotter）堆算法（Heap）下面依次介绍算法的内容，实现和优缺点。 在介绍这些算法之前，我们先做一些示例和代码上的约定： 我的代码实现是使用 Go 语言，且仅实现了求int切片的所有排列，其它类型自行扩展也不难。除非特殊说明，我假定输入的int中无重复元素，有重复元素可自行去重，其中有个别算法可处理重复元素的问题。完整代码放在Github上。 暴力法描述暴力法是很直接的一种分治法：先生成 n-1 个元素的排列，加上第 n 个元素即可得到 n 个元素的排列。算法步骤如下： 将第 n 个元素依次交换到最后一个位置上递归生成前 n-1 个元素的排列加上最后一个元素即为 n 个元素的排列实现算法实现也很简单。这里引入两个辅助函数，拷贝和反转切片，后面代码都会用到： func copySlice(nums []int) []int { n := make([]int, len(nums), len(nums)) copy(n, nums) return n}// 反转切片nums的[i, j]范围func reverseSlice(nums []int, i, j int) { for i < j { nums[i], nums[j] = nums[j], nums[i] i++ j-- }}算法代码如下： func BruteForce(nums []int, n int, ans *[][]int) { if n == 1 { *ans = append(*ans, copySlice(nums)) return } n := len(nums) for i := 0; i < n; i++ { nums[i], nums[n-1] = nums[n-1], nums[i] BruteForce(nums, n-1, ans) nums[i], nums[n-1] = nums[n-1], nums[i] }}作为一个接口，需要做到尽可能简洁，第二个参数初始值就是前一个参数切片的长度。优化接口： ...

题目要求A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.For example, these are arithmetic sequences:1, 3, 5, 7, 97, 7, 7, 73, -1, -5, -9The following sequence is not arithmetic.1, 1, 2, 5, 7 A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.The function should return the number of arithmetic subsequence slices in the array A.The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1. Example:Input: [2, 4, 6, 8, 10]Output: 7Explanation:All arithmetic subsequence slices are:[2,4,6][4,6,8][6,8,10][2,4,6,8][4,6,8,10][2,4,6,8,10][2,6,10]从一个无序的整数数组中，找到所有等差子数列的数量。这里需要注意，等差子数列要求从原数组中找出Pk个下标的元素，其中P0 < P1 < P2... < Pk，且满足A[P1]-A[P0] = A[P2] - A[P1] ... = A[Pk]-A[Pk-1]。 ...

DescriptionGiven two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2. Note: The length of both num1 and num2 is < 5100.Both num1 and num2 contains only digits 0-9.Both num1 and num2 does not contain any leading zero.You must not use any built-in BigInteger library or convert the inputs to integer directly. 描述给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。 注意： num1 和num2 的长度都小于 5100.num1 和num2 都只包含数字 0-9.num1 和num2 都不包含任何前导零。你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。 ...

题目要求Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2.**Example:****Input:** [4, 6, 7, 7]**Output:** [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]**Note:**1. The length of the given array will not exceed 15.2. The range of integer in the given array is [-100,100].3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.现有一个无序的整数数组，要求找到所有递增的子序列。 ...

题目要求Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.Note:1. input and output values are in floating-point.2. radius and x-y position of the center of the circle is passed into the class constructor.3. a point on the circumference of the circle is considered to be in the circle.4. randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.Example 1:Input: ["Solution","randPoint","randPoint","randPoint"][[1,0,0],[],[],[]]Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]Example 2:Input: ["Solution","randPoint","randPoint","randPoint"][[10,5,-7.5],[],[],[]]Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]Explanation of Input Syntax:The input is two lists: the subroutines called and their arguments. Solution's constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren't any.假设现在已知圆的圆心的x和y坐标，以及该圆的半径radius。要求写一个随机点生成器，要求该生成器生成的点必须在圆内，且每一个点被生成的概率为相等的。规定圆周上的点也属于圆内。 ...

题目要求A magical string S consists of only '1' and '2' and obeys the following rules:The string S is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself.The first few elements of string S is the following: S = "1221121221221121122……"If we group the consecutive '1's and '2's in S, it will be:1 22 11 2 1 22 1 22 11 2 11 22 ......and the occurrences of '1's or '2's in each group are:1 2 2 1 1 2 1 2 2 1 2 2 ......You can see that the occurrence sequence above is the S itself.Given an integer N as input, return the number of '1's in the first N number in the magical string S.Note: N will not exceed 100,000.Example 1:Input: 6Output: 3Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.这题是描述了一个魔法字符串，该字符串完全由数字1和2构成。这个字符串的魔法点在于，如果将该该字符串连续的数字数量进行统计并且构成一个新的字符串，会发现新的字符串与原来的字符串完全相同。比如1 22 11 2 1 22 1 22 11 2 11 22字符串，经过统计后发现有1个1，2个2，2个1，1个2，1个1，2个2，1个1，2个2，2个1，1个2，2个1，2个2，将统计的数量合并为新的字符串，会发现新的字符串为1 22 11 2 1 22 1 22，和原字符串完全匹配。 ...

原题地址：https://leetcode-cn.com/probl... repo 地址: https://github.com/pigpigever...题目剖析????两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。比如说存在这样两个二进制数值： 001100它们之间的汉明距离就是 2，我们要求的就是两个二进制数值中位数不一样的地方，比如你是 1 他是 0，那么汉明距离就 +1。 前置知识????异或运算是相对基础的知识，但是由于在平时的开发中几乎不会用到，难免生疏。这里简单罗列下常见的异或运算： & : 按二进制位进行 与运算，相同位同时为 1 时结果为 1，否则为 0| : 按二进制位进行 或运算，相同位存在 0 和 1 时结果为 1，否则为 1^ : 按二进制位进行 异或运算，相同位相同时为 0，否则为 1>> : 右移运算是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃，左边移出的空位或者一律补 0<< : 左移运算是将一个二进制位的操作数按指定移动的位数向左移位，移出位被丢弃，右边的空位一律补 0梳理逻辑????思路其实很简单，如下： 遍历两个数值，位数不相同那么 +1示例代码????/** * @param {number} x * @param {number} y * @return {number} */var hammingDistance = function(x, y) { let ans = 0 while (x !== 0 || y !== 0) { if ((x & 1) !== (y & 1)) { ans++ } x >>= 1 y >>= 1 } return ans};写在最后一直在 LeetCode 上刷题，之前还加入了组织，有兴趣加入一起学习的同学可以在下方留言或者关注我的微信公众号「tony老师的前端补习班」并在后台留言，可以进群跟大佬们一起学习。 ...

提出问题：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。 示例："abbcc" --> "ab" or "bc"、"abcadef" --> "adef"解决思路：使用蛮力算法算法很容易实现，但是时间复杂度为O(n^2)。本题可以通过一次遍历完成，比如"abcadef"，正常遍历，如果当前遍历字符不在字符串中，将它添加至字符串；当遍历到第2个a时，发现重复，此时截取第1个a后的第一个字符开始到第2个a为新字符串，并比较最大长度，依此类推。 a --> ab --> abc -a重复-> bca --> bcad --> bcade --> bcadef代码如下(￣▽￣)： class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if len(s) == 0: return 0 st = '' length = 0 for i in range(len(s)): if s[i] not in st: st+=s[i] length=length if(length>len(st)) else len(st) else: st = st[st.find(s[i])+1:] + s[i] return length时间与空间复杂度占用： 原题链接：https://leetcode-cn.com/probl...

题目要求The Hamming distance between two integers is the number of positions at which the corresponding bits are different.Now your job is to find the total Hamming distance between all pairs of the given numbers.Example:Input: 4, 14, 2Output: 6Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (justshowing the four bits relevant in this case). So the answer will be:HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.Note:1. Elements of the given array are in the range of 0 to 10^92. Length of the array will not exceed 10^4.计算N个数字之间的汉明码距离之和。汉明码是指两个数字的二进制表示形式中，在对应位置上值不同的数量总和。如2和4，4的二进制表达式为100， 2的二进制表达式010，则二者在第二位和第三位的值不同，因此汉明码值为2。 ...

提出问题：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807 解题思路：设置两个指针指向两条链表，构造新节点存储两个当前指针节点的值，当前节点被遍历过后，指针后移。对于满10进1的情况，设置一个变量判断即可。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: if l1==None: return l2 elif l2==None: return l1 else: h1 = l1 h2 = l2 flag = 0 new = ListNode(0) res = new while h1 or h2: temp = 0 if h1: temp += h1.val h1 = h1.next if h2: temp += h2.val h2 = h2.next if flag == 1: temp += 1 flag = 0 if temp >= 10: temp -= 10 flag = 1 res.next = ListNode(temp) res = res.next if flag == 1: res.next = ListNode(1) return new.next时间与空间复杂度： ...

题目要求Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.Note: p consists of only lowercase English letters and the size of p might be over 10000.Example 1:Input: "a"Output: 1Explanation: Only the substring "a" of string "a" is in the string s.Example 2:Input: "cac"Output: 2Explanation: There are two substrings "a", "c" of string "cac" in the string s.Example 3:Input: "zab"Output: 6Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.假设存在一个从a-z26个字母无限循环的字符串s，现在输入一个字符串p，问该字符串有多少个子字符串在s中循环出现？ ...

提出问题：给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 解决思路：使用新的遍历方式（右子树，根、左子树）遍历整棵树。设置全局变量累加值，再逐一更新节点。 代码如下(￣▽￣)： # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def __init__(self): self.re = 0 def convertBST(self, root: TreeNode) -> TreeNode: if root==None: return root self.toBST(root) return root def toBST(self,node: TreeNode): if node==None: return else: self.toBST(node.right) node.val=node.val + self.re self.re = node.val self.toBST(node.left)时间与空间复杂度： 链接：https://leetcode-cn.com/probl...

提出问题：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4 解决思路：合并链表很简单，设置两个指针遍历两个链表，同时遍历并比较大小，如果1链表的当前节点值较小，将该节点添加到新链表中，1链表遍历指针后移一位，直到两个链表内所有节点都添加到新链表中。注意：题目要求新链表是通过拼接给定的两个链表的所有节点组成的，所以初始新建一个头节点，将头节点下一个节点指针指向两个链表中的最小节点，最后返回头节点的下一个节点。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1==None: return l2 elif l2==None: return l1 else: h1 = l1 h2 = l2 head = ListNode(0) result = head while h1!=None and h2!=None: if h1.val <= h2.val: head.next = h1 h1 = h1.next else: head.next = h2 h2 = h2.next head = head.next if h1!=None: head.next = h1 if h2!=None: head.next = h2 return result.next时间与空间复杂度： ...

题目要求Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining. Note:Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000. Example:Given the following 3x6 height map:[ [1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1]]Return 4. ...

public int findLengthOfLCIS(int[] nums) { if(nums == null || nums.length == 0) return 0; int sum = 1; int p = 0; int[] count = new int[nums.length]; for(int i = 1; i < nums.length; i++){ if(nums[i-1] < nums[i]){ sum++; }else{ count[p] = sum; sum = 1; p = i; } } count[p] = sum; int max = 0; for(int i = 0; i < count.length; i++){ if(count[i] > max) max = count[i]; } return max;}法二，用临时变量，减少了空间 ...

题目要求In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.Note:The given numbers of 0s and 1s will both not exceed 100The size of given string array won't exceed 600. Example 1:Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3Output: 4Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0” Example 2:Input: Array = {"10", "0", "1"}, m = 1, n = 1Output: 2Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".已知有m个0和n个1，问最多能构成数组中多少个数字。已知每个0和1只能使用一次。 ...

提出问题：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。 解决思路：判断众数实则是判断重复元素的个数。遇到重复元素首先考虑字典。字典key值存放数组元素，value存放元素出现次数，如果次数超过n/2，则为答案。 代码如下(￣▽￣)： class Solution: def majorityElement(self, nums: List[int]) -> int: d = {} for i in nums: if i in d: d[i]+=1 else: d[i]=1 for key,value in d.items(): if d[key] > len(nums)/2: return key return 0时间与空间复杂度： 题目来源：https://leetcode-cn.com/probl...

提出问题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 解题思路：使用异或运算解决。异或运算规则：1.相同数字进行异或运算结果为0。2. 0与任何数进行异或运算结果为该数字。比如[4,1,1] 4与1异或为5，5与1异或为4，最终输出4为正确答案。所以算法先设定最终输出值为0，让输出值与数组中所有元素进行一次异或操作，即可得出最终答案。 代码如下(￣▽￣)： class Solution: def singleNumber(self, nums: List[int]) -> int: num = 0 for i in range(len(nums)): num = num^nums[i] return num时间与空间复杂度： 题目链接：https://leetcode-cn.com/probl...

问题提出：反转一个单链表 解决思路：最先想到的是使用栈来存储链表的第一遍遍历的值。再重新遍历链表，遍历的同时弹出栈的元素（弹出的顺序刚好是链表节点值的倒序），为当前节点赋值当前弹出的值。python可以直接使用list结构存储遍历值，读取的时候倒序读取list元素，就相当于栈的原理。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def reverseList(self, head: ListNode) -> ListNode: l = [] temp = head while temp!=None: l.append(temp.val) temp = temp.next i = len(l)-1 temp2 = head while i>=0: temp2.val = l[i] i-=1 temp2 = temp2.next return head时间与空间消耗： 题目来源：https://leetcode-cn.com/probl...

题目要求Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Example 1:Input: [[1,2],[2,3],[3,4],[1,3]]Output: 1Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.Example 2:Input: [[1,2],[1,2],[1,2]]Output: 2Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.Example 3:Input: [[1,2],[2,3]]Output: 0Explanation: You don't need to remove any of the intervals since they're already non-overlapping. Note:You may assume the interval's end point is always bigger than its start point.Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.使用二维数组表示区间组，每一个子数组的第一个值表示区间的开始坐标，第二个值表示区间的结束坐标。计算最少进行多少次删除操作，可以确保剩下的区间不会产生任何重叠。 ...

前言LeetCode题库多线程部分的 按序打印： 我们提供了一个类： public class Foo {  public void one() { print("one"); }  public void two() { print("two"); }  public void three() { print("three"); }}三个不同的线程将会共用一个 Foo 实例。 线程 A 将会调用 one() 方法线程 B 将会调用 two() 方法线程 C 将会调用 three() 方法请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。 示例1： 输入: [1,2,3]输出: "onetwothree"解释: 有三个线程会被异步启动。输入 [1,2,3] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 two() 方法，线程 C 将会调用 three() 方法。正确的输出是 "onetwothree"。示例2： 输入: [1,3,2]输出: "onetwothree"解释: 输入 [1,3,2] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 three() 方法，线程 C 将会调用 two() 方法。正确的输出是 "onetwothree"。提示：尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。 ...

题目描述给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器，且 n 的值至少为 2。 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 示例: 输入: [1,8,6,2,5,4,8,3,7]输出: 49思路分析暴力法这个暴力法可太暴力了，没有什么意义，就是两两遍历所有的边，然后乘出来一个面积，找出最大的，时间复杂度 $$O(n^2)$$ 空间复杂度 $$O(1)$$ 双指针法这种方法是基于对题目特性的分析，因为如果完全没有规律，只是要求最大面积，那肯定只能是暴力法。但是题目为什么要特意强调盛水？盛水这种物理行为有什么特殊的规律？就好比有序数组的有序性导致可以使用二分查找，盛水的具有短板效应，所谓短板效应就是容器能盛多少水完全取决于最短的那个边 基于此特性，可以归纳出以下几种情况： 如果从高的这边往低的这边走，不论遇到更高的还是更低的都没有意义高的遇到低的，和上面同理，宽度本来就低了，高度也低，面积肯定更小，没有意义高的那侧遇到更高的，可是由于短板效应，面具取决短板，所以围起来的面积不受高的一侧的影响 综上，只有从短板向高的一侧遍历，并且只有短板升高了这种情况是存在面积变大的可能性的，因此循环就可以变成一层循环 代码实现暴力法跳过 class Solution { public int maxArea(int[] height) { int left = 0; int right = height.length - 1; int max = 0; int theLower = 0; while(left < right) { int lowerSide; int lower; if(height[left] < height[right]) { lowerSide = left; lower = height[left]; } else { lowerSide = right; lower = height[right]; } if(lower > theLower) { // probably update max int area = lower * (right - left); max = Math.max(max, area); theLower = lower; // update theLower } if(lowerSide == left) { left++; } else { right--; } } return max; }}总结说实话这种问题没有固定套路，纯靠数学和物理学的感觉，思路大概就是遇事不决先暴力，然后再思考盛水这种东西有什么特点，想到短板效应，归纳出所有情况；或者看了解题思路以后背吧，遇到类似的盛水问题的时候可以想一下短板效应类似题目trapping-rain-water ...

题目描述https://leetcode-cn.com/probl... 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 输入示例： 输入:s = "aab"p = "c*a*b"输出: true解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。输入:s = "mississippi"p = "mis*is*p*."输出: false 思路分析双指针游走法（失败的方法）自己最开始想到的方法，相当于是没有回溯的回溯法，导致s='aaa' p='a*a'这种情况匹配失败 暴力解法（官网答案叫做回溯法）大体上就是通过递归的手段把匹配的问题抛给下一层 动态规划基于暴力解法，通过自顶向下的备忘录方式，或者自底向上的方式记录信息 根据pattern生成状态机这种是标准的正则表达式的解决方式，通过解析请求的pattern，然后画出来一幅该正则式的有限状态机图，然后再对着图匹配字符串 代码实现个人的错误解法这个是个错误解法，aaa和a*a的情况会由于指针没有回溯导致匹配失败，稍后分析 class Solution { public boolean isMatch(String s, String p) { int i = 0, j = 0; while(i < s.length() && j < p.length()) { if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') { if(j + 1 < p.length() && p.charAt(j+1) == '*') { i++; } else { i++; j++; } } else if(j + 1 < p.length() && p.charAt(j+1) == '*') { j += 2; } else { return false; } } while(i == s.length() && j + 1 < p.length() && p.charAt(j+1) == '*') { j+=2; } if(i == s.length() && j == p.length()) { return true; } else { return false; } }}个人总结

题目描述 分析题目按照题意我们只要先对每个子数组先做逆序，再做 0 --> 1 和 1 --> 0 的替换即可，于是我们可以写出以下代码： /** * @param {number[][]} A * @return {number[][]} */var flipAndInvertImage = function(A) { for (let i = 0; i < A.length; i++) { let j = 0, k = A[i].length - 1 while (j < k) { [A[i][j], A[i][k]] = [A[i][k], A[i][j]] A[i][j] = A[i][j] ? 0 : 1 A[i][k] = A[i][k] ? 0 : 1 j++, k-- } if (j === k) { A[i][j] = A[i][j] ? 0 : 1 } } return A};优化对于 0 --> 1 和 1 --> 0 的替换，我们大可不必用三元运算符，而是采用异或运算，可以把代码简化如下： ...

1. 百度百家号一面面完回来搜素，才发现这道题其实是LeetCode540。 540 medium 有序数组中的单一元素 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 示例 1:输入: [1,1,2,3,3,4,4,8,8]输出: 2 示例 2:输入: [3,3,7,7,10,11,11]输出: 10 第一种方法：滑动窗口/** * 解法1：滑动窗口 * @param {number[]} nums * @return {number} */var singleNonDuplicate = function(nums) { for (let i = 0; i < nums.length; i++){ // 两个边界情况 if (i === 0 && nums[i]!==nums[i+1])return nums[i]; if (i === nums.length - 1 && nums[i]!==nums[i-1])return nums[i]; if (nums[i] !== nums[i+1] && nums[i] !== nums[i-1]){ return nums[i] } }};第二种方法：位运算/** * 解法2：位运算 * @param {number[]} nums * @return {number} */var singleNonDuplicate2 = function(nums) { let a = nums[0] for (let i = 1; i < nums.length; i++){ a = a ^ nums[i] } return a;};头条财经部门一面二维数组的回形遍历 ...

5:最长回文子串给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2： 输入: "cbbd"输出: "bb"一、法一暴力破解这个就不用多解释了 class Solution { /** * 法一： * @param String $s * @return String */ function longestPalindrome($s) { $len = strlen($s); $tmps = ''; $max = 0; for($i=0 ; $i<$len; $i++){ //起始下标 for($j=$i+1; $j<=$len;$j++){ //长度 if($this->isPalindrome(substr($s,$i,$j)) && $j > $max){ $tmps = substr($s,$i,$j); $max = $j; } } } return $tmps; } function isPalindrome($subs){ $len = strlen($subs); for($i=0; $i<(int)($len/2); $i++){ if($subs[$i] != $subs[$len-$i-1]){ return false; } } return true; }}二、最长公共子串思路：就是把字符串反转过来，例如 s=‘ababc’，反正s‘=’cbaba‘，两个字符串左右重合，得出最长的子串就是答案，也就是bab（或aba）。但是有可能会出现==特例（如：S = abc435cba，S' = abc534cba）==，重合，子串为abc。不符合条件，需要加判断 ...

TAG: 贪婪 原题Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue. Note:The number of people is less than 1,100. ...

题目要求A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.Note:Starting point is assumed to be valid, so it might not be included in the bank.If multiple mutations are needed, all mutations during in the sequence must be valid.You may assume start and end string is not the same. Example 1:start: "AACCGGTT"end: "AACCGGTA"bank: ["AACCGGTA"]return: 1 Example 2:start: "AACCGGTT"end: "AAACGGTA"bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]return: 2 Example 3:start: "AAAAACCC"end: "AACCCCCC"bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]return: 3假设现在有两个基因序列，并且用一个字符串数组bank来表示一个基因序列银行。已知每一步可以将当前基因序列中的一位进行改变，变成另一个已知的基因序列。问最少需要多少步可以将初始的基因序列转化为目标基因序列。如果无法转换，则返回-1。 ...

D104 167. Two Sum II - Input array is sorted题目链接167. Two Sum II - Input array is sorted 题目分析给定一个已经排序好的整数数组，从中寻找两个数字，使其相加之后等于给定的一个数字。 返回这两个数字对应的下标。 思路首先想到的思路当然是逐个遍历，但是会超时。就不细说了。 之后想到的是用二分法找到小于目标数字的位置，用以减少遍历次数。 最后想到的是，把给定数组倒转过来，用isset去搜索是否存在指定加数。 最终代码<?phpclass Solution { /** * @param Integer[] $numbers * @param Integer $target * @return Integer[] */ function twoSum($numbers, $target) { $repeatItems = array_filter(array_count_values($numbers),function($v){ return $v>1; }); $vs = array_flip($numbers); foreach($vs as $k => $v){ if(isset($vs[$target-$k])){ if(isset($repeatItems[$target-$k])){ return [$v, $v+1]; } return [$v+1, $vs[$target-$k]+1]; } } return [null, null]; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25一 目录不折腾的前端，和咸鱼有什么区别 | 目录 || --- | | 一 目录 | | 二 前言 || 三 汇总 || 3.1 LeetCode 已攻略 || 3.2 Function & Object || 四 总结 | 二 前言返回目录自 2019-05-16 开始，jsliang 每天折腾一道及以上 LeetCode 题目，并将其解题思路记录成文章，发布到 GitHub 和 微信公众号。 微信公众号记录截图： GitHub 记录截图： 目前关于这块 LeetCode（算法与数据结构） 的安排： 2019/08/15 前。LeetCode 简单难度题目 - 完成 100 道简单 LeetCode 题目的题解。2019/08/15 - 2019/09/15。初步钻研算法与数据结构。时间未知。LeetCode 中等难度题目 - 完成 50 道中等 LeetCode 题目的题解。时间未知。进一步钻研算法与数据结构。时间未知。LeetCode 困难难度题目 - 完成 20 道困难 LeetCode 题目的题解。时间未知。完善算法与数据结构。截至目前为止，jsliang 在攻略 LeetCode 中的收获： ...

leetcode 100 斩！从第 1 题开始，到现在也差不多快一年了，回顾纪念一下。 为什么开始刷题？从大一就知道了 leetcode，但刷题总是三天打鱼，两天晒网，会发现刷过的题，隔一段时间再看还是需要很久才能再想起来，于是就萌发了刷一题总结一题的想法。 另一方面，leetcode 上的 discuss 里一些解，有时候讲解的很少，甚至只丢一些代码，对于我等这种菜鸟有时候看的太废劲了，所以不如自己把各种解法都理清楚，然后详细的总结出来，也方便其他人更好的理解。 刚开始的感觉大一的时候，听过 ACM，然后暑假也去学校的 ACM 集训试了试，但当时基础太差了，栈和队列都不知道是什么，所以也就没有走上 ACM 的道路。之后就各种学安卓、web、后端的应用开发的一些东西了。后来准备开始刷题是大四毕业的时候了吧。 当时对回溯、动态规划也都只是上课的时候学过，也并不熟练。开始几题的时候，也都很慢，很多都自己想不出来。然后就去看别人的题解。看完以后，就什么都不看，然后按自己的思路再写一遍代码。 尤其是第 5 题，求最长回文序列，现在都印象深刻，记得当时用了好几天才把所有解法总结了出来。 所以大家如果想刷题的话，也不用怕自己基础不好，大不了哪些名词不会就去查，一点点积累就可以，重要的是开始和坚持。 现在的感觉从开始可能只是觉得该刷一刷题，到现在可能真的是爱上了刷题。 现在刷题基本可以想出一种思路，有时候甚至和最优解想到了一起，还会想出一些别人没有想到的解法，这种成就感可能就是打游戏超神的感觉吧，哈哈。 此外，看 discuss 的时候，每当看到令人拍案称奇的思路的时候，真的是让人心旷神怡，开心的不得了，就像中了彩票一样的开心，赶快去和同学分享。 有时候也会看到一些让人捧腹的评论，题目是输入一个字符串，输出所有可能的 ip 地址。 Input: "25525511135" Output: ["255.255.11.135","255.255.111.35"] 刷题的收获在总结的过程中，因为力求给他人讲懂，在理清思路的动机的过程中，会发现之前的想法可能是错的，会总结着总结着就明白了另一种解法，或者产生新的想法，或者明白各个解法相互之间的联系，会比仅仅 AC 多出很多收获。 从理清他人的想法，再到自己写出代码，再到把各个解法用自己的理解串起来，会有一种「纸上得来终觉浅，绝知此事要躬行」的感觉。有时候虽然大的框架有了，但是小的细节方面还是需要自己去体会。为什么加这个 if？为什么是小于等于？每一句代码的产生都是有原因的，绝不会是可有可无的代码。 所以虽然一道题从看题，理解，自己考虑，看别人解法，到重新实现，再到总结出来，可能需要 3、4 个小时，甚至 5、6 个小时或者更多，但我觉得是值得的。 此外，也有很多人加自己的微信过来亦或是感谢自己，亦或是指出错误，亦或是询问问题，亦或是没说过话的，哈哈。有微软、谷歌、百度、阿里、腾讯的大佬，有各个大学的学生，甚至巧的是还能加上高中的校友，世界真小，哈哈。 上边是最近加的一些人，每次收到别人的称赞自己也会很开心。此外，博客是直接放在 github 上的，目前也有 280 stars 了，是自己 github 上 start 数最多的项目了，说来也惭愧，希望以后自己努力可以有一个好的开源项目。 刷题的理解一些人可能会纠结用什么语言去刷，其实没必要纠结的。刷题需要考虑的是算法，而不是语言。算法就像是从家里到超市该怎么走？出门左拐，右拐直走….而语言是我们选择的交通工具，骑车？步行？开车？平衡车？每种交通工具都有自己的优点和缺点，语言也是如此。而好的算法可能更像是，我们偶然发现了一条近路，降低了我们的时间复杂度或者是空间复杂度。 刷了 100 道题了，我觉得必须要掌握的就是递归的思想了，利用这个思想可以解大部分的题了。计算机擅长的就是记忆以及速度，而递归可以把这两个优势发挥到极致。遇到问题以后，我们可以考虑如何把大问题分解成小问题，想出来以后，代码很容易就出来了。 ...

D103 447. Number of Boomerangs题目链接447. Number of Boomerangs 题目分析给定一个坐标数组，从中任意取3个坐标(i,j,k)，使得从i到j的距离等于i到k的距离。且(i,j,k)与(i,k,j)不是同一个组合，需单独计算。 思路逐个遍历，计算两点距离。并记录在一个数组中。 对于具有相同距离的边的个数，组合数量有以下规律： 当有2条边时，可以组合成2条； 当有3条边时，可以组合成6条； 当有4条边时，可以组合成12条； 当有n条边时，可以组合成n(n-1)条。 对于每一个起点都如此计算，将最后的和返回即可。 最终代码<?phpclass Solution { /** * @param Integer[][] $points * @return Integer */ function numberOfBoomerangs($points) { $c = 0; $totalPoints = count($points); for($i = 0; $i<$totalPoints; $i++){ $distances = []; $iv = $points[$i]; for($j = 0; $j<$totalPoints; $j++){ if($i == $j){ continue; } $jv = $points[$j]; $ij = pow($iv[0]-$jv[0],2) + pow($iv[1]-$jv[1],2); if(!isset($distances[$ij])){ $distances[$ij] = 0; } $distances[$ij]++; } foreach($distances as $v){ $c += $v*$v-$v; } } return $c; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

题目要求Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.Note:You may assume the interval's end point is always bigger than its start point.You may assume none of these intervals have the same start point. Example 1:Input: [ [1,2] ]Output: [-1]Explanation: There is only one interval in the collection, so it outputs -1. Example 2:Input: [ [3,4], [2,3], [1,2] ]Output: [-1, 0, 1]Explanation: There is no satisfied "right" interval for [3,4].For [2,3], the interval [3,4] has minimum-"right" start point;For [1,2], the interval [2,3] has minimum-"right" start point. Example 3:Input: [ [1,4], [2,3], [3,4] ]Output: [-1, 2, -1]Explanation: There is no satisfied "right" interval for [1,4] and [3,4].For [2,3], the interval [3,4] has minimum-"right" start point.NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.假设一个二维的整数数组中每一行表示一个区间，每一行的第一个值表示区间的左边界，第二个值表示区间的右边界。现在要求返回一个整数数组，用来记录每一个边界右侧最邻近的区间。 ...

题目给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。 重复出现的子串要计算它们出现的次数。 示例1: 输入: "00110011"输出: 6解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。请注意，一些重复出现的子串要计算它们出现的次数。另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。注意： s.length 在1到50,000之间。s 只包含“0”或“1”字符。思路1 (暴力枚举)解1e.g. s= '110011', s.length = 6reg的可取值 /01/g 或/10/g, /0011/g或/1100/g, /000111/g或/111000/g步骤: 动态拼接reg所有reg对应的s.match(reg).length求和就是所求子串的数量const countBinarySubstrings = function (s) { const len = s.length let count = 0 let s1 = '' let s2 = '' for (let index = 1; index <= Math.floor(len / 2); index++) { s1 += '0' s2 += '1' let res1 = s.match(new RegExp(s1 + s2, 'g')) || [] let res2 = s.match(new RegExp(s2 + s1, 'g')) || [] count += res1.length count += res2.length } return count}解2序号过程输入00110011100110011200110011300110011400110011500110011600110011需要两次循环:外循环: 从头到尾遍历每个字母,内循环: 第i轮: subStri = s.slice(i), 从头开始匹配符合规则的子串时间复杂度O($n^2$) ...

D102 383. Ransom Note题目链接383. Ransom Note 题目分析给定一个字符串，判断这些字母在另一个给定的字符串中，出现次数是否相等。 思路先获取两个字符串中各字符的出现次数，再逐个遍历，判断出现次数是否满足条件。 最终代码<?phpclass Solution { /** * @param String $ransomNote * @param String $magazine * @return Boolean */ function canConstruct($ransomNote, $magazine) { if(!$ransomNote){ return true; } $rArr = array_count_values(str_split($ransomNote)); $mArr = array_count_values(str_split($magazine)); foreach($rArr as $char => $amount){ if(!isset($mArr[$char])){ return false; } if($mArr[$char]<$amount){ return false; } } return true; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

很不擅长的一部分内容，值得总结一下monotonic queue的应用有1.求previous less element(PLE), next greater element(NLE), previous greater element(PGE), next greater element(NGE)。以求PGE为例，有两种方式： 从前往后扫，维护一个decreasing monotonic queuepublic int[] PGE(int[] nums) { int[] res = new int[nums.length]; Arrays.fill(res, nums.length); // nums.length表示不存在NGE Stack<Integer> s = new Stack<>(); for (int i = 0; i < nums.length; i ++) { while (!s.isEmpty() && nums[i] > nums[s.peek()]) res[s.pop()] = i; s.push(i); } return res;}从后往前扫，维护一个decreasing monotonic queuepublic int[] PGE(int[] nums) { int[] res = new int[nums.length]; Arrays.fill(res, nums.length); Stack<Integer> s = new Stack<>(); for (int i = nums.length-1; i >= 0; i --) { while (!s.isEmpty() && nums[s.peek()] <= nums[i]) s.pop(); if (!s.isEmpty()) res[i] = s.peek(); s.push(i); } return res;}

虽然之前在Sliding Window那篇小结里总结了一些关于subarray sum的题目，但总觉得还不够系统所以打算花更大的篇幅对leetcode中涉及到subarray sum的题目做一个小结。 1. 求subarray sum的最大值53 Maximum Subarray:一道非常经典的dp题，这里就不作总结了 2. 求满足条件的subarray sum的个数560. Subarray Sum Equals K:求subarray sum等于K的subarray的个数，这里用HashMap记录每个前缀和的个数，和元素的正负无关。 那如果不是要求相等，而是要求>=或<=K的个数呢（当然>或<也是一样的，这里仅用>=和<=做例子）？（1）如果所有元素均为正数：印象中并未在leetcode中见过完全一样的题目，不过应该有一些类似的题目。总而言之都是用sliding window来处理，复杂度：O(N) O(1)。既然leetcode中没找到，那就自己写吧：求一个正数数组中>=K的subarray sum的个数 public int countSubarray(int[] nums, int k) { for int count = 0, sum = 0, l = 0; for (int r = 0; r < nums.length; r ++) { sum += nums[r]; while (sum >= K) sum -= nums[l++]; count += l; } return count;}求一个正数数组中<=K的subarray sum的个数 ...

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],输出:[ ["ate","eat","tea"], ["nat","tan"], ["bat"]]说明： 所有输入均为小写字母。不考虑答案输出的顺序。答案参考： /** * @param {string[]} strs * @return {string[][]} */var groupAnagrams = function(strs) { var newStrs = strs.map(item=>{ return item.split('').sort().join('')}) var hash = {}; for(var i = 0, len = newStrs.length; i < len; i++) { if(!hash[newStrs[i]]) { hash[newStrs[i]] = []; hash[newStrs[i]].push(i); } else { hash[newStrs[i]].push(i); } } var newArr = []; Object.keys(hash).forEach(item=>{ var arrItem = []; for(var j = 0; j < hash[item].length; j++) { arrItem.push(strs[hash[item][j]]) } newArr.push(arrItem) }) return newArr;}; ...

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。 说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例 1: 给定 matrix = [ [1,2,3], [4,5,6], [7,8,9]],原地旋转输入矩阵，使其变为:[ [7,4,1], [8,5,2], [9,6,3]]示例 2: 给定 matrix =[ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16]], 原地旋转输入矩阵，使其变为:[ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11]]答案参考 /** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */var rotate = function (matrix) { matrix.reverse() for (let i = 0; i < matrix.length; i++) { for (let j = i + 1; j < matrix[0].length; j++) { let tmp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = tmp } }}; ...

D101 100. Same Tree题目链接100. Same Tree 题目分析判断给定的两颗树是否相等。即对应位置的对应值是否都相等。 思路同时逐个遍历，一遇到不相等的就直接返回false。 二叉树的遍历就不细说了。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { /** * @param TreeNode $p * @param TreeNode $q * @return Boolean */ function isSameTree($p, $q) { if(is_null($p) && is_null($q)){ return true; } if((is_null($p) && !is_null($q)) || (!is_null($p)&&is_null($q))){ return false; } if($p->val !== $q->val){ return false; } $l = $this->isSameTree($p->left, $q->left); if($l === false){ return false; } $r = $this->isSameTree($p->right, $q->right); if($r === false){ return false; } return true; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

D100 387. First Unique Character in a String题目链接387. First Unique Character in a String 题目分析返回给定字符串中第一个只出现了一次的单词下标。 若没有，则返回-1。 思路把遇到的单词存进两个数组。 一个用来记录只出现了一次的数组A，另一个记录出现了不只一次的数组B。 遍历每个字母，当当前字母存在与数组B时，代表该字母出现了不止一次，那么忽略即可。 当不存在于数组B，而存在于数组A时，说明当前字母是第二次出现。那么从数组A中删除，并存入数组B。 否则说明当前字母是第一次出现，直接存入数组A即可。 最终，返回第一个数组A的值。 最终代码<?phpclass Solution { /** * @param String $s * @return Integer */ function firstUniqChar($s) { $s = array_filter(str_split($s)); $a = []; $b = []; foreach($s as $k => $v){ if(!isset($b[$v])){ if(isset($a[$v])){ unset($a[$v]); $b[$v] = $k; } else{ $a[$v] = $k; } } } return count($a) ? current($a) : -1; }}不过，这代码也只超过了33.33%的提交。看来还有很大的优化空间。 ...

Preorder Iterator class BSTIterator { Stack<TreeNode> s = new Stack<>(); public BSTIterator(TreeNode root) { if (root != null) s.push(root); } public int next() { TreeNode cur = s.pop(); if (cur.right != null) s.push(cur.right); if (cur.left != null) s.push(cur.left); return cur.val; } public boolean hasNext() { return (!s.isEmpty()); }}Postorder Iterator class BSTIterator { Stack<TreeNode> s = new Stack<>(); public BSTIterator(TreeNode root) { push(root); } public int next() { TreeNode cur = s.pop(); if (!s.isEmpty()) { TreeNode top = s.peek(); if (cur == top.left) push(top.right); } return cur.val; } public boolean hasNext() { return (!s.isEmpty()); } public void push(TreeNode node) { while (node != null) { s.push(node); if (node.left != null) node = node.left; else node = node.right; } }}Inorder Iterator ...

D99 860. Lemonade Change题目链接860. Lemonade Change 题目分析这道题目是典型的收银问题了。 假设你在开店第一天没有零钱，你的商品卖5元。纸币有5元、10元、20元三种。给定一个数组代表你今天遇到的客人在买东西时给的钱。判断你的钱箱能不能顺利给每一位客人找零。（假设每一位客人都只买一件商品） 思路首先判断客户给的是哪种。 如果是5元的话，直接放入钱箱，不需要判断钱箱内的钱。 如果是10元，则需判断钱箱内是否有多于1张5元。没有则直接中断交易，返回false。否则，把10元放入钱箱，并拿走一张5元。 如果是20元，则优先判断是否有多于1张5元和1张10元。若没有，判断有没有多于3张5元。符合的话和前面做同样的操作，把客户的钱放入钱箱，并找零。 最终代码<?phpclass Solution { /** * @param Integer[] $bills * @return Boolean */ function lemonadeChange($bills) { $inHand = [0,0,0]; foreach($bills as $bill){ switch($bill){ case 5: $inHand[0] += 1; break; case 10: $inHand[1] += 1; if($inHand[0]>=1){ $inHand[0] -= 1; } else{ return false; } break; case 20: $inHand[2] +=1; //10 + 5 if($inHand[0]>=1 && $inHand[1]>=1){ $inHand[0] -= 1; $inHand[1] -= 1; } // 5 * 3 else if($inHand[0]>=3){ $inHand[0] -= 3; } else{ return false; } break; } } return true; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

前言Weekly Contest 144的 航班预订统计： 这里有 n 个航班，它们分别从 1 到 n 进行编号。 我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。 请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。 示例： 输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5输出：[10,55,45,25,25]提示： 1 <= bookings.length <= 200001 <= bookings[i][0] <= bookings[i][1] <= n <= 200001 <= bookings[i][2] <= 10000解题思路本题题目的思路其实比较简答： 读取出每条预定记录bookings[i] = [i, j, k]的起点i，终点j和座位数k处于起点i和j之间的result[n]需要增加对应的座位数k，即若i<=n+1<=k（因为n为数组下标索引，所以需要n+1），则result[n]+=k下面会通过题目的示例分析： 输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5输出：[10,55,45,25,25]运算过程 第1行数据[1,2,10]表示起点是1，终点是2，座位数是10。所以result[0]+=10，result[1]+=10。此时 ...

前言Weekly Contest 144的 IP 地址无效化，分值只有1分，是一道十分简单的题目： 给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。 所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。 示例1： 输入：address = "1.1.1.1"输出："1[.]1[.]1[.]1"提示： 示例2： 输入：address = "255.100.50.0"输出："255[.]100[.]50[.]0"提示： 给出的 address 是一个有效的 IPv4 地址解题思路本题十分简单，只需要遍历每个字符，如果为.则替换为[.]即可。 实现代码 /** * 5117. IP 地址无效化 * @param address * @return */ public String defangIPaddr(String address) { StringBuilder builder = new StringBuilder(); for (int i = 0; i < address.length(); i++) { if (address.charAt(i) == 46) { // 46为.的ASCII码 builder.append("[.]"); } else { builder.append(address.charAt(i)); } } return builder.toString(); }

D98 697. Degree of an Array题目链接697. Degree of an Array 题目分析返回出现次数最多的元素的键差最小的值。 思路先用array_count_values计算元素出现次数，用arsort排序。 再遍历该数组，记录第一个元素的值。用以记录最大值。 获取当前遍历元素在原数组中的最小下标和最大下标。其差值为所求数。 最后返回最小的该数即可。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @return Integer */ function findShortestSubArray($nums) { $elementCount = array_count_values($nums); $revNums = array_reverse($nums); $numAmounts = count($nums); arsort($elementCount); $minLength = 50000; $maxValue = key($elementCount); $maxAmount = current($elementCount); foreach($elementCount as $elk => $elv){ if($elv<$maxAmount){ break; } $left = array_search($elk, $nums); $right = $numAmounts - array_search($elk, $revNums)-1; if($right-$left+1 <$minLength){ $minLength = $right-$left+1; } }; return $minLength; } } 本代码运行时间只超过了20%的提交。故肯定是有更优解的。 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

题目要求You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Example:Input: 1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULLOutput:1-2-3-7-8-11-12-9-10-4-5-6-NULL思路一：递归实现深度优先遍历从深度优先遍历的角度来看，每次遇到一个包含子节点中间双链表节点，就递归的调用展开方法将其展开，并将展开的结果插入到当前节点的后面。这里需要注意双链表前节点前后指针的变更。步骤如下： ...

D97 783. Minimum Distance Between BST Nodes题目链接783. Minimum Distance Between BST Nodes 题目分析给定一个二叉树，返回任意两节点的最小差。 思路先获取所有节点值，再逐个比对。不过这样效率很低。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { /** * @param TreeNode $root * @return Integer */ function minDiffInBST($root) { $this->preOrder($root); $amount = count($this->values); $minValue = 9999999; for($i=0; $i<$amount; $i++){ for($j=$i+1;$j<$amount; $j++){ $diff = abs($this->values[$i] - $this->values[$j]); if($diff<$minValue){ $minValue = $diff; } } } return $minValue; } function preOrder($root){ if(is_null($root->val)){ return; } $this->values[] = $root->val; if($root->left){ $this->preOrder($root->left); } if($root->right){ $this->preOrder($root->right); } }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D96 530. Minimum Absolute Difference in BST题目链接530. Minimum Absolute Difference in BST 题目分析给定一个二叉树，返回任意两节点的最小差。 思路先获取所有节点值，再逐个比对。不过这样效率很低。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { protected $values = []; /** * @param TreeNode $root * @return Integer */ function getMinimumDifference($root) { $this->preOrder($root); $amount = count($this->values); $minValue = 9999999; for($i=0; $i<$amount; $i++){ for($j=$i+1;$j<$amount; $j++){ $diff = abs($this->values[$i] - $this->values[$j]); if($diff<$minValue){ $minValue = $diff; } } } return $minValue; } function preOrder($root){ if(is_null($root->val)){ return; } $this->values[] = $root->val; if($root->left){ $this->preOrder($root->left); } if($root->right){ $this->preOrder($root->right); } } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

题目描述Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.大意：给定一组不含重复数字的数组和一个目标数字，在数组中找出所有数加起来等于给定的目标数字的组合。 输入candidates = [2,3,6,7], target = 7输出[ [7], [2,2,3]]分析题目由于我们需要找到多个组合，简单的使用 for 循环肯定是不行的，这时候我们可以使用回溯算法来解决这个问题。 ...

题目要求Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.Find all the elements that appear twice in this array.Could you do it without extra space and in O(n) runtime?Example:Input:[4,3,2,7,8,2,3,1]Output:[2,3]存在一个整数数组，其中的所有元素都位于1~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。 思路一：交换为了在O(N)的时间内找到所有的出现两次的数字，其核心要求在于用现有的数组记录已经访问过的元素，同时不会丢失尚未访问过的元素。思路一采用交换的核心思想，即每次都将当前下标上的值和以该值为下标的位置上的值进行交换，如果该值下标位置上的值和其相等，则说明该数字已经被遍历过一遍了。 代码如下： public List<Integer> findDuplicates(int[] nums) { int index = 0; List<Integer> result = new ArrayList<Integer>(); while(index < nums.length) { int num = nums[index]; if(num == 0){ index++; }else if (nums[num-1] == num) { if(index != num-1){ result.add(num); nums[index] = 0; } index++; }else{ swap(index, num-1, nums); } } return result; } public void swap(int i, int j, int[] nums) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }思路二：取反有没有一种办法在既保留当前位置上的值nums[i]的同时，又能够用某种方式记录i+1是否已经被访问过了？可以通过取反的方法来记录是否被访问过这个情况。如果访问到下标为i的位置上的值，则去判断nums[nums[i]-1]位置上的值是否为负数，如果是，则说明num[i]出现了两次，否则将nums[nums[i]-1]位置上的值取反保留。 ...

题目要求Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.Example:Input:[1,2,3]Output:3Explanation:Only three moves are needed (remember each move increments two elements):[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]从一个长度为n非空整数数组中，找到能够使得数组中每个元素的值都相等的最少步数，一步是指选择对数组中的n-1个元素加一。比如将[1,2,3]这个数组达到均等的最小步数要求为3步，过程如下： [1,2,3][2,3,3][3,3,4][4,4,4]思路和代码假设这个具有n个元素的数组中的最小值为min，这个数组所有元素的和为sum，使其达到均等的最小步数为move，均等的值为target，则可以得到公式sum + (n - 1) * move = target * n。其中，可以推导出target = min + move，即在每一步中都会对初始时最小的元素加一。对二者进行计算可以得出sum - move = min * n。 ...

题目： Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd" Output: "bb" 即求最长回文子序列 原题链接：https://leetcode.com/problems... 此篇博客仅为学习记录 我的解法及代码暴力解决，用outP及innerP进行两层遍历：outP循环中套一层for循环，用innerP遍历，求最长回文序列字符串，同时用logest变量记录最长子序列 这种写法很暴力，效率很低，outP一层循环，innerP一层循环，回文序列对比一层，时间复杂度为n^3 辣鸡代码 /** * @param {string} s * @return {string} */var longestPalindrome = function(s) { let strL = s.length, longest = 0, resultS = ''; for(let outP = 0; outP < strL; outP ++){ for(let innerP = outP + longest; innerP < strL; innerP++){ let tempS = s.slice(outP, innerP + 1), tempSL = tempS.length, halfL = parseInt(tempSL/2), sub1 = null, sub2 = tempS.slice(halfL, tempSL); if(tempSL % 2 === 0){ sub1 = tempS.slice(0, halfL) }else{ sub1 = tempS.slice(0, halfL + 1) } // console.log('halfL：' + halfL); // console.log('tempS：' + tempS); // console.log('sub1：' + sub1); // console.log('sub2：' + sub2); // console.log('------------------') if(compareReverse(sub1, sub2)){ longest = tempSL; resultS = tempS; } } } return resultS;};function compareReverse(s1, s2){ let length = s1.length, half = Math.ceil(length), flag = true; for(let i = 0; i < half; i++){ if( !(s1[i] === s2[length-1-i])){ flag = false; break; } } return flag;}学习高效的解法主要学习了两种，一种是常规的中心检测法，时间复杂度为n^2，一种是Manacher's Algorithm 马拉车算法，时间复杂度为n。 这里主要学习高效的马拉车写法学习及参考链接在此：最长回文子串——Manacher 算法 ...

# 题目 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？ 示例 1: 输入: [1,0,2]输出: 5解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2: 输入: [1,2,2]输出: 4解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。题解我们首先给每一个小朋友都发糖果，保证每位喜至少分配到一个糖果；从左到右遍历，考虑右边的小朋友比左边小朋友排名高的情况，此时更新为 candy[i] = candy[i - 1] + 1，暂时不考虑左边比右边高的情况；从右到左遍历，考虑左边比右边高的情况，希望左边比右边高，但是又需要考虑不破坏第二点中的已经满足的规则，所以更新条件为candy[i] = max(candy[i], candy[i + 1] + 1)；把所有的分配加起来；class Solution { public int candy(int[] ratings) { if (ratings == null || ratings.length == 0) return 0; int[] resCandy = new int[ratings.length]; for (int i = 0; i < resCandy.length; i++) { resCandy[i] = 1; } for (int i = 1; i < ratings.length; i++) { // 比左边的小朋友排名更高. if (ratings[i] > ratings[i - 1]) { resCandy[i] = resCandy[i - 1] + 1; } } for (int i = ratings.length - 2; i >= 0; i--) { // 当前比右边的小朋友排名更高.resCandy[i] = resCandy[i + 1] + 1 // 同时需要保证不破坏当前比左边小朋友高的规则 if (ratings[i] > ratings[i + 1]) { resCandy[i] = Math.max(resCandy[i + 1] + 1, resCandy[i]); } } int res = 0; for (int i = 0; i < resCandy.length; i++) { res += resCandy[i]; } return res; }}热门阅读看了很多技术书，为啥仍然写不出项目？【Spring】IOC是啥有什么好处百度社招面试题——Redis实现分布式锁【Leetcode】114. 二叉树展开为链表 ...

[TOC] 题目给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1: 输入: "()"输出: true示例 2: 输入: "()[]{}"输出: true示例 3: 输入: "(]"输出: false示例 4: 输入: "([)]"输出: false示例 5: 输入: "{[]}"输出: true来源：力扣（LeetCode）链接：https://leetcode-cn.com/probl...著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 解答class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ li = [] if s == "": return True if len(s) == 0 or s[0] in ')''}'']': return False for i in s: if i in '(''{''[': li.append(i) else: a = "" if len(li) == 0: return False if i == ")": a = "(" if i == "}": a = "{" if i == "]": a = "[" if li[-1] == a: li.pop() else: return False if li: return False else: return True执行效果执行结果：通过执行用时 :32 ms, 在所有 Python 提交中击败了71.50%的用户内存消耗 :11.7 MB, 在所有 Python 提交中击败了36.20%的用户

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1] 方法1，暴力解法。 直接每一个元素都与自己之前的元素相加看是否有目标值，有就输出。 代码如下： class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ n = len(nums) for i in range(n): for j in range(i): if nums[i] + nums[j] == target: target_num = [i,j] return target_num return None时间消耗和空间消耗如下： ...

前言Weekly Contest 143的 分糖果 II 排排坐，分糖果。 我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。 然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。 重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。 返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。 示例1： 输入：candies = 7, num_people = 4输出：[1,2,3,1]解释：第一次，ans[0] += 1，数组变为 [1,0,0,0]。第二次，ans[1] += 2，数组变为 [1,2,0,0]。第三次，ans[2] += 3，数组变为 [1,2,3,0]。第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。示例2： 输入：candies = 10, num_people = 3输出：[5,2,3]解释：第一次，ans[0] += 1，数组变为 [1,0,0]。第二次，ans[1] += 2，数组变为 [1,2,0]。第三次，ans[2] += 3，数组变为 [1,2,3]。第四次，ans[0] += 4，最终数组变为 [5,2,3]。提示： ...

[TOC] 题目**编写一个函数来查找字符串数组中的最长公共前缀。**如果不存在公共前缀，返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"]输出: "fl"示例 2: 输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。说明: 所有输入只包含小写字母 a-z 。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/probl...著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 解答先找到最短字符串的长度，这样能减少循环次数然后在进行循环找到公共前缀 class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ a= 0 num = [] len_strs = len(strs) for i in strs: num.append(len(i)) if num ==[]: return "" min_num = min(num) for i in range(min_num): for j in range(len_strs-1): if strs[j][i] != strs[j+1][i]: break else: a +=1 continue break return strs[0][:a]执行效果执行结果：通过执行用时 :28 ms, 在所有 Python 提交中击败了79.27%的用户内存消耗 :12 MB, 在所有 Python 提交中击败了16.85%的用户

[TOC] 题目罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值I 1V 5X 10L 50C 100D 500M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。 ...