888. Fair Candy Swap

2023-12-21 16:08
文章标签 swap 888 fair candy

本文主要是介绍888. Fair Candy Swap,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

888. 公平的糖果交换

爱丽丝和鲍勃有不同大小的糖果棒:A[i] 是爱丽丝拥有的第 i 块糖的大小,B[j] 是鲍勃拥有的第 j 块糖的大小。

因为他们是朋友,所以他们想交换一个糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)

返回一个整数数组 ans,其中 ans[0] 是爱丽丝必须交换的糖果棒的大小,ans[1] 是 Bob 必须交换的糖果棒的大小。

如果有多个答案,你可以返回其中任何一个。保证答案存在。

 

示例 1:

输入:A = [1,1], B = [2,2]
输出:[1,2]

示例 2:

输入:A = [1,2], B = [2,3]
输出:[1,2]

示例 3:

输入:A = [2], B = [1,3]
输出:[2,3]

示例 4:

输入:A = [1,2,5], B = [2,4]
输出:[5,4]

 

提示:

  • 1 <= A.length <= 10000
  • 1 <= B.length <= 10000
  • 1 <= A[i] <= 100000
  • 1 <= B[i] <= 100000
  • 保证爱丽丝与鲍勃的糖果总量不同。
  • 答案肯定存在。

解法一

//时间复杂度O(n), 空间复杂度O(n)
class Solution {
public:vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {unordered_set<int> us1, us2;int sum1 = 0, sum2 = 0;for(int num : A) {us1.insert(num);sum1 += num;}for(int num : B) {us2.insert(num);sum2 += num;}int diff = (sum1 - sum2) / 2;//差一定是偶数for(int elem : us1) {if(us2.count(elem - diff)) return {elem, elem - diff};}return {};}
};

思路:

  1. 分别对数组A、B求和sum1, sum2;同时使用两个哈希set对出现过的元素做记录;
  2. 求两数组和之差的一半,记为diff;
  3. 遍历其中一个set的每个元素elem,查找另一个set中是否存在元素值为elem + diff,若有则返回。
2019/07/26 23:10

这篇关于888. Fair Candy Swap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/520626

相关文章

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

linux定时监听ssh服务是否启动-------麒麟操作系统永久关闭swap

linux监听ssh服务是否启动 1、监听脚本2、定时任务3、麒麟操作系统,永久关闭swap 1、监听脚本 #在/usr/local/bin目录下新建脚本文件 cd /usr/local/bintouch check_sshd.sh#给可执行权限chmod +x /usr/local/bin/check_sshd.sh 脚本内容如下: #!/bin/bashs

日常避坑指南:如何合理利用Swap优化MongoDB内存管理

MongoDB作为一款高性能的NoSQL数据库,广泛应用于大数据处理和实时应用中。然而,面对批量数据写入时,MongoDB对内存的需求极为苛刻,尤其是在测试服务器或资源受限的环境下,容易引发系统性能问题。本文将探讨如何通过合理利用Swap来优化MongoDB的内存管理,确保系统的稳定运行。 问题背景:内存不足与系统卡死 在测试环境中,当MongoDB执行大规模数据读写操作时,服务器负载常常

AI预测体彩排3采取888=3策略+和值012路或胆码测试9月2日升级新模型预测第70弹

经过近70期的测试,当然有很多彩友也一直在观察我每天发的预测结果,得到了一个非常有价值的信息,那就是9码定位的命中率非常高,已到达90%的命中率,这给喜欢打私菜的朋友提供了极高价值的预测结果~当然了,大部分菜友还是走的正常渠道,因此,得想办法进行缩水,尽可能少的缩少注数。         当然了,经过近70期的观察和内部测试,发现了如果不考虑8码定位,而是重点把大底放在9码定位上

Linux内存、Swap、Cache、Buffer详细解析

点击上方“朱小厮的博客”,选择“设为星标” 后台回复"书",获取 后台回复“k8s”,可领取k8s资料 来源:r6d.cn/abK6G 1. 通过free命令看Linux内存 total:总内存大小。 used:已经使用的内存大小(这里面包含cached和buffers和shared部分)。 free:空闲的内存大小。 shared:进程间共享内存(一般不会用,可以忽略)。 buffers:

CF C. Candy Store

原题链接:Problem - C - Codeforces 题意:多测,先给出n代表n种糖果,每种糖果分别给出数量和单价,可以将糖果平均分成若干袋,每一袋的的价格是一袋糖果数量×单价,对于每一种糖果都求出一袋的价格,对于每种糖果都需要用标签贴出一袋的价格,但是如果相邻的糖果价格相同,那么就可以用一个标签来代表价格,问最少使用几个标签。 思路:如果一段糖果价格是一样的,那么设置价格为cost。因

HDU 2819 Swap (行列匹配+输出解)

题意:能否使对角线上全是1 ,这个简单直接按行列匹配,难在路径的输出,我们知道X,Y左右匹配完了之后,不一定是1–1,2–2,3–3……这样的匹配。可能是1–3,2–1,3–2,我们要把他们交换成前一种的匹配形式,也就是路径的答案,再有矩阵的一些关于秩的性质,行变换和列变换是等价的。 #include<cstdio>#include<iostream>#include<algorithm>

AI预测福彩3D采取888=3策略+和值012路或胆码测试8月29日新模型预测第71弹

经过70期的测试,当然有很多彩友也一直在观察我每天发的预测结果,得到了一个非常有价值的信息,那就是9码定位的命中率非常高,近70期一共只错了7次,这给喜欢打私房菜的朋友提供了极高价值的预测结果~当然了,大部分菜友还是走的正常渠道,因此,得想办法进行缩水,尽可能少的缩少注数。         当然了,经过70期的观察和内部测试,发现了如果不考虑8码定位,而是重点把大底放在9码定位

条款25 考虑写出一个不抛异常的swap函数

总结:      如果 std::swap 对于你的类型来说是低效的,请提供一个 swap 成员函数,并确保你的 swap 不会抛出异常。      如果你提供一个成员 swap,请同时提供一个调用成员swap的非成员swap。对于类(非模板),还要特化 std::swap。      调用swap时,请为std::swap使用一个using声明式,然后在调用 swap时不使用任何names

【888题竞赛篇】第六题,2023ICPC济南-来自知识的礼物(Gifts from Knowledge)

这里写自定义目录标题 更多精彩内容256题算法特训课,帮你斩获大厂60W年薪offer 原题2023ICPC济南真题来自知识的礼物B站动画详解 问题分析思路分析算法实现代码详解标准代码程序C++代码Java代码Python代码Javascript代码 复杂度分析时间复杂度空间复杂度 总结 更多精彩内容 这里是带你游历编程世界的Dashcoding编程社,我是Dash/北航硕士/