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 条评论
登录 后参与评论

相关文章

来自专栏追不上乌龟的兔子

[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

2555
来自专栏Vamei实验室

Python基础08 面向对象的基本概念

Python使用类(class)和对象(object),进行面向对象(object-oriented programming,简称OOP)的编程。 面向对象的最...

2157
来自专栏编舟记

函数式编程简介

1900年,Hilbert 提出了数学界悬而未决的10大问题,后续陆续添加成了23个问题,被称为著名的 Hilbert 23 Problem。针对其中第2个决定...

1984
来自专栏C语言及其他语言

[每日一题]矩阵问题

今天给大家分享的是二维数组的基本用法,主要是利用数组对行列的控制 题目描述 求一个3×3矩阵对角线元素之和。 输入 矩阵 输出 主对角线 副对角线 元素和 ...

3237
来自专栏落影的专栏

程序员进阶之算法练习(二十五)

前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

3839
来自专栏数说工作室

1. PRXMATCH () | 提取文本数据,分析师小王初上手!

【SAS Says·扩展篇】分析师小王初上手! | 1. PRXMATCH () 本集目录: 0. 小王初上手 1. 初始PRXMATCH() 2. metac...

3236
来自专栏绿巨人专栏

Category Theory: 01 One Structured Family of Structures

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

1303
来自专栏儿童编程

编程之美——让你的电脑秒变绘画大师的几行代码(Python turtle)

今天很兴奋,只用了一小段Python turtle代码(附在文末)就把电脑变成了绘画大师,太神奇了。

1.1K4
来自专栏专注数据中心高性能网络技术研发

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

3429
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

2812

扫码关注云+社区

领取腾讯云代金券