p258

发表于 | 分类于 |

LeetCode P258 Add Digits 题解

1.题目：

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?

题意：

输入一个数字，将这个数字所有位数相加一直到得到一个小于10的数，返回这个数
希望复杂度为O(1)

2.解题思路:

一般最开始都会想用个循环就出来了，然复杂度要求O(1)，即没有循环。
看到这样的复杂度发觉肯定是有规律可以推出公式的，尝试。
11 ：2，比原来减少了9
22 ：4，比原来减少了18
可以这样想 一个两位数变成个位加十位 减少十位上的数字(10-1)
……
反之可以推，知道这个数ans,原来的数n=9k+ans；得到公式

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
package leetcode;

import java.util.Scanner;


/**
 * 
 * @author ZhangMengRou
 *
 */
public class p292 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String a = in.nextLine();
		String[] list = a.split(" ");
		int[] al = new int[list.length];
		for (int i=0;i<list.length;i++)
		{
			al[i]=Integer.parseInt(list[i]);
		}
		int ans = singleNumber(al);
		System.out.print(ans);
	}

	public static int singleNumber(int[] nums) {
		
		int as = 0;
		for (int i = 0; i < nums.length; i++) {
			as = as ^ nums[i];
		}
		return as;
        
    }

}


4.一些总结：

第一次提交Wrong了。。。忘记考虑k*9%9=0,然答案应该是9