关关的刷题日记81 – Leetcode 258. Add Digits

关关的刷题日记81 – 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 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

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

题目的意思是给定一个非负整数,不断地重复这个过程:将其每一位数字加起来求和。直到最终得到的结果仅有一位数字。不用循环或者递归能否实现时间复杂度为O(1)的做法?

方法1:写了一个循环版本的。

class Solution {
public:
    int addDigits(int num) {
        int re=0;
        while(1)
        {
            while(num>0)
            {
                re+=num%10;
                num/=10;
            }
            if(re<10)
               return re;   
            num=re;
            re=0;
        }
        return 0;
    }
};

方法2:写了一个递归版本的。

class Solution {
public:
    int addDigits(int num) {
        int re = 0;
        while (num > 0)
        {
            re += num % 10;
            num /= 10;
        }
        if (re < 10)
            return re;
        return addDigits(re);
    }
};

方法3:不用循环或者递归能否实现时间复杂度为O(1)的做法。看了一下答案,这道题实际上是求给定数的树根:a的数根b = ( a - 1) % 9 + 1。

class Solution {
public:
    int addDigits(int num) {
        return (num-1)%9+1;
    }
};

人生易老,唯有陪伴最长情,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-12-30

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

关关的刷题日记88 – Leetcode 367.Valid Perfect Square

关关的刷题日记88 – Leetcode 367.Valid Perfect Square 题目 Given a positive integer num, w...

3049
来自专栏专知

【 关关的刷题日记47】Leetcode 38. Count and Say

关关的刷题日记47 – Leetcode 38. Count and Say 题目 The count-and-say sequence is the sequ...

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

【每日一题】1443 [蓝桥杯][历届试题]数字游戏

每日一题,一年365天,想不成为大神都难! 题目描述 栋栋正在和同学们玩一个数字游戏。 游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数...

3055
来自专栏编程

零基础学习人工智能之Python篇1-Python定义

学习Python首先咱要明白Python是什么 定义: Python是一种面向对象的解释型计算机程序设计语言 我们分解下Python的定义,主要是要理解面向对象...

2156
来自专栏大数据钻研

JavaScript 世界万物诞生记

一. 无中生有 起初,什么都没有。 造物主说:没有东西本身也是一种东西啊,于是就有了null: ? 现在我们要造点儿东西出来。但是没有原料怎么办? 有一个声音说...

3448
来自专栏专知

【LeetCode 136】 关关的刷题日记32 Single Number

关关的刷题日记32 – Leetcode 136. Single Number 题目 Given an array of integers, every ele...

3516
来自专栏专知

关关的刷题日记85 – Leetcode 326. Power of Three

关关的刷题日记85 – Leetcode 326. Power of Three 题目 Given an integer, write a function t...

37310
来自专栏吴伟祥

学习数据结构的原因&方法 原

761
来自专栏专知

【 关关的刷题日记53】 Leetcode 100. Same Tree

关关的刷题日记53 – Leetcode 100. Same Tree 题目 Given two binary trees, write a function ...

3307
来自专栏专知

【LeetCode 242】 关关的刷题日记36 Valid Anagram

关关的刷题日记36 – Leetcode 242. Valid Anagram 题目 Given two strings s and t, write a fu...

3569

扫码关注云+社区

领取腾讯云代金券