6287. Categorize Box According to Criteria
给你四个整数 length ，width ，height 和 mass ，分别表示一个箱子的三个维度和质量，请你返回一个表示箱子 类别 的字符串。
- 如果满足以下条件，那么箱子是 "Bulky" 的：
- 箱子 至少有一个 维度大于等于 10^4 。
- 或者箱子的 体积 大于等于 10^9 。
- 如果箱子的质量大于等于 100 ，那么箱子是 "Heavy" 的。
- 如果箱子同时是 "Bulky" 和 "Heavy" ，那么返回类别为 "Both" 。
- 如果箱子既不是 "Bulky" ，也不是 "Heavy" ，那么返回类别为 "Neither" 。
- 如果箱子是 "Bulky" 但不是 "Heavy" ，那么返回类别为 "Bulky" 。
- 如果箱子是 "Heavy" 但不是 "Bulky" ，那么返回类别为 "Heavy" 。
注意，箱子的体积等于箱子的长度、宽度和高度的乘积。测试样例
输入：length = 1000, width = 35, height = 700, mass = 300
输出："Heavy"
解释：
箱子没有任何维度大于等于 10^4 。
体积为 24500000 <= 10^9 。所以不能归类为 "Bulky" 。
但是质量 >= 100 ，所以箱子是 "Heavy" 的。
由于箱子不是 "Bulky" 但是是 "Heavy" ，所以我们返回 "Heavy" 。
解答：这题根据条件硬编码即可
class Solution {
public String categorizeBox(int length, int width, int height, int mass) {
long volume = 1;
volume = volume * length * width * height;
boolean[] mark = {false, false};
if (length >= 10000 || width >= 10000 || height >= 10000 || volume >= 1_000_000_000) {
mark[0] = true;
}
if (mass >= 100) {
mark[1] = true;
}
if (mark[0] && mark[1]) {
return "Both";
}
if (!mark[0] && !mark[1]) {
return "Neither";
}
if (mark[0]) {
return "Bulky";
}
if (mark[1]) {
return "Heavy";
}
return null;
}
}6288. Find Consecutive Integers from a Data Stream
给你一个整数数据流，请你实现一个数据结构，检查数据流中最后 k 个整数是否 等于 给定值 value 。
请你实现 DataStream 类：
- DataStream(int value, int k) 用两个整数 value 和 k 初始化一个空的整数数据流。
- boolean consec(int num) 将 num 添加到整数数据流。如果后 k 个整数都等于 value ，返回 true ，否则返回 false 。如果少于 k 个整数，条件不满足，所以也返回 false 。
测试样例
输入：["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]输出：[null, false, false, true, false]
解释：
DataStream dataStream = new DataStream(4, 3); // value = 4, k = 3
dataStream.consec(4); // 数据流中只有 1 个整数，所以返回 False 。dataStream.consec(4); // 数据流中只有 2 个整数, 由于 2 小于 k ，返回 False 。
dataStream.consec(4); // 数据流最后 3 个整数都等于 value， 所以返回 True 。
dataStream.consec(3); // 最后 k 个整数分别是 [4,4,3], 由于 3 不等于 value ，返回 False 。
解答：这道题目利用队列缓冲最近的k个整数。为了方便查看最近k个数是不是都是value，所以我多用了一个HashMap。这样就能在O(1)的时间内统计出结果。
class DataStream {
private HashMap<Integer, Integer> map;
private Deque<Integer> queue;
private int value, k;
public DataStream(int _value, int _k) {
value = _value;
k = _k;
map = new HashMap<>();
queue = new LinkedList<>();
}
public boolean consec(int num) {
queue.add(num);
map.put(num, map.getOrDefault(num, 0) + 1);
if (queue.size() > k) {
int f = queue.removeFirst();
int c = map.get(f);
if (c == 1) {
map.remove(f);
} else {
map.put(f, c - 1);
}
}
return map.getOrDefault(value, 0).equals(k);
}
}6289. Find Xor-Beauty of Array
给你一个下标从 0 开始的整数数组 nums 。
三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。
一个数组的 xor 美丽值 是数组中所有满足 0 <= i, j, k < n 的三元组 (i, j, k) 的 有效值 的异或结果。
请你返回 nums 的 xor 美丽值。
注意：
- val1 | val2 是 val1 和 val2 的按位或。
- val1 & val2 是 val1 和 val2 的按位与。
测试样例：
输入：nums = [1,4]
输出：5
解释：
- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4
数组的 xor 美丽值为所有有效值的按位异或 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5 。
解答: 这题需要对&和｜运算符有一点思考。由于最后结果是按位异或，所以可以统计每位1的个数。如果1的个数是偶数个，则当前位是0，否则是1。
那现在的问题就弱化成如果统计每一位的1个数。我们可以知道一下几种情况可以得出1:
- (1 | 1) & 1
- (1 | 0) & 1
- (0 | 1) & 1
所以我们可以统计一下每位对应数组的0，1个数。然后利用公式：
(mem[1] * mem[1]) * mem[1] + 2 * (mem[0] * mem[1]) * mem[1]
得出每位的1个数。
class Solution {
public int xorBeauty(int[] nums) {
long len = nums.length;
int res = 0;
for (int o = 0; o < 31; ++o) {
long[] mem = {0,0};
for (int i = 0; i < len; ++i) {
int m = (nums[i] >> o) & 1;
mem[m] += 1;
}
long one = (mem[1] * mem[1]) * mem[1] + 2 * (mem[0] * mem[1]) * mem[1];
if (one % 2 == 1) {
res += (1 << o);
}
}
return res;
}
}6290. Maximize the Minimum Powered City
给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。
每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。
- |x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。
一座城市的 电量 是所有能给它供电的供电站数目。政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。
给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小供电站数目的最大值是多少。
这 k 座供电站可以建在多个城市。
测试样例：
输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5。无法得到更优解，所以我们返回 5 。
解答：二分查找 + 贪婪算法。首先如果要添加电厂且我们准备从左至右遍历，那么电厂配置在越靠右的位置越好（需要保证左侧满足要求，且右侧有最多的城市可以被覆盖到）。
再者这题存在单调性，最小供电站数目越大，则需要更多的电厂。所以利用二分查找。
class Solution {
public long maxPower(int[] stations, int r, int k) {
long st = 0, ed = 2_000_000_000_0L;
int len = stations.length;
int[] dp = new int[len];
while (st < ed) {
long mid = (st + ed + 1) / 2;
long remain = k;
Arrays.fill(dp, 0);
int left = 0, right = 0;
long sum = 0;
boolean isValid = true;
for (int i = 0; i < len; ++i) {
while (i - left > r) {
sum -= stations[left];
sum -= dp[left];
++left;
}
while (right < len && right - i <= r) {
sum += stations[right];
++right;
}
if (sum < mid) {
long d = mid - sum;
if (d <= remain) {
remain -= d;
dp[right - 1] = (int) (dp[right - 1] + d);
sum += d;
} else {
isValid = false;
break;
}
}
}
if (isValid) {
st = mid;
} else {
ed = mid - 1;
}
}
return st;
}
}这周题目难度不算很大，但是需要一些数学推导减少算法复杂度。