【leetcode】集合和映射 Set&Map

发表于 更新于
集合和映射的练习题（简单）

1、leetcode1：两数之和

给定一个整数数组 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
def twoSum(nums, target):
    hashmap = {}
    for index, num in enumerate(nums):
        another_num = target - num
        if another_num in hashmap:
            return [hashmap[another_num], index]
        hashmap[num] = index
    return None

print(twoSum([2, 7, 11, 15], 9))

2、leetcode136：只出现一次的数字

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
def singleNumber(nums):
    dic = {}
    for i in nums:
        if i in dic:
            dic[i] +=1
        else:
            dic[i] = 1
        if dic[i] == 2:
            del dic[i]
    return [k for k in dic][0]

print(singleNumber([2,2,1]))

拓展：不使用额外空间（利用异或）
这里用到了异或（xor），相同的数字异或后为0，0异或任何数都等于那个数，用reduce在列表所有元素之间使用异或^，那么留下的就是那个单独的数字了。时间复杂度O(1)

1
2
3
4
5
6
7
def singleNumber(nums):
    a = 0
    for num in nums:
        a = a ^ num
    return a

print(singleNumber([2,2,1]))

3、leetcode349：两个数组的交集

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def intersection1(nums1, nums2):
    # 使用哈希映射
    dic = {}
    for i in nums1:
        if not dic.get(i):
            dic[i]=1
    new = []
    for i in nums2:
        if dic.get(i):
            new.append(i)
            dic[i] -= 1
    return new

def intersection2(nums1, nums2):
    # set函数求交集
    return list(set(nums1) & set(nums2))

print(intersection1([2,2,1], [2,1]))
print(intersection2([2,2,1], [2,1]))

4、leetcode202：快乐数

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

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

1
2
3
4
5
6
7
8
9
10
11
12
def isHappy(n):
    n = str(n)
    visited = set()
    while 1:
        n = str(sum(int(i) ** 2 for i in n))
        if n == "1":
            return True
        if n in visited:
            return False
        visited.add(n)

print(isHappy(19))

5、leetcode500：键盘行

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。

示例：
输入: [“Hello”, “Alaska”, “Dad”, “Peace”]
输出: [“Alaska”, “Dad”]

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
def findWords1(words):
    l1 = 'qwertyuiopQWERTYUIOP'
    l2 = 'asdfghjklASDFGHJKL'
    l3 = 'zxcvbnmZXCVBNM'
    l1,l2,l3 = set(l1),set(l2),set(l3)
    final = []
    for i in range(len(words)):
        s = set(words[i])
        if s&l1 == s or s&l2==s or s&l3==s:
            final.append(words[i])
    return final

def findWords2(words):
    set1 = set('qwertyuiop')
    set2 = set('asdfghjkl')
    set3 = set('zxcvbnm')
    res = []
    for i in words:
        x = i.lower()
        setx = set(x)
        if setx<=set1 or setx<=set2 or setx<=set3:
            res.append(i)
    return res

print(findWords1(["Hello", "Alaska", "Dad", "Peace"]))
print(findWords2(["Hello", "Alaska", "Dad", "Peace"]))

6、leetcode217：存在重复元素

给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

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

示例 2:
输入: [1,2,3,4]
输出: false

示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

1
2
3
4
5
6
7
8
9
10
11
12
13
def containsDuplicate1(nums):
    t = {}
    for i in nums:
        if i in t:
            return True
        t[i] = 1
    return False

def containsDuplicate2(nums):
    return len(nums) != len(set(nums))

print(containsDuplicate1([1,1,1,3,3,4,3,2,4,2]))
print(containsDuplicate2([1,1,1,3,3,4,3,2,4,2]))

7、leetcode219：存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

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

示例 2:
输入: nums = [1,0,1,1], k = 1
输出: 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
25
26
27
28
29
def containsNearbyDuplicate1(nums, k):
    # 题目中差值最大为k, 意思是只要小于等于k则为True, 而不是所有差值的最大值小于等于k
    # 将相同值的索引存储起来
    import collections
    d = collections.defaultdict(list)
    for i, v in enumerate(nums):
        d[v].append(i)
    
    # 对索引值进行差值的判断, 小于等于k, 则返回True
    for v in d.values():
        for i in range(len(v) - 1):
            if v[i + 1] - v[i] <= k:
                return True
    
    return False

