Ext做网站,哪些网站做的好看的图片,王色网站,查询企业联系方式的软件知识补充 python赋值的执行顺序#xff1a; 在41中#xff0c;对于测试案例[-1,4,3,1] 当i1时#xff0c;以下两条语句的执行结果不一致#xff1a; “nums[nums[i]-1], nums[i] nums[i], nums[nums[i]-1]” “nums[i], nums[nums[i]-1] nums[nums[i]-1], nums[i]” 解析…知识补充 python赋值的执行顺序 在41中对于测试案例[-1,4,3,1] 当i1时以下两条语句的执行结果不一致 “nums[nums[i]-1], nums[i] nums[i], nums[nums[i]-1]” “nums[i], nums[nums[i]-1] nums[nums[i]-1], nums[i]” 解析① 先计算右侧nums[i] 4, nums[nums[i]-1] nums[4-1] nums[3] 再执行从左到右的赋值nums[nums[i]-1] nums[i] 4 导致nums[3] 4 nums[i] nums[3] 1 导致nums[1] 1 得到 [-1,1,3,4] 的交换结果 ② 先计算右侧nums[nums[i]-1] nums[4-1] nums[3]nums[i] 4 再执行从左到右的赋值nums[i] nums[3] 1 导致nums[1] 1 nums[nums[i]-1] nums[1-1] nums[i] 4 导致nums[0] 4 得到 [4,1,3,1] 的交换结果 问题出在语句②左侧的计算顺序在nums[i]重新赋值之后 15 三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。 1.i/j/k不等只往i后取j只往j后取k 2.三元组组合不重复hashmap/set去重要求排序 方法一回溯 枚举每种组合可能看是否同时满足len3sum0 方法二固定nums[i]转为在[i:-1]里查找两数之和为-nums[i]的组合可能 方法三双指针 排序后固定nums[i]用一头一尾双指针来控制sum大小需要保证元素不重复 class Solution(object):def threeSum(self, nums)::type nums: List[int]:rtype: List[List[int]]# 固定一个数然后在排列好的数组中一头一尾取nums.sort()n len(nums)res []for i in range(n):if i and nums[i]nums[i-1]: continuej,k i1,n-1while jk:tmp nums[i]nums[j]nums[k]if tmp0: res.append([nums[i],nums[j],nums[k]])while jn and nums[j] tmp-(nums[i]nums[k]): # 跳到下一个不同的nums[j]j 1elif tmp0: j 1else: k - 1# 实际上只有tmp0是需要跳到下一个不相同的数避免有效答案不重复即可return res 560 和为K的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。 连续非空序列求和区间和前缀和 知识补充 前缀和sum[i]num[1]num[2]……num[i] 实现区间和的O(1)查询 核心操作sum(num[i:j]) sum[j-1] - sum[i-1] 差分数组cf[i]num[i]-num[i-1] 实现区间修改的O(1)操作 核心操作对num[i:j]全1 等价于 cf[i]1 cf[j1]-1 b[1] a[1] b[2] a[2] - a[1] ... b[n] a[n] - a[n-1] 两者关系b[i] 是 a[i] 的差分数组a[i] 是 b[i] 的前缀和某种程度上的逆运算对差分数组进行前缀和操作可以得到原数组 为了不特殊处理perSum[i]表示sum(num[:i-1]) 一维前缀和sum[i:j] perSum[j1] - perSum[i] 二维前缀和sum[i:j][m:n] perSum[j1][n1] - perSum[j][m] - perSum[i][n] perSum[i][m] 相关题目leetcode1480/303/304/ 方法构造前缀和后转为找两个数的差值为K两数之和也是先判断再插入字典 class Solution(object):def subarraySum(self, nums, k)::type nums: List[int]:type k: int:rtype: inttmp {0:1} summ, res 0, 0for num in nums:summ numif summ-k in tmp: # 这俩if不能交换位置res tmp[summ-k]if summ not in tmp:tmp[summ] 1else:tmp[summ] 1return res 239 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。 方法在窗口中只保留能用到的元素即nums[i]的排序 class Solution(object):def maxSlidingWindow(self, nums, k)::type nums: List[int]:type k: int:rtype: List[int]n len(nums)if kn: return [max(nums)]stack, res sorted(nums[:k], reverseTrue), []res.append(max(stack))for i in range(k, n):while stack and nums[i] stack[-1]: #只留下比nums[i]大的值stack.pop()stack.append(nums[i]) # 插入当前值if nums[i-k] in stack: # 移出仍在stack中超过窗口长度的值stack.remove(nums[i-k])res.append(stack[0])return res 案例[-6,-10,-7,-1,-9,9,-8,-4,10,-5,2,9,0,-7,7,4,-2,-10,8,7] k7 无法通过 原因窗口[-7,-1,-9,9,-8,-4,10]对应的stack是[10] 而窗口[-8,-4,10,-5,2,9,0]对应的stack是[10,9,0] 但此时nums[i-k]9 就把第12位的9当成第6位的9移出stack 解决利用不重复的值下标来表示每个元素 class Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:n len(nums)if kn: return [max(nums)]stack, res [], []for i in range(n): while stack and nums[i] nums[stack[-1]]: #只留下比nums[i]大的下标值stack.pop() stack.append(i) # 插入当前下标值if ik-1:if (i-k) in stack: # 移出仍在stack中超过窗口长度的值stack.remove(i-k)res.append(nums[stack[0]])return res 76 最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。 方法先右侧扩展至找齐t的所有字符再左侧缩减至缺少t的一个字符记录长度 class Solution:def minWindow(self, s: str, t: str) - str:m, n len(s), len(t)left, right 0, 0tmp, cnt, res {}, n, swhile leftright and rightm:if cnt: # 未找齐全部字符 右侧扩展if rightn:if t[right] in tmp: tmp[t[right]] 1else: tmp[t[right]] 1if s[right] in tmp: tmp[s[right]] - 1if not tmp[s[right]]: cnt - 1 # 要确保是tmp[s[right]]还差right 1else: # 找齐全部字符左侧收缩if right-left len(res):res s[left:right]if s[left] in tmp:tmp[s[left]] 1if tmp[s[left]]: cnt 1left 1while leftm and not cnt: # 最后处理if right-left len(res):res s[left:right]if s[left] in tmp:tmp[s[left]] 1if tmp[s[left]]: cnt 1left 1return if ress else res 案例s abc t cba 无法通过 原因同步计数使遍历s的a时被认为不在t中 解决先对t计数 案例s aa t aa 无法通过 原因判断 tmp[s[right]] 条件错误初始化和最终结果相同无法具体判断 解决初始化res2*s 有效字符判断条件改成 if tmp[s[right]]0 from collections import Counter
class Solution:def minWindow(self, s: str, t: str) - str:m, n len(s), len(t)left, right 0, 0cnt, res n, 2*stmp Counter(t)while leftright and rightm:if cnt: # 未找齐全部字符 右侧扩展if s[right] in tmp: tmp[s[right]] - 1if tmp[s[right]]0: cnt - 1 # 要确保是tmp[s[right]]还差right 1else: # 找齐全部字符左侧收缩if right-left len(res):res s[left:right]if s[left] in tmp:tmp[s[left]] 1if tmp[s[left]]0: cnt 1left 1while leftm and not cnt: # 最后处理if right-left len(res):res s[left:right]if s[left] in tmp:tmp[s[left]] 1if tmp[s[left]]0: cnt 1left 1return if res2*s else res 53 最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组 是数组中的一个连续部分。 方法一区间和—构造前缀和找后-前的最大值 O(n^2) 方法二动态规划 dp[i]表示以i结尾的连续子数组的最大值 dp[i] dp[i-1]nums[i] if dp[i-1]0 else nums[i] class Solution(object):def maxSubArray(self, nums)::type nums: List[int]:rtype: intn len(nums)dp, res [0]*n, float(-inf)for i,num in enumerate(nums):if i0:dp[i] numelse:if dp[i-1]0: dp[i] numelse: dp[i] dp[i-1]numres max(res, dp[i])return res# 完成如上代码后发现可以优化空间
class Solution(object):def maxSubArray(self, nums)::type nums: List[int]:rtype: intn len(nums)dp, res 0, float(-inf)for i,num in enumerate(nums):if i0:dp numelse:if dp0: dp numelse: dp dp numres max(res, dp)return res 41 缺失的第一个正数
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 方法原地哈希 越界值不处理 class Solution:def firstMissingPositive(self, nums: List[int]) - int:i, n 0, len(nums)while in:if 0nums[i]n and nums[i] ! i1 and nums[nums[i]-1] ! nums[i]: # 注意交换条件:当前值在处理范围且不在正确位置同时需要被交换的值也不在正确位置# 注意交换顺序# nums[i], nums[nums[i]-1] nums[nums[i]-1], nums[i]nums[nums[i]-1], nums[i] nums[i], nums[nums[i]-1]else: i1 # 越界值不处理for i in range(n):if nums[i] ! i1: return i1return n1 142 环形列表II 检测链表是否有环快慢指针判断是否会再次相遇 求链表环入口假设入环前长度x环长度y当快慢指针相遇时fast比slow多在环内绕n圈则slowny即slow再走x步即可到达环入口 class Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:if head None:return Noneslow, fast head, head.nextwhile fast and fast.next and fast ! slow:fast, slow fast.next.next, slow.nextif not fast or not fast.next:return None # 无环fast, slow head, slow.nextwhile fast ! slow:fast, slow fast.next, slow.nextreturn fast 437 路径总和III
给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。 相当于求区间和为目标值的所有区间——前缀和 class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) - int:global restmp, res, hashmap 0, 0, {0:1}def backtrack(node, tmp):if not node: returnglobal restmp node.val # 当前前缀和if tmp-targetSum in hashmap: # 能找到区间和为targetSum的区间res hashmap[tmp-targetSum]if tmp in hashmap: hashmap[tmp] 1 # 更新前缀和else: hashmap[tmp] 1backtrack(node.left, tmp)backtrack(node.right, tmp)hashmap[tmp] - 1tmp - node.valreturnbacktrack(root, tmp)return res 994 腐烂的橘子
在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一
值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。
每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。 方法一次遍历统计新鲜橘子个数和腐烂橘子位置模拟腐烂后统计腐烂时间需要多点同时腐烂才能得到最小分钟数 class Solution:def orangesRotting(self, grid: List[List[int]]) - int:m, n len(grid), len(grid[0])stack, cnt, res [], 0, 0for i in range(m):for j in range(n):if grid[i][j] 1: cnt 1elif grid[i][j] 2: stack.append([i,j])if cnt0: return 0if not stack: return -1while stack:# print(stack)time len(stack)for _ in range(time):[x, y] stack.pop(0) # 左出右进for [i,j] in ([0,-1],[0,1],[-1,0],[1,0]):if 0xim and 0yjn:# print([xi,yj])if grid[xi][yj] 1:grid[xi][yj] 0 # 避免后续重复stack.append([xi, yj])cnt - 1res 1if cnt: return -1else: return res-1 153 寻找旋转排序数组最小数
已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 由于题目强调数组中的元素值互不相同所以增加特殊判断避免mid和left/right元素值相同的情况 class Solution:def findMin(self, nums: List[int]) - int:# 不限制时间复杂度的话一次遍历找到断点即可left, right 0, len(nums)-1while leftright:mid (leftright)//2if nums[left]nums[mid]: # 左侧有序if nums[left]nums[right]: return nums[left]else:left mid 1elif nums[mid]nums[right]: # 右侧有序right midelse: return min(nums[left], nums[right]) 416 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 方法一计算数组总和后转为求数组和为sum//2的子集组合——回溯 方法二动态规划dp代表元素和 class Solution:def canPartition(self, nums: List[int]) - bool:summ sum(nums)if summ%2: return Falseelse: summ summ//2dp [False]*(summ1)dp[0] Truefor num in nums:for i in range(summ, num-1, -1): # 从后往前避免加入num后使dp[k*num]都有效if dp[i-num]: dp[i] Truereturn dp[-1] 1143 最长公共子序列
给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 思路动态规划 dp[i][j]表示text1[:i]和text2[:j]的最长公共子序列长度 状态转移 当text1[i-1]text2[j-1]时dp[i][j] dp[i-1][j-1]1 当text1[i-1]!text2[j-1]时dp[i][j] max(dp[i-1][j], dp[i][j-1]) class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:m, n len(text1), len(text2)dp [[0]*(n1) for _ in range(m1)]for i in range(m1):for j in range(n1):if i0: dp[i][j] 0 # 和空字符串的最长公共子序列为0elif j0: dp[i][j] 0else:if text1[i-1]text2[j-1]:dp[i][j] dp[i-1][j-1]1else:dp[i][j] max(dp[i-1][j], dp[i][j-1])return dp[-1][-1] 72 编辑距离
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符 思路动态规划 dp[i][j]表示word1[:i]转换成word2[:j]的最少操作数 状态转移dp[i][j] dp[i][j-1]1 (插入) dp[i][j] dp[i-1][j]1 (删除) dp[i][j] dp[i-1][j-1]1替换 故dp[i][j] min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])1 class Solution:def minDistance(self, word1: str, word2: str) - int:m, n len(word1), len(word2)dp [[0]*(n1) for _ in range(m1)]for i in range(m1):for j in range(n1):if i0: dp[i][j] j # 空的word1变成word2直接插入elif j0: dp[i][j] i # word1变成空的word2直接删除else:if word1[i-1]word2[j-1]: # 不用操作dp[i][j] dp[i-1][j-1]else:dp[i][j] min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])1# print(dp)return dp[-1][-1] 287 寻找重复数
给定一个包含 n 1 个整数的数组 nums 其数字都在 [1, n] 范围内包括 1 和 n可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 取消数组不修改的限制可以用原地哈希 本质上是一个环形链表找环入口的问题 建立下标i和nums[i]的映射关系若有重复的nums[i]则代表有多个不同的i能映射到nums[i]即构成环解决思路参考142 class Solution:def findDuplicate(self, nums: List[int]) - int:if len(nums) 1: return nums[0]fast, slow nums[nums[0]], nums[0]while fast ! slow: fast nums[nums[fast]]slow nums[slow]idx1, idx2 0, fastwhile idx1 ! idx2:idx1 nums[idx1]idx2 nums[idx2]return idx1
