宝宝也能看懂的 leetcode 周赛 - 171 - 1
2020/1/19 5:19:47
本文主要是介绍宝宝也能看懂的 leetcode 周赛 - 171 - 1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1317. 将整数转换为两个无零整数的和
Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。
这里是第 171 期的第 1 题,也是题目列表中的第 1317 题 -- 『将整数转换为两个无零整数的和』
题目描述
「无零整数」是十进制表示中 不含任何 0 的正整数。
给你一个整数 n,请你返回一个 由两个整数组成的列表 [A, B]
,满足:
-
A
和B
都是无零整数 A + B = n
题目数据保证至少有一个有效的解决方案。
如果存在多个有效解决方案,你可以返回其中任意一个。
示例 1:
输入:n = 2 输出:[1,1] 解释:A = 1, B = 1. A + B = n 并且 A 和 B 的十进制表示形式都不包含任何 0 。
示例 2:
输入:n = 11 输出:[2,9]
示例 3:
输入:n = 10000 输出:[1,9999]
示例 4:
输入:n = 69 输出:[1,68]
示例 5:
输入:n = 1010 输出:[11,999]
提示:
2 <= n <= 10^4
官方难度
EASY
解决思路
题目的要求为,给定一个整数,需要返回把它当作和的一对不包含 0 的整数加数。
读完题目后,我的第一反应是,是不是有什么数学方法可以找到答案。摸摸猪鼻子,想了一会,没想到什么靠谱的方法。一定是小猪太苯了,蓝瘦 T_T
接下来把思路转向了偏计算机的方式。那么第一反应就是,暴力枚举。时间复杂度 O(n),应该能 AC,那就先试试吧。
枚举
这种思路其实非常直接,就是遍历一边所有可能的加数,然后判断它们是否包含 0 即可。由于题目对于返回的解没有要求,所以我们直接返回第一组遇到的解即可。具体流程如下:
- 从 1 开始遍历所有的加数。
- 判断该加数和对应的被加数是否包含 0。
- 返回遇到的第一个解。
不过这里可以做一点小小的优化。一方面是,在判断 0 的过程中,我们在除以 10 之后的取整操作可以直接用位运算实现。另一方面是,对于每一个整数,它是否包含 0 是一个客观的事实。所以我们可以针对所有的测试用例进行全局的缓存,避免不必要的计算。并且由于题目限制了范围是 [2, 10^4]
,所以我们可以用一个固定长度的数组来进行记录。
具体代码如下:
const memo = new Uint8Array(10000); const helper = x => { if (memo[x] !== 0) return memo[x] === 1; while (x > 0) { if (x % 10 === 0) { memo[x] = 2; return false; } x = x / 10 << 0; } memo[x] = 1; return true; }; const getNoZeroIntegers = n => { let m = 0; while (n--) { if (helper(++m) && helper(n)) return [m, n]; } };
非枚举
熟悉小猪的小伙伴可能会猜到,如果只给一个 brute force 方案,小猪一定不会满足哒 >.<
于是在一番绞尽脑汁之后,小猪决定先去玩几盘吃鸡, 小猪把思路从新放回了题目条件本身。如果想把一个整数变成一个不包含 0 的整数,那么可能有两种情况。第一种,这个数本身就不包含 0,那么我们祝它新年快乐。第二种,其中某一位数字是 0,对于这种情况,我们详细分析一下。
首先,这个 0 不可能是最高位,因为题目给定的是普通的整数。那么我们如果想要把它变成别的数字的话,要么是增,要么是减。由于我们是在寻找加数,所以只能选择减。并且由于不是先导 0,所以减是安全的。减的数值基于当前位置来确定,例如百位的话就减 100,十位的话就减 10。这样我们就把当前位置的 0 替换成了非 0。
不过这里需要注意的是,我们的一对加数都需要进行同步的加减运算,并且都需要反复进行是否包含 0 的验证。具体流程如下:
- 把 1 和
n - 1
作为初始值。 -
判断它们是否包含 0:
- 如果包含的话,找到 0 的位置,并减去对应位置的基数,回到步骤 2。
- 如果不包含,祝它新年快乐。
- 输出结果。
基于这个流程,我们可以实现类似这样的代码:
const helper = x => { let digit = 0; while (x > 0) { if (x % 10 === 0) break; x = x / 10 << 0; ++digit; } return 10 ** digit; }; const getNoZeroIntegers = n => { let x = 1, y = n - 1; while (true) { let num = helper(y); if (num < y) { y -= num; x += num; continue; } num = helper(x); if (num > x) break; y -= num; x += num; } return [x, y]; };
这段代码暂时 beats 100%。
总结
周赛第一题,惯例送保底分。不过这道题我觉得用枚举的方式已经 OK 了,后面提供的非枚举的思路只是供小伙伴们娱乐一下。因为虽然不知道为什么,不过我总觉得这样去处理问题有点怪怪的。
嘛,可能有很多小伙伴已经回家啦,或者被堵在了回家的路上。这里还是提前送上小猪诚挚的祝福,希望大家在新的一年里,发际线一定要平安哦。么么哒 >.<
相关链接
这篇关于宝宝也能看懂的 leetcode 周赛 - 171 - 1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解