LeetCodeCampsDay6哈希表part01

以及几题目主要利用hash table的“唯一性”思想解决题目

关键词：哈希表；快慢指针；双指针；用set/dict/当成hash表；

242. 有效的字母异位词

https://leetcode.cn/problems/valid-anagram/

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

思路

  1. 使用hash table可解决
  2. 开辟一块26个int型的数组即可，比如对于字符串s，"a"出现一次，则’a’ - ‘a’的下标（应该是0）对应的数据加一；而对于字符串t，就将反着“检查”，比如’n’出现一次，就要将’n’ - 'a’的下标对应的数据减一；
  3. 最后，判断是否有「非零」数，若存在则s与t不是字母异位词
  4. 可以通过判断s与t长度提前判断；

如动画所示

img

代码

ord(.)用于获取字符的ascii码

  • 时间复杂度O(n)
  • 空间复杂度O(1)，指仅用了26个int型（因为length <= 5*10^4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        nums = [0] * 26
        # 如果两者长度不相等直接False
        if len(s)!= len(t):
            return False
        for i in s:
            nums[ord(i) - ord('a')] += 1
        for i in t:
            nums[ord(i) - ord('a')] -= 1
        for i in nums:
            if i != 0:
                return False
        return True

代码改进，可以使用zip减少一次遍历次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        nums = [0] * 26
        # 如果两者长度不相等直接False
        if len(s)!= len(t):
            return False
        # 仅当长度相等时，同步推进，减少一次遍历次数
        for i,j in zip(s,t):
            nums[ord(i) - ord('a')] += 1
            nums[ord(j) - ord('a')] -= 1
        for i in nums:
            if i != 0:
                return False
        return True

349. 两个数组的交集

https://leetcode.cn/problems/intersection-of-two-arrays/

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

思路

  1. 如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费，此时就要使用另一种结构体set

  2. 先将nums1转成unordered_set，再将nums2与这unordered_set比较，得到二次筛选后的unordered_set.

  3. 在python时使用dict字典即可，将nums1的数据添加到字典了（如果已经存在就不用添加了，也是变相地一种set）

如动画所示

img

代码

python提供了集合set函数，可以直接使用

1
2
3
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

手动实现，使用字典dict和列表list实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
		def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dictSet = dict()
        for i in nums1:
          	# 如果i 不在dictSet中，返回-1，并且添加到dictSet中，赋值为1（随便给）
            # get 方法内部也会进行哈希表查找，一次查询的平均时间复杂度也是 O(1)
            # 与if i in dictSet:一样
            if dictSet.get(i, -1) == -1:
                dictSet[i] = 1
        res = list()
        for i in nums2:
            if i in dictSet:
                res.append(i)
                # 删除dictSet中的这个数据，防止被反复添加
                del dictSet[i]
        return res
      	
        # 或者将res设置为set，可以减少删除dictSet中数字的步骤
        # res = set()
        # for i in nums2:
        #     if dictSet.get(i, -1) != -1:
        #         res.add(i)
        # return list(res)

当然也可以使用数组（list）实现，这题目限制范围是0<=num<=1000数据，可以开1001个位置的数据并按242. 有效的字母异位词的思路赋值再查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   dictSet = [0] * 1001
# 在nums1中的数据先在dictSet设置为1
   for i in nums1:
       dictSet[i] = 1
   # 在nums2中的数据，并且在dictSet设置为1的，再设置为2
   # 好处是如果dictSet中有重复的数据，不用被重复设置
   for i in nums2:
       if dictSet[i] == 1:
           dictSet[i] = 2
   res = list()
   # 最后输出dictSet中为2的，就是同时出现在两个nums的并且不重复的数据
   for i in range(1001):
       if dictSet[i] == 2:
           res.append(i)
   return res

Pytorch版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import torch

def intersection(nums1: List, nums2: List)
		# 转成tensor
		nums1_tensor = torch.tensor(nums1)
  	nums2_tensor = troch.tensor(nums2)
    # 使用unique（与set类似）
    unique_nums1 = torch.unique(nums1_tensor)
    # isin返回一个bool张量，表示每个元素是否在nums2_tensor中
    mask = torch.isin(unique_nums1, nums2_tensor)
    # 傅mask过滤得到交集元素。
    intersection_tensor = unique_nums1[mask]
    # 转回list格式
    return intersection_tensor.tolist()

# 示例测试
nums1 = [1, 2, 2, 1, 6]
nums2 = [2, 2, 4, 6]
result = intersection(nums1, nums2)
print(result)  # 输出: [2, 6]

202. 快乐数

https://leetcode.cn/problems/happy-number/

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

1
2
输入：n = 2
输出：false

提示：

  • 1 <= n <= 231 - 1

