Leetcode题解 - 哈希表

本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站， 刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是哈希表相关题目题解总结。

[TOC]

哈希表

哈希表使用O(N)的空间复杂度存储数据，并且以O(1)的时间复杂度求解问题。

1. 两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return []
        Dict = {}
        for i in range(len(nums)):
            if target-nums[i] in Dict:
                return [Dict[target-nums[i]], i]
            else:
                Dict[nums[i]] = i

3. 无重复字符的最长子串

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

使用字典保存字符最后一次出现的位置，如果这个字符在前面出现过，即这个区间已经有重复的字符了，需要更新左边界，移动到当前遍历字符在字典中保存的位置的下一个位置，同时更新当前字符的位置（右边界）。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        res = 0
        left = 0
        Dict = {}
        for right in range(len(s)):
            if s[right] in Dict:
                left = max(left, Dict[s[right]]+1)
            Dict[s[right]] = right
            res = max(res, right-left+1)
        return res

18. 四数之和

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题思路

先对数组进行排序，使用字典保存每两个元素和的下标组成的元祖，例如[1,2,2,3]，Dict={3:[(0,1),(0,2)], 4:[(0,3),(1,2)], 5:[(2,3)]}，然后对数组进行两层遍历，判断target-nums[i]-nums[j]在不在字典中，如果在字典中，则找到了一组解。由于需要去重，使用set()类型的数据结构。

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return []
        
        nums.sort()
        Dict = {}
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] not in Dict:
                    Dict[nums[i]+nums[j]] = [(i, j)]
                else:
                    Dict[nums[i]+nums[j]].append((i, j))
        
        res = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)-2):
                residue = target-nums[i]-nums[j]
                if residue in Dict:
                    for pair in Dict[residue]:
                        if pair[0] > j:
                            res.add((nums[i], nums[j], nums[pair[0]], nums[pair[1]]))

        return list(res)

首先做排序，对前两个数遍历，后两个数在剩下的区间内寻找，找的方式使用两个指针指向首尾，判断四个数组成的和是否为target。注意需要在移动过程中去重。(超出时间限制)

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return []
        
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n-3):
            if (i > 0 and nums[i] == nums[i-1]) or nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target:
                continue
            if nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target:
                break
            for j in range(i+1, n-2):
                if (j > i+1 and nums[j] == nums[j-1]) or nums[i]+nums[j]+nums[n-2]+nums[n-1] < target:
                    continue
                if nums[i]+nums[j]+nums[j+1]+nums[j+2] > target:
                    break
                left, right = j+1, n-1
                while left < right:
                    temp = nums[i]+nums[j]+nums[left]+nums[right]
                    if temp == target:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        left += 1
                        right -= 1
                        while left < right:
                            if nums[left] == nums[left-1]:
                                left += 1
                        while left < right:
                            if nums[right] == nums[right+1]:
                                right -= 1
                    elif temp > target:
                        right -= 1
                    else:
                        left += 1
        return res

36. 有效的数独

题目描述

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

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

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 给定数独序列只包含数字 1-9 和字符 ‘.’ 。
• 给定数独永远是 9x9 形式的。

解题思路

