leetcode-258-Add Digits

题目描述:

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 111 + 1 = 2. Since 2 has only one digit, return it.

Follow up: Could you do it without any loop/recursion in O(1) runtime?

要完成的函数:

int addDigits(int num) 

说明:

1、暴力解法如下,应该不难看懂:

    int addDigits(int num) 
    {
        int result;
        while(!(num>=0&&num<=9))//不是单位数的情况就进入处理
        {
            result=0;
            while(num!=0)//得到新的num
            {
                result+=num%10;
                num/=10;
            }
            num=result;
        }
        return num;
    }

2、这道题目比较有意思的是,挑战能不能用O(1)的时间复杂度,也就是不用循环和递归的方法求得输出结果。

上述代码中,外层循环是用来不断地处理数的。不让用循环,也就意味着我们必须要从数学上寻求规律。

看一下笔者举的下述例子:

原数

0

1

2

3

4

5

6

7

8

9

对应的数

0

1

2

3

4

5

6

7

8

9

原数

10

11

12

13

14

15

16

17

18

19

对应的数

1

2

3

4

5

6

7

8

9

10/1

原数

20

21

22

23

24

25

26

27

28

29

对应的数

2

3

4

5

6

7

8

9

10/1

11/2

上述从1到9为一个循环,那么是不是后续的数字也会遵循这样的规律,从而最终得到在[1,9]之间的结果呢?

答案是肯定的。

因为我们假设一个比较大的两位数,比如ab,其实ab的值是a*10+b,那么对应的数应该是a+b。因为a和b都是正数,那么肯定对应之后的数要小于原来的数。除非a=0,那这时候由上述表格中第一行看得很清楚。

这样子每一个对应的数都小于原来的数,减小了9*a,那么不断地往前腾挪,最终必然到达[1,9]之间。

那么我们由上述表格可以很直观地得到一个结论:

假设要处理的数为n,则最终对应的数=(num-1)%9+1

原本我们可以直接num%9,但是对于num=9或者num=18这些9的整倍数,结论不符合,略微修改一下。

代码如下:

    int addDigits(int num) 
    {
        return 1 + (num - 1) % 9;
    }

PS:觉得有点奇怪,2中O(1)的做法实测8ms,1中循环迭代的做法实测7ms,竟然O(1)花费时间更长……

   有同学知道原因么?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-342-Power of Four

    chenjx85
  • leetcode-504-Base 7

    chenjx85
  • leetcode-367-Valid Perfect Square

    chenjx85
  • 【答疑解惑】c语言判断一个数是否为整数

    这个问题在现实中用到的概率还是比较少的,但是小伙伴有此疑问,我们用代码来做做练习 #include<stdio.h> int main(void) { ...

    程序员互动联盟
  • 利用爬虫和树莓派3打造自己的语音天气闹钟

    前言 前不久又一次一个人在他乡过了生日,悄悄买了一台树莓派3送给自己做生日礼物。终于算是实现了大学以来一直的一个小愿望。买回来之后当然不能让他落灰,于是就利用自...

    木制robot
  • 丑数

    一份执着✘
  • leetcode 31 Next Permutation

    @坤的
  • 用Java实现JVM第七章《方法调用和返回》

    本章节主要用java实现;方法调用指令、返回指令、解析方法符号引用、参数传递等。实现新的指令后我们的虚拟机就可以执行稍微复杂的运算并输出结果。

    小傅哥
  • leetcode-342-Power of Four

    chenjx85
  • 【每周一坑】校验文件哈希

    先说个通知,给参与了码上行动的同学:又一期展示学习成果的编程擂台活动开始了,即是练手的好机会,又能得到助教的全程支持,还可以得积分赢奖金。赶紧来报名吧!从课程首...

    Crossin先生

扫码关注云+社区

领取腾讯云代金券