这应该是最近最后一篇关于数据结构的内容了，写完之后我会开始把动态规划、回溯、贪婪等算法过一过，如果有时间，也会总结一下排序、查找等常用算法。
- 目录：
算法：附录
算法（1）：递归
算法（2）：链表
算法（3）：数组
算法（4）：字符串
算法（5）：二叉树
算法（6）：二叉查找树
算法（7）：队列和堆栈（附赠BFS和DFS）
算法（8）：动态规划
算法（9）：哈希表
算法（10）：排序
算法（11）：回溯法
哈希表就是使用哈希函数来组织数据的一种数据结构，支持快速的插入和查找功能（有的哈希表也提供删除功能，当然，删除功能也是快速的）。常见的哈希表两种结构：hash set 和 hash map（个人感觉就是python 里的 set 和 dict）。
哈希表因为哈希函数设计的不同，会出现哈希碰撞，一般解决方法为拉链法和开放寻址法（也叫线性探测法）。
我突然有点懒得写了，，，先贴几个链接，回头再整理。
上题上题，不上题我心里痒痒。
问题1：快乐数字（Hapy Number）大家读到这里，扪心自问一下，今天你快乐吗？给一个正整数，我们把每一位拆开，然后求平方和，并一直重复该过程，直到最后等于1，或者陷入无限轮回循环......如果最终结果为1，那么它就是快乐数字，输出True，反之False。（该题用了 hash set）
输入: 19
输出: true
解释:
class Solution:
def isHappy(self, n: int) -> bool:
visited = set()
while n not in visited:
if n == 1:
return True
num = [int(x) for x in str(n)]
visited.add(n)
n = sum([x**2 for x in num])
return False
if __name__ == '__main__':
solution = Solution()
ans = solution.isHappy(2)
print(ans)
ans = solution.isHappy(19)
print(ans)
问题2：两数之和，给一个数组和一个目标值，找到数组当中两个数，使其加起来等于目标值，返回这两个数的索引。（该题用了 hash map）
例子：
输入： nums = [2, 7, 11, 15]，target = 9
输出：[0, 1]
解释：nums[0] + nums[1] = 2 + 7 = 9
class Solution:
def twoSum(self, nums: list, target: int) -> list:
hashmap = {}
for idx, num in enumerate(nums):
if target - num in hashmap:
return [hashmap[target - num], idx]
hashmap[num] = idx
return False
if __name__ == '__main__':
nums = [2, 7, 11, 15]
target = 9
solution = Solution()
ans = solution.twoSum(nums,target)
print(ans)
问题3：列表最小索引和（Minimum Index Sum of Two Lists）。小红和小明去吃饭，两个人都有最喜欢餐厅列表。需要我们从中找出他们共同喜欢并且索引和最小的饭店（假设一定存在），如果有多个，则输出全部。（该题用了 hash map）
例子：
输入：
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["KFC", "Shogun", "Burger King"]
输出：["Shogun"]（虽然KFC也满足要求，但其索引和为3，大于和为1的Shogun）
class Solution:
def findRestaurant(self, list1: list, list2: list) -> list:
hashmap = {name: idx for idx, name in enumerate(list1)}
best, ans = 1e5, []
for idx, name in enumerate(list2):
i = hashmap.get(name, 1e5)
if i + idx < best:
best = i + idx
ans = [name]
elif i + idx == best:
ans.append(name)
return ans
if __name__ == '__main__':
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
solution = Solution()
ans = solution.findRestaurant(list1,list2)
print(ans)
问题4：字符串中第一个唯一字符（First Unique Character in a String）。找到字符串当中第一个有且只有一个的字符，并返回其索引，如果不存在，返回-1。（用了hash set 和 hash map，打出了一套漂亮的组合拳）
例子：
输入：’loveleetcode‘
输出：2 （’v‘在字符串当中有且只有一个，并且其索引最小）
class Solution:
def firstUniqChar(self, s: str) -> int:
hashmap = {}
seen = set()
for idx, c in enumerate(s):
if c not in seen:
seen.add(c)
hashmap[c] = idx
elif c in hashmap:
hashmap.pop(c)
return min(hashmap.values()) if hashmap else -1
if __name__ == '__main__':
s='loveleetcode'
solution = Solution()
ans = solution.firstUniqChar(s)
print(ans)
问题5：我擦这个题目名字我真不会翻译（Group Anagrams），给定一个存放字符串的数组，将具有相同字母的字符串（字母以及每个字母个数相同，但不要求位置相同）放入同一个列表当中，并返回。（这个用到了hash map，有一点需要注意，那就是需要自己构造出来一个合适的key，而不是直接用字符串，或者索引等）
例子：
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[["ate","eat","tea"],
["nat","tan"],
["bat"]]
class Solution:
def groupAnagrams(self, strs: list) -> list:
hashmap = {}
for i in strs:
li = "".join(sorted(i))
hashmap[li] = hashmap.get(li, []) + [i]
return list(hashmap.values())
if __name__ == '__main__':
s=["eat", "tea", "tan", "ate", "nat", "bat"]
solution = Solution()
ans = solution.groupAnagrams(s)
print(ans)
附录：
如何设计hash map 的 key？
-
当字符串/数组中每个元素的顺序无关紧要时，可以使用排序的字符串/数组作为键。
1.png
-
如果你只关心每个值的偏移量（通常是第一个值的偏移量），则可以使用偏移量作为键。
2.png
-
在树中，你可能希望有时直接使用TreeNode作为键。 但在大多数情况下，子树的序列化（变成string）可能是一个更好的主意。（见算法：附录 第四题）
3.png
-
在矩阵中，更常用行索引或列索引作为键。
-
在Sudoku中，可以组合行索引和列索引来标识此元素所属的块。（见算法：附录 第三题）（在python3 中
i/3需要改成i//3）
4.png
-
有时，在矩阵中，可能希望聚合同一对角线中的值来作为键。
5.png
赞赞我把~
网友评论