西安做网站找腾帆,怎么做电力设计公司网站,wordpress自定义类型模板,收到网站建设费分录2917. 找出数组中的 K-or 值
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
nums 中的 K-or 是一个满足以下条件的非负整数#xff1a;
只有在 nums 中#xff0c;至少存在 k 个元素的第 i 位值为 1 #xff0c;那么 K-or 中的第 i 位的值才是 1 。
返回 nums …
2917. 找出数组中的 K-or 值
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
nums 中的 K-or 是一个满足以下条件的非负整数
只有在 nums 中至少存在 k 个元素的第 i 位值为 1 那么 K-or 中的第 i 位的值才是 1 。
返回 nums 的 K-or 值。
注意 对于整数 x 如果 (2^i AND x) 2^i 则 x 中的第 i 位值为 1 其中 AND 为按位与运算符。
示例 1
输入nums [7,12,9,8,9,15], k 4
输出9
解释nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。
nums[0] 和 nums[5] 的第 1 位的值为 1 。
nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。
nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。
只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此答案为 2^0 2^3 9 。示例 2
输入nums [2,12,1,11,4,5], k 6
输出0
解释因为 k 6 nums.length 所以数组的 6-or 等于其中所有元素按位与运算的结果。因此答案为 2 AND 12 AND 1 AND 11 AND 4 AND 5 0 。示例 3
输入nums [10,8,5,9,11,6,8], k 1
输出15
解释因为 k 1 数组的 1-or 等于其中所有元素按位或运算的结果。因此答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 15 。提示
1 nums.length 500 nums[i] 2^311 k nums.length 思路
简单题目直接遍历就好了。
最多只有31位而且数组长度也才50。重点是 (2^i AND x) 2^i
两层遍历外层范围[0-31]内层范围[0-n]n是数组的长度。
ac code
class Solution {public int findKOr(int[] nums, int k) {int ans 0;for (int j0;j31;j) {int cnt 0;for (int num : nums) {if ((num (1 j)) (1 j)) {cnt 1;}if (cnt k) {ans ans (1 j);break;}}}return ans;}
}
2918. 数组的最小相等和
给你两个由正整数和 0 组成的数组 nums1 和 nums2 。
你必须将两个数组中的 所有 0 替换为 严格 正整数并且满足两个数组中所有元素的和 相等 。
返回 最小 相等和 如果无法使两数组相等则返回 -1 。
示例 1
输入nums1 [3,2,0,1,0], nums2 [6,5,0]
输出12
解释可以按下述方式替换数组中的 0
- 用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 [3,2,2,1,4] 。
- 用 1 替换 nums2 中的一个 0 。得到 nums2 [6,5,1] 。
两个数组的元素和相等都等于 12 。可以证明这是可以获得的最小相等和。示例 2
输入nums1 [2,0,2,0], nums2 [1,4]
输出-1
解释无法使两个数组的和相等。
提示
1 nums1.length, nums2.length 10^50 nums1[i], nums2[i] 10^6
思路
直接模拟。答案分几种情况只要捋清楚即可。
1、nums1不存在0: 1nums2不存在0: value1nums1的sum值同下 value2nums2的sum值同下那么就return -1 2nums2存在0: value1 (value2cnt2(代表nums2种0的个数同下))因为0是严格替换成了正整数那么最小也是1已经比value1还要大了再加上正整数不可能使得value2变小所以return -1 value1 value 2因为可以换成任意正整数所以value2肯定可以变大成任意值。那么最小的话肯定就是value1所以return value1即可。
2、nums1存在0: 1nums2 不存在0: 同理(value1 cnt1) value2 即可return -1 value1 value2则 return value2 2nums2 存在0 因为0最小也是换成1所以value的范围其实是可以确定的。例如nums1值的范围是[value1 cnt1nums1存在0的个数, 正无穷) 那么nums2也是同理。所以返回的值取范围交集即可。return Math.max(value1cnt1, value2cnt2)为什么是max呢因为交集 不懂得可以画个图或者举几个例子。
捋清楚之后按照分类写清楚就行( 之前没捋清楚还wa了一次。。。
具体细节看代码
ac code
class Solution {public long minSum(int[] nums1, int[] nums2) {long value1 0; // nums1的sumlong value2 0; // nums2的sumint cnt1 0; // num1的0的个数int cnt2 0; // num2的0的个数for (int num : nums1) {if (num 0) {cnt1 1;}value1 num;}for (int num : nums2) {if (num 0) {cnt2 1;}value2 num;}// 需要判断value1 如果小于 value2 cnt2那么无论如何都不可能if (cnt1 0 value1 (value2cnt2)) {if (cnt2 0 value1 value2) {return value1;} else if (value1 (value2cnt2)) {return value1;}return -1;}if (cnt2 0 value2 (value1cnt1)) {if (cnt1 0 value1 value2) {return value1;} else if (value2 (value1cnt1)) {return value2;}return -1;}if (cnt1 0) {return value1;}if (cnt2 0) {return value2;}return Math.max(value1cnt1, value2cnt2); }
}
2919. 使数组变美的最小增量运算数
给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k 。
你可以执行下述 递增 运算 任意 次可以是 0 次
从范围 [0, n - 1] 中选择一个下标 i 并将 nums[i] 的值加 1 。
如果数组中任何长度 大于或等于 3 的子数组其 最大 元素都大于或等于 k 则认为数组是一个 美丽数组 。
以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。
子数组是数组中的一个连续 非空 元素序列。
示例 1
输入nums [2,3,0,0,2], k 4
输出3
解释可以执行下述递增运算使 nums 变为美丽数组
选择下标 i 1 并且将 nums[1] 的值加 1 - [2,4,0,0,2] 。
选择下标 i 4 并且将 nums[4] 的值加 1 - [2,4,0,0,3] 。
选择下标 i 4 并且将 nums[4] 的值加 1 - [2,4,0,0,4] 。
长度大于或等于 3 的子数组为 [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4] 。
在所有子数组中最大元素都等于 k 4 所以 nums 现在是美丽数组。
可以证明无法用少于 3 次递增运算使 nums 变为美丽数组。
因此答案为 3 。示例 2
输入nums [0,1,3,3], k 5
输出2
解释可以执行下述递增运算使 nums 变为美丽数组
选择下标 i 2 并且将 nums[2] 的值加 1 - [0,1,4,3] 。
选择下标 i 2 并且将 nums[2] 的值加 1 - [0,1,5,3] 。
长度大于或等于 3 的子数组为 [0,1,5]、[1,5,3]、[0,1,5,3] 。
在所有子数组中最大元素都等于 k 5 所以 nums 现在是美丽数组。
可以证明无法用少于 2 次递增运算使 nums 变为美丽数组。
因此答案为 2 。示例 3
输入nums [1,1,2], k 1
输出0
解释在这个示例中只有一个长度大于或等于 3 的子数组 [1,1,2] 。
其最大元素 2 已经大于 k 1 所以无需执行任何增量运算。
因此答案为 0 。提示
3 n nums.length 10^50 nums[i] 10^90 k 10^9
思路
挺有意思的一道题目算是益智题了。一开始想到的是滑动窗口最小长度3然后将窗口内最大值进行增大到k值后来发现不对因为窗口内最大值并不一定是最优的那么就会希望有一个后悔的操作比如增大了a但是发现不是最优的想要增大相邻的b。如何“后悔”增大某个数字
举个例子
[43,31,14,4]
73
如果按照原本的想法增大窗口内最大值窗口长度是3。那么应该增大43然后窗口向右滑动后没有满足条件的k值则增大31到k值。这样发现一共花费了30 42 62。
但是如果我们仅仅只增大31呢 那么其实就只需要花费42即可。
此时我们可以考虑下如果我们选择了43的时候如果后续需要后悔那么对于相邻的31是不是需要进行变大操作。
一步步来看[xxx]表示窗口
[433114]4
经过操作 假设先按照之前的贪心的想法先把43进行变动为
[733114]4
此时我们已经花费了30了如果只是单纯将31 - 73 是需要42目前已经花费了30那么就还需要12所以我们可以将31同步转换为61,同理14同步转换为44即
[736144]4
所以在下一个窗口后那么就是
73[61444]
这个时候我们就只需要花费12 就可以满足条件这样相当于就是执行了后悔的操作。是不是很巧妙的一个办法。
而且我们还需要注意窗口尽可能往后取值。
具体实现细节可以看看代码。
ac code
class Solution {public long minIncrementOperations(int[] nums, int k) {int first nums[0];int second nums[1];int third nums[2];int n nums.length;long ans 0;// 窗口长度为3for (int i3;in;i) {// 如果没有满足条件的值才需要进行变换if (first k second k third k) {// 找到最大值int tmp Math.max(first, Math.max(second, third));ans (k - tmp); // 计算代价if (third tmp) { // 如果是最后一个的话直接变就行因为它在窗口待最久third k;} else if (second tmp) { // 如果是第二个只需要把后面的加上后悔操作即可毕竟第一个马上要出窗口了second k;third (k - tmp);} else { // 同上first k;second (k - tmp);third (k - tmp);}}// 窗口向右滑动if (i n) {first second;second third;third nums[i];}}return ans;}
} 2920. 收集所有金币可获得的最大积分
节点 0 处现有一棵由 n 个节点组成的无向树节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges 其中 edges[i] [ai, bi] 表示在树上的节点 ai 和 bi 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k 其中 coins[i] 表示节点 i 处的金币数量。
从根节点开始你必须收集所有金币。要想收集节点上的金币必须先收集该节点的祖先节点上的金币。
节点 i 上的金币可以用下述方法之一进行收集
收集所有金币得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数你将会失去 abs(coins[i] - k) 点积分。收集所有金币得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。
返回收集 所有 树节点的金币之后可以获得的最大积分。 示例 1 输入edges [[0,1],[1,2],[2,3]], coins [10,10,3,3], k 5
输出11
解释
使用第一种方法收集节点 0 上的所有金币。总积分 10 - 5 5 。
使用第一种方法收集节点 1 上的所有金币。总积分 5 (10 - 5) 10 。
使用第二种方法收集节点 2 上的所有金币。所以节点 3 上的金币将会变为 floor(3 / 2) 1 总积分 10 floor(3 / 2) 11 。
使用第二种方法收集节点 3 上的所有金币。总积分 11 floor(1 / 2) 11.
可以证明收集所有节点上的金币能获得的最大积分是 11 。 示例 2 输入edges [[0,1],[0,2]], coins [8,4,4], k 0
输出16
解释
使用第一种方法收集所有节点上的金币因此总积分 (8 - 0) (4 - 0) (4 - 0) 16 。提示
n coins.length2 n 10^50 coins[i] 10^4edges.length n - 10 edges[i][0], edges[i][1] n0 k 10^4
思路
树上dp不太会。。。 放下别人的题解。。。
把 floor(coins[i] / 2) 看成右移操作。
一个数最多右移多少次就变成 000 了在本题的数据范围下这至多是 141414 次。
同时右移操作是可以叠加的我们可以记录子树中的节点值右移了多少次。
所以可以定义 dfs(i,j)\textit{dfs}(i,j)dfs(i,j) 表示子树 iii 在已经右移 jjj 次的前提下最多可以得到多少积分。
用「选或不选」来思考即是否右移
不右移答案为 (coins[i]j)−k(\textit{coins}[i]j)-k(coins[i]j)−k 加上每个子树 ch\textit{ch}ch 的 dfs(ch,j)\textit{dfs}(ch,j)dfs(ch,j)。 右移答案为 coins[i](j1)\textit{coins}[i](j1)coins[i](j1) 加上每个子树 ch\textit{ch}ch 的 dfs(ch,j1)\textit{dfs}(ch,j1)dfs(ch,j1)。 这两种情况取最大值。
作者灵茶山艾府
class Solution {public int maximumPoints(int[][] edges, int[] coins, int k) {int n coins.length;ListInteger[] g new ArrayList[n];Arrays.setAll(g, e - new ArrayList());for (int[] e : edges) {int x e[0], y e[1];g[x].add(y);g[y].add(x);}int[][] memo new int[n][14];for (int[] m : memo) {Arrays.fill(m, -1); // -1 表示没有计算过}return dfs(0, 0, -1, memo, g, coins, k);}private int dfs(int i, int j, int fa, int[][] memo, ListInteger[] g, int[] coins, int k) {if (memo[i][j] ! -1) { // 之前计算过return memo[i][j];}int res1 (coins[i] j) - k;int res2 coins[i] (j 1);for (int ch : g[i]) {if (ch fa) continue;res1 dfs(ch, j, i, memo, g, coins, k); // 不右移if (j 13) { // j1 14 相当于 res2 0无需递归res2 dfs(ch, j 1, i, memo, g, coins, k); // 右移}}return memo[i][j] Math.max(res1, res2); // 记忆化}
}
