3个月用python刷完leetcode600题!-hash table简单题(二)

综合编程 2017-06-18

十五天的时间,刷完了所有的简单题,避免遗忘,所以开始简单题的二刷,第一遍刷题的时候过得速度比较快,因为我觉得基础不好的我,不要硬着头皮去想最优的方法,而是应该尽量去学一些算法思想,所以每道题只给自己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 =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,加我要写好备注哟!:

我的微信

您可能感兴趣的

Python学习第一天 一、Python的介绍 Python可以应用于众多领域,如:数据分析、组件集成、网络服务、图像处理、数值计算和科学计算等众多领域。目前业内几乎所有大中型互联网企业都在使用Python,如:Youtube、Dropbox、BT、Quora(中国知乎)、豆瓣、知乎、Google、Yahoo!、Fac...
08_Python的控制判断循环语句2(break、continue)_Python编程之路... 上一节简单的讲了Python的判断语句,和循环语句,if , while ,for等 这一节我们来深入了解循环内的一些语句 Break Python中的break和其他语言都一样,可以跳出一个循环语句 通常来讲,有的循环语句是可以有else的,如果一个循环被break终止了...
python为mysql实现restful接口 编辑推荐: 本文来自于朱念洋 ,文中针对游戏服务层的案例详细介绍的,代码描述详细。 最近在做游戏服务分层的时候,一直想把mysql的访问独立成一个单独...
网络字体反爬之pyspider爬取起点中文小说... 感谢关注天善智能,走好数据之路↑↑↑ 欢迎关注天善智能,我们是专注于商业智能BI,人工智能AI,大数据分析与挖掘领域的垂直社区,学习,问答、求职一站式搞定! 对商业智能BI、大数据分析挖掘、机器学习,python,R等数据领域感兴趣的同学加微信:tstoutiao,邀请你进入数据爱好者交...
How to process weather satellite data in real-time... By Lak Lakshmanan, Technical Lead, Data and ML Professional Services Since the 1960s, scientists have been forecasting the weather using satellite-c...