机器人的运动范围

面试题13. 机器人的运动范围 - 力扣（Leetcode）

题目要求

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

例子：

1
2
输入：m = 2, n = 3, k = 1
输出：3

提示：

  • 1 <= n,m <= 100
  • 0 <= k <= 20

思路分析

深度优先：时间O(n*m)

思路

使用深度优先进行搜索，所有大于k的格子认定为障碍物，不能进入；机器人上下左右进行搜索，直到找到所有的格子，为了防止走重复的格子，每当走过一个格子就对它进行标记。

优化

官方题解-机器人的运动范围 - 力扣（Leetcode）

观察官方给的图解中障碍物分布规律，发现我们只需要向左和向下查找，就能找到所有符合条件的格子。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    // 定义全局变量
    int m,n,k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        // 初始化
        this.m = m;
        this.n = n;
        this.k = k;
        visited = new boolean[m][n];
        // 调用dfs
        return dfs(0,0);
    }
    int dfs(int i,int j){
        // 判断是否在格子内||是否被访问过||是否是障碍物
        if(i<0 || j<0 || i>=m || j>=n ||visited[i][j]||k<sum(i)+sum(j)){
            return 0;
        }
        // 标记被访问过
        visited[i][j] = true;
        // 像四个方向访问 下->右->上->左
        // return 1+dfs(i+1,j)+dfs(i,j+1)+dfs(i-1,j)+dfs(i,j-1);
        // 根据官方图解优化，去掉向上和向左两个方向
        return 1+dfs(i+1,j)+dfs(i,j+1);
    }
    // 求数位和方法
    int sum(int x){
        int res = 0;
        while(x!=0){
            res = res + x % 10;
            x = x / 10;
        }
        return res;
    }
}

剪绳子

剑指 Offer 14- I. 剪绳子 - 力扣（Leetcode）

题目要求

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

例子：

1
2
3
4
5
6
7
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
    
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

  • 2 <= n <= 58

思路分析

  1. 不等式公式：(x1+x22)2({x_1+x_2 \over 2})^2>=x12+x22x_1^2+x_2^2；让改不等式无限接近相等，它们的乘积最大；
  2. 当我们在切绳子时：
    • 当x<=4时，我们不切绳子；
    • 当x>=5时，公式：(x2)2>x({x\over2})^2>x恒成立，我们切绳子的所计算的乘积比不切大；
    • 如果切的结果中同时存在2和4，那么我们尽可能把它们合并为3；因为2*4<3*3;
    • 如果只存在单个2或者4，就不需要合并为3这一步骤；
  3. 由上可得，我们再切绳子的结果中，尽可多切出3，并且不要让2和4同时存在；(多个2也不是不可以的，例如：2，2，2 合并后为：2，4 不符合我们上方的要求；多个4也同理)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int cuttingRope(int n) {
        // 排除特殊情况
        if(n<=2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        // 定义切割数和余数
        int res = n / 3;
        int mod = n % 3;
        // 判断结果
        if(mod==0){
            // 用3正好分割完，直接返回res^3
            return pow(3,res);
        }else if(mod==1){
            // 把1合并到res中
            return pow(3,res-1) * 4;
        }else{
            // 余数为2，直接相乘
            return pow(3,res) * 2;
        }
    }
    // 计算a的n次方
    int pow(int a,int n){
        int sum = 1;
        for(int i=1;i<=n;i++){
            sum = sum * a;
        }
        return sum;
    }
}

剪绳子Ⅱ

剑指 Offer 14- II. 剪绳子 II - 力扣（Leetcode）

题目要求

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

例子：

1
2
3
4
5
6
7
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

  • 2 <= n <= 1000

思路分析

该题和上一题基本一直，唯一不同点是n的范围较大，结果也会很大，需要我们进行取余；

取余知识补充：

  1. (x1+x2)(x_1+x_2)%p = (x1x_1%p+x2x_2%p)%p
  2. (x1∗x2)(x_1*x_2)%p = (x1x_1%p$ * x_2%p)%p (x_1x_2$<p)

分析：

ana^n%p (aa<p)：

  • resnres_n = ana^n%p = [(an−1a^{n-1}%p)∗*(aa%p)]%p = [(an−1a^{n-1}%p)∗*aa]%p
  • resn−1res_{n-1} = an−1a^{n-1}%p = (resn−2∗ares_{n-2}*a)%p
  • res1res_1 = (1∗*aa)%p

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    int p;
    public int cuttingRope(int n) {
         // 排除特殊情况
        if(n<=2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        // 初始化p
        this.p = 1000000007;
        // 定义切割数和余数
        int res = n / 3;
        int mod = n % 3;
        // 判断结果
        if(mod==0){
            // 用3正好分割完，直接返回res^3
            return (int)pow(3,res);
        }else if(mod==1){
            // 把1合并到res中
            return (int)(pow(3,res-1) * 4 % p);
        }else{
            // 余数为2，直接相乘
            return (int)(pow(3,res) * 2 % p);
        }
    }
    // a^n %p
    long pow(int a,int n){
        long res = 1;
        for(int i= 1;i<=n;i++){
            res = (res * a) % p;
        }
        return res;
    }
}

二进制中1的个数

剑指 Offer 15. 二进制中1的个数 - 力扣（Leetcode）

题目要求

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数

例子：

1
2
3
4
5
6
7
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
    
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

  • 输入必须是长度为 32 的 二进制串 。

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

  • 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的例子中，输入表示有符号整数 -3。

思路分析

解法

方法一：不断除以2，直到结果为0，就可以统计出1的个数；

方法二：位运算公式：n = n & (n-1)，没与一次就能消除掉最右边的一个1，直到n为0就能统计出1的各个数；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
        while(n!=0){
            // 公式：n = n & (n-1)
            n = n & (n-1);
            sum++; // 统计1的个数
        }
        return sum;
    }
}

数值的整数次方

剑指 Offer 16. 数值的整数次方 - 力扣（Leetcode）

题目要求

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xnx^n）。不得使用库函数，同时不需要考虑大数问题。

例子：

1
2
3
4
5
6
7
8
9
输入：x = 2.00000, n = 10
输出：1024.00000
    
输入：x = 2.10000, n = 3
输出：9.26100
    
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • -104 <= xn <= 104

思路分析

快速幂思想

例如求 x8x^8：

  • x∗x=x2x*x=x^2
  • x2∗x2=x4x^2*x^2=x^4
  • x4∗x4=x8x^4*x^4=x^8

又或者：x13x^{13}=x1∗x4∗x8x^1*x^4*x^8

我是使用位运算演示：

例如13的二进制：1101

计算公式：

前提：long y = n double res = 1;

n < 0

y=−yy = -y

将x颠倒：x=1xx ={1 \over x}

y > 0

  • yy%2 == 1(表示n是奇数) -> res=res∗xres = res*x;

  • x=x∗xx = x*x

  • y=y/2y = y/2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        // 这里用int类型会超出范围，所以用long来保存
        long y = n; 
        if(n < 0){
            // 先将y变为正数
            y = -y;
            // 将x颠倒
            x = 1 / x;
        }
        while(y > 0){
            // 判断是否位奇数
            if(y % 2 == 1){
                res = res * x;
            }
            // 计算次方
            x = x * x;
            // 将y/2，直到它不大于0，循环结束
            y = y / 2;
        }
        return res;
    }
}