理论基础

用Python的defaultdic来构建类似于map的哈希表。需要注意的是对每个key生成dict时value默认是零。

题目

P242

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        cnt=0
        dict=defaultdict(int)
        for i in range(len(s)):
            dict[ord(s[i])]+=1

        for i in range(len(t)):
            dict[ord(t[i])]-=1

        for x in dict:
            if dict[x] !=0:
                return False
                break
            else:
                cnt+=1
        if cnt==len(dict):
            return True

python通过ord()转换字符为ascll码

P349

给定两个数组 nums1 和 nums2 ，返回 它们的 交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ls=[]
        dict=defaultdict(int)
        set1=set(nums1)
        set2=set(nums2)

        for x in set1:
            dict[x]+=1

        for x in set2:
            dict[x]-=1

        for x in dict:
            if dict[x]==0:
                ls.append(x)
        return ls

P1

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        List=[]
        dict=defaultdict(int)
        for i in range(len(nums)):
            if dict[target-nums[i]] !=0:
                List.append(i)
                List.append(dict[target-nums[i]])
            else:
                if i !=0 and nums[i]+nums[0]==target:
                    List.append(i)
                    List.append(dict[target - nums[i]])
                else:
                    dict[nums[i]]=i
        List.sort()
        return List

P454

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] 输出：2 解释： 两个元组如下： 1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0 示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] 输出：1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ls=[]
        dict=defaultdict(int)
        set1=set(nums1)
        set2=set(nums2)

        for x in set1:
            dict[x]+=1

        for x in set2:
            dict[x]-=1

        for x in dict:
            if dict[x]==0:
                ls.append(x)
        return ls