【刷题】哈希表

发表于 更新于 分类于
本文字数： 4.9k 阅读时长 ≈ 16 分钟

前言

哈希表

242. 有效的字母异位词

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# [242] 有效的字母异位词

# @lc code=start
class Solution:
    def isAnagram(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
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        r = collections.Counter(ransomNote)
        m = collections.Counter(magazine)
        for i in r.keys():
            if i not in m.keys():
                return False
            m[i] -= r[i]
            if m[i] < 0:
                return False
        return True

利用list来构造hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# [383] 赎金信

# @lc code=start
class Solution:
    def canConstruct(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:
                return False
            else:
                arr[ord(i)-ord('a')] -= 1

        return True

49. 字母异位词分组

解题思路：

1
2
3
4
5
6
7
8
9
10
11
# [49] 字母异位词分组

# @lc code=start
class Solution:
    def groupAnagrams(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)
        return list(st.values())

438. 找到字符串中所有字母异位词

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# [438] 找到字符串中所有字母异位词

# @lc code=start
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        left = 0
        len_s = len(s)
        len_p = len(p)
        ans = []
        dic_p = collections.Counter(p)
        for i in range(len_s - len_p + 1):
            if collections.Counter(s[i:i + len_p])==dic_p:
                ans.append(i)
            # dic_p = collections.Counter(p)
            # flag = 1
            # cp = s[i:i + len_p]
            # for j in cp:
            #     # print(j, end=" ")
            #     if j not in dic_p.keys():
            #         flag = 0
            #         break
            #     dic_p[j] -= 1
            #     # print(dic_p, end=" ")
            #     if dic_p[j] < 0:
            #         flag = 0
            #         break
            # print("cp", cp, flag)
            # if flag != 0:
            #     ans.append(i)
        return ans

349. 两个数组的交集

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# [349] 两个数组的交集

# @lc code=start
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 方法1：使用list作为hash表 ## 80.82%, 13.89%

        hash = [0]*1000
        ans = []
        for i in nums1:
            hash[i] = 1
        for i in nums2:
            if hash[i] == 1:
                ans.append(i)
        return list(set(ans))

        # 方法2：使用dict作为hash表 ## 59.66%, 95.32%

        # dic1 = collections.Counter(nums1)
        # dic2 = collections.Counter(nums2)
        # return list(dic1.keys() & dic2.keys())

350. 两个数组的交集 II

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# [350] 两个数组的交集 II

# @lc code=start
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 方法1：使用list作为hash表 ## 68.24%, 27.37%

        # 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 _ in range(min(dic1[i],dic2[i])):
                    ans.append(i)
        return ans

202. 快乐数

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# [202] 快乐数

# @lc code=start
class Solution:
    def isHappy(self, n: int) -> bool:
        # 该题只要出现了重复的sum，则进入死循环，不可能变为1
        # 该题无需计算sum出现次数，所以使用set即可（可去重）
        def caculateHappy(n):
            sum = 0
            while (n):
                sum += (n % 10)**2
                # print(sum)
                n = n//10
            return sum
        ans = set()  # 不重复
        while True:
            cal = caculateHappy(n)
            if cal == 1:
                return True
            elif cal in ans:
                return False
            ans.add(cal)
            n = cal

1. 两数之和

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
# [1] 两数之和

# @lc code=start
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i, j in enumerate(nums):
            if target-j not in dict.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
class Solution:
    def fourSumCount(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:
                if 0-(i+j) in record:
                    ans += record[0-(i+j)]

15. 三数之和

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# [15] 三数之和

# @lc code=start

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 使用双指针法
        nums = sorted(nums)  # 排序
        if(nums[0] > 0 or nums[-1] < 0): # 如果排序后第一个数大于0，最后一个数小于0，则直接不满足条件
            return []
        ans = []
        for i in range(len(nums)):
            left, right = i+1, len(nums)-1 # 定义双指针
            if(i >= 1 and nums[i] == nums[i-1]):  # 对i去重
                    continue
            while(left < right):
                sum = nums[i]+nums[left]+nums[right]
                if sum == 0:
                    ans.append([nums[i], nums[left], nums[right]])
                    ## 对left和right去重，即比较后一个和目前数是否相等，相等就跳过
                    while(left < right and nums[left] == nums[left+1]):
                        left += 1
                    while(left < right and nums[right] == nums[right-1]):
                        right -= 1
                    left += 1
                    right -= 1
                elif sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
        return ans

18. 四数之和

解题思路：
在三数之和上加了一个循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# [18] 四数之和

# @lc code=start
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 使用双指针法
        nums = sorted(nums)  # 排序
        ans = []
        for j in range(len(nums)):
            if(j >= 1 and nums[j] == nums[j-1]):  # 对i去重
                continue
            for i in range(j+1, len(nums)):
                if(i > j+1 and nums[i] == nums[i-1]):  # 对i去重
                    continue
                left, right = i+1, len(nums)-1  # 定义双指针
                while(left < right):
                    sum = nums[j]+nums[i]+nums[left]+nums[right]
                    if sum == target:
                        ans.append([nums[j], nums[i], nums[left], nums[right]])
                        # 对left和right去重，即比较后一个和目前数是否相等，相等就跳过
                        while(left < right and nums[left] == nums[left+1]):
                            left += 1
                        while(left < right and nums[right] == nums[right-1]):
                            right -= 1
                        left += 1
                        right -= 1
                    elif sum < target:
                        left += 1
                    elif sum > target:
                        right -= 1
        return ans
----------到结尾啦！！ Hoohoo----------