算法题目 哈希表

Posted by SunQH Blog on February 13, 2021

Leetcode按类型

字典，哈希表

总结

字典使用和查字典方法

  • 遍历列表同时查字典 – 字典查找速度快
  • 搜索元素就想字典(hash表)
1
2
3
4

for i, n in enumerate(nums):
    if target - n in dct:
        return [dct[target - n], i]
    dct[n] = i

1
2

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

1
2
3
4
5
6
7
8
9
10
11
12
13

# 主要思想: 
# 判断 if target - n in dct

class Solution:
    def twoSum(nums, target):
        dct = {}
        for i, n in enumerate(nums):
            if target - n in dct:
                return [dct[target - n], i]
            dct[n] = i
            
result = Solution.twoSum(nums,target)
result

1
2

# 直接从数组中找
# 800ms so slow

1
2
3
4
5
6
7
8
9
10
11
12
13

start = time.time()
class Solution:
    def twoSum(nums, target):
        for i, n in enumerate(nums):
            if (target - n) in nums[i+1:]:
                j = nums[i+1:].index(target - n)
                return [i, j+i+1]

result = Solution.twoSum(nums,target)
result

end = time.time()
print((start - end))

✅ 169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

1
2
3
4
5
6
7
8

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

1
2
3
4
5
6
7
8
9
10

# 排序法,自己写的
class Solution:
    def majorityElement(self, nums) -> int:
        nums.sort()
        return nums[(len(nums)-1)//2]
        
nums = [2,2,1,1,1,2,2]
solution = Solution()
result = solution.majorityElement(nums)
print(result)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Boyer-Moore 投票算法
class Solution:
    def majorityElement(self, nums) -> int:
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)
        
        return candidate
        
        
nums = [2,2,1,1,1,2,2]
solution = Solution()
result = solution.majorityElement(nums)
print(result)

###

🚩1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

1
2
3
4
5

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

字典使用和查字典方法

  • 遍历列表同时查字典 – 字典查找速度快
  • 搜索元素就想字典(hash表)
1
2
3
4

for i, n in enumerate(nums):
    if target - n in dct:
        return [dct[target - n], i]
    dct[n] = i

1
2

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

1
2
3
4
5
6
7
8
9
10
11
12
13

# 主要思想: 
# 判断 if target - n in dct

class Solution:
    def twoSum(nums, target):
        dct = {}
        for i, n in enumerate(nums):
            if target - n in dct:
                return [dct[target - n], i]
            dct[n] = i
            
result = Solution.twoSum(nums,target)
result

1
2

# 直接从数组中找
# 800ms so slow

1
2
3
4
5
6
7
8
9
10
11
12
13

start = time.time()
class Solution:
    def twoSum(nums, target):
        for i, n in enumerate(nums):
            if (target - n) in nums[i+1:]:
                j = nums[i+1:].index(target - n)
                return [i, j+i+1]

result = Solution.twoSum(nums,target)
result

end = time.time()
print((start - end))

2️⃣ (1.5h)

✅ 136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

1
2
3
4
5
6
7
8
9
10
11
12

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

2️⃣

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        res = 0
        for num in nums:
            res ^= num

        return res

✅ (40m) 448. 找到所有数组中消失的数字

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

1
2
3
4
5
6
7

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

2️⃣原地修改方法 对i处位置的值为索引将其数字 *-1

1
2
3
4
5
6
7
8
9

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for num in nums:
            if num < 0:
                num = -num
            if nums[num-1] > 0:
                nums[num-1] *= -1
        
        return [i+1  for i in range(len(nums)) if nums[i] > 0]  # 顺序是从前往后的, for, if

✅ (5m) 104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

2️⃣

✅(30m) 36. 有效的数独

难度中等531收藏分享切换为英文接收动态反馈

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。

  • 只需要根据以上规则，验证已经填入的数字是否有效即可。

    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

    class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            row = set()
            column = set()
            gong = set()
  
            for j in range(9):
                if board[i][j] != '.':
                    if board[i][j] in row:
                        return False
                    else:
                        row.add(board[i][j])
                if board[j][i] != '.':
                    if board[j][i] in column:
                        return False
                    else:
                        column.add(board[j][i])
                if board[i//3*3+j//3][i%3*3+j%3] != '.':
                    if board[i//3*3+j//3][i%3*3+j%3] in gong:
                        return False
                    else:
                        gong.add(board[i//3*3+j//3][i%3*3+j%3])
                # print(i)
                # print(row, column, gong)
        return True

✅(40m) 49. 字母异位词分组

难度中等760收藏分享切换为英文接收动态反馈

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

1
2
3
4
5
6
7

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        
        res_dict = defaultdict()
        for s in strs:
            str_key = str(sorted(s))
            # print(str_key)
            if str_key not in res_dict.keys():
                res_dict[str_key] = []
            res_dict[str_key].append(s)

        # print(res_dict)
        return list(res_dict.values())

✅(15m)187. 重复的DNA序列

难度中等169收藏分享切换为英文接收动态反馈

所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例 1：

1
2

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

1
2

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

1
2
3
4
5
6
7
8
9
10

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        res_set = set()
        res = []
        for i in range(len(s)-9):  # 注意，要len-9才能到len-10
            if s[i:i+10] in res_set and  s[i:i+10] not in res:
                res.append(s[i:i+10][:])
            else:
                res_set.add(s[i:i+10][:])
        return res

✅(10m) 202. 快乐数

难度简单621收藏分享切换为英文接收动态反馈

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

「快乐数」定义为：

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

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

示例 1：

1
2
3
4
5
6
7

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

1
2

输入：n = 2
输出：false

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

class Solution:
    def isHappy(self, n: int) -> bool:
        def recursion(n):
            new_n = 0
            while n:
                c = n % 10
                new_n += c**2
                n //= 10
            # print(new_n)
            if new_n ==1:
                return True
            elif new_n in n_set:
                return False
            else:
                n_set.add(new_n)
                return recursion(new_n)
        n_set = set()
        return recursion(n)

✅(20m) 205. 同构字符串

难度简单360收藏分享切换为英文接收动态反馈

给定两个字符串 s 和 *t*，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 *t* ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

1
2

输入：s = "egg", t = "add"
输出：true

示例 2：

1
2

输入：s = "foo", t = "bar"
输出：false

示例 3：

1
2

输入：s = "paper", t = "title"
输出：true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        res_dict = {}

        if len(s) != len(t):
            return False

        for i in range(len(s)):
            if s[i] in res_dict:
                if t[i] != res_dict[s[i]]:
                    return False
            else:
                res_dict[s[i]] = t[i]

        s, t = t, s
        res_dict = {}
        for i in range(len(s)):
            if s[i] in res_dict:
                if t[i] != res_dict[s[i]]:
                    return False
            else:
                res_dict[s[i]] = t[i]

        return True

技巧：只要s和t里的字符是一一对应关系即可

1
2
3
4

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return len(set(s)) == len(set(t)) and len(set(s)) == len(set(zip(s, t)))
CATALOG
    FEATURED TAGS
    Paper summary job 比赛项目 AI算法 数据结构 C++ 算法 Summary
    Other websites