leetcode第369周赛

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 <= 50
  • 0 <= nums[i] < 2^31
  • 1 <= 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 j=0;j<31;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^5
  • 0 <= nums1[i], nums2[i] <= 10^6

思路:

直接模拟。答案分几种情况,只要捋清楚即可。

1、nums1不存在0:

  1)nums2不存在0:

       value1(nums1的sum值,同下)!= value2(nums2的sum值,同下)那么就return -1

  2)nums2存在0:

      value1 <= (value2+cnt2(代表nums2种0的个数,同下)):因为0是严格替换成了正整数,那么最小也是1,已经比value1还要大了,再加上正整数,不可能使得value2变小,所以,return -1 ;

     value1 > value 2:因为可以换成任意正整数,所以,value2肯定可以变大成任意值。那么最小的话,肯定就是value1,所以return value1即可。

2、nums1存在0:

  1)nums2 不存在0:

      同理,(value1 + cnt1) >= value2 即可return -1;

      value1 < value2,则 return value2

  2)nums2 存在0:

      因为0最小也是换成1,所以value的范围其实是可以确定的。例如nums1值的范围是[value1 + cnt1(nums1存在0的个数), 正无穷)

      那么nums2也是同理。所以,返回的值取范围交集即可。return Math.max(value1+cnt1, value2+cnt2),为什么是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 <= (value2+cnt2)) {if (cnt2 == 0 && value1 == value2) {return value1;} else if (value1 == (value2+cnt2)) {return value1;}return -1;}if (cnt2 == 0 && value2 <= (value1+cnt1)) {if (cnt1 == 0 && value1 == value2) {return value1;} else if (value2 == (value1+cnt1)) {return value2;}return -1;}if (cnt1 == 0) {return value1;}if (cnt2 == 0) {return value2;}return Math.max(value1+cnt1, value2+cnt2); }
}

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^5
  • 0 <= nums[i] <= 10^9
  • 0 <= 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]表示窗口)

[43,31,14],4

经过操作 假设先按照之前的贪心的想法,先把43进行变动为

[73,31,14],4

此时我们已经花费了30了,如果只是单纯将31 -> 73 是需要42,目前已经花费了30,那么就还需要12,所以,我们可以将31同步转换为61,同理14同步转换为44,即

[73,61,44],4

所以在下一个窗口后那么就是:

73,[61,44,4]

这个时候我们就只需要花费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 i=3;i<=n;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.length
  • 2 <= n <= 10^5
  • 0 <= coins[i] <= 10^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= 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]>>(j+1)\textit{coins}[i]>>(j+1)coins[i]>>(j+1) 加上每个子树 ch\textit{ch}ch 的 dfs(ch,j+1)\textit{dfs}(ch,j+1)dfs(ch,j+1)。
这两种情况取最大值。

作者:灵茶山艾府
 