思路一

  1. 题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
  2. 可以使用Hash Table，如果sum在表中出现了则说明有循环，可以直接退出；否则就一直找，直到sum=1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isHappy(self, n: int) -> bool:
        # 设置个set，如果未在set中即可添加进来，否则就出现循环了
        table = set()
        while n != 1:
          	# python中将数字按位划分的最方便形式就是转成str后按数组对付
            n_str = str(n)
            n = 0
            for i in n_str:
                n += int(i)*int(i)
            if n not in table:
                table.add(n)
            else:
                return False
        return True

相似的思路，如果不在list中就添加进来，一直计算sum直到等于1停止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isHappy(self, n: int) -> bool:
        # 设置个set，如果未在set中即可添加进来，否则就出现循环了
        table = list()
        while n not in table:
          	table.append(n)
          	# python中将数字按位划分的最方便形式就是转成str后按数组对付
            n_str = str(n)
            n = 0
            for i in n_str:
                n += int(i)*int(i)
            if n == 1:
              	return True
        return False

思路二快慢指针

  1. 这题目可以用快慢指针解决，如果出现了"循环"（sum会重复出现），其实就是“链表有环”的问题
  2. 慢指针每次走一步；快指针每次走两步。即慢指针每次计算sumN(slow)，快指针每次计算sumN(sumN(fast))
  3. 如果slow == fast则说明有环（有重复的sum）返回False
  4. while跳出条件是sumN(fast)!=1，这和fast.next不为空即可[在有环链表题目中，while fast and fast.next则执行]

代码

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
class Solution:
    def sumN(self, n:int):
        n_str = str(n)
        new_n = 0
        for i in n_str:
            new_n += int(i)*int(i)  
        return new_n
      
    def sumNByhand(self, n:int):
        new_n = 0
        while n:
            temp = n % 10
            new_n += temp ** 2
            n = n // 10
        return new_n
      
    def isHappy(self, n: int) -> bool:
        slow = n
        fast = n
        while self.sumN(n) != 1 and self.sumN(self.sumN(fast)) != 1:
            slow = self.sumN(slow)
            fast = self.sumN(self.sumN(fast))
            if slow == fast:
                return False
        return True

1. 两数之和

https://leetcode.cn/problems/two-sum/

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路

  1. 使用hash map, 本题目可以使用dict，因为它已经假设每种输入只有一个答案
  2. 记录table[target - nums[i_1]] = i_1，如果target - nums[i_1] == nums[i_2]则说明target == nums[i_1] + nums[i_2]
  3. 如果nums[i_2]在table中，则找到了一个匹配的返回i_1和i_2

img

img

代码

如果使用双重循环的方式，时间复杂度O(N^2)，但空间复杂度可以到O(1)；所以本质还是空间换时间

  • 时间复杂度O(N)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 使用个hash map，记录table[target - nums[i_1]] = i_1
        # 如果nums[i_2]在table中，则找到了一个匹配的返回i_1和i_2
        table = dict()
        L = len(nums)
        for i in range(L):
          	# 如果当前元素在table内，说明已经找到匹配的了
            if nums[i] in table:
                return table[nums[i]], i
            # 否则，target-nums[i] 就是需要等的数字
            table[target - nums[i]] = i
        return

思路二双指针

  1. 可以使用双指针做，但前提是：数组是有序的(从小到大）
  2. left指针从左向右遍历；right指针从右向左遍历
  3. 每次计算left和right所指数字的和；并与target判断大小；如果current_sum大了，则right向左移动；小了则left向右移动；如果相等，有点儿的麻烦的是，需要将left和right在原nums的下标进行还原；
  4. 初次的还原使用nums.index(nums_sorted[left])，但会出现left_index == right_index的情况，因为题目规定不能使用同一个下标，所以需要将right_index进行调整，调整到nums[left_index+1:].index(nums_sorted[right]) + left_index + 1，也就是强行在nums[left_index+1:]里找right数字对应的下标（返回的是nums[left_index+1:]的下标值，即相对下标）所以需要再加上left_index+1成为绝对下标

代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)—因为占用了个空间存放排序后的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# method2 双指针
nums_sorted = sorted(nums)

left = 0
right = len(nums) - 1
while left < right:
    current_sum = nums_sorted[left] + nums_sorted[right]
    print(current_sum)
    if current_sum == target:
        # 如果两个数字之和等于target就返回两个数的下标（原nums数组中的）
        left_index = nums.index(nums_sorted[left])
        right_index = nums.index(nums_sorted[right])
        if left_index == right_index:
            right_index = nums[left_index+1:].index(nums_sorted[right]) + left_index + 1
        return left_index, right_index
    # 否则left向右移动
    elif current_sum < target:
        left += 1
    else:
        right -= 1
return