class Solution:
def Find(self, target, array):
rows = len(array)-1
cols = len(array[0]) - 1
i = rows
j = 0
while j<=cols and i>=0:
if target<array[i][j]:
i -= 1
elif target>array[i][j]:
j += 1
else:
return True
return False
2.替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
代码
class Solution:
# s 源字符串
def replaceSpace(self, s):
s_ = ''
for j in s:
if j == ' ':
s_ = s_ + '%20'
else:
s_ = s_ + j
return s_
3.从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：使用栈从头到尾push链表的元素，然后pop所有的元素到一个list中并返回。
代码
class Solution:
def printListFromTailToHead(self, listNode):
if not listNode:
return []
p = listNode
stack = []
res = []
while p:
stack.append(p.val)
p = p.next
for i in range(len(stack)-1,-1,-1):
res.append(stack[i])
return res
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
if not self.stack1:
return None
while self.stack1:
self.stack2.append(self.stack1.pop())
res = self.stack2.pop()
while self.stack2:
self.stack1.append(self.stack2.pop())
return res
class Solution:
def minNumberInRotateArray(self, rotateArray):
if not rotateArray:
return 0
for i in range(len(rotateArray)-1):
if rotateArray[i] > rotateArray[i+1]:
return rotateArray[i+1]
return rotateArray[0]
2.二分查找时间复杂度O(logn)
class Solution:
def minNumberInRotateArray(self, rotateArray):
if not rotateArray:
return 0
l = 0
r = len(rotateArray) - 1
while l < r:
mid = (l + r)/2
if rotateArray[mid] > rotateArray[r]:
l = mid+1
else:
r = mid
return rotateArray[l]
class Solution:
def jumpFloor(self, number):
if number < 0: return 0
if number == 1: return 1
if number == 2: return 2
result = [1, 2]
for i in range(2,number):
result.append(result[i-1] + result[i-2])
return result[-1]
class Solution:
def jumpFloorII(self, number):
if number <= 0: return 0
if number == 1: return 1
if number == 2: return 2
result = [1,2]
for i in range(2,number):
result.append(2*result[-1])
return result[-1]
class Solution:
def rectCover(self, number):
if number <= 0: return 0
if number == 1: return 1
if number == 2: return 2
result = [1,2]
for i in range(2,number):
result.append(result[-1]+result[-2])
return result[-1]
class Solution:
def FindKthToTail(self, head, k):
if not head or k <=0:
return None
p = q = head
t = 0
while p and t < k:
p = p.next
t = t+1
if t < k:
return None
while p != None:
p = p.next
q = q.next
return q
15.反转链表
class Solution(object):
def reverseList(self, head):
if not head:
return None
p = head
q = head.next
while q:
head.next = q.next
q.next = p
p = q
q = head.next
return p
16.合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
class Solution(object):
def mergeTwoLists(self, l1, l2):
cur = head =ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return head.next
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
if not pRoot1 or not pRoot2:
return False
result = False
if pRoot1.val == pRoot2.val:
result = self.isSubTree(pRoot1,pRoot2)
if not result:
result = self.HasSubtree(pRoot1.left,pRoot2)
if not result:
result = self.HasSubtree(pRoot1.right,pRoot2)
return result
def isSubTree(self,pRoot1,pRoot2):
if not pRoot2:
return True
if not pRoot1:
return False
if pRoot1.val != pRoot2.val:
return False
return self.isSubTree(pRoot1.left,pRoot2.left) and self.isSubTree(pRoot1.right,pRoot2.right)
class Solution(object):
def invertTree(self, root):
if not root:
return None
root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
return root
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
result = []
while(matrix):
result += matrix.pop(0)
if not matrix:
break
matrix = self.turn(matrix)
return result
def turn(self,matrix):
num_r = len(matrix)
num_c = len(matrix[0])
newmat = []
for i in range(num_c):
newmat2 = []
for j in range(num_r):
newmat2.append(matrix[j][i])
newmat.append(newmat2)
newmat.reverse()
return newmat
class Solution:
def IsPopOrder(self, pushV, popV):
stack = []
for i in pushV:
stack.append(i)
while stack and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
if not stack:
return True
else:
return False
22.从上到下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
#二叉树的层次遍历
class Solution:
def PrintFromTopToBottom(self, root):
if not root:
return []
stack = [root]
res = []
while stack:
temp = stack
stack = []
for node in temp:
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
self.res = []
if not root:
return []
self.subPath(root,[],expectNumber)
return self.res
def subPath(self, root, path,number):
if not root.left and not root.right:
if number == root.val:
self.res.append(path+[root.val])
if root.left:
self.subPath(root.left,path+[root.val],number-root.val)
if root.right:
self.subPath(root.right,path+[root.val],number-root.val)
class Solution:
def Permutation(self, ss):
if len(ss)==0 or len(ss)==1:
return ss
res = []
self.helper(ss, res, '')
return sorted(list(set(res)))
def helper(self, ss, res, path):
if not ss:
res.append(path)
else:
for i in range(len(ss)):
self.helper(ss[:i]+ss[i+1:],res,path+ss[i])
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
count = 0
numbers.sort()
res = numbers[len(numbers)/2]
for i in numbers:
if i == res:
count +=1
if count >len(numbers)/2:
return res
else:
return 0
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
res=numbers[0]
count = 0
for i in numbers:
if res == i:
count +=1
else:
count -=1
if count < 0:
res = i
count = 1
count2 = 0
for i in numbers:
if res == i:
count += 1
if count > len(numbers)/2:
return res
else: return 0
#堆排序
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if len(tinput) < k or k==0:
return []
self.buildHeap(tinput[:k],k)
for i in range(k,len(tinput)):
if tinput[i] > self.heap[0]:
continue
else:
self.heap[0] = tinput[i]
self.perceDown(0,k)
return sorted(self.heap)
def buildHeap(self,tinput,k):
self.heap = tinput
for i in range(k//2,-1,-1):
self.perceDown(i,k)
def perceDown(self,i,k):
temp = self.heap[i]
while (2 * i + 1) < k:
child = 2 * i + 1
if (child < k - 1) and self.heap[child] < self.heap[child+1]:
child = child + 1
if temp < self.heap[child]:
self.heap[i] = self.heap[child]
i = child
else:
break
self.heap[i] = temp
class Solution(object):
def maxSubArray(self, nums):
if max(nums) < 0:
return max(nums)
local_max, global_max = 0, 0
for i in nums:
local_max = max(0, local_max + i)
global_max = max(global_max, local_max)
return global_max
31.从1到n的整数中1出现的个数
比如，1-13中，1出现6次，分别是1，10，11，12，13。
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
count = 0
for i in range(1,n+1):
j = i
while j > 0:
if j%10 == 1:
count += 1
j = j/10
return count
class Solution:
def PrintMinNumber(self, numbers):
if not len(numbers):
return ""
arr = [str(x) for x in numbers]
arr.sort(lambda x,y:cmp(x+y,y+x))
return int("".join(arr))
class Solution:
def FirstNotRepeatingChar(self, s):
#建立哈希表,有256个字符，于是创建一个长度为256的列表
ls=[0]*256
#遍历字符串,下标为ASCII值,值为次数
for i in s:
ls[ord(i)]+=1 #ord()函数以一个字符作为参数，返回对应的ASCII数值
for j in s:
if ls[ord(j)]==1:
return s.index(j)
break
return -1
class Solution(object):
def getIntersectionNode(self, headA, headB):
p1 = headA
p2 = headB
while p1 != p2:
if p1 == None:
p1 = headB
else:
p1 = p1.next
if p2 == None:
p2 = headA
else:
p2 = p2.next
return p2
37.统计一个数字在排序数组中的出现的次数
思路：考虑数组为空的情况，直接返回0；用二分查找法，找到i和j的位置。
class Solution:
def GetNumberOfK(self, data, k):
if len(data) == 0:
return 0
i = 0
j = len(data) - 1
while i < j and data[i] != data[j]:
if data[i] < k:
i += 1
if data[j] > k:
j -= 1
if data[i] != k:
return 0
return j-i+1
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
res = 0
for i in array:
res ^= i
splitBit = 1
while splitBit & res == 0:
splitBit = splitBit << 1
res1 = 0
res2 = 0
for i in array:
if i & splitBit == 0:
res1 ^= i
else:
res2 ^= i
return [res1,res2]
class Solution:
def FindContinuousSequence(self, tsum):
res = []
i = 1
j = 2
curSum = i + j
while i <= tsum/2:
if curSum == tsum:
res.append(range(i,j+1))
j = j + 1
curSum += j
elif curSum > tsum:
curSum -= i
i += 1
else:
j += 1
curSum += j
return res
class Solution:
def LeftRotateString(self, s, n):
m = len(s)
res1 = s[n:m]
res2 = s[0:n]
res = res1+res2
return res
44.翻转单词顺序列
例如，“student. a am I”翻转为“I am a student.”。
思路：按空格切分为数组，依次入栈，再出栈(用空格连接)
class Solution:
def ReverseSentence(self, s):
if s is None or len(s) == 0:
return s
stack = []
for i in s.split(' '): #split()通过指定分隔符对字符串进行切片
stack.append(i)
res = ""
while len(stack) > 0:
res += stack.pop() + " "
res = res[:-1]
return res
class Solution:
def IsContinuous(self, numbers):
if not numbers:
return False
numbers.sort()
zeros = 0
while numbers[zeros]==0:
zeros = zeros + 1
for i in range(zeros,len(numbers)-1):
if numbers[i+1] == numbers[i] or (numbers[i+1] - numbers[i] - 1) > zeros:
return False
else:
zeros -= (numbers[i+1]-numbers[i]-1)
return True
class Solution:
def LastRemaining_Solution(self, n, m):
if not n and not m :
return -1
res = range(n)
i = 0
while len(res)>1:
i = (m+i-1)%len(res)
res.pop(i)
return res[0]
class Solution:
def StrToInt(self, str):
str = str.strip()
if not str:
return 0
number, flag = 0, 1
#符号位的判断是否有正负号
if str[0] == '-':
str = str[1:]
flag = -1
elif str[0] == '+':
str = str[1:]
#遍历除+，-以外的所有字符，如果遇到非数字，则直接返回0
for c in str:
if c >= '0' and c <= '9':
number = 10*number + int(c)
else:
return 0
number = flag * number
return number
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
for i in range(len(numbers)):
while numbers[i] != i:
m = numbers[i]
if numbers[m] == numbers[i]:
duplication[0] = m
return True
else:
numbers[i] = numbers[m]
numbers[m] = m
return False
class Solution:
def multiply(self, A):
C,D = [],[]
for i in range(len(A)):
if i == 0:
C.append(1)
else:
C.append(C[i-1]*A[i-1])
for i in range(len(A)):
if i == 0:
D.append(1)
else:
D.append(D[i-1]*A[len(A)-i])
D = D[::-1]
B = []
for i in range(len(A)):
B.append(C[i]*D[i])
return B
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
if s == pattern:
return True
if len(pattern)>1 and pattern[1] == '*':
if s and (s[0]==pattern[0] or pattern[0] == '.'):
return self.match(s,pattern[2:]) or self.match(s[1:],pattern)
else:
return self.match(s,pattern[2:])
elif s and pattern and (s[0] == pattern[0] or pattern[0]=='.'):
return self.match(s[1:],pattern[1:])
return False
class Solution:
# s字符串
def isNumeric(self, s):
hasE = False
hasDot = False
hasSign = False
for i in range(len(s)):
if s[i] == 'e' or s[i] == 'E':
if hasE or i == len(s) - 1:
return False
hasE = True
elif s[i] == '.':
if hasDot or hasE:
return False
hasDot = True
elif s[i] == '+' or s[i] == '-':
if hasSign and s[i - 1] != 'e' and s[i - 1] != 'E':
return False
if not hasSign:
if i != 0 and s[i - 1] != 'e' and s[i - 1] != 'E':
return False
hasSign = True
else:
if s[i] < '0' or s[i] > '9':
return False
return True
class Solution:
# 返回对应char
def __init__(self):
self.s=''
self.dict1={}
def FirstAppearingOnce(self):
for i in self.s:
if self.dict1[i]==1:
return i
return '#'
def Insert(self, char):
self.s=self.s+char
if char in self.dict1:
self.dict1[char]=self.dict1[char]+1
else:
self.dict1[char]=1
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
if pHead==None or pHead.next==None or pHead.next.next==None:
return None
low=pHead.next
fast=pHead.next.next
while low!=fast:
if fast.next==None or fast.next.next==None:
return None
low=low.next
fast=fast.next.next
fast=pHead
while low!=fast:
low=low.next
fast=fast.next
return fast
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
dummy = ListNode(-1)
dummy.next = head
pre = dummy
cur = head
while cur:
while cur.next and cur.val == cur.next.val:
cur = cur.next
if pre.next == cur:
pre = pre.next
else:
pre.next = cur.next
cur = cur.next
return dummy.next
class Solution:
def isSymmetrical(self, pRoot):
if pRoot is None:
return True
return self.isSymmetricTree(pRoot.left,pRoot.right)
def isSymmetricTree(self,left,right):
if left is None and right is None:
return True
if left is None or right is None or left.val != right.val:
return False
return self.isSymmetricTree(left.left,right.right) and self.isSymmetricTree(left.right,right.left)
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Print(self, pRoot):
queue = [pRoot]
res = []
if not pRoot:
return []
while queue:
templist = []
templen = len(queue)
for i in range(templen):
temp = queue.pop(0)
templist.append(temp.val)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
res.append(templist)
return res
class Solution:
def Print(self, pRoot):
queue = [pRoot]
res = []
flag = 1 #判断flag是否为负，如果为负表示偶数行，从右往左遍历
if not pRoot:
return []
while queue:
templist = []
templen = len(queue)
for i in range(templen):
temp = queue.pop(0)
templist.append(temp.val)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
if flag == -1:
templist = templist[::-1] #反转
res.append(templist)
flag *= -1
return res
class Solution:
def maxInWindows(self, num, size):
res = []
i = 0
while size > 0 and i + size - 1 < len(num):
res.append(max(num[i:i + size]))
i += 1
return res
思路2：双向队列，queue存入num的位置，时间复杂度O(n)
class Solution:
def maxInWindows(self, num, size):
queue = []
res = []
i = 0
while size>0 and i<len(num):
if len(queue)>0 and i-size+1 > queue[0]: #若最大值queue[0]位置过期 则弹出
queue.pop(0)
while len(queue)>0 and num[queue[-1]]<num[i]: #每次弹出所有比num[i]的数字
queue.pop()
queue.append(i)
if i>=size-1:
res.append(num[queue[0]])
i += 1
return res
64.矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如，在下面的3 X 4 矩阵中包含一条字符串"bfce"的路径，但是矩阵中不包含"abfb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
class Solution:
def dfs(self,matrix,flag,rows,cols,r,c,s):
if s=='':
return True
dx = [-1,1,0,0]
dy = [0,0,-1,1] # 利用两个数组，来实现对每个格子周围格子的访问
for k in range(4):
x = dx[k] + r
y = dy[k] + c
if x >= 0 and x < rows and y >= 0 and y < cols and flag[x][y] and matrix[x*cols+y]==s[0]:
flag[x][y]=False # 修改当前格子的标识
if self.dfs(matrix,flag[:],rows,cols, x, y,s[1:]): # 递归
return True
flag[x][y]=True
# 如果上一个判断条件返回的是False，那么就说明这个格子目前还不是路径上的格子，再把当前格子的标识修改回来。
return False
def hasPath(self, matrix, rows, cols, path):
if path == '':
return True
flag = [[True for c in range(cols)] for r in range(rows)] # 定义一个表示矩阵
for r in range(rows):
# 对这个矩阵中的元素进行遍历，不断找路径进入矩阵的起点，直到以某个格子为起点找到整个路径为止。
for c in range(cols):
if matrix[r*cols+c] == path[0]:
flag[r][c] = False
if self.dfs(matrix,flag[:],rows,cols, r, c,path[1:]):
return True
flag[r][c] = True
return False
class Solution:
def __init__(self): # 机器人可以倒回来，但不能重复计数。
self.count = 0
def movingCount(self, threshold, rows, cols):
flag = [[1 for i in range(cols)] for j in range(rows)]
self.findWay(flag,0,0,threshold) # 从（0，0）开始走
return self.count
def findWay(self,flag,i,j,k):
if i >= 0 and j >= 0 and i < len(flag) and j < len(flag[0]) and sum(list(map(int,str(i)))) + sum(list(map(int,str(j)))) <= k and flag[i][j] == 1:
flag[i][j] = 0
self.count += 1
self.findWay(flag,i-1,j,k)
self.findWay(flag,i+1,j,k)
self.findWay(flag,i,j-1,k)
self.findWay(flag,i,j+1,k)
