3个月用python刷完leetcode600题!-hash t

十五天的时间，刷完了所有的简单题，避免遗忘，所以开始简单题的二刷，第一遍刷题的时候过得速度比较快，因为我觉得基础不好的我，不要硬着头皮去想最优的方法，而是应该尽量去学一些算法思想，所以每道题只给自己5-10分钟的时间想，想不出来的就去找相关的答案，所以刷的比较快。二刷的时候按照leetcode官方给出的题目分类展开，同时，将解题思路记录于简书加深印象。
想要一起刷题的小伙伴，我们一起加油吧！
我的github连接：https://github.com/princewen/leetcode_python

389. Find the Difference

Find the Difference

利用hashtable，我们先将s中字母出现的次数进行保存，随后，遍历t中的字母，此时有两种情况找到添加的字母：第一种情况是新添加的字母没有在s中出现，直接返回这个字母；第二种情况是这个字母在s中出现了，但比s中出现多一次。

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        dic = dict()
        for single in s:
            dic[single] = dic.get(single, 0) + 1
        for single in t:
            if single in dic:
                dic[single] = dic[single] - 1
                if dic[single] == 0:
                    del dic[single]
            else:
                return single

利用之前的数组题，找出只出现一次的元素的思路，将两个字符串拼接，必然有一个字母单独出现了一次，我们可以用
异或将其找出

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        return chr(reduce(operator.xor, map(ord, (s + t))))

409. Longest Palindrome

Longest Palindrome

利用hashtable将每个字母出现的次数记录下来，最长的回文数可以由三部分组成：1、出现次数为偶数的，总长度增加其出现次数。2、出现次数为奇数，但是大于1次的，此时总长度增加其出现次数-1次。3、只要有出现次数为奇数的元素，总长度再加1。
python中collecitons的Counter数据结构其实就是遍历数组形成一个hashtable并对各元素出现次数进行计数，使用非常方便。

import collections
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        t = collections.Counter(s)
        return sum([t[x] for x in t if t[x] %2==0]) + sum([t[x]-1 for x in t if t[x] > 1 and t[x]%2==1])+max([1 for x in t if t[x]%2==1] or [0])

438. Find All Anagrams in a String

Find All Anagrams in a String

使用一个hashtable 记录下p个元素的应该出现次数，然后用两个指针去遍历字符串。在此过程中，不能将在p中没有出现过的元素加入hashtable中。

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res = []
        left = right = 0
        count = len(p)
        dic = dict()
        for i in p:
            dic[i] = dic.get(i,0)+1
        while right < len(s):
            if s[right] in dic.keys():
                if dic[s[right]]>=1:
                    count = count - 1
                dic[s[right]] = dic[s[right]]-1
            right = right+1
            if count == 0 :
                res.append(left)
            if right - left == len(p):
                if s[left] in dic.keys():
                    if dic[s[left]]>=0:
                        count = count + 1
                    dic[s[left]]+=1
                left = left+1
        return res

447. Number of Boomerangs

Number of Boomerangs

O(n^2)的时间复杂度，循环套循环，每次循环一个元素，计算其他元素到该元素的距离，并用hashtable保存，最后进行汇总。

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        res = 0
        for p in points:
            cmap = {}
            for q in points:
                dis = (p[0]-q[0]) ** 2 + (p[1]-q[1])**2
                cmap[dis] = cmap.get(dis,0)+1
            for key in cmap:
                res += (cmap[key]) * (cmap[key]-1)
        return res

463. Island Perimeter

Island Perimeter
统计岸边的个数，很容易看出岸边数是元素为1的个数4，减去相邻两个数都为1的邻居个数2，那么我们在统计邻居的时候，为了避免重复，循环每一个元素时只统计其上方和左方元素是否为1.

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        num = 0
        neighbor = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    num = num + 1
                    if i > 0 and grid[i-1][j] == 1:
                        neighbor += 1
                    if j>0 and grid[i][j-1] == 1:
                        neighbor += 1
        return num * 4 - neighbor *2

575. Distribute Candies

Distribute Candies

因为是平均分配，所以姐姐获得的不同糖果的个数最多为n／2,如果种类超过n/2,那么姐姐可以获得n/2种，否则可以获得的是种类的最大值。

class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        return len(set(candies)) if len(set(candies)) < len(candies)/2 else len(candies)/2

594. Longest Harmonious Subsequence

Longest Harmonious Subsequence

使用一个字典计录元素出现的次数，随后遍历字典，找到两个差距为1的元素，这两个元素出现的次数都大于0而且相加出现的次数最大.

import collections
class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = dict(collections.Counter(nums))
        max = 0
        for i in dic:
            if dic.get(i,0) > 0 and dic.get(i+1,0) > 0 and dic.get(i,0)+dic.get(i+1,0) > max:
                max = dic.get(i,0) + dic.get(i+1,0)
        return max

599. Minimum Index Sum of Two Lists

Minimum Index Sum of Two Lists

使用hashtable，这里需要注意的一点就是可以出现多个餐馆.

class Solution(object):
    def findRestaurant(self, list1, list2):
        """
        :type list1: List[str]
        :type list2: List[str]
        :rtype: List[str]
        """
        dic1 = {v:i for i,v in enumerate(list1)}
        best,ans = 1e9,[]
        for i,v in enumerate(list2):
            if v in dic1:
                if i+dic1[v] < best:
                    best = i+dic1[v]
                    ans = [v]
                elif i+dic1[v] == best:
                    ans.append(v)
        return ans

如果你喜欢我写的文章，可以帮忙给小编点个赞或者加个关注，我一定会互粉的！
如果大家对leetcode感兴趣，欢迎跟小编进行交流，小编微信为sxw2251，加我要写好备注哟！：

我的微信