剑指刷题7

发表于 | 分类于 ，

面试题13: 机器人的运动范围

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

解题思路：回溯体现在迭代中，所以算法肯定是一个迭代的算法，然后，因为统计的是能够达到的格子数量，所以可以为每个格子做一个标记（二维数组），标记为0时表示这个已经是能够达到的格子。，用类属性count统计可达到的格子数量。

代码：

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def __init__(self):
        self.count = 0
    def movingCount(self, threshold, rows, cols):
        # write code here
        arr = [[1 for i in range(cols)] for j in range(rows)]
        self.findway(arr, 0, 0, threshold)
        return self.count
    def findway(self, arr, i, j, k):
        if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]):
            return
        tmpi = list(map(int, list(str(i))))
        tmpj = list(map(int, list(str(j))))
        if sum(tmpi) + sum(tmpj) > k or arr[i][j] != 1:
            return
        arr[i][j] = 0
        self.count += 1
        self.findway(arr, i + 1, j, k)
        self.findway(arr, i - 1, j, k)
        self.findway(arr, i, j + 1, k)
        self.findway(arr, i, j - 1, k)

代码思路：arr和count写在迭代外面，是global的值。list(map(int, list(str(i))))这个的意思是，先将字符串转换成str的list，然后用一个map将这些str转成int，然后在生成list。每个findway里面有四个迭代函数，表示向上下左右进行搜索。

面试题14:剪绳子

题目：给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

解题思路：这题可以用贪婪算法来求解。原因如下：

算法：

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def cutRope(self, number):
        # write code here
        if number<2:
            return 0
        if number == 2:
            return 1
        if number ==3:
            return 2
        timesOf3 = number//3
        if number - timesOf3*3 == 1:
            timesOf3 -= 1
        timesOf2 = (number - timesOf3*3)//2
        return pow(3,timesOf3)*pow(2,timesOf2)

算法思路：就是先写出最简单的情况，然后尽量使得3的数量最多，当最后一段可以为4时，就让它为4，而不是3和1。最后就是n个3和m个2。

请作者喝杯咖啡吧！