Toasobi的博客

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

剪绳子（中等）

剪绳子（中等）

这道题即是整数拆分题，常见的方法有贪心，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 评论

斐波那契数列（简单）

斐波那契数列（简单）

这道题上来一个递归，按道理应该是正确的，但是递归会超出时间限制、<div> class Solution { public int fib(int n) { int num = 0; if(n == 0) return 0; if(n == 1) return 1; //主函数 num += fib(n-1) + fib(n-2); return num; } } </div>下面来看不同的解决方法=========================滚动数组（动态规划）这里的滚动数组并不是真的数组，而是三个变量滚动赋值初始的时候是001，一次后是011，两次过后是112......<div> class Solution { public int fib(int n) { final int MOD = 1000000007; if (n < ...

2023-03-03

剑指offer（第二版）

0 阅读

0 评论

2023年03月03日

0 阅读

0 评论

Toasobi博主

暂无访问

125 文章数

1 评论量

互动读者

热门文章

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

繁

返回顶部~