3个月用python刷完leetcode600题!-hash table简单题（一）

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

1、Two Sum

同 http://www.jianshu.com/p/b71fc7307e42

136. Single Number

Single Number

"""
这道题虽然放在了hashtable里，但其实用二进制的算法更容易求解
两个相同数的二进制异或为0，所以遍历一边数组，出现两次的异或值变为0，那么剩下的数就是出现一次的数
"""

class Solution(object):

    def singleNumber(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        res = 0

        for i in nums:

            res = res ^ i

        return res

202. Happy Number

Happy Number

"""解法1，用列表保存出现过的数，当出现重复的数字的时候，说明出现了循环，循环有两种情况，一种不是hayyp数，循环的数必不是1，如果是happy数，那么会出现1的不断循环"""

class Solution(object):

    def isHappy(self, n):

        """

        :type n: int

        :rtype: bool

        """

        c = set()

        while not n in c:

            c.add(n)

            n = sum([int(x) ** 2 for x in str(n)])

        return n==1

"""解法2，使用追赶法，快的指针每次前进两步，慢的指针每次只前进一步，当快的指针追上慢的指针即二者数字相同时，同样说明出现了循环，情况同上"""

class Solution(object):

    def isHappy(self, n):

        """

        :type n: int

        :rtype: bool

        """

        slow = n

        quick = sum([int(x) ** 2 for x in str(n)])

        while quick != slow:

            quick = sum([int(x) ** 2 for x in str(quick)])

            quick = sum([int(x) ** 2 for x in str(quick)])

            slow = sum([int(x) ** 2 for x in str(slow)])

        return slow == 1

204. Count Primes

Count Primes

统计比n小的质数有多少，首先设置一个数组，全部质为true，然后遍历2-sqrt（n）的数，把他们的倍数所在的数组位置
置为True这里为了避免重复，从ii的位置开始，而不是从i2的位置开始，因为i2，i3，i*n-1其实已经置为false了.

class Solution(object):

    def countPrimes(self, n):

        """

        :type n: int

        :rtype: int

        """

        if n < 3:

            return 0

        res = [True] * n

        res[0] = res[1] = False

        for i in range(2,int(math.sqrt(n)) + 1):

            res[i*i:n:i] = [False] * len(res[i*i:n:i])

        return sum(res)

205. Isomorphic Strings

Isomorphic Strings

一开始我的解法是这样的，但是这是不对的，如下面的情况s='ab',t='aa' 就会出现错误

class Solution(object):

    def isIsomorphic(self, s, t):

        """

        :type s: str

        :type t: str

        :rtype: bool

        """

        if len(s) != len(t):

            return False

        dic = dict()

        for i in range(len(s)):

            if s[i] in dic and dic[s[i]] != t[i]:

                return False

            else:

                dic[s[i]] = t[i]

        return True

所以用两个dict分别对应保存两个字符串对应位置的对方字符，只要其中一个不满足条件，则返回错误

class Solution(object):

    def isIsomorphic(self, s, t):

        """

        :type s: str

        :type t: str

        :rtype: bool

        """

        if len(s) != len(t):

            return False

        dic1 = dict()

        dic2 = dict()

        for i in range(len(s)):

            if (s[i] in dic1 and dic1[s[i]] != t[i]) or (t[i] in dic2 and dic2[t[i]] != s[i]):

                return False

            else:

                dic1[s[i]] = t[i]

                dic2[t[i]] = s[i]

        return True

其实，还有更简单的解法,使用zip将两个数组对应位置元素相连，再利用set不能有重复元素的特性，判断三者的长度是否相同即可

class Solution(object):

    def isIsomorphic(self, s, t):

        """

        :type s: str

        :type t: str

        :rtype: bool

        """

        return len(set(zip(s,t))) == len(set(s)) == len(set(t))

217、Contains Duplicate

219、Contains Duplicate||

这两题参见http://www.jianshu.com/p/217cb8cc5d08

242. Valid Anagram

Valid Anagram

用两个字典保存字符出现的情况，判断两个字典是否相同即可

class Solution(object):

    def isAnagram(self, s, t):

        """

        :type s: str

        :type t: str

        :rtype: bool

        """

        dic1 = {}

        dic2 = {}

        for i in s:

            dic1[i] = dic1.get(i,0)+1

        for i in t:

            dic2[i] = dic2.get(i,0)+1

        return dic1 == dic2

290. Word Pattern

Word Pattern

将str 用split分开之后，解法类似于205题

class Solution(object):

    def wordPattern(self, pattern, str):

        """

        :type pattern: str

        :type str: str

        :rtype: bool

        """



        return len(pattern) == len(str.split(' ')) and len(set(zip(pattern, str.split(' ')))) == len(

            set(pattern)) == len(set(str.split(' ')))

349. Intersection of Two Arrays

Intersection of Two Arrays

可以使用hash table保存下数组1的出现的元素，然后判断数组2中的各元素是否在数组1中出现过，但直接使用set更简单

class Solution(object):

    def intersection(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: List[int]

        """



        nums1 = set(nums1)

        return [x for x in set(nums2) if x in nums1]

350. Intersection of Two Arrays II

Intersection of Two Arrays II

使用两个字典记录下两个数组中元素出现的次数

class Solution(object):

    def intersect(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: List[int]

        """

        dic1,dic2 = dict(),dict()

        for num in nums1:

            dic1[num] = dic1.get(num,0) + 1

        for num in nums2:

            dic2[num] = dic2.get(num,0) + 1

        return [x for x in dic2 for j in range(min(dic1.get(x,0),dic2.get(x,0)))]

但是python内置了Counter类型数组，可以方便实现计数功能

import collections



class Solution(object):

    def intersect(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: List[int]

        """

        c1,c2 = collections.Counter(nums1),collections.Counter(nums2)

        return [i for i in c1.keys() for j in range(min([c1[i], c2[i]]))]

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

我的微信