桂林做网站哪家好,网站建设公司哪个好,深圳台历制作,tp框架网站开发参考文献2019.08.05 3.无重复字符的最长字串
基本思想#xff1a;双指针、哈希表实现#xff1a; 使用 head 指向无重复子串的头#xff0c;ind 指向当前位置#xff08;即当前无重复子串的尾#xff09;#xff0c;len_max记录当前无重复字串的最长长度#xff0c;使用字典的 …2019.08.05 3.无重复字符的最长字串
基本思想双指针、哈希表实现 使用 head 指向无重复子串的头ind 指向当前位置即当前无重复子串的尾len_max记录当前无重复字串的最长长度使用字典的 key 存储串 s 的字符value 存储字符在串中的位置。当 k当前字符不在字典中时表明 k 是当前无重复子串的尾元素故当前无重复字符的子串长度为( ind - head 1 )与最大长度进行比较看是否更新然后将此 k 放入字典中当 k 已经存在于字典中时还需判断 字典中的这个 k 的 value即在串中的位置是否大于等于 head因为 head 是当前无重复子串的首位置如果小于 head 则认为这个已经存在的 k 早已废弃与当前无重复子串无关与 k 不在字典中时的情况一致处理k 的 value 大于等于 head 则认为遇到了重复元素k 之前的无重复子串的长度为 ( ind - head )与最大长度进行比较看是否需要更新然后 head 跟新为 被重复了的元素 k~ 的下一个位置这样从 k~ 的下一个位置到当前 k 的位置的子串又是另一个无重复子串同时更新 k 的 value 值最后返回依次遍历过程中的最大长度。 def lengthOfLongestSubstring(self, s: str) - int:head 0len_max 0_dict {}for ind, k in enumerate(s):if k in _dict and _dict.get(k) head:len_max (ind - head) if (ind - head) len_max else len_maxhead _dict.get(k) 1_dict[k] indelse:len_max (ind - head 1) if (ind - head 1) len_max else len_max_dict[k] indreturn len_max
15.三数之和
基本思想双指针、回溯实现 1. 找组合思路固定三个数字中最左数字的指针 a遍历数组找到每个 a 对应的所有满足nums[a] nums[b] nums[c] 0 的 b,c 组合 2. 当 nums[a] 0 时直接跳出因为 c b a即三个数字都大于 0在此k之后不可能找到组合了 3. 当 a 0 且 nums[a] nums[a - 1] 时跳过此数字因为 nums[a - 1] 的所有组合已经被加入到结果中本次搜索只会搜索到重复组合。 4. bc 分设在数组 [a1, len(nums)-1] 两端根据 sum 与 0 的大小关系交替向中间逼近如果遇到等于 0 的组合则加入 arr 中需要注意移动 ij 需要跳过所有重复值以避免重复答案被计入 arr。 def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort()arr []for a in range(len(nums)-2):if nums[a] 0:break# 剪枝操作if a 0 and nums[a] nums[a-1]:continueb a 1c len(nums) - 1while b c:if nums[a] nums[b] nums[c] 0:arr.append([nums[a], nums[b], nums[c]])b 1c - 1while b c and nums[b] nums[b-1]:b 1while b c and nums[c] nums[c1]:c - 1elif nums[a] nums[b] nums[c] 0:c - 1while b c and nums[c] nums[c1]:c - 1else:b 1while b c and nums[b] nums[b-1]:b 1return arr
2019.08.06 18.四数之和
基本思想双指针、回溯实现可以在三数之和的基础上做或者找出所有符合条件的四数再去重。 def fourSum(self, nums: List[int], target: int) - List[List[int]]:nums.sort()ansset() #去重for i in range(len(nums)-3): #固定第一个数if i 0 and nums[i] nums[i-1]:continue # 剪枝for j in range(i1,len(nums)-2): #固定第二个数if j i1 and nums[j] nums[j-1]:continue # 剪枝leftj1 #左指针rightlen(nums)-1 #右指针while(rightleft):tempnums[i]nums[j]nums[left]nums[right]if temptarget:ans.add((nums[i],nums[j],nums[left],nums[right]))left1right-1if temptarget:right-1 #太大了右指针左移if temptarget:left1 #反之res[] #修改返回格式for i in ans:res.append(list(i))return res
2019.08.09 16.最接近的三数之和
基本思想双指针、回溯实现在三数之和的基础上设置最小差值每次出现新的组合时更新最小差值并保留最小差值时的三数之和。 def threeSumClosest(self, nums: List[int], target: int) - int:nums.sort()min_t sys.maxsizefor i in range(len(nums) - 2):#剪枝操作if i 0 and nums[i] nums[i-1]:continueleft i 1right len(nums) - 1while(left right):sum_t nums[i] nums[right] nums[left]if abs(sum_t - target) min_t:min_t abs(sum_t - target) res sum_tif sum_t target:right - 1elif sum_t target:left 1else:return sum_treturn res
