Toasobi的博客

搜索到 28 篇与的结果 ———

剪绳子2（中等）

剪绳子2（中等）

这道题和上一道的区别是：使用取模前的数字进行比较，输出结果要取模。因为有取模环节。其次这题数字很大，属于大数考察一开始做这题的时候想用int，发现必超内存，于是就想使用long，但是由于需要使用pow函数，该函数返回值是double，double强转long会丢失精度，会导致解题错误，于是最终妥协使用了BigInteger要注意BigInteger的使用，里面的取幂，乘积，比较等等都是需要该类下的指定函数的。下面是代码：<div> import java.math.BigInteger; class Solution { public int cuttingRope(int n) { BigInteger max = BigInteger.valueOf(0); //long max = 0; int s = (int)Math.sqrt(n); if(n == 1 || n ==2) return 1; if(n == 3) ret...

2023-03-07

剑指offer（第二版）

0 阅读

0 评论

2023年03月07日

0 阅读

0 评论

剪绳子（中等）

剪绳子（中等）

这道题即是整数拆分题，常见的方法有贪心，dp算法初次写这道题时，利用高中数学知识--求矩阵最大面积求解，即使剪断后的绳子长度都相互接近，这时的乘机可能最大。问题---知道接近最大，但是到底要剪几段？答：可以使用for循环，其中i表示段数，将所有乘积比较取最大即可；同时由数学知识得最大值在根号n与n/2之间，所以代码的for循环可以进行优化，优化后时间复杂度大大降低;代码实现：<div>class Solution { public int cuttingRope(int n) { int max = 0; int s = (int)Math.sqrt(n); if(n == 1 || n ==2) return 1; if(n == 3) return 2; for(int i=(s-1>0?s-1:s);i<=n/2;i++){ //m表示几段 int temp = 1; ...

2023-03-07

剑指offer（第二版）

0 阅读

0 评论

2023年03月07日

0 阅读

0 评论

矩阵中的路径（中等）

矩阵中的路径（中等）

一般遇到矩阵中求路径的题，首先想到的是dfs递归回溯算法，具体的图解如下注意两个for循环一直在检测是否匹配，若匹配则开始递归，不匹配则进入下一个循环。同时注意我们传递的参数的重要性，包括检测坐标是否超出界限（超出则立即返回false剪枝），并且每次访问一个节点都要修改其值表示已经访问下面则是代码<div> class Solution { public boolean exist(char[][] board, String word) { char[] words = word.toCharArray(); int row = board.length; int col = board[0].length; for(int i = 0;i < row; i++){ for(int j = 0;j < col; j++){ if(dfs(board,words,i,j,0)){ retur...

2023-03-03

剑指offer（第二版）

0 阅读

0 评论

2023年03月03日

0 阅读

0 评论

旋转数组中最小的数字（简单）

旋转数组中最小的数字（简单）

这道题我使用了双端队列（栈）来写，先把第一个数放进去，然后每次放进去之前比较一下栈顶元素和它的大小即可<div> class Solution { public int minArray(int[] numbers) { LinkedList<Integer> stack = new LinkedList(); //构造栈 stack.push(numbers[0]); for(int i = 1;i < numbers.length;i++){ if(numbers[i] >= stack.peekFirst()){ stack.push(numbers[i]); }else{ return numbers[i]; } } return stack.peekLast(); } } </div>

2023-03-03

剑指offer（第二版）

0 阅读

0 评论

2023年03月03日

0 阅读

0 评论

青蛙跳台阶问题（简单）

青蛙跳台阶问题（简单）

这个问题类似于斐波那契数列问题，也可以使用递归来解决，但是递归时间复杂度太高，所以我们可以学习上次做斐波那契数列的滚动数组的做法来解决这道题下面是代码<div> class Solution { public int numWays(int n) { final int MOD = 1000000007; if(n <= 3){ if(n != 0) return n; return 1; } int a = 0; int b = 2; int r = 3; for(int i=4;i <= n;i++){ a = b; b = r; r = (a + b)%MOD; } return r; } } </div>

2023-03-03

剑指offer（第二版）

0 阅读

0 评论

2023年03月03日

0 阅读

0 评论

Toasobi博主

暂无访问

125 文章数

1 评论量

互动读者

热门文章

大佬太牛啦！！！！！！！！！！！！！

繁

返回顶部~