跳水板

发表于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

LeetCode每日一题，面试题16.11. Diving Board LCCI

先看题目描述

大意就是有两种长度的木板，共有 k 块，返回所有的总长度情况

算法和思路

很简单的一道数学题，找出规律就可以

  • 用 res 数组存储答案，因为 shorter 可使用 0 到 k 次，故 res 数组长度为 k + 1
  • res[0] = shorter * k
  • res[i] = res[i - 1] + longer - shorter
  • 注意边际情况，k = 0 时，返回空数组，shorter = longer 时，返回 [shorter * k]

实现也不难，但这道题如何改进效率值得注意

算法源码

一开始实现的是这个源码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    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[] res = new int[k + 1];
        res[0] = shorter * k;
        for (int i = 1; i <= k; i++) {
            res[i] = res[i - 1] + longer - shorter;
        }
        return res;
    }
}

提交结果是这样的

于是就想着怎么提升到100%，后来看了题解里面评论，想到可以用临时变量，就不需要重复访问数组了，可以节省时间

新的实现源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    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[] res = new int[k + 1];
        int temp = shorter * k;
        int val = longer - shorter;
        res[0] = temp;
        for (int i = 1; i <= k; i++) {
            temp += val;
            res[i] = temp;
        }
        return res;
    }
}

提交结果