2144. 打折购买糖果的最小开销 - 力扣（LeetCode）
2144. 打折购买糖果的最小开销 - 一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。 免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。 * 比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。 给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得...
思路
贪心，从贵到便宜，每三个一组，其中第三个是免费送的。剩余无法成组的直接加到结果里。
代码
class Solution {
public int minimumCost(int[] cost) {
Arrays.sort(cost);
int ans = 0;
int i = cost.length - 1;
for (; i >= 2; i -= 3) {
ans += cost[i] + cost[i - 1];
}
for (; i >= 0; i--) {
ans += cost[i];
}
return ans;
}
}
补一下前两天的题。
5-30 3161. 物块放置查询
思路
其实第一想法是B+树，但是想了想复杂度，觉得还是算了吧，用线段树好像也可以。
用线段树存储从0到当前坐标的最大空间，用有序集合存储障碍物的坐标。
如果查询的节点在障碍物上，那直接就能获取。如果节点不在障碍物上，那就找到前一个障碍物，获取最大空间，与节点坐标-前一个障碍物的坐标取最大值。
代码
class Solution {
// 线段树节点
private static class SegmentTreeNode {
// 线段左下标
int l;
// 线段右下标
int r;
// 线段分段下标
int mid;
// 线段中的最大间隔
int maxSpace;
public SegmentTreeNode(int l, int r) {
this.l = l;
this.r = r;
this.mid = (l + r) >> 1;
}
}
// 线段树
private static class SegmentTree {
// 线段树节点数组
private final SegmentTreeNode[] tree;
public SegmentTree(int max) {
tree = new SegmentTreeNode[2 << (32 - Integer.numberOfLeadingZeros(max))];
build(1, 0, max);
}
/**
* 构造线段树
* @param idx 当前序号
* @param l 左下标
* @param r 右下标
*/
private void build(int idx, int l, int r) {
var node = new SegmentTreeNode(l, r);
tree[idx] = node;
// 如果是叶子节点，赋值后直接返回
if (l == r) {
return;
}
// 不是叶子节点，分别构造左子树和右子树
build( idx << 1, l, node.mid);
build((idx << 1) + 1, node.mid + 1, r);
}
/**
* 更新某段线段的值
* @param idx 当前节点
* @param l 线段左下标
* @param r 线段右下标
* @param p 要更新的坐标
* @param val 要更新的值
*/
private void update(int idx, int l, int r, int p, int val) {
var node = tree[idx];
if (l == r) {
node.maxSpace = val;
return;
}
// 更新左子树部分
if (node.mid >= p) {
update(idx << 1, l, node.mid, p, val);
}
// 更新右子树部分
else {
update((idx << 1) + 1, node.mid + 1, r, p, val);
}
node.maxSpace = Math.max(tree[idx << 1].maxSpace, tree[(idx << 1) + 1].maxSpace);
}
private int getMaxSpace(int idx, int r, int p) {
var node = tree[idx];
// 端点超过线段右点，直接取最大值
if (p >= r) {
return node.maxSpace;
}
// 端点在线段左半，递归左子树
if (p <= node.mid) {
return getMaxSpace(idx << 1, node.mid, p);
}
// 端点在线段右半，取左子树与递归右子树最大值
return Math.max(tree[idx << 1].maxSpace, getMaxSpace((idx << 1) + 1, r, p));
}
}
public List<Boolean> getResults(int[][] queries) {
int max = 0;
for (int[] query : queries) {
max = Math.max(max, query[1]);
}
max++;
List<Boolean> ans = new ArrayList<>();
SegmentTree tree = new SegmentTree(max);
// 有序集合用于快速取出新障碍物所在点与前后的距离
TreeSet<Integer> set = new TreeSet<>();
set.add(0);
set.add(max);
for (int[] query : queries) {
int r = query[1];
int pre = set.floor(r - 1);
if (query[0] == 1) {
int next = set.ceiling(r);
set.add(r);
tree.update(1, 0, max, r, r - pre);
tree.update(1, 0, max, next, next - r);
} else {
int maxSpace = Math.max(tree.getMaxSpace(1, max, pre), r - pre);
ans.add(maxSpace >= query[2]);
}
}
return ans;
}
}
5-31 2126. 摧毁小行星
思路
明显的贪心，先吃小的更合适。
另外要注意， 1 <= asteroids.length <= 105 1 <= asteroids[i] <= 105 所以最终结果可能超出int范围。
代码
class Solution {
public boolean asteroidsDestroyed(int mass, int[] asteroids) {
Arrays.sort(asteroids);
long sum = mass;
for (int asteroid : asteroids) {
if (sum >= asteroid) {
sum += asteroid;
} else {
return false;
}
}
return true;
}
}
2 个帖子 - 2 位参与者
来源: LinuxDo 最新话题查看原文