欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指Offer-机器人的运动范围(两种详细解法,python)

程序员文章站 2022-07-08 10:09:43
题目描述:地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?解题方法:这个题目可以有两种解法:(1)回溯法(2)规律法(自创的)我们首先来看回溯法~1.回溯法回溯法就是,我现在处于一个满足条件的格子,然后我...

题目描述:

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

解题方法:

这个题目可以有两种解法:(1)回溯法(2)规律法(自创的)
我们首先来看回溯法~
1.回溯法
回溯法就是,我现在处于一个满足条件的格子,然后我会判断我的上下左右四个方向的格子是否满足条件,如果有1个以上的格子满足条件,那么我们可以先选一个格子,(每到一个满足条件的格子,相应的count加一),让现在的格子位置进入下一个位置,然后重复判断。当某个格子四个方向都不满足条件,或者四个方向的格子都已经走完了,这时count就已经达到最大了。
看看完整代码:

class Solution:
    def Judge(self, threshold, i, j):
        #判断格子位数是否满足条件
        if sum(list(map(int, str(i)+str(j)))) <= threshold:
            return True
        else:
            return False
    def FindGrid(self, threshold, rows, cols, matrix, i,j):
        count = 0
        if i>=0 and j>=0 and i< rows and j<cols and self.Judge(threshold, i, j) and matrix[i][j]==0:
            matrix[i][j]=1
            count = 1+self.FindGrid(threshold, rows, cols, matrix, i, j+1)\
                     +self.FindGrid(threshold, rows, cols, matrix, i, j-1)\
                     +self.FindGrid(threshold, rows, cols, matrix, i+1, j)\
                     +self.FindGrid(threshold, rows, cols, matrix, i-1, j)
        return count
    def movingCount(self, threshold, rows, cols):
        matrix = [[0 for i in range(cols)] for j in range(rows)]
        count = self.FindGrid(threshold, rows, cols, matrix, 0, 0)
        return count

2.规律法(想法来源于小果)
(1)寻找条件满足与条件不满足的边界:
当threshold<=9时,边界t=threshold+1,那么边界t右上方的格子均不满足。
当threshold>9时,边界t = 10*(threshold-8)+9(<=threshold+1=x/10+9), 同样边界t上方的格子也均不满足条件,可以不遍历。
代码如下:

class Solution:
       def movingCount(self, threshold, rows, cols):
           if threshold<=9:
              t = threshold+1
           else:
              t = 10*(threshold-8)+9
           count = 0
           for i range(rows):
               for j in range(cols):
                   w = self.getSum(i)+self.getSum(j)
                   if w <= threshold and (i+j) < t :
                      count += 1
           return count
           
       def getSum(self,num):
           while num !=0:
                 return num
           return num%10+self.getSum(num/10)

两种方法均能通过测试,其中第一种方法运行时间22ms, 第二种方法运行时间17ms。另外可以看出,第一种方法的空间复杂度为O(mn),而第二种方法为O(1)。但是规律法并不常见,也不适用。虽然在时间和空间上复杂度均比较低,但是还是推荐回溯法,毕竟这才是容易想到的编程算法啊。

本文地址:https://blog.csdn.net/peppermint_xiao/article/details/107889766

相关标签: 刷题