# @lc code=start classSolution: defisAnagram(self, s: str, t: str) -> bool: s=collections.Counter(s) t=collections.Counter(t) return s==t ## return方法1 ## return 方法2 # if len(s)!=len(t): # return False # for i in s.keys(): # if s[i]!=t[i]: # return False # return True
383. 赎金信
解题思路:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# [383] 赎金信
# @lc code=start classSolution: defcanConstruct(self, ransomNote: str, magazine: str) -> bool: r = collections.Counter(ransomNote) m = collections.Counter(magazine) for i in r.keys(): if i notin m.keys(): returnFalse m[i] -= r[i] if m[i] < 0: returnFalse returnTrue
利用list来构造hash表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# [383] 赎金信
# @lc code=start classSolution: defcanConstruct(self, ransomNote: str, magazine: str) -> bool: arr = [0] * 26# 使用列表构造hash表,由于全是小写字母 for i in magazine: arr[ord(i)-ord('a')] += 1 for i in ransomNote: if arr[ord(i)-ord('a')] <= 0: returnFalse else: arr[ord(i)-ord('a')] -= 1
returnTrue
49. 字母异位词分组
解题思路:
1 2 3 4 5 6 7 8 9 10 11
# [49] 字母异位词分组
# @lc code=start classSolution: defgroupAnagrams(self, strs: List[str]) -> List[List[str]]: st = collections.defaultdict(list) for s in strs: d = "".join(sorted(s)) # print(d) st[d].append(s) returnlist(st.values())
# hash = [0] * 1001 # ans = [] # for i in nums1: # hash[i] += 1 # if hash[i] > 0: # ans.append(i) # hash[i] -= 1 # return ans
# 方法2:使用dict作为hash表 ## 95.39%, 11.89%
dic1 = collections.Counter(nums1) dic2 = collections.Counter(nums2) ans = [] for i in dic2.keys(): if i in dic1.keys(): for _ inrange(min(dic1[i],dic2[i])): ans.append(i) return ans
# @lc code=start classSolution: defisHappy(self, n: int) -> bool: # 该题只要出现了重复的sum,则进入死循环,不可能变为1 # 该题无需计算sum出现次数,所以使用set即可(可去重) defcaculateHappy(n): sum = 0 while (n): sum += (n % 10)**2 # print(sum) n = n//10 returnsum ans = set() # 不重复 whileTrue: cal = caculateHappy(n) if cal == 1: returnTrue elif cal in ans: returnFalse ans.add(cal) n = cal
1. 两数之和
解题思路:
1 2 3 4 5 6 7 8 9 10 11 12
# [1] 两数之和
# @lc code=start classSolution: deftwoSum(self, nums: List[int], target: int) -> List[int]: dict = {} for i, j inenumerate(nums): if target-j notindict.keys(): dict[j]=i else: return [dict[target-j],i]
454. 四数相加 II
解题思路:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# [454] 四数相加 II
# @lc code=start classSolution: deffourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int: record = {} ans = 0 for i in nums1: for j in nums2: record[i+j] = record.get(i+j, 0)+1 for i in nums3: for j in nums4: if0-(i+j) in record: ans += record[0-(i+j)]