【数据结构】集合和映射 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"))
0%