LeetCode-周赛-思维训练-中等难度

2023-12-13 11:40:33

第一题

1798. 你能构造出连续值的最大数目

在这里插入图片描述

解题思路

我们先抛开原题不看,可以先完成一道简单的题目,假设现在就给你一个目标值X,问你能够构造出从【1~X】的连续整数,最小需要几个数?

贪心假设

期望:我们要尽量用最少的数目,构造出最长的连续数字。

使用数组` x = [1]`,那么能构造出来的连续整数的范围就是`【1】` 
使用数组 `x = [1,2]`,那么能构造出来的连续整数的范围就是`【1~3】` 
使用数组 `x = [1,2,4]`,那么能构造出来的连续整数的范围就是`【1~7】` 
	使用数组`x = [1,2,3]`,那么只能构造出`【1~6】`。
	而同样是`3`个数,`x = [1,2,4]`,却能构造出`【1~7】`。
	所以在尽量少的数目前提下,选择:`[1,2,4]` 
使用数组 `x = [1,2,4,8]`,那么能构造出来的连续整数的范围就是`【1~15】`

结论:如果有一些已经从小到大排序好的数`【a1,a2,a3...an】`,能够连续构造出来的整数范围是`【1~N】`,那么下一个能够造成的最大范围则为`【1~ (N + N +1)】`

在这里插入图片描述

根据结论,我们很容易给出代码实现

public int simple_minimumAdded(int target) {
    int ans = 0;
    int n = 0;
    while (n < target) {
      n = n + n + 1;
      ans++;
    }
    return ans;
}

现在,让我们回到原题中,虽然题目中给出的coins数组所包含的元素并不是按照最佳期望给的,但这并不影响整体的解题方式。

比如,题目中的示例2:`coins = [1,1,1,4]`,我们还是将数组分解拆开讨论

当 `coins = [1]` 时,范围 `【1】`
当 `coins = [1,1]` 时,范围 `【1~2】`
当 `coins = [1,1,1] `时,范围 `【1~3】`
当 `coins = [1,1,1,4] `时,范围 `【1~7】`

结论:如果有一些已经从小到大排序好的数`【a1,a2,a3...an】`,能够连续构造出来的整数范围是`【1~N】`,那么下一个能够造成的最大范围则为`【1 ~ (an + N)】`。

但是这里还有一个前提,`an`如果大于`N+1`,则就无法构造连续整数了,且缺失的连续整数为`【N + 1 ~ an - 1】`

把4换成6,连续范围只能是【1~3】【6~9】45两个数字。
在这里插入图片描述

代码实现

根据这个结论,本题的代码实现如下:

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int n = 0;
        for(int c : coins){
            if(c > n + 1){
                break;
            }
            n += c;
        }
        // 由于题目中0也算一个数,所以最后答案为: n + 1
        return n + 1;
    }
}

第二题

2952. 需要添加的硬币的最小数量

在这里插入图片描述

在有了前一题的基础上,再来做这一题,就简单了许多,本题可以看作当数组无法构造连续整数,且又未达到target时,你可以通过添加一些数字,使其满足要求,问你最少需要添加几次。

代码实现

class Solution {
    public int minimumAddedCoins(int[] coins, int target) {
        Arrays.sort(coins);
        long max = 0;
        int idx = 0;
        int ans = 0;
        while (max < target) {
            if (idx < coins.length && coins[idx] <= max + 1) {
                max += coins[idx];
                idx++;
            } else {
                max = max + max + 1;
                ans++;
            }
        }
        return ans;
    }
}

整个实现逻辑,实际上就是分别考虑了两种情况,一种是数组中的元素本身可以维持连续性,一种是数组中的元素本身无法维持连续性,需要补齐。而面对这两种情况下的处理方式实际上就是前一题中的解法。

文章来源:https://blog.csdn.net/CSDN_WYL2016/article/details/134833734
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。