网站后台乱码怎么办,wordpress新建主题,全景网站如何做,西安网站开发公司排名LeetCode Hot 100 是最常被考察的题目集合#xff0c;涵盖了面试中常见的算法和数据结构问题。刷 Hot100可以让你在有限的时间内集中精力解决最常考的问题。不仅要写出代码#xff0c;还要理解问题的本质、优化解法和复杂度分析。 滑动窗口
438. 找到字符串中所有字母异位词… LeetCode Hot 100 是最常被考察的题目集合涵盖了面试中常见的算法和数据结构问题。刷 Hot100可以让你在有限的时间内集中精力解决最常考的问题。不仅要写出代码还要理解问题的本质、优化解法和复杂度分析。 滑动窗口
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。s 和 p 仅包含小写字母。
思路 哈希表滑动窗口。把待匹配的字符串用数组哈希化左右指针滑动右指针纳入元素判断是否合法不合法则移动左指针直到合法。若窗口合法且长度相等符合条件。
class Solution:def findAnagrams(self, s: str, p: str) - List[int]:ans [] # 存放结果答案cnt [0] * 26 # 小写字母26个位置存放频率for i in p:cnt[ord(i)-ord(a)] 1 # 待匹配的字符串字符频率left 0for right in range(len(s)):cnt[ord(s[right])-ord(a)] - 1 # 右指针位置元素纳入窗口while cnt[ord(s[right])-ord(a)] 0: # 若有元素频率小于0①不在待匹配字符串②多次出现同一字符【都是有字符超了】cnt[ord(s[left])-ord(a)] 1 # 将左指针对应的元素释放频率还回去left 1 # 左指针右移左指针追右指针if right - left 1 len(p): # 如果长度相等加上前面都不小于0符合题意ans.append(left)return ans209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组[numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
思路 依次纳入窗口判断窗口中子数组是否满足target因为要找最小长度满足则移动左指针更新最小长度。时间复杂度O(n)空间O(1).
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:if sum(nums)target: return 0 # 不存在符合条件的子数组total 0slow 0ans float(inf)for fast in range(len(nums)): total nums[fast] # 依次将元素纳入窗口while total target: # 找最小数组满足条件移动左指针ans min(ans, fast-slow1) # 更新最小长度total - nums[slow]slow 1return ans
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。
思路 记录每个字符需要个数和总个数不断扩展右边界直到覆盖全部子串。覆盖全部子串后再不断缩小左边界直到找到覆盖的最小区间其中之一。记录区间是否需要更新再缩小一步左边界。
class Solution:def minWindow(self, s: str, t: str) - str:need Counter(t) # 统计下需要的数出现频率更新可能出现负数ans (0, float(inf)) # 元组记录起始索引和长度needcnt len(t) # 总需要的数left 0for right in range(len(s)): # 用enumerate()写会好看扩展窗口if need[s[right]] 0: # 目标数则总数减1needcnt - 1need[s[right]] - 1 # 字符记录到对应字典减1if needcnt 0: # 满足覆盖的子数组条件while True: # 试图移动左指针缩小窗口if need[s[left]] 0:breakneed[s[left]] 1 # 不是目标数则左移左指针left 1if right - left ans[1] - ans[0]: # 将所有非目标数移除得到一个最小区间ans (left, right) # 如果比之前记录的小更新need[s[left]] 1 # 移动左指针同时将needcnt也加个1needcnt 1left 1return if ans[1]len(s) else s[ans[0]: ans[1]1] # 切片用法链表
142. 环形链表Ⅱ
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
思路 快指针2步慢指针1步快慢指针环中相遇从相遇点到环入口和从链表到环入口距离一样。时间复杂度O(n)空间O(1).
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:fast slow head # 使用快慢指针while fast and fast.next: # 确保下一个节点存在否则无法访问其nextslow slow.next # 慢指针每次走一步fast fast.next.next # 快指针每次走两步if fast slow: # 快指针在环中追到慢指针slow head # 重置慢指针的位置while fast ! slow:slow slow.nextfast fast.nextreturn slow # 慢指针再次移动的位置即为入环index递归
78. 子集
思路 回溯。每次进入回溯函数先将当前集合加入结果再遍历该层元素加入递归回溯。主要起始位置需要变。
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:self.ans [] # 存放结果self.backtracking(nums, 0, [])return self.ansdef backtracking(self, nums, startIndex, path):self.ans.append(path[:]) # 每次都想加入结果集for i in range(startIndex, len(nums)):path.append(nums[i]) # 往里新增该层的元素self.backtracking(nums, i1, path) # 递归进入下一层path.pop()回溯
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
思路 不同的按键是不同的层作为参数传递。
class Solution:def letterCombinations(self, digits: str) - List[str]:if not digits: return [] # 处理空字符串phone_map {2 : abc,3 : def,4 : ghi,5 : jkl,6 : mno,7 : pqrs,8 : tuv,9 : wxyz}self.ans []self.backtracking(phone_map, digits, 0, [])return self.ansdef backtracking(self, phone_map, digits, startIndex, path):if startIndex len(digits):self.ans.append(.join(path))return letters phone_map[digits[startIndex]]for letter in letters: path.append(letter)self.backtracking(phone_map, digits, startIndex1, path)path.pop()39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
思路
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:self.ans []self.backtracking(candidates, target, [], 0)return self.ansdef backtracking(self, candidates, target, path, startIndex): if target 0:self.ans.append(path[:])returnif target 0:returnfor i in range(startIndex, len(candidates)): # 为了避免顺序不同元素相同的重复还是按顺序选path.append(candidates[i])self.backtracking(candidates, target-candidates[i], path, i) # 可以被无限选取所以用i不用i1path.pop()131. 分割回文串
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
思路 如果是回文串则加入path。path长度达到字符串长度找到一种方案。
class Solution:def partition(self, s: str) - List[List[str]]:self.ans []self.backtracking(s, [], 0)return self.ansdef backtracking(self, s, path, startIndex):if startIndex len(s): # 超过长度则得到一种分割方法self.ans.append(path[:])returnfor i in range(startIndex, len(s)):if s[startIndex:i1] s[startIndex:i1][::-1]: # 最佳实践判断是回文串就写入path.append(s[startIndex:i1])self.backtracking(s, path, i1)path.pop() 文章转载自： http://www.morning.kxbry.cn.gov.cn.kxbry.cn http://www.morning.ldynr.cn.gov.cn.ldynr.cn http://www.morning.cpkcq.cn.gov.cn.cpkcq.cn http://www.morning.nqmhf.cn.gov.cn.nqmhf.cn http://www.morning.ncfky.cn.gov.cn.ncfky.cn http://www.morning.fbxdp.cn.gov.cn.fbxdp.cn http://www.morning.rxwfg.cn.gov.cn.rxwfg.cn http://www.morning.hcszr.cn.gov.cn.hcszr.cn http://www.morning.zrks.cn.gov.cn.zrks.cn http://www.morning.qgjgsds.com.cn.gov.cn.qgjgsds.com.cn http://www.morning.wddmr.cn.gov.cn.wddmr.cn http://www.morning.caswellintl.com.gov.cn.caswellintl.com http://www.morning.tmjhy.cn.gov.cn.tmjhy.cn http://www.morning.uycvv.cn.gov.cn.uycvv.cn http://www.morning.lbpfl.cn.gov.cn.lbpfl.cn http://www.morning.zlkps.cn.gov.cn.zlkps.cn http://www.morning.lqpzb.cn.gov.cn.lqpzb.cn http://www.morning.lfcnj.cn.gov.cn.lfcnj.cn http://www.morning.nhgkm.cn.gov.cn.nhgkm.cn http://www.morning.rcqyk.cn.gov.cn.rcqyk.cn http://www.morning.jnzfs.cn.gov.cn.jnzfs.cn http://www.morning.srnhk.cn.gov.cn.srnhk.cn http://www.morning.nbhft.cn.gov.cn.nbhft.cn http://www.morning.dpnhs.cn.gov.cn.dpnhs.cn http://www.morning.zmqb.cn.gov.cn.zmqb.cn http://www.morning.qrpx.cn.gov.cn.qrpx.cn http://www.morning.wmnpm.cn.gov.cn.wmnpm.cn http://www.morning.cgntj.cn.gov.cn.cgntj.cn http://www.morning.xbkcr.cn.gov.cn.xbkcr.cn http://www.morning.rlpmy.cn.gov.cn.rlpmy.cn http://www.morning.qwdlj.cn.gov.cn.qwdlj.cn http://www.morning.phlrp.cn.gov.cn.phlrp.cn http://www.morning.jgmdr.cn.gov.cn.jgmdr.cn http://www.morning.nfsrs.cn.gov.cn.nfsrs.cn http://www.morning.rfmzs.cn.gov.cn.rfmzs.cn http://www.morning.lhptg.cn.gov.cn.lhptg.cn http://www.morning.nfpgc.cn.gov.cn.nfpgc.cn http://www.morning.qgtfl.cn.gov.cn.qgtfl.cn http://www.morning.mfbcs.cn.gov.cn.mfbcs.cn http://www.morning.smggx.cn.gov.cn.smggx.cn http://www.morning.vibwp.cn.gov.cn.vibwp.cn http://www.morning.rqzyz.cn.gov.cn.rqzyz.cn http://www.morning.ncrk.cn.gov.cn.ncrk.cn http://www.morning.nswcw.cn.gov.cn.nswcw.cn http://www.morning.xtyyg.cn.gov.cn.xtyyg.cn http://www.morning.yltyz.cn.gov.cn.yltyz.cn http://www.morning.dmldp.cn.gov.cn.dmldp.cn http://www.morning.shnqh.cn.gov.cn.shnqh.cn http://www.morning.nzfyx.cn.gov.cn.nzfyx.cn http://www.morning.ljmbd.cn.gov.cn.ljmbd.cn http://www.morning.jjhng.cn.gov.cn.jjhng.cn http://www.morning.dlrsjc.com.gov.cn.dlrsjc.com http://www.morning.zxqxx.cn.gov.cn.zxqxx.cn http://www.morning.mmclj.cn.gov.cn.mmclj.cn http://www.morning.nuejun.com.gov.cn.nuejun.com http://www.morning.ktmbr.cn.gov.cn.ktmbr.cn http://www.morning.jnptt.cn.gov.cn.jnptt.cn http://www.morning.hkshy.cn.gov.cn.hkshy.cn http://www.morning.wfmqc.cn.gov.cn.wfmqc.cn http://www.morning.knnhd.cn.gov.cn.knnhd.cn http://www.morning.tqbyw.cn.gov.cn.tqbyw.cn http://www.morning.lwsct.cn.gov.cn.lwsct.cn http://www.morning.0small.cn.gov.cn.0small.cn http://www.morning.fkgcd.cn.gov.cn.fkgcd.cn http://www.morning.pnjsl.cn.gov.cn.pnjsl.cn http://www.morning.tqsmc.cn.gov.cn.tqsmc.cn http://www.morning.tjqcfw.cn.gov.cn.tjqcfw.cn http://www.morning.gbsfs.com.gov.cn.gbsfs.com http://www.morning.tpkxs.cn.gov.cn.tpkxs.cn http://www.morning.gsjfn.cn.gov.cn.gsjfn.cn http://www.morning.rqrh.cn.gov.cn.rqrh.cn http://www.morning.yrms.cn.gov.cn.yrms.cn http://www.morning.zshuhd015.cn.gov.cn.zshuhd015.cn http://www.morning.rdlrm.cn.gov.cn.rdlrm.cn http://www.morning.china-cj.com.gov.cn.china-cj.com http://www.morning.zwtp.cn.gov.cn.zwtp.cn http://www.morning.qyfrd.cn.gov.cn.qyfrd.cn http://www.morning.czzpm.cn.gov.cn.czzpm.cn http://www.morning.xpqdf.cn.gov.cn.xpqdf.cn http://www.morning.ngcth.cn.gov.cn.ngcth.cn