def containsNearbyDuplicate2(nums, k):
    lookup = {}
    # 没有重复元素, 肯定返回False
    if len(set(nums)) == len(nums): return False
    # 只要有一个重复元素 相差的索引号 <=k 返回True
    for idx, num in enumerate(nums):
        if num in lookup and abs(idx - lookup[num]) <= k:
            return True
        lookup[num] = idx
    return False

print(containsNearbyDuplicate1([1,2,3,1], 3))
print(containsNearbyDuplicate2([1,0,1,1], 1))

8、leetcode389：找不同

给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。

示例：
输入：
s = “abcd”
t = “abcde”
输出：
e

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
def findTheDifference1(s, t):
    res = {}
    for i in s:
        if res.get(i):
            res[i] += 1  # 记录s中的字符出现次数
        else:
            res[i] = 1
    for i in t:
        if res.get(i):   # 消除字典中存在的字符
            res[i] -= 1
        else:
            return i     # 字典中没有相同字符，则返回该字符

def findTheDifference2(s, t):
    # 字符与ASCII码值转换
    a = 0
    b = 0
    for i in s:
        a += ord(i)
    for i in t:
        b += ord(i)
    return chr(b-a)

print(findTheDifference1("abcd","abcde"))
print(findTheDifference2("abcd","abcde"))

9、leetcode594：最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:
输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findLHS(nums):
    hashmap = {}
    for item in nums:
        if item not in hashmap:
            hashmap[item] = 1
        else:
            hashmap[item] += 1
    res = 0
    for item in hashmap:
        if item+1 in hashmap:
            up = hashmap[item+1] 
            res = max(res,up+hashmap[item])
    return res

print(findLHS([1,3,2,2,5,2,3,7]))

10、leetcode575：分糖果

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。
你需要把这些糖果平均分给一个弟弟和一个妹妹，使得妹妹可以获得的糖果的种类数最大。

示例 1:
输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。最优分配方案是妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 :
输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

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
def distributeCandies1(candies):
    # 将糖果种类的数字值作为 key 存储在字典中，糖果一旦存在则进行标记，并将糖果种类加一
    length = len(candies)
    each = length // 2
    type_dict = dict()
    type_cnt = 0
    
    for c in candies:
        if type_dict.get(c, 0) == 0:
            type_dict[c] = 1
            type_cnt += 1
    
    if type_cnt >= each:
        return each
    else:
        return type_cnt

def distributeCandies2(candies):
    # 利用集合无重复元素的特性，将数据存入集合，从而求出糖果的种类。
    each = len(candies) // 2
    candies_set = set(candies)
    return each if each <= len(candies_set) else len(candies_set)

print(distributeCandies1([1,1,2,2,3,3]))
print(distributeCandies2([1,1,2,2,3,3]))

11、leetcode205：同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:
输入: s = “egg”, t = “add”
输出: true

示例 2:
输入: s = “foo”, t = “bar”
输出: false

示例 3:
输入: s = “paper”, t = “title”
输出: true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def isIsomorphic(s, t):
    if len(s) != len(t):  # 如果两个字符串的长度不一致，则不同构
        return False
    # 用字典来记录每个字母最后出现的位置，判断s和t中每个字母最后出现的位置是否相同，不相同则不同构
    last_a ,last_b= {},{}
    for i in range(len(s)):
        if s[i] not in last_a:
            last_a[s[i]] = i
        if t[i] not in last_b:
            last_b[t[i]] = i
        if last_a[s[i]] != last_b[t[i]]:
            return False
        last_a[s[i]] = i
        last_b[t[i]] = i
    return True

print(isIsomorphic("paper", "title"))

12、leetcode242：有效的字母异位词

给定两个字符串 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
def isAnagram1(s, t):
    dict_1, dict_2 = {}, {}
    for item in s:
        dict_1[item] = dict_1.get(item, 0) + 1
    for item in t:
        dict_2[item] = dict_2.get(item, 0) + 1
    return dict_1 == dict_2

def isAnagram2(s, t):
    from collections import Counter
    return Counter(s)==Counter(t)

print(isAnagram1("rat", "tar"))
print(isAnagram2("rat", "tar"))