每日刷题记录 (十八)

转x33g5p2x  于2022-07-10 转载在 其他  
字(4.9k)|赞(0)|评价(0)|浏览(264)

第一题: 剑指 Offer 13. 机器人的运动范围

LeetCode: 剑指 Offer 13. 机器人的运动范围

描述:
地上有一个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. 从0,0 开始,利用回溯的方法, 从左和右出发, 计算满足的个数
  3. 如果下标超出预期 返回0
  4. 如果走过的路线, 返回0, 这里需要使用一个boolean数组来进行标记
  5. 要满足题目, 行坐标和列坐标的位数之和不能大于k, 例如, 当前坐标为(i , j ), 满足要求 i%10 + i/10 + j%10 + j/10<=k

代码实现:

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] tmp = new boolean[m][n];
        return dfs(0,0,m,n,k,tmp);
    }
    public int dfs(int i, int j, int m, int n, int k, boolean[][] tmp) {
        if(i >= m || j >=n || tmp[i][j] || (i%10 + i/10 + j%10 + j/10)>k) {
            return 0;
        }
        tmp[i][j] = true;
        return 1 + dfs(i+1,j,m,n,k,tmp) + dfs(i,j+1,m,n,k,tmp);
    }
}

第二题: 剑指 Offer 14- I. 剪绳子

LeetCode: 剑指 Offer 14- I. 剪绳子

描述:
给你一根长度为 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. 初始的时候, 例如 长度为2的时候, 减了之后只能为 1 * 1 = 1, 长度为3的时候, 只能为 1 * 2 = 2.
  3. 状态 F(i) : 当前绳长最大可以减成的乘积
  4. 状态转移方程: F(i) = Math.max(F(i),F(j-i)*F(j))
  5. 初始状态: F(1) = 1, F(2) = 2 , F(3) = 3;
  6. 返回结果: F(n)

代码实现:

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        if(n == 2) return 1;
        if(n == 3) return 2;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 4; i <= n; i++) {
            for(int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i-j]);
            }
        }
        return dp[n];
    }
}

第三题: 剑指 Offer 14- II. 剪绳子 II

LeetCode: 剑指 Offer 14- II. 剪绳子 II

描述:
给你一根长度为 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. 这里, 首先把初始的时候解决, 例如n是2和n是3的情况
  2. 所以这里尽可能的让n多分出3出来.特殊的4的情况, 4分不分都应有, 因为4=2*2最大.
  3. 一直让n进行分解3, 直到n<=4的时候, 此时n为4,3,2中任何一个的时候,都说不用再拆分的了

代码实现:

class Solution {
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        long ans = 1;
        // 只要n>4就拆分
        while (n > 4) {
            ans *= 3;
            ans = ans % 1000000007;
            n -= 3;
        }
        // 拆分到 n <= 4的时候, 直接成.
        return (int)(ans * n % 1000000007);
    }
}

第四题: 剑指 Offer 16. 数值的整数次方

LeetCode: 剑指 Offer 16. 数值的整数次方

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

解题思路:

这里使用分治的方法,

  1. 例如这里的求 x的n次, 如果这里的n是16
    相当于: x -> x^2 -> x^4 -> x^8 -> x^16 这里进行了4次计算得到了
  2. 如果这里的n是17
    相当于: x -> x^2 -> x^4 -> x^8 -> x^17 这里也进行了4次计算. 不一样的是 x^8 ->x^17是进行了 平方之后还成了一个x
  3. 所以使用递归的方式去进行求得 y = x^(n/2)
  4. 如果为偶数, 直接让 x^n = y^2
  5. 如果为奇数, 直接让 x^n = y^2 * x

代码实现:

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N > 0 ? myPow2(x,n) : 1/myPow2(x,-n);
    }
    public double myPow2(double x, int n) {
        if(n == 0){
            return 1;
        }
        double y = myPow2(x,n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }
}

第五题: 剑指 Offer 20. 表示数值的字符串