遍历每一个不为’.’的位置，将其值保存下来，并将其所在位置暂时替换为无关字符，然后判断其所在行、列和9宫格内是否重复，如果重复则直接返回，否则将其位置重新赋原来的值。

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        if len(board) == 0:
            return False
        
        for x in range(len(board)):
            for y in range(len(board[0])):
                if board[x][y] == '.':
                    continue
                val = board[x][y]
                board[x][y] = 'D'
                if not self.isValid(x, y, board, val):
                    return False
                else:
                    board[x][y] = val
        
        return True
    
    def isValid(self, x, y, board, val):
        
        for i in range(len(board)):
            if board[i][y] == val:
                return False
        
        for i in range(len(board[0])):
            if board[x][i] == val:
                return False
        
        for i in range(3):
            for j in range(3):
                if board[(x//3)*3+i][(y//3)*3+j] == val:
                    return False
        
        return True

依次判断行、列和九宫格是否有重复的，使用set去重然后与没去重的比较长度。

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        if len(board) == 0:
            return False
        
        return self.isValidRow(board) and self.isValidCol(board) and self.isValidSpace(board)
    
    def isValidRow(self, board):
        for row in range(len(board)):
            temp = [board[row][col] for col in range(len(board[0])) if board[row][col] != '.']
            if len(set(temp)) != len(temp):
                return False
        return True
    
    def isValidCol(self, board):
        for col in range(len(board[0])):
            temp = [board[row][col] for row in range(len(board)) if board[row][col] != '.']
            if len(set(temp)) != len(temp):
                return False
        return True
    
    def isValidSpace(self, board):
        for i in range(0, len(board), 3):
            for j in range(0, len(board[0]), 3):
                temp = []
                for row in range(3):
                    for col in range(3):
                        if board[row+i][col+j] != '.':
                            temp.append(board[row+i][col+j])
                if len(set(temp)) != len(temp):
                    return False
        return True

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        
        for i in range(9):
            if not self.judge(board[i]):
                return False
        
        for i in range(9):
            temp = []
            for j in range(9):
                temp.append(board[j][i])
            if not self.judge(temp):
                return False
        
        for i in range(0,9,3):
            for j in range(0,9,3):
                temp = []
                for row in range(3):
                    for col in range(3):
                        temp.append(board[row+i][col+j])
                if not self.judge(temp):
                    return False
        
        return True
                
    
    def judge(self, nums):
        Dict = {}
        for x in nums:
            if x == '.':
                continue
            if x in Dict:
                return False
            Dict[x] = 1
        return True

37. 解数独

题目描述

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

解题思路

某个位置里放入的数字，必须不在其所在行，列及3x3宫内出现过，所以首先统计每行，列，宫内未出现的数字，则该位置只能填入该位置对应的行列宫都未出现的数字（即三者交集）。
然后遍历数独，当遍历到需要’.’时，将该位置可能填入的数字（行列宫交集）逐一尝试，该位置填入数字，并将行列宫中的数字删除，如果填入的数字可以继续填入数字则返回True，否则填错了，将该位置恢复成’.’，并将行列宫中的被删除的数字恢复。

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        
        nums = set([str(j) for j in range(1, 10)])
        rows = [set([str(j) for j in range(1, 10)]) for i in range(9)]
        cols = [set([str(j) for j in range(1, 10)]) for i in range(9)]
        spaces = [set([str(j) for j in range(1, 10)]) for i in range(9)]
        
        for i in range(9):
            for j in range(9):
                n = (i//3)*3 + j//3
                if board[i][j] != '.':
                    rows[i].remove(board[i][j])
                    cols[j].remove(board[i][j])
                    spaces[n].remove(board[i][j])
        self.dfs(board, rows, cols, spaces)
        
    def dfs(self, board, rows, cols, spaces):
        for i in range(9):
            for j in range(9):
                n = (i//3)*3 + j//3
                intersection = rows[i]&cols[j]&spaces[n]
                if board[i][j] == '.':
                    for item in intersection:
                        board[i][j] = item
                        rows[i].remove(item)
                        cols[j].remove(item)
                        spaces[n].remove(item)
                        if self.dfs(board, rows, cols, spaces):
                            return True
                        board[i][j] = '.'
                        rows[i].add(item)
                        cols[j].add(item)
                        spaces[n].add(item)
                    return False
        return True

49. 字母异位词分组

题目描述

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

示例:

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

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

解题思路

遍历字符串，对字符串进行排序，使用字典将同样的字符串放在一起。

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        if len(strs) == 0:
            return []
        
        Dict = {}
        for x in strs:
            temp = ''.join(sorted(x))
            if temp not in Dict:
                Dict[temp] = [x]
            else:
                Dict[temp].append(x)
        
#         res = []
#         for val in Dict.values():
#             res.append(val)
            
#         return res
    
        return list(Dict.values())

166. 分数到小数

题目描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:

输入: numerator = 1, denominator = 2
输出: "0.5"

示例 2:

输入: numerator = 2, denominator = 1
输出: "2"

示例 3:

输入: numerator = 2, denominator = 3
输出: "0.(6)"

解题思路

用字典保存余数及余数对应的结果的长度，当余数存在于字典中时，说明为循环小数，循环起始位字典中保存的位置。

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        res = ''
        if numerator * denominator < 0:
            res += '-'
        
        numerator, denominator = abs(numerator), abs(denominator)
        
        res += str(numerator // denominator)
        residue = numerator % denominator
        
        if residue == 0:
            return res
        
        res += '.'
        Dict = {}
        Dict[residue] = len(res)
        
        while residue:
            numerator = residue * 10
            res += str(numerator // denominator)
            residue = numerator % denominator
            if residue not in Dict:
                Dict[residue] = len(res)
            else:
                start = Dict[residue]
                res = res[:start] + '(' + res[start:] + ')'
                break
                
        return res

187. 重复的DNA序列

题目描述

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

编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出: ["AAAAACCCCC", "CCCCCAAAAA"]

解题思路

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        
        res = set()
        seen = set()
        for i in range(len(s)-9):
            if s[i:i+10] in seen:
                res.add(s[i:i+10])
            else:
                seen.add(s[i:i+10])
        
        return list(res)

205. 同构字符串

题目描述

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

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

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

示例 2:

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

示例 3:

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

说明:
你可以假设 s 和 t 具有相同的长度。

解题思路

遍历数组，用哈希表保存s和t中的对应关系，当s[i]不在哈希表的key中，如果t[i]在哈希表的value中，则返回False，如ab和aa的情况，否则将s[i]—t[i]保存到哈希表中，当s[i]在哈希表的key中，检查对应的值是否和t[i]相等，如果不相等，则返回False。遍历完成最后返回True。

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        
        if s == t:
            return True
        if len(s) != len(t):
            return False
        
        Dict = {}
        for i in range(len(s)):
            if s[i] not in Dict:
                if t[i] in Dict.values():
                    return False
                Dict[s[i]] = t[i]
            else:
                if Dict[s[i]] != t[i]:
                    return False
        
        return True

242. 有效的字母异位词

题目描述

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

示例 1:

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

示例 2:

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

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

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

解题思路

水

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        
        return sorted(s) == sorted(t)

词频统计

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        
        if len(s) != len(t):
            return False
        
        scnt = [0] * 26
        tcnt = [0] * 26
        
        for i in range(len(s)):
            scnt[ord(s[i]) - 97] += 1
            tcnt[ord(t[i]) - 97] += 1
        
        for i in range(26):
            if scnt[i] != tcnt[i]:
                return False
        
        return True

274. H指数

题目描述

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”

示例:

输入: citations = [3,0,6,1,5]
输出: 3 
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。

解题思路

好难理解。。。

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        
        if len(citations) == 0:
            return 0
        
        maxi = len(citations)
        for x in sorted(citations):#假设h为N 那么所有的论文引用次数都大于等于N，如果存在引用次数小于N,h-
            if x >= maxi:
                break
            else:
                maxi -= 1
        return maxi

290. 单词模式

题目描述

给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。

示例1:

输入: pattern = "abba", str = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", str = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"
输出: false

说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

解题思路

分别将pattern和str分割，如果长度不一致则返回False

使用hash表，遍历pattern，依次保存pattern和str的映射关系

• 如果某个pattern[i]不存在hash表中，需要首先判断对应的str[i]是否已经在hash表中，如果在说明该str[i]已经被其他pattern占用，返回False;
• 如果某个pattern[i]已经在hash中，那么只需要判断当前对应的str[i]是否和保存起来的str是否一致即可。

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        
        pattern = list(pattern)
        str = str.split()
        
        if len(pattern) != len(str):
            return False
        
        Dict = {}
        for i in range(len(pattern)):
            if pattern[i] not in Dict:
                if str[i] in Dict.values():
                    return False
                Dict[pattern[i]] = str[i]
            else:
                if str[i] != Dict[pattern[i]]:
                    return False
        
        return True

299. 猜数字游戏

题目描述

你正在和你的朋友玩 猜数字（Bulls and Cows）游戏：你写下一个数字让你的朋友猜。每次他猜测后，你给他一个提示，告诉他有多少位数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位数字猜对了但是位置不对（称为“Cows”, 奶牛）。你的朋友将会根据提示继续猜，直到猜出秘密数字。

请写出一个根据秘密数字和朋友的猜测数返回提示的函数，用 A 表示公牛，用 B 表示奶牛。

请注意秘密数字和朋友的猜测数都可能含有重复数字。

示例 1:

输入: secret = "1807", guess = "7810"

输出: "1A3B"

解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。

示例 2:

输入: secret = "1123", guess = "0111"

输出: "1A1B"

解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛。

说明: 你可以假设秘密数字和朋友的猜测数都只包含数字，并且它们的长度永远相等。

解题思路

用hash表保存secret中数字重现的次数；
定义两个变量，allmatch统计secret和guess中都出现的次数，另一个统计Bulls；
然后遍历guess，如果当前字符在hash中出现过，说明这个字符在secret和guess都出现过，allmatch+=1，同时判断位置在这secret和guess的位置是否相同，相同Bulls+=1;
最后Cows = allmatch - bulls。

class Solution(object):
    def getHint(self, secret, guess):
        """
        :type secret: str
        :type guess: str
        :rtype: str
        """
        
        if len(secret) != len(guess) or len(secret) == 0:
            return ""
        
        
        Dict = {}
        for c in secret:
            if c not in Dict:
                Dict[c] = 1
            else:
                Dict[c] += 1
        
        allmatch = 0
        Bulls = 0
        for i in range(len(guess)):
            if guess[i] in Dict and Dict[guess[i]] != 0:
                Dict[guess[i]] -= 1
                allmatch += 1
            if secret[i] == guess[i]:
                Bulls += 1
                
        Cows = allmatch - Bulls
        
        return str(Bulls) + 'A' + str(Cows) + 'B'

347. 前K个高频元素

题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

说明：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

解题思路

hash统计，values降序，取前k个

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        
        if len(nums)  < k or k <= 0:
            return []
        
        Dict = {}
        for x in nums:
            if x not in Dict:
                Dict[x] = 1
            else:
                Dict[x] += 1
                
        Dict = sorted(Dict.items(), key = lambda item:-item[1])

        return [Dict[i][0] for i in range(k)]

349. 两个数组的交集

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

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

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

  解题思路

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        
        
        if not nums1 or not nums2:
            return []
        
        res = []
        for x in nums2:
            if x in nums1 and x not in res:
                res.append(x)
        
        return res

350. 两个数组的交集 II

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

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

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

• 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
• 我们可以不考虑输出结果的顺序。

进阶:

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解题思路

先用hash表将nums1的数字和对应次数保存起来，
遍历nums2，查看当前遍历元素是否在Dict中存在，且次数大于0,
如果存在需要将Dict[x] -= 1

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        
        
        if not nums1 or not nums2:
            return []
        
        Dict = {}
        for x in nums1:
            if x not in Dict:
                Dict[x] = 1
            else:
                Dict[x] += 1
        
        res = []
        for x in nums2:
            if x in Dict and Dict[x] != 0:
                res.append(x)
                Dict[x] -= 1
        
        return res

380. 常数时间插入、删除和获取随机元素

题目描述

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

• insert(val)：当元素 val 不存在时，向集合中插入该项。
• remove(val)：元素 val 存在时，从集合中移除该项。
• getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

解题思路

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.keyIndex = {}#记录键、下标对
        self.indexKey = {}#记录下标、键对
        self.len = 0#记录长度，便于随机返回元素
        
    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        #插入时，分别对两个哈希表都进行插入，同时len+1
        if val not in self.keyIndex:
            self.len += 1
            self.keyIndex[val] = self.len
            self.indexKey[self.len] = val
            return True
        return False
        
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        #删除时将index_key中键为len的覆盖到键为key_index[val]，然后删除键为len的；key_index操作类似。最后len-1
        if val in self.keyIndex:
            self.indexKey[self.keyIndex[val]] = self.indexKey[self.len]
            self.keyIndex[self.indexKey[self.len]] = self.keyIndex[val]
            self.indexKey.pop(self.len)
            self.keyIndex.pop(val)
            self.len -= 1
            return True
        return False
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return self.indexKey[random.randint(1, self.len)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.set = []
        

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.set:
            self.set.append(val)
            return True
        else:
            return False
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.set:
            self.set.remove(val)
            return True
        else:
            return False
        
        
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        import random
        
        return self.set[random.randint(0, len(self.set)-1)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

389. 找不同

题目描述

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

输入：
s = "abcd"
t = "abcde"

输出：
e

解释：
'e' 是那个被添加的字母。

解题思路

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        
        
        if not t or len(s) >= len(t):
            return ''
        
        s = list(s)
        
        for c in t:
            if c not in s:
                return c
            else:
                s.remove(c)
                
        return ''