上海网站建设方案策划,外贸业务员怎么开发客户,外包公司简介,建设网站免费模板下载第一题
1798. 你能构造出连续值的最大数目 解题思路
我们先抛开原题不看#xff0c;可以先完成一道简单的题目#xff0c;假设现在就给你一个目标值X#xff0c;问你能够构造出从【1~X】的连续整数#xff0c;最小需要几个数#xff1f;
贪心假设期望#xff1a;我们要…第一题
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数组所包含的元素并不是按照最佳期望给的但这并不影响整体的解题方式。
比如题目中的示例2coins [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如果大于N1则就无法构造连续整数了且缺失的连续整数为【N 1 ~ an - 1】把4换成6连续范围只能是【1~3】和【6~9】缺4和5两个数字。
代码实现
根据这个结论本题的代码实现如下
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 1return 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;}
}整个实现逻辑实际上就是分别考虑了两种情况一种是数组中的元素本身可以维持连续性一种是数组中的元素本身无法维持连续性需要补齐。而面对这两种情况下的处理方式实际上就是前一题中的解法。
