Python

算法（9）：哈希表

2019-03-18  本文已影响125人  大王叫我来巡老和山

这应该是最近最后一篇关于数据结构的内容了，写完之后我会开始把动态规划、回溯、贪婪等算法过一过，如果有时间，也会总结一下排序、查找等常用算法。

  哈希表就是使用哈希函数来组织数据的一种数据结构，支持快速的插入和查找功能（有的哈希表也提供删除功能，当然，删除功能也是快速的）。常见的哈希表两种结构：hash set 和 hash map（个人感觉就是python 里的 set 和 dict）。
  哈希表因为哈希函数设计的不同，会出现哈希碰撞，一般解决方法为拉链法和开放寻址法（也叫线性探测法）。
  我突然有点懒得写了，，，先贴几个链接，回头再整理。

哈希表（散列表）原理详解
浅谈算法和数据结构: 十一 哈希表

上题上题，不上题我心里痒痒。

问题1：快乐数字（Hapy Number）大家读到这里，扪心自问一下，今天你快乐吗？给一个正整数，我们把每一位拆开，然后求平方和，并一直重复该过程，直到最后等于1，或者陷入无限轮回循环......如果最终结果为1，那么它就是快乐数字，输出True，反之False。（该题用了 hash set）
输入: 19
输出: true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

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？

赞赞我把~

上一篇下一篇

猜你喜欢

热点阅读