Catalog
Simple string matching algorithm ：
LRU Cache elimination algorithm ：
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
self.end = '/'
def insert(self, word): # Insert
"""
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):# lookup
"""
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):# 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# Simple matching
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
# test
a = "asdefvgty"
b = "vgt"
print matchStr(a,b)【 Reverse string 】
Write a function , Its function is to invert the input string . Input string as character array char[] Given in the form of .
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]【 Flip the words in the string 】
Given a string , Flip each word in the string one by one .
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)【 String conversion integers (atoi)】
First , This function discards the useless start space characters as needed , Until the first non space character is found .
When the first non empty character we find is a positive or negative sign , Then combine the symbol with as many consecutive numbers as possible on the back face , As the sign of the integer ; If the first non empty character is a number , Then combine it directly with the following consecutive numeric characters , Form an integer .
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]=='+':# Minus sign
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():# Letter
return 0
else:# Numbers
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
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 Given an array of integers nums And a target value target, Please find and as the target value in the array Two Integers , And return their array subscripts
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【 Happy number 】
Write an algorithm to determine whether a number is “ Happy number ”.
One “ Happy number ” Defined as ： For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions , Then repeat the process until the number becomes 1, It can also be an infinite loop but never change 1. If it can be 1, So this number is the happy number .
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