题目: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)
题目:每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。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)
题目:求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)
题目:写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
思路:二进制异或进位。
# -*- 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)
题目:将一个字符串转换成一个整数(实现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)
题目:在一个长度为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)
# 题目
# 给定一个数组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)
题目:请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配。
思路:
当模式中的第二个字符不是
*
时:
当模式中的第二个字符是 *
时:
x*
被忽略。即模式串中*与他前面的字符和字符串匹配0次。*
可以匹配多位。即模式串中*与他前面的字符和字符串匹配多次。# -*- 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)
题目:请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+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)
题目:请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"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)
题目:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出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)
题目:在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表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)
题目:给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
思路:分析二叉树的下一个节点,一共有以下情况: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()
题目:请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
思路:采用递归的方法来判断两数是否相同。
# -*- 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)
题目:请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
思路: 把当前列结果存放到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)
题目:从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
# -*- 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)
题目:请实现两个函数,分别用来序列化和反序列化二叉树。
思路:转变成前序遍历,空元素利用"#"代替,然后进行解序列。
# -*- 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)
题目:给定一棵二叉搜索树,请找出其中的第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)
题目:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用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)
题目:给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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)
题目:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。例如 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)
题目:地上有一个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)