leetcode 258. Add Digits

雨点打透心脏的1/2处 2022-06-08 13:24 93阅读 0赞

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?

题意很简单，最简单的做法就是使用字符串，但是题意说可以使用公式之类的，我是参考网上的做法。

代码如下：

/*
     * 这个使用Java的字符串技巧最方便
     * */
    public class Solution
    {
        /*
         * 循环做法，使用字符串最方便
         * */
        public int addDigitsByLoop(int num) 
        {
            String numStr=num+"";
            while(numStr.length()>1)
            {
                int sum=0;
                for(int i=0;i<numStr.length();i++)
                    sum+=Integer.parseInt(""+numStr.charAt(i));
                numStr=sum+"";
            }
            return Integer.parseInt(numStr);
        }
    
        int floor(int x) 
        {
            return (x - 1) / 9;
        }
    
        /*
         * 这个是利用公式直接计算，很棒，但是想不到
         * */
        int addDigits(int num) 
        {
            return num - 9 * floor(num);
        }
    }

下面是C++的做法，就是写一个两层循环，直接计算即可，代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int addDigits(int num)
        {
            if (num <= 9)
                return num;
    
            while (num >= 10)
            {
                int sum = 0;
                while (num > 0)
                {
                    sum += num % 10;
                    num /= 10;
                }
                num = sum;
            }
            return num;
        }
    };