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

2017-06-18

### 389. Find the Difference

Find the Difference

```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

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

```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

```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

```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

```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

```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```

## 您可能感兴趣的

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的访问独立成一个单独...

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...