LeetCode: 剑指 Offer 20. 表示数值的字符串

描述:

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

  1. 若干空格
  2. 一个 小数 或者 整数
  3. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
  4. 若干空格

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（‘+’ 或 ‘-’）

  • 下述格式之一：

  • 至少一位数字，后面跟着一个点 ‘.’

  • 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字

  • 一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（‘+’ 或 ‘-’）
  2. 至少一位数字

部分数值列举如下：

  • ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

  • ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

解题思路:

  1. 首先对字符串进行前后空格去除.
  2. 如果去除之后长度为0直接返回false

  • 这里开始根据当前是否存在e进行判断.

  • 如果当前有 e 或 E , 对前部分进行判断, 判断是否为整数或者小数, 对后部分进行判断, 是否为整数

  • 如果当前没有 e 或 E, 对整个部分进行判断, 是否为小数或者整数

  • 如果有多个 e 或 E, 直接返回false

  • 注意整数和小数正负号不是必须的, 但是整数和小数都必须有数字,小数必须要有小数点.

代码实现:

class Solution {
    public boolean isNumber(String s) {
        s = s.trim();
        if(s.length() == 0) return false;
        StringBuilder sb = new StringBuilder();
        boolean flg = true;
        for(int i = 0; i < s.length();i++){
            if(s.charAt(i) != 'e' && s.charAt(i) != 'E'){
                sb.append(s.charAt(i));
            }else{
                if(!flg) return false;
                flg = false;
                if(isdecimal(sb)){
                    sb = new StringBuilder();
                    continue;
                }else{
                    return false;
                }
            }
        }
        if(!flg && isInteger(sb)){
            return true;
        }
        if(flg && (sb.length()==0 || isdecimal(sb)) || isInteger(sb)){
            return true;
        }else{
            return false;
        }
    }
    public boolean isdecimal(StringBuilder s) {
        if(s.length() == 0) return false;
        int i = 0;
        if(s.charAt(0) == '+' || s.charAt(0) == '-'){
            i++;
        }
        boolean flg = true;
        boolean tmp = true;
        while(i < s.length()) {
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                tmp = false;
                i++;
            }else if(flg && s.charAt(i) == '.') {
                flg = false;
                i++;
            }else{
                return false;
            }
        }
        if(tmp){
            return false;
        }
        return true;
    }
    public boolean isInteger(StringBuilder s) {
        if(s.length() == 0) return false;
        int i = 0;
        if(s.charAt(0) == '+' || s.charAt(0) == '-'){
            i++;
        }
        if(s.length() == i) return false;
        while(i < s.length()) {
            if(!Character.isDigit(s.charAt(i))){
                return false;
            }
            i++;
        }
        return true;
    }
}

第六题: 剑指 Offer 29. 顺时针打印矩阵

LeetCode: 剑指 Offer 29. 顺时针打印矩阵

描述:
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

解题思路:

  1. 首先设定几个点, 从左到右,设置 left ~ right, 从上到下 设置 high ~ low
  2. 遍历, 按照顺时间的顺序加入到结果数组中/

代码实现:

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[]{};
        int high = 0;
        int low = matrix.length-1;
        int left = 0;
        int right = matrix[0].length-1;
        int[] ans = new int[matrix.length * matrix[0].length];
        int index = 0;
        while(left <= right && high <= low) {
            for(int i = left; i <= right; i++) {
                ans[index++] = matrix[high][i];
            }
            for(int i = high+1; i <= low; i++) {
                ans[index++] = matrix[i][right];
            }
            if(left < right && high < low){
                for(int i = right - 1; i >= left; i--) {
                    ans[index++] = matrix[low][i];
                }
                for(int i = low - 1; i > high ; i--) {
                    ans[index++] = matrix[i][left];
                } 
            }
            left++;
            right--;
            high++;
            low--;
        }
        return ans;
    }
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://wangzhi430.blog.csdn.net/article/details/125690831

内容来源于网络，如有侵权，请联系作者删除！

leetcode算法深度优先

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com