宝宝也能看懂的 leetcode 周赛 - 169 - 1
2020/1/4 5:21:21
本文主要是介绍宝宝也能看懂的 leetcode 周赛 - 169 - 1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1304. Find N Unique Integers Sum up to Zero
Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 题解。
这里是第 169 期的第 1 题,也是题目列表中的第 1304 题 -- 『Find N Unique Integers Sum up to Zero』
题目描述
Given an integer n
, return any array containing n
unique integers such that they add up to 0.
Example 1:
Input: n = 5 Output: [-7,-1,1,3,4] Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].
Example 2:
Input: n = 3 Output: [-1,0,1]
Example 3:
Input: n = 1 Output: [0]
Constraints:
1 <= n <= 1000
官方难度
EASY
解决思路
题目内容很简单,返回一个符合要求的数组即可,要求包含几点:
- 长度是
n
- 不能有重复的数字
- 所有数字和为 0
看完要求之后,我第一反应就是,一正一负不就正好是 0 咯。
直接方案
基于以上思路,我们可以得到一个直接的解题方案。需要注意的是,对于奇数来说,再额外补充一个 0 即可。
我这里的代码额外做了一点小优化,即通过一个定长的数组来避免数组自动伸缩带来的开销。
const sumZero = n => { const ret = new Int16Array(n); for (let i = 1; i <= Math.floor(n / 2); ++i) { ret[i - 1] = i; ret[n - i] = -i; } return ret; };
换个思路
我们回看一下题目的限制条件,n
的取值范围是 [1,1000]
,全部加在一起求和是 500500,是一个安全的 int32 整数。于是一个方案孕育而生,我们直接添加 n - 1
个连续的数字,然后把它们求和的负数放进去即可。
const sumZero = n => { const ret = new Int32Array(n); for (let i = 1; i < n; ++i) { ret[i] = i; } ret[0] = -((1 + n) * n / 2 - n); return ret; };
再换个思路
我们尝试写几组可能的解来看看:
n = 1, [0] n = 2, [-1, 1] n = 3, [-2, 0, 2] n = 4, [-3, -1, 1, 3] n = 5, [-4, -2, 0, 2, 4]
有没有觉得这是一个很熟悉的数组,反正我是印象在大学 C++ 教材里有题目要求输出这个数组,哈哈哈哈。
对于这个数组,我们尝试找一下规律应该就能发现,每个数字其实是符合这个公式的:
ret[i] = i * 2 - n + 1;
有了公式那么就直接写进代码即可。
const sumZero = n => { const ret = new Int16Array(n); for (let i = 0; i < n; ++i) { ret[i] = i * 2 - n + 1; } return ret; };
总结
第 169 期周赛的第一题,想得到 Accepted 是很简单的。所以这里尝试给出了几种不同的思路方向。当然我相信大家还会有更有意思的思路。>.<
相关链接
这篇关于宝宝也能看懂的 leetcode 周赛 - 169 - 1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09一定要避坑:关于微信H5分享,温馨提示你不要再踩坑了!!!
- 2024-05-09本地项目放到公网访问!炒鸡煎蛋!
- 2024-04-07金融企业区域集中库的设计构想和测试验证
- 2024-03-11前端CSS的工程化——掌握Sass这四大特性就够了
- 2024-02-21h5关联css样式(html怎么和css关联)-icode9专业技术文章分享
- 2024-02-07Firefox禁止远程字体加速网页加载及图标字体补充安装
- 2024-02-07一个菜鸡前端的3年总结-「2023」
- 2024-01-18最火前端Web组态软件(可视化)
- 2024-01-12程序员提效 x10 的必备开源“神器”
- 2024-01-11前端可以监控静态资源的时间吗-icode9专业技术文章分享