建设网站的安全措施,360网站做二维码,短视频公司网站建设方案,网站建设在哪块做目录 1、LeetCode #xff1a;242.有效的字母异位词
2、349. 两个数组的交集
3、202. 快乐数
4、1. 两数之和
5、454. 四数相加 II
6、383. 赎金信
7、15. 三数之和
8、18. 四数之和 1、LeetCode #xff1a;242.有效的字母异位词
还是比较简单的#xff0c;直接统计…目录 1、LeetCode 242.有效的字母异位词
2、349. 两个数组的交集
3、202. 快乐数
4、1. 两数之和
5、454. 四数相加 II
6、383. 赎金信
7、15. 三数之和
8、18. 四数之和 1、LeetCode 242.有效的字母异位词
还是比较简单的直接统计就行
def isAnagram242(s, t):ss{}if len(s)!len(t):return Falsefor i in range(len(s)):if s[i] in ss:ss[s[i]] ss[s[i]]1else:ss[s[i]] 1for j in range(len(t)):if t[j] in ss and ss[t[j]]0:ss[t[j]] ss[t[j]]-1else:return Falsereturn True
2、349. 两个数组的交集
def intersection349( nums1, nums2):nums1 set(nums1)nums2 set(nums2)res []for i in nums1:if i in nums2:res.append(i)return res
def intersection34902( nums1, nums2):res []for i in nums1:if i in nums2 and i not in res:res.append(i)return res
3、202. 快乐数 终点是无线循环会出现重复的数才退出循环
def isHappy202(n):sum[]while(n!1):s 0for i in str(n):s sint(i)*int(i)n sif n in sum:return Falsesum.append(n)return True
4、1. 两数之和 第一反应就是排序双指针但因为要返回下标又进行了一次for
def twoSum1( nums, target):numsa sorted(nums)i 0j len(numsa)-1while(ij):if numsa[i]numsa[j]target:breakelif numsa[i]numsa[j]target:jj-1else:i i1i1 numsa[i]j1 numsa[j]s1 -1s2 -1for k in range(len(nums)):if nums[k]i1 and s1-1 :s1 kelif nums[k]j1:s2 kreturn [s1,s2] 题解应该是用map感觉思路差不多,而已find in 不就又是一次for吗但时间从52到了48两层for循环达到了1531ms看来还是不一样
def twoSum102( nums, target):map {}for i in range(len(nums)):map[nums[i]] ifor i in range(len(nums)):tmp target - nums[i]if tmp in map and map[tmp] ! i:return [i, map[tmp]]
5、454. 四数相加 II 跟前面有点类似第一想法就是两两相加但我写的计算出来怎么怎么慢608ms题解也很慢548ms好吧看来还是c快吧
def fourSumCount454(nums1, nums2, nums3, nums4):map1 {}for i in range(len(nums1)):for j in range(len(nums2)):s nums1[i]nums2[j]if s in map:map1[s] map1[s]1else:map1[s] 1map2 {}c 0for i in range(len(nums3)):for j in range(len(nums4)):s nums3[i]nums4[j]if -1*s in map1:c cmap1[-1*s]return c 6、383. 赎金信 这种题思路就比较一致匹配的就直接map查找就行C的话数组可能会更快一点
def canConstruct383( ransomNote, magazine):map{}for i in magazine:if i in map:map[i] map[i]1else:map[i]1for i in ransomNote:if i in map and map[i]0:map[i] map[i]-1else:return Falsereturn True
7、15. 三数之和
def threeSum15(nums):nums sorted(nums)res []for i in range(len(nums)):if nums[i]0:breaktmp -1*nums[i]l i1r len(nums)-1while(lr):if nums[l] nums[r] tmp :if [nums[i], nums[l], nums[r]] not in res:res.append([nums[i],nums[l],nums[r]])ll1elif nums[l]nums[r]tmp:r r-1else:l l1return res
理论上不需要说啥但是也太慢了6004ms一个去重降到4696ms if i0 and nums[i]nums[i-1]:continue 把res里面的去重拿到外面降到1248ms只打败了41%的python3用户剩下的人是怎么做到的
def threeSum1502( nums):nums sorted(nums)res []for i in range(len(nums)):if nums[i] 0:breakif i 0 and nums[i] nums[i - 1]:continuetmp -1 * nums[i]l i 1r len(nums) - 1while (l r):if nums[l] nums[r] tmp:res.append([nums[i], nums[l], nums[r]])if nums[l] nums[r] tmp:r r - 1while (l r and nums[r] nums[r 1]):r r - 1else:l l 1while (l r and nums[l] nums[l - 1]):l l 1return res8、18. 四数之和 四数之和跟前面三数之和类似主要是剪枝和有可能是负数不能直接比大小直接上最后的剪完版本772ms def fourSum(self, nums: List[int], target: int) - List[List[int]]:nums sorted(nums)all[]for i in range(len(nums)-3):if nums[i]target and nums[i]0:breakif i0 and nums[i]nums[i-1]:continuefor j in range(i1,len(nums)):sum nums[i]nums[j]if sumtarget and nums[j]0:breakif ji1 and nums[j]nums[j-1]:continuelj1r len(nums)-1while(lr):if nums[l]nums[r]target-sum:res [nums[i],nums[j],nums[l],nums[r]]#if res not in all:all.append(res)if nums[l]nums[r]target-sum:r r-1while (l r and nums[r] nums[r 1]):r r - 1else:ll1while (l r and nums[l] nums[l - 1]):l l 1return all 总结
数组主要是逻辑的东西好像之前也又做过还是快的
查找匹配直接上mappython只验证了逻辑c应该要考虑结构数组集合映射之类的
数组很多是双指针
