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