Python 字符 字符串 哈希

Trie树：

LRU缓存淘汰算法：

# 字符串：

## Trie树：

``````class Trie(object):
def __init__(self):
"""
"""
self.root = {}
self.end = '/'
def insert(self, word): #插入
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node[self.end] = None
def search(self, word):#查找
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.root
for c in word:
if c not in node:
return False
node = node[c]
if self.end in node:
return True
else:
return False
def startsWith(self, prefix):#前缀
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.root
for c in prefix:
if c not in node:
return False
node = node[c]
return Tru``````

## 朴素的字符串匹配算法：

``````#朴素匹配
def matchStr(strs,substrs):
i = 0
j = 0
if not substrs:
return True
if not strs:
return False
while i<len(strs) and j<len(substrs):
print 'str: ',strs[i]
print 'substr: ',substrs[j]
if strs[i]==substrs[j]:
i += 1
j += 1
else:
i = i-j+1
j = 0
if j >= len(substrs):
return True
return False
#测试
a = "asdefvgty"
b = "vgt"
print matchStr(a,b)``````

## 相关练习：

``````class Solution(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
l = len(s)
if l<=1:
return
for i in range(l/2):
s[i],s[l-1-i] = s[l-1-i],s[i]``````

``````class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
s_list = s.split(' ')
ret_list = [i for i in s_list if i != '']
ret_list = ret_list[::-1]
return ' '.join(ret_list)``````

``````class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
s = str.strip()
ret =''
if len(s)<1:
return 0
if s[0]=='-' or s[0]=='+':#负号
if len(s)<=1 or not s[1].isdigit():
return 0
else:
ret += s[0]
for i in range(1,len(s)):
if s[i].isdigit():
ret += s[i]
else:
break
elif not s[0].isdigit():#字母
return 0
else:#数字
for i in range(0,len(s)):
if s[i].isdigit():
ret += s[i]
else:
break
num = int(ret)
if num>2**31-1:
return 2**31-1
elif num<-2**31:
return -2**31
else:
return num``````

# 哈希表：

## LRU缓存淘汰算法：

``````from collections import OrderedDict
class LRU():
def __init__(self,capacity = 10):
self.maxcount = capacity
self.queue = OrderedDict()
def get(self,key):
if key not in self.queue:
return -1
else:
value = self.queue.pop(key)
self.queue[key] = value
return value
def put(self,key,data):
if key in self.queue:
self.queue.pop(key)
self.queue[key] = data
else:
if len(self.queue.items()) == self.maxcount:
self.queue.popitem(last = False)
self.queue[key] = data
else:
self.queue[key] = data``````

## 相关练习：

``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
mydict = {}
for i in range(len(nums)):
if target-nums[i] in mydict:
return [mydict[target-nums[i]],i]
else:
mydict[nums[i]] = i``````

``````class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
history = []
while n>=10:
print 'n-:',n
sumnow = 0
m = 0
while n>=10:
m = n%10
n = n/10
sumnow += m*m
sumnow += n*n
n = sumnow
print 'n+:',n
return n == 1 or n == 7``````

https://blog.csdn.net/m0_38019841/article/details/88356378