Day81(动态规划、十叉树遍历)

64、最小路径和

给定一个包含非负整数的 m x n 网格 grid &＃xff0c;请找出一条从左上角到右下角的路径&＃xff0c;使得路径上的数字总和为最小。说明&＃xff1a;每次只能向下或者向右移动一步。

 推导公式&＃xff1a;dp[i][j]&＃43;&＃61;Math.min(dp[i][j-1],dp[i-1][j])&＃43;grid[i][j];

class Solution {//注意是n行m列的矩阵&＃xff0c;n和m可以不相等&＃xff01;&＃xff01;&＃xff01;public int minPathSum(int[][] grid) {int [][]dp&＃61;new int[grid.length][grid[0].length];dp[0][0]&＃61;grid[0][0];//初始化第一行for(int i&＃61;1;i}

386、字典序排数

给你一个整数 n &＃xff0c;按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

 字典序排序&＃xff1a;就是数字的前缀、     字典序——————>十叉树

十叉树的结构如图所示&＃xff1a;

class Solution {Listlist&＃61;new ArrayList<>();public List lexicalOrder(int n) {//字典序&＃xff1a;就是数字的前缀//字典序——————>十叉树for(int i&＃61;1;i<&＃61;9;i&＃43;&＃43;){dfs(i,n);}return list;}public void dfs(int current,int limit){if(current>limit) return ;list.add(current);for(int i&＃61;0;i<&＃61;9;i&＃43;&＃43;){dfs(current*10&＃43;i,limit);}}
}

396、旋转函数

给定一个长度为 n 的整数数组 nums 。假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组&＃xff0c;我们定义 nums 的 旋转函数  F 为&＃xff1a;

• F(k) &＃61; 0 * arrk[0] &＃43; 1 * arrk[1] &＃43; ... &＃43; (n - 1) * arrk[n - 1]

返回 F(0), F(1), ..., F(n-1)中的最大值 。

 法一&＃xff1a;暴力解法——超时

class Solution {public int maxRotateFunction(int[] nums) {int res&＃61;Integer.MIN_VALUE;for(int i&＃61;0;i}

法二&＃xff1a;通过数学推导出动态规划的推导公式

F(1)&＃61;F(0)&＃43;sum&＃43;nums.length*nums[nums.length-1]&＃xff1b;

F(2)&＃61;F(1)&＃43;sum&＃43;nums.length*nums[nums.length-2]&＃xff1b;

 F(i)&＃61;F(i-1)&＃43;sum-nums.length*nums[nums.length-i];

class Solution {public int maxRotateFunction(int[] nums) {//推导公式&＃xff1a;F(i)&＃61;F(i-1)&＃43;sum-nums.length*nums[nums.length-i];int sum&＃61;0;int F&＃61;0;//算出F(0)和sumfor(int i&＃61;0;i}