代码随想录算法训练营第二十九天

其他:

今日总结
往期打卡

---

62. 不同路径

跳转: 62. 不同路径

学习: 代码随想录公开讲解

问题:

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路:

左边上边的数量和推出当前数量,第一排第一列都是1,可以直接初始化剪枝

复杂度:

• 时间复杂度: $O(mn)$
• 空间复杂度: $O(mn)$

代码:

class Solution {int[][] f;int dfs(int m, int n){if(m==1&&n==1) return 1;if(m<=0||n<=0) return 0;if(f[m][n]>0) return f[m][n];return f[m][n] = dfs(m-1,n)+dfs(m,n-1); }public int uniquePaths(int m, int n) {f = new int[m+1][n+1];for(int i=1;i<=m;i++){f[i][0] = 1;}for(int i=1;i<=n;i++){f[0][i] = 1;}return dfs(m,n);}
}

---

63. 不同路径 II

跳转: 63. 不同路径 II

学习: 代码随想录公开讲解

问题:

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

思路:

比上一题加个条件判断,初始化时也要注意,当然可以加上如果终点或起点为1直接返回0来优化

复杂度:

• 时间复杂度: $O(mn)$
• 空间复杂度: $O(mn)$

代码:

class Solution {int[][] obstacleGrid;int[][] fn;int dfs(int m,int n){if(m<0||n<0||obstacleGrid[m][n]==1) return 0;if(fn[m][n]>-1) return fn[m][n];return fn[m][n] = dfs(m-1,n)+dfs(m,n-1);}public int uniquePathsWithObstacles(int[][] obstacleGrid) {this.obstacleGrid = obstacleGrid;int m = obstacleGrid.length;int n = obstacleGrid[0].length;fn = new int[m][n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){fn[i][j] = -1;}}for(int i=0;i<m;i++){if(obstacleGrid[i][0]==1) break;fn[i][0] = 1;}for(int i=0;i<n;i++){if(obstacleGrid[0][i]==1) break;fn[0][i] = 1;}return dfs(m-1,n-1);}
}

---

343. 整数拆分

跳转: 343. 整数拆分

学习: 代码随想录公开讲解

问题:

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

思路:

拆分剩下的值相等要乘的最大值就相等,从低到高可以遍历一次求最大值递推

复杂度:

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n)$

代码:

class Solution {int[] dp = new int[60];{dp[2] = 1;for(int i=3;i<60;i++) dp[i] = -1;}int dfs(int n){if(dp[n]>-1) return dp[n];for(int i=1;i<=n/2;i++){// System.out.println(dp[n]);dp[n] = Math.max(i*dfs(n-i),Math.max(dp[n],i*(n-i)));}return dp[n];}public int integerBreak(int n) {return dfs(n);}
}

---

96. 不同的二叉搜索树

跳转: 96. 不同的二叉搜索树

学习: 代码随想录公开讲解

问题:

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

思路:

分配到左边右边的序列都能看作递增或递减序列,只关注数量从1个节点为1,两个为2,三个节点开始所有可能情况左乘右再加和,层层往上推即可

复杂度:

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n)$

代码:

class Solution {int[] dp = new int[20];public int numTrees(int n) {dp[0] = 1;dp[1] = 1;dp[2] = 2;for(int i=3;i<=n;i++){for(int j=1;j<=i;j++)dp[i]+=dp[j-1]*dp[i-j];} return dp[n];}
}

---

2302. 统计得分小于 K 的子数组数目(每日一题)

跳转: 2302. 统计得分小于 K 的子数组数目

学习: 灵茶山艾府题解

问题:

一个数组的 分数 定义为数组之和 乘以 数组的长度。

• 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。

子数组 是数组中的一个连续元素序列。

思路:

滑动窗口,遍历尾部,每次收缩到正好合法,继续收缩都是合法值直接下标做差即可求出数量

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

代码:

class Solution {public long countSubarrays(int[] nums, long k) {long ans = 0;long sum = 0;int left = 0;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum * (right - left + 1) >= k) {sum -= nums[left];left++;}ans += right - left + 1;}return ans;}
}

---

总结

练习了动态规划和滑动窗口

往期打卡

代码随想录算法训练营第二十八天

代码随想录算法训练营第二十七天(补)

代码随想录算法训练营第二十六天

代码随想录算法训练营第二十五天

代码随想录算法训练营第二十四天

代码随想录算法训练营第二十三天

代码随想录算法训练营周末四

代码随想录算法训练营第二十二天(补)

代码随想录算法训练营第二十一天

代码随想录算法训练营第二十天

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天