45.撲克牌順序
題目：LL今天心情特别好,因為他去買了一副撲克牌,發現裡面居然有2個大王,2個小王(一副牌原本是54張^_^)...他随機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現在,要求你使用這幅牌模拟上面的過程,然後告訴我們LL的運氣如何， 如果牌能組成順子就輸出true，否則就輸出false。為了友善起見,你可以認為大小王是0。
# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if numbers==[]:
return False
numbers.sort()
zero=0
for i in range(0,len(numbers)):
if numbers[i]==0:
zero=zero+1
for i in range(zero+1,len(numbers)):
if numbers[i]==numbers[i-1]:
return False
if numbers[i]-numbers[i-1]==1:
continue
else:
diff=numbers[i]-numbers[i-1]-1
zero=zero-diff
if zero<0:
return False
return True
if __name__=='__main__':
numbers=[1,0,0,1,0]
solution=Solution()
ans=solution.IsContinuous(numbers)
print(ans) 複制
46.孩子們的圈圈(圈圈中最後剩下的數)
題目：每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小遊戲。其中,有個遊戲是這樣的:首先,讓小朋友們圍成一個大圈。然後,他随機指定一個數m,讓編号為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然後可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0...m-1報數....這樣下去....直到剩下最後一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)。請你試着想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編号是從0到n-1)。
思路：約瑟夫環問題。
# 題目
# 每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小遊戲。
# 其中,有個遊戲是這樣的:首先,讓小朋友們圍成一個大圈。然後,他随機指定一個數m,讓編号為0的小朋友開始報數。
# 每次喊到m-1的那個小朋友要出列唱首歌,然後可以在禮品箱中任意的挑選禮物,并且不再回到圈中,
# 從他的下一個小朋友開始,繼續0...m-1報數....這樣下去....直到剩下最後一個小朋友,可以不用表演,
# 并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)。請你試着想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編号是從0到n-1)
# 思路
# 約瑟夫環問題
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n<1 or m<1:
return -1
last=0
for i in range(2,n+1):
last=(last+m)%i
return last
if __name__=='__main__':
n,m=8,4
solution=Solution()
ans=solution.LastRemaining_Solution(n,m)
print(ans) 複制
47.求1+2+3+...+n
題目：求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷語句（A?B:C）。
思路：利用遞歸當作計算結果。
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here
if n==0:
return 0
return self.Sum_Solution(n-1)+n
if __name__=='__main__':
n=6
solution=Solution()
ans=solution.Sum_Solution(n)
print(ans) 複制
48.不用加減乘除做加法
題目：寫一個函數，求兩個整數之和，要求在函數體内不得使用+、-、*、/四則運算符号。
思路：二進制異或進位。
# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
while num2!=0:
sum=num1^num2
carry=(num1&num2)<<1
num1=sum
num2=carry
return num1
if __name__=='__main__':
num1,num2=10,500000
solution=Solution()
ans=solution.Add(num1,num2)
print(ans) 複制
49.把字元串轉換成整數
題目：将一個字元串轉換成一個整數(實作Integer.valueOf(string)的功能，但是string不符合數字要求時傳回0)，要求不能使用字元串轉換整數的庫函數。 數值為0或者字元串不是一個合法的數值則傳回0。
輸入描述：輸入一個字元串,包括數字字母符号,可以為空輸出描述:如果是合法的數值表達則傳回該數字，否則傳回0。
示例
+2147483647
1a33
2147483647
0 複制
# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
# write code here
if len(s) == 0:
return 0
else:
if s[0] > '9' or s[0] < '0':
a = 0
else:
a = int(s[0]) * 10 ** (len(s) - 1)
if len(s) > 1:
for i in range(1, len(s)):
if s[i] >= '0' and s[i] <= '9':
a = a + int(s[i]) * 10 ** (len(s) - 1 - i)
else:
return 0
if s[0] == '+':
return a
if s[0] == '-':
return -a
return a
if __name__=='__main__':
s='115'
solution=Solution()
ans=solution.StrToInt(s)
print(ans) 複制
50.數組中重複的數字
題目：在一個長度為n的數組裡的所有數字都在0到n-1的範圍内。 數組中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出數組中任意一個重複的數字。例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那麼對應的輸出是第一個重複的數字2。
思路：利用dict計算重複數字。
# -*- coding:utf-8 -*-
class Solution:
# 這裡要特别注意~找到任意重複的一個值并指派到duplication[0]
# 函數傳回True/False
def duplicate(self, numbers, duplication):
# write code here
numset=set(numbers)
dict={}
duplication.append(0)
for val in numbers:
dict[val]=0
for i in range(0,len(numbers)):
dict[numbers[i]]=dict[numbers[i]]+1
for val in numset:
if dict[val]>1:
duplication[0]=val
return True
return False
if __name__=='__main__':
numbers=[2,1,3,1,4]
solution=Solution()
duplication=[]
ans=solution.duplicate(numbers,duplication)
print(ans) 複制
51.建構乘積數組
# 題目
# 給定一個數組A[0,1,...,n-1],請建構一個數組B[0,1,...,n-1],
# 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
# 思路
# 審題仔細 沒有A[i]
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
B=[]
for i in range(0,len(A)):
temp=1
for j in range(0,len(A)):
if j==i:
continue
temp=temp*A[j]
B.append(temp)
return B
if __name__=='__main__':
solution=Solution()
A=[1,2,3,4,5]
ans=solution.multiply(A)
print(ans) 複制
52.正規表達式比對
題目：請實作一個函數用來比對包括'.'和'*'的正規表達式。模式中的字元'.'表示任意一個字元，而'*'表示它前面的字元可以出現任意次（包含0次）。在本題中，比對是指字元串的所有字元比對整個模式。例如，字元串"aaa"與模式"a.a"和"ab*ac*a"比對，但是與"aa.a"和"ab*a"均不比對。
思路：
當模式中的第二個字元不是 *
- 如果字元串第一個字元和模式中的第一個字元相比對，那麼字元串和模式都後移一個字元，然後比對剩餘的。
- 如果字元串第一個字元和模式中的第一個字元相不比對，直接傳回false。
當模式中的第二個字元是
*
時：
- 如果字元串第一個字元跟模式第一個字元不比對，則模式後移2個字元，繼續比對。
- 如果字元串第一個字元跟模式第一個字元比對，可以有3種比對方式。
- 模式後移2字元，相當于
x*
- 字元串後移1字元，模式後移2字元。即模式串中*與他前面的字元和字元串比對1次。
- 字元串後移1字元，模式不變，即繼續比對字元下一位，因為
*
# -*- coding:utf-8 -*-
class Solution:
# s, pattern都是字元串
def match(self, s, pattern):
if s == pattern:
return True
if not pattern:
return False
if len(pattern) > 1 and pattern[1] == '*':
if (s and s[0] == pattern[0]) or (s and pattern[0] == '.'):
return self.match(s, pattern[2:]) \
or self.match(s[1:], pattern) \
or self.match(s[1:], pattern[2:])
else:
return self.match(s, pattern[2:])
elif s and (s[0] == pattern[0] or pattern[0] == '.'):
return self.match(s[1:], pattern[1:])
return False
if __name__=='__main__':
solution=Solution()
s='aaa'
pattern='a*a.a'
ans=solution.match(s,pattern)
print(ans) 複制
53.表示數值的字元串
題目：請實作一個函數用來判斷字元串是否表示數值（包括整數和小數）。例如，字元串"+100","5e2","-123","3.1416"和"-1E-16"都表示數值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
# -*- coding:utf-8 -*-
class Solution:
# s字元串
def isNumeric(self, s):
# write code here
# 标記符号、小數點、e是否出現過
sign,decimal,hasE=False,False,False
for i in range(0,len(s)):
if s[i]=='e' or s[i]=='E':
if i==len(s)-1:# e後面一定要接數字
return False
if hasE==True:# 不能出現兩次e
return False
hasE=True
elif s[i]=='+' or s[i]=='-':
#第二次出現+或-一定要在e之後
if sign and s[i-1]!='e' and s[i-1]!='E':
return False
# 第一次出現+或-，如果不是出現在字元最前面，那麼就要出現在e或者E後面
if sign==False and i>0 and s[i-1]!='e' and s[i-1]!='E':
return False
sign=True
elif s[i]=='.':
# e後面不能出現小數點，小數點不能出現兩次
if decimal or hasE:
return False
decimal=True
elif s[i]>'9' or s[i]<'0':
return False
return True
if __name__=='__main__':
solution=Solution()
s='123e.1416'
ans=solution.isNumeric(s)
print(ans) 複制
54.字元流中第一個不重複的字元
題目：請實作一個函數用來找出字元流中第一個隻出現一次的字元。例如，當從字元流中隻讀出前兩個字元"go"時，第一個隻出現一次的字元是"g"。當從該字元流中讀出前六個字元“google"時，第一個隻出現一次的字元是"l"。
輸出描述：如果目前字元流沒有存在出現一次的字元，傳回#字元。
# -*- coding:utf-8 -*-
class Solution:
# 傳回對應char
def __init__(self):
self.all={}
self.ch=[]
def FirstAppearingOnce(self):
# write code here
if self.all is None:
return '#'
for c in self.ch:
if self.all[c]==1:
return c
return '#'
def Insert(self, char):
# write code here
self.ch.append(char)
if char in self.all:
self.all[char]=self.all[char]+1
else:
self.all[char]=1
if __name__=='__main__':
solution=Solution()
solution.Insert('g')
ans = solution.FirstAppearingOnce()
print(ans)
solution.Insert('o')
ans = solution.FirstAppearingOnce()
print(ans)
solution.Insert('o')
ans = solution.FirstAppearingOnce()
print(ans)
solution.Insert('g')
ans = solution.FirstAppearingOnce()
print(ans)
solution.Insert('l')
ans = solution.FirstAppearingOnce()
print(ans)
solution.Insert('e')
ans = solution.FirstAppearingOnce()
print(ans) 複制
55.連結清單中環的入口節點
題目：給一個連結清單，若其中包含環，請找出該連結清單的環的入口結點，否則，輸出null。
思路：把連結清單中節點值放到dict數組中，并記錄出現的次數，如果出現次數超過一次，則為環的入口節點。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if pHead is None:
return None
num,dict,flag=[],{},True
tempans=0
while pHead and flag==True:
num.append(pHead.val)
numset=set(num)
for c in numset:
dict[c]=0
for c in num:
dict[c]=dict[c]+1
for c in num:
if dict[c]>1:
flag=False
tempans=c
pHead=pHead.next
while pHead:
if pHead.val==tempans:
return pHead
pHead=pHead.next
return None
if __name__=='__main__':
pHead1 = ListNode(1)
pHead2 = ListNode(2)
pHead3 = ListNode(3)
pHead4 = ListNode(4)
pHead5 = ListNode(5)
pHead1.next=pHead2
pHead2.next=pHead3
pHead3.next=pHead4
pHead4.next=pHead5
pHead5.next=pHead1
solution=Solution()
ans=solution.EntryNodeOfLoop(pHead1)
print(ans.val) 複制
56.删除連結清單中重複的節點
題目：在一個排序的連結清單中，存在重複的結點，請删除該連結清單中重複的結點，重複的結點不保留，傳回連結清單頭指針。 例如，連結清單1->2->3->3->4->4->5 處理後為 1->2->5。
思路：記錄連結清單中出現的數字，然後建構新連結清單。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
num=[]
tempnum1=pHead
while tempnum1:
num.append(tempnum1.val)
tempnum1=tempnum1.next
dict={}
for c in num:
dict[c]=0
for c in num:
dict[c]=dict[c]+1
newnum=[]
for c in num:
if dict[c]==1:
newnum.append(c)
if newnum==[]:
return None
head=ListNode(newnum[0])
temphead=head
for i in range(1,len(newnum)):
tempnode=ListNode(newnum[i])
temphead.next=tempnode
temphead=tempnode
# while head:
# print(head.val)
# head=head.next
return head
if __name__=='__main__':
pHead1 = ListNode(1)
pHead2 = ListNode(1)
pHead3 = ListNode(1)
pHead4 = ListNode(1)
pHead5 = ListNode(1)
pHead6 = ListNode(1)
pHead7 = ListNode(1)
pHead1.next=pHead2
pHead2.next=pHead3
pHead3.next=pHead4
pHead4.next=pHead5
pHead5.next=pHead6
pHead6.next=pHead7
solution=Solution()
ans=solution.deleteDuplication(pHead1)
print(ans) 複制
57. 二叉樹中的下一個節點
題目：給定一個二叉樹和其中的一個結點，請找出中序周遊順序的下一個結點并且傳回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。
思路：分析二叉樹的下一個節點，一共有以下情況：1.二叉樹為空，則傳回空；2.節點右孩子存在，則設定一個指針從該節點的右孩子出發，一直沿着指向左子結點的指針找到的葉子節點即為下一個節點；3.節點不是根節點。如果該節點是其父節點的左孩子，則傳回父節點；否則繼續向上周遊其父節點的父節點，重複之前的判斷，傳回結果。
# -*- coding:utf-8 -*-
class TreeLinkNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
class Solution:
def GetNext(self, pNode):
# write code here
if not pNode:
return pNode
if pNode.right:
left1=pNode.right
while left1.left:
left1=left1.left
return left1
while pNode.next:
tmp=pNode.next
if tmp.left==pNode:
return tmp
pNode=tmp
if __name__=='__main__':
solution=Solution() 複制
58.對稱的二叉樹
題目：請實作一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。
思路：采用遞歸的方法來判斷兩數是否相同。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSymmetrical(self, pRoot):
# write code here
if not pRoot:
return True
result=self.same(pRoot,pRoot)
return result
def same(self,root1,root2):
if not root1 and not root2:
return True
if root1 and not root2:
return False
if not root1 and root2:
return False
if root1.val!= root2.val:
return False
left=self.same(root1.left,root2.right)
if not left:
return False
right=self.same(root1.right,root2.left)
if not right:
return False
return True
if __name__=='__main__':
A1 = TreeNode(1)
A2 = TreeNode(2)
A3 = TreeNode(2)
A4 = TreeNode(3)
A5 = TreeNode(4)
A6 = TreeNode(4)
A7 = TreeNode(3)
A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A3.left=A6
A3.right=A7
solution = Solution()
ans=solution.isSymmetrical(A1)
print(ans) 複制
59.按之字形順序列印二叉樹
題目：請實作一個函數按照之字形列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右至左的順序列印，第三行按照從左到右的順序列印，其他行以此類推。
思路： 把目前列結果存放到list之中，設定翻轉變量，依次從左到右列印和從右到左列印。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def Print(self, pRoot):
# write code here
root=pRoot
if not root:
return []
level=[root]
result=[]
righttoleft=False
while level:
curvalues=[]
nextlevel=[]
for i in level:
curvalues.append(i.val)
if i.left:
nextlevel.append(i.left)
if i.right:
nextlevel.append(i.right)
if righttoleft:
curvalues.reverse()
if curvalues:
result.append(curvalues)
level = nextlevel
righttoleft = not righttoleft
return result
if __name__=='__main__':
A1 = TreeNode(1)
A2 = TreeNode(2)
A3 = TreeNode(3)
A4 = TreeNode(4)
A5 = TreeNode(5)
A6 = TreeNode(6)
A7 = TreeNode(7)
A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A3.left=A6
A3.right=A7
solution = Solution()
ans=solution.Print(A1)
print(ans) 複制
60.把二叉樹列印成多行
題目：從上到下按層列印二叉樹，同一層結點從左至右輸出。每一層輸出一行。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 傳回二維清單[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
root=pRoot
if not root:
return []
level=[root]
result=[]
while level:
curvalues=[]
nextlevel=[]
for i in level:
curvalues.append(i.val)
if i.left:
nextlevel.append(i.left)
if i.right:
nextlevel.append(i.right)
if curvalues:
result.append(curvalues)
level = nextlevel
return result
if __name__=='__main__':
A1 = TreeNode(1)
A2 = TreeNode(2)
A3 = TreeNode(3)
A4 = TreeNode(4)
A5 = TreeNode(5)
A6 = TreeNode(6)
A7 = TreeNode(7)
A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A3.left=A6
A3.right=A7
solution = Solution()
ans=solution.Print(A1)
print(ans) 複制
61.序列化二叉樹
題目：請實作兩個函數，分别用來序列化和反序列化二叉樹。
思路：轉變成前序周遊，空元素利用"#"代替，然後進行解序列。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
import collections
class Solution:
def Serialize(self, root):
# write code here
if not root:
return None
res=[]
self.pre(root,res)
return res
def pre(self,root,res):
if not root:
return
res.append(root.val)
if root.left:
self.pre(root.left, res)
else:
res.append('#')
if root.right:
self.pre(root.right,res)
else:
res.append('#')
def Deserialize(self, s):
if s=='':
return None
vals=[]
for i in range(0,len(s)):
vals.append(s[i])
vals=collections.deque(vals)
ans=self.build(vals)
return ans
def build(self,vals):
if vals:
val = vals.popleft()
if val == '#':
return None
root = TreeNode(int(val))
root.left = self.build(vals)
root.right = self.build(vals)
return root
return self.build(vals)
# [1, ',', 2, ',', 4, ',', ',', ',', 5, ',', ',', ',', 3, ',', 6, ',', ',', ',', 7, ',', ',']
if __name__=="__main__":
A1 = TreeNode(1)
A2 = TreeNode(2)
A3 = TreeNode(3)
A4 = TreeNode(4)
A5 = TreeNode(5)
A6 = TreeNode(6)
A7 = TreeNode(7)
A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A3.left=A6
A3.right=A7
solution = Solution()
ans=solution.Serialize(A1)
print(ans)
root=solution.Deserialize(ans)
res=solution.Serialize(root)
print(res) 複制
62.二叉搜尋樹中的第K個節點
題目：給定一棵二叉搜尋樹，請找出其中的第k小的結點。例如（5，3，7，2，4，6，8）中，按結點數值大小順序第三小結點的值為4。
思路：中序周遊後，傳回第K個節點值。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 傳回對應節點TreeNode
def KthNode(self, pRoot, k):
# write code here
res=[]
if not pRoot:
return None
self.order(pRoot,res)
if len(res)<k or k<=0:
return None
else:
return res[k-1]
def order(self,root,res):
if not root:
return
self.order(root.left,res)
res.append(root)
self.order(root.right,res)
if __name__=='__main__':
A1 = TreeNode(5)
A2 = TreeNode(3)
A3 = TreeNode(7)
A4 = TreeNode(2)
A5 = TreeNode(4)
A6 = TreeNode(6)
A7 = TreeNode(8)
A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A3.left=A6
A3.right=A7
k=3
solution = Solution()
ans=solution.KthNode(A1,k)
print(ans) 複制
63.資料流中的中位數
題目：如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從資料流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使用Insert()方法讀取資料流，使用GetMedian()方法擷取目前讀取資料的中位數。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.data=[]
def Insert(self, num):
# write code here
self.data.append(num)
self.data.sort()
def GetMedian(self):
# write code here
length=len(self.data)
if length%2==0:
return (self.data[length//2]+self.data[length//2-1])/2.0
else:
return self.data[int(length//2)]
if __name__=="__main__":
solution=Solution()
solution.Insert(5)
ans = solution.GetMedian()
print(ans)
solution.Insert(2)
ans = solution.GetMedian()
print(ans)
solution.Insert(3)
ans = solution.GetMedian()
print(ans)
solution.Insert(4)
ans = solution.GetMedian()
print(ans)
solution.Insert(1)
ans = solution.GetMedian()
print(ans) 複制
64.滑動視窗的最大值
題目：給定一個數組和滑動視窗的大小，找出所有滑動視窗裡數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動視窗的大小3，那麼一共存在6個滑動視窗，他們的最大值分别為{4,4,6,6,6,5}； 針對數組{2,3,4,2,6,2,5,1}的滑動視窗有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}，{2,3,4,2,6,[2,5,1]}。
# -*- coding:utf-8 -*-
class Solution:
def maxInWindows(self, num, size):
# write code here
if size==0 or num==[]:
return []
res=[]
for i in range(0,len(num)-size+1):
tempnum=[]
for j in range(i,i+size):
tempnum.append(num[j])
res.append(max(tempnum))
return res
if __name__=="__main__":
solution=Solution()
num=[2,3,4,2,6,2,5,1]
size=3
ans=solution.maxInWindows(num,size)
print(ans) 複制
65.矩陣中的路徑
題目：請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字元串所有字元的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則之後不能再次進入這個格子。例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字元串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字元串的第一個字元b占據了矩陣中的第一行第二個格子之後，路徑不能再次進入該格子。
思路：當起點第一個字元相同時，開始進行遞歸搜尋，設計搜尋函數。
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
for i in range(0,rows):
for j in range(0,cols):
if matrix[i*rows+j]==path[0]:
if self.find_path(list(matrix),rows,cols,path[1:],i,j):
return True
return False
def find_path(self,matrix,rows,cols,path,i,j):
if not path:
return True
matrix[i*cols+j]=0
if j+1<cols and matrix[i*cols+j+1]==path[0]:
return self.find_path(matrix,rows,cols,path[1:],i,j+1)
elif j-1>=0 and matrix[i*cols+j-1]==path[0]:
return self.find_path(matrix, rows, cols, path[1:], i, j - 1)
elif i+1<rows and matrix[(i+1)*cols+j]==path[0]:
return self.find_path(matrix, rows, cols, path[1:], i+1, j)
elif i-1>=0 and matrix[(i-1)*cols+j]==path[0]:
return self.find_path(matrix, rows, cols, path[1:], i-1, j)
else:
return False
if __name__=='__main__':
solution=Solution()
matrix='ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS'
rows=5
cols=8
path='SGGFIECVAASABCEHJIGQEMS'
ans=solution.hasPath(matrix,rows,cols,path)
print(ans) 複制
66.機器人的運動範圍
題目：地上有一個m行和n列的方格。一個機器人從坐标0,0的格子開始移動，每一次隻能向左，右，上，下四個方向移動一格，但是不能進入行坐标和列坐标的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？
思路：對未走過的路徑進行周遊，搜尋所有的路徑值。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.vis = {}
def movingCount(self, threshold, rows, cols):
# write code here
return self.moving(threshold, rows, cols, 0, 0)
def moving(self, threshold, rows, cols, row, col):
rowans,colans=0,0
rowtemp,coltemp=row,col
while rowtemp>0:
rowans=rowans+rowtemp%10
rowtemp=rowtemp//10
while coltemp>0:
colans=colans+coltemp%10
coltemp=coltemp//10
if rowans+colans>threshold:
return 0
if row >= rows or col >= cols or row < 0 or col < 0:
return 0
if (row, col) in self.vis:
return 0
self.vis[(row, col)] = 1
return 1 + self.moving(threshold, rows, cols, row - 1, col) +\
self.moving(threshold, rows, cols, row + 1,col) + \
self.moving(threshold, rows,cols, row,col - 1) + \
self.moving(threshold, rows, cols, row, col + 1)
if __name__=='__main__':
solution=Solution()
threshold=10
rows,cols=1,100
ans=solution.movingCount(threshold,rows,cols)
print(ans) 複制