首页 / GIT / LeetCode——Add Digits

LeetCode——Add Digits

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode——Add Digits，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1216字，纯文字阅读大概需要2分钟。

内容图文

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)，恐怕我也就直接模拟去解决这道题了。

考虑到O(1)肯定不能用模拟来求解了，经过一番推导最终求出找出了规律，推导如下：

假设原来的数字为X,X可以表示为：

X=fn*Xn+fn-1*Xn-1+...+f1*x1 , Xn=pow(10,n-1);

对X进行一次操作后得到X‘：

X’=fn+fn-1+...f1

X-X‘：

X-X‘ = fn*(Xn - 1) + fn-1*(Xn-1 - 1) + ... f1*(X1 - 1)
     = fn*9···99 + fn-1*9···9 + ... f1*0
     = 9*( fn*1···11 + fn-1*1···1 + ... f2*1 + f1*0 )
     = 9*S (S is a non-negative integer)

 

每一次都比原来的数少了个9的倍数！

还要考虑一些特殊情况，最终程序：

             1
            class
             Solution {

             2
            public
            :

             3
            int addDigits(int num) {
 4/* 5  X=fn*Xn+fn-1*Xn-1+...+f1*x1 , Xn=pow(10,n-1);
 6  Every operator make X=> X‘=fn+fn-1+...f1
 7   X-X‘ =fn*(Xn - 1)+fn-1*(Xn-1 - 1)+...f1*(X1 - 1)
 8        =fn*9···99+fn-1*9···9+..f1*0
 9        =9*(fn*1···11+fn-1*1···1+...f2*1+f1*0)
10          =9*S (S is a non-negative integer)
11  => Everytime reduce a number of multiple 9
12*/13if(num==0) return0;
14int t=num%9;
15return (t!=0)?t:9;
16    }
17 };

 

原文：http://www.cnblogs.com/wrj2014/p/4981350.html

内容总结

以上是互联网集市为您收集整理的LeetCode——Add Digits全部内容，希望文章能够帮你解决LeetCode——Add Digits所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1073141.html

来源：【匿名】