Leetcode面试题16.11：跳水板

面试题16.11：跳水板

• • 题目
  • 思路一——暴力

题目

思路一——暴力

由于需要K个木板，首先需要排除特殊情况：

• 当 K = 0，返回空；
• 当shorter == longer 为真时，返回长度为1的数组，且值为shorter * k;

然后，由于有shorter 和longer两个值，因此每一个值范围为0～k,则返回数组长度为k+1，一次遍历即可，每次的值为 shorter * i + (k - i) * longer;
最后，题目要求返回结果需从小到大排序，则调用Arrays.sort(ret)即可。

class Solution {public int[] divingBoard(int shorter, int longer, int k) {//step1:判断特殊情况if(k == 0) return new int[]{};if(shorter == longer) return new int[]{ shorter * k};//Step2:定义结果变量int[] ret = new int[ k + 1];//Step3:一次遍历for(int i = 0; i <= k; i++){ret[i] = i * shorter + (k - i) * longer;}//Step4:排序Arrays.sort(ret);//Step5:返回结果return ret;}}

如何降低执行时间：
每次都需要执行i * shorter + (k - 1) * longer,四次运算，通过观察发现，i递增时，都只增加了（longer - shorter),可以提前定义一个变量 diff = longer - shorter ，每次当I 递增时，都用ret[I - 1] + diff，只需要两次加法操作，整体运行时间提高了3ms.

		int diff = longer - shorter;ret[0] = k * shorter;//Step3:一次遍历for(int i = 1; i <= k; i++){ret[i] = ret[i - 1] + diff;}

时间复杂度：O（N）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！