招标网站的服务费怎么做分录,苏州营销型网站建设方案,长沙网站建站公司,修改 wordpress 模版258. 各位相加
难度#xff1a;简单
题目
给定一个非负整数 num#xff0c;反复将各个位上的数字相加#xff0c;直到结果为一位数。返回这个结果。
示例 1:
输入: num 38
输出: 2
解释: 各位相加的过程为#xff1a;
38 -- 3 8 -- 11
11 -- 1 1 --简单
题目
给定一个非负整数 num反复将各个位上的数字相加直到结果为一位数。返回这个结果。
示例 1:
输入: num 38
输出: 2
解释: 各位相加的过程为
38 -- 3 8 -- 11
11 -- 1 1 -- 2
由于 2 是一位数所以返回 2。示例 2:
输入: num 0
输出: 0提示
0 num 2^31 - 1
**进阶**你可以不使用循环或者递归在 O(1) 时间复杂度内解决这个问题吗
个人题解
方法一打表法
思路
显然由题目可知这是一道找规律的题目先编写不管复杂度的程序将10000以下对应的的答案打印出来观察规律
public class Main {public static void main(String[] args) {Main main new Main();for (int i 0; i 10000; i) {System.out.println(main.addDigits(i) i);}}public int addDigits(int num) {while (num 10) {int sum 0;while (num 10) {sum num % 10;num / 10;}num sum num;}return num;}}观察输出除了小于 10 的数后面数字都是一直从 1~9 逐位递增观察规律当能被 9 整除时对应答案是 9否则是 除以9 的余数则编写以下代码
class Solution {public int addDigits(int num) {if (num 10) {return num;}return num % 9 0 ? 9 : num % 9;}
}复杂度分析
时间复杂度O(1)空间复杂度O(1)
官方题解
方法一模拟
class Solution {public int addDigits(int num) {while (num 10) {int sum 0;while (num 0) {sum num % 10;num / 10;}num sum;}return num;}
}复杂度分析
时间复杂度O(log num)空间复杂度O(1)
方法二数学
从数学角度分析答题题解字数很多本人不想看想看的可直接点击后面链接查看
class Solution {public int addDigits(int num) {return (num - 1) % 9 1;}
}复杂度分析
时间复杂度O(1)空间复杂度O(1)
作者力扣官方题解 链接https://leetcode.cn/problems/add-digits/solutions/1301157/ge-wei-xiang-jia-by-leetcode-solution-u4kj/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
