网站建设需求分析,网页设计模板免费下载网站,顺企网app下载,泰安人才网招聘信息网电焊工给定一个非负整数 num#xff0c;反复将各个位上的数字相加#xff0c;直到结果为一位数。
示例:
输入: 38 输出: 2 解释: 各位相加的过程为#xff1a;3 8 11, 1 1 2。 由于 2 是一位数#xff0c;所以返回 2。 进阶: 你可以不使用循环或者递归#xff0c;且在 O(…给定一个非负整数 num反复将各个位上的数字相加直到结果为一位数。
示例:
输入: 38 输出: 2 解释: 各位相加的过程为3 8 11, 1 1 2。 由于 2 是一位数所以返回 2。 进阶: 你可以不使用循环或者递归且在 O(1) 时间复杂度内解决这个问题吗
时间复杂度为O(1)的解法
除个位外每一位上的值都是通过(91)进位的过程得到的想一下拨算盘进位 把整数n看成n样物品原本是以10个1份打包的现在从这些10个1份打包好的里面拿出1个让它们以9个为1份打包。 这样就出现了两部分的东西 原本10个现在9个1份的打包好的物品这些我们不用管 零散的物品它们还可以分成 从原来打包的里面拿出来的物品它们的总和 》 原来打包好的份数 》 10进制进位的次数 》 10进制下除个位外其他位上的值的总和 以10个为1份打包时打不进去的零散物品 》 10进制个位上的值 如上零散物品的总数就是第一次处理num后得到的累加值 如果这个累加值9那么如题就还需要将各个位上的值再相加直到结果为个位数为止。也就意味着还需要来一遍如上的过程。 那么按照如上的思路似乎可以通过n % 9得到最后的值 但是有1个关键的问题如果num是9的倍数那么就不适用上述逻辑。原本我是想得到n被打包成10个1份的份数打不进10个1份的散落个数的和。通过与9取模去获得那个不能整除的1作为计算份数的方式但是如果可以被9整除我就无法得到那个1也得不到个位上的数。 所以需要做一下特殊处理(num - 1) % 9 1 可以这么做的原因原本可以被完美分成9个为一份的n样物品我故意去掉一个那么就又可以回到上述逻辑中去得到我要的n被打包成10个一份的份数打不进10个一份的散落个数的和。而这个减去的1就相当于从在10个1份打包的时候散落的个数中借走的本来就不影响原来10个1份打包的份数先拿走再放回来都只影响散落的个数所以没有关系。 代码 class Solution { public int addDigits(int num) { return (num - 1) % 9 1; } }