class Solution {public int maximumPoints(int[][] edges, int[] coins, int k) {int n = coins.length;List<Integer>[] 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, List<Integer>[] 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) { // j+1 >= 14 相当于 res2 += 0,无需递归res2 += dfs(ch, j + 1, i, memo, g, coins, k); // 右移}}return memo[i][j] = Math.max(res1, res2); // 记忆化}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/175522.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2.数据结构-链表

概述 目标 链表的存储结构和特点链表的几种分类及各自的存储结构链表和数组的差异刷题(反转链表) 概念及存储结构 先来看一下动态数组 ArrayList 存在哪些弊端 插入&#xff0c;删除时间复杂度高需要一块连续的存储空间&#xff0c;对内存要求比较高&#xff0c;比如要申请…

NUXT前端服务端渲染技术框架

服务端渲染又称SSR&#xff08;Server Side Render&#xff09;实在服务端完成页面的内容&#xff0c;而不是在客户端通过AJAX获取数据 优势&#xff1a;更好的SEO&#xff0c;由于搜索引擎爬虫抓取工具可以直接查看完全渲染的页面 Nuxt.js是一个基于Vue.js的轻量级应用框架&a…

【WSL 2】Windows10 安装 WSL 2,并配合 Windows Terminal 和 VSCode 使用

【WSL 2】Windows10 安装 WSL 2&#xff0c;并配合 Windows Terminal 和 VSCode 使用 1 安装 Windows Terminal2 安装 WSL 23 在 Windows 文件资源管理器中打开 WSL 项目4 在 VSCode 中使用 WSL 24.1 必要准备4.2 从 VSCode 中 Connect WSL4.3 从 Linux 中打开 VSCode 1 安装 W…

计算机网络第3章-TCP协议(2)

TCP拥塞控制 TCP拥塞控制的三种方式&#xff1a; 慢启动、拥塞避免、快速恢复 慢启动 当一条TCP连接开始时&#xff0c;cwnd的值是一个很小的MSS值&#xff0c;这使得初始发送速率大约为MSS/RTT。 在慢启动状态&#xff0c;cwnd的值以1个MSS开始并且每当传输的报文段首次被…

塔望食观察丨从“一药难求”看国内退烧药品牌是怎样炼成的

随着新冠疫情防疫的全面放开&#xff0c;感染患者不断增多&#xff0c;市民在未知的恐慌中开启了囤药模式&#xff0c;药店中的“四类药”&#xff08;退烧、止咳、抗病毒、抗生素类药品&#xff09;被一抢而空&#xff0c;尤其是以退烧类药物更为短缺&#xff0c;以解热镇痛的…

贪心算法总结(未完结)

贪心的定义&#xff08;摘自百度百科&#xff09; 贪心算法&#xff08;greedy algorithm&#xff0c;又称贪婪算法&#xff09;是指&#xff0c;在对问题求解时&#xff0c;总是做出在当前看来是最好的选择。也就是说&#xff0c;不从整体最优上加以考虑&#xff0c;算法得到的…

4.2 SSAO算法 屏幕空间环境光遮蔽

一、SSAO介绍 AO 环境光遮蔽&#xff0c;全程Ambient Occlustion&#xff0c;是计算机图形学中的一种着色和渲染技术&#xff0c;模拟光线到达物体能力的粗略的全局方法&#xff0c;描述光线到达物体表面的能力。 SSAO 屏幕空间环境光遮蔽&#xff0c;全程 Screen Space Amb…

掌握组件缓存:解开Vue.js中<keep-alive>的奥秘

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…

【C++】搜索二叉树

提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、搜索二叉树概念二、搜索二叉树的操作1.插入2. 查找3. 中序遍历4. 删除 三、默认成员函数1.析构函数2.拷贝构造3. 赋值运算符重载 四、完整代码 一、搜索二叉树概…

「实用技巧」后端如何使用 Eolink Apikit 快速调试接口?

程序员最讨厌的两件事&#xff1a; 写文档 别人不写文档 写文档、维护文档比较麻烦&#xff0c;而且费时&#xff0c;还会经常出现 API 更新了&#xff0c;但文档还是旧的&#xff0c;各种同步不一致的情况&#xff0c;从而耽搁彼此的时间&#xff0c;大多数开发人员不愿意写…

抽奖之星软件,可用作随机分组分班、比赛顺序抽签摇号

抽奖之星软件简介 抽奖之星&#xff0c;极品晚会抽奖软件&#xff0c;大气美观&#xff0c;功能全面&#xff0c;请安装试用或咨询客服。支持作弊内定、指定中奖人、名单分组、中奖几率。(www.wsgsoft.com/plds/) 比赛顺序抽签设置 奖项设置&#xff1a;只一个奖项即可&…

分享一下怎么做一个商城小程序

如何制作一个商城小程序&#xff1a;功能解析、设计思路与实现方法 一、引言 随着移动设备的普及和微信小程序的兴起&#xff0c;越来越多的消费者选择在商城小程序上进行购物。商城小程序具有便捷、高效、即用即走等特点&#xff0c;为企业提供了新的销售渠道和推广方式。本…

Kubernetes Taint(污点) 和 Toleration(容忍)

Author&#xff1a;rab 目录 前言一、Taint&#xff08;污点&#xff09;1.1 概述1.2 查看节点 Taint1.3 标记节点 Taint1.4 删除节点 Taint 二、Toleration&#xff08;容忍&#xff09; 前言 Kubernetes 中的污点&#xff08;Taint&#xff09;和容忍&#xff08;Toleration…

学习笔记|正态分布|图形法|偏度和峰度|非参数检验法|《小白爱上SPSS》课程:SPSS第三讲 | 正态分布怎么检验?看这篇文章就够了

目录 学习目的软件版本原始文档为什么要假设它服从正态分布呢?t检验一、图形法1、频数分布直方图解读 2、正态Q-Q图操作解读 3、正态P-P图SPSS实战操作解读 二、偏度和峰度解读&#xff1a; 三、非参数检验法注意事项 四、规范表达五、小结划重点 学习目的 SPSS第三讲 | 正态…

Shopee流量和销量不佳?或许你没有掌握正确的引流方法

很多卖家做了很久&#xff0c;但是发现流量和销量都没怎么增长&#xff0c;今天陈哥就分享一下如何正确的引流。 以下是一些有效的引流策略&#xff1a; 1. 站内引流&#xff1a;选择高性价比的潮流商品&#xff0c;根据目标客户群和重点品类进行选品。优化商品名称和描述&am…

Power BI 傻瓜入门 18. 让您的数据熠熠生辉

本章内容包括&#xff1a; 配置Power BI以使数据增量刷新发现使用Power BI Desktop and Services保护数据集的方法在不影响性能和完整性的情况下管理海量数据集 如果有更新的、更相关的数据可用&#xff0c;旧数据对组织没有好处。而且&#xff0c;老实说&#xff0c;如果数据…

设计模式_观察者模式

观察者模式 介绍 设计模式定义案例问题堆积在哪里解决办法观察者是行为型设计模式 多个对象 观察 1个对象小强考试完 成绩公布了 家长/同学得知成绩后 做出不同反应一个一个通知很麻烦 先通知谁 也有讲究的 信息发布方 抽象出一个信息管理类 负责管理监听者 类图 代码 Obse…

学习视频剪辑:如何从指定时段快速抽出视频图片!高效技巧分享

随着数字媒体的普及&#xff0c;越来越多的人开始接触视频剪辑。在视频剪辑过程中&#xff0c;有时候我们需要从指定时段快速抽出视频图片。这不仅可以帮助我们提高剪辑效率&#xff0c;还可以让我们的视频更加丰富多彩。本文将分享一些高效技巧&#xff0c;帮助你轻松实现从指…

尚未解决:use_python()和use_virtualenv()的使用

reticulate包为Python和R之间的互操作性提供了一套全面的工具。该包包含以下功能&#xff1a; 以多种方式从R调用Python&#xff0c;包括RMarkdown、获取Python脚本、导入Python模块以及在R会话中交互使用Python。 R和Python对象之间的转换&#xff08;例如&#xff0c;R和Pan…

Three.js 开发引擎的特点

Three.js 是一个流行的开源 3D 游戏和图形引擎&#xff0c;用于在 Web 浏览器中创建高质量的三维图形和互动内容。以下是 Three.js 的主要特点和适用场合&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作…