做原油的网站,网时代it培训官网,学校招办网站怎么做,html5购物网站【问题描述】[简单] 【解答思路】
边界问题
k0 #xff0c;不能产生跳水板#xff0c;返回空数组shorter 等于longer#xff0c;只有一种跳水板#xff0c;返回longerk 思路 一般情况#xff0c;k块木板#xff0c;k种可能 跳水板的长度是 shorter(k-j)longer*j#x…【问题描述】[简单] 【解答思路】
边界问题
k0 不能产生跳水板返回空数组shorter 等于longer只有一种跳水板返回longerk 思路 一般情况k块木板k种可能 跳水板的长度是 shorter(k-j)longer*j其中 0 ≤ i j ≤ k且为升序排列
1. 数学
时间复杂度O(N^2) 空间复杂度O(1) public int[] divingBoard(int shorter, int longer, int k) {if(k0){return new int[]{};}if(shorterlonger){return new int[1]{shorter*k};}int[] ans new int[k1];for(int i 0 ;ik;i){ans[i] (k-i) *shorter i*longer;}return ans;}2. 动态规划
动态规划流程 第 1 步设计状态 lengths[i] 为第 i 条跳水板的长度 第 2 步状态转移方程 int distance longer - shorter; lengths[i] lengths[i-1] distance; 第 3 步考虑初始化 lengths[0] shorter * k; 第 4 步考虑输出 return lengths;
时间复杂度O(N) 空间复杂度O(1)
public int[] divingBoard(int shorter, int longer, int k) {if (k 0) {return new int[0];}if (shorter longer) {return new int[]{shorter * k};}int distance longer - shorter;int[] lengths new int[k 1];lengths[0] shorter * k;for(int i 1; i k; i) {lengths[i] lengths[i-1] distance;}return lengths;}【总结】
1.数组的使用分声明和初始化两部分两者可同时进行也可分开进行int[] array; 声明
int[] array new int{element1,element2,element3…}; 初始化方式1
int[] array new int[length]; 初始化方式2
数组的初始化方式分为两种
一.静态初始化初始化时由程序员显式指定每个数组元素的初始值
int[] arrayName new int[]{element1,element2,element3…}
二.动态初始化初始化时由程序员指定数组的长度由系统初始化每个数组元素的默认值。
int[] arrayName new int[length];
注意不要同时使用静态初始化和动态初始化也就是说不要在进行数组初始化时既指定数组的长度也为每个数组元素分配初始值。
2.能用简单数学推导的就用数学 本题的动态规划也是基于数学推导
3.动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
