【数据结构与算法】LeetCode：day4

1. 各位相加

我的思路：

如果 num < 10 则直接返回 num
如果 num > 10 ，则将 num 各位相加得到 res
1. res < 10 直接返回
2. res >= 10 带入函数进行递归

我的代码：

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

执行结果：

感觉方法有点笨，肯定有更好的方法！

更好的方法：

看了下 Discuss ，原来要求的数叫做数字根，看下维基百科的定义。

在数学中，数根(又称位数根或数字根Digital root)是自然数的一种性质，换句话说，每个自然数都有一个数根。

数根是将一正整数的各个位数相加（即横向相加），若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于十为止，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。

例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。

然后是它的用途。

数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。

数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。

另外，数根也可以用来判断数字的整除性，如果数根能被3或9整除，则原来的数也能被3或9整除。

接下来讨论我们怎么求出树根。

我们把 1 到 30 的树根列出来。
1
2
原数: 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
数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3 
可以发现数根 9 个为一组， 1 - 9 循环出现。我们需要做就是把原数映射到树根就可以，循环出现的话，想到的就是取余了。

结合上边的规律，对于给定的 n 有三种情况。

n 是 0 ，数根就是 0。

n 不是 9 的倍数，数根就是 n 对 9 取余，即 n mod 9。

n 是 9 的倍数，数根就是 9。

我们可以把两种情况统一起来，我们将给定的数字减 1，相当于原数整体向左偏移了 1，然后再将得到的数字对 9 取余，最后将得到的结果加 1 即可。

原数是 n，树根就可以表示成 (n-1) mod 9 + 1，可以结合下边的过程理解。
1
2
3
4
原数: 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
偏移: 0 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 
取余: 0 1 2 3 4 5 6 7 8  0  1  2  3  4  5  6  7  8  0  1  2  3  4  5  6  7  8  0  1  2  
数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3 
所以代码的话其实一句就够了。

作者：windliang
链接：https://leetcode-cn.com/problems/add-digits/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3

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

2. 字符串相加

我的思路：

受到昨天 二进制求和 的启发，二进制求和与十进制求和本质是一样的，故可搬用二进制求和的那一套！

我的代码：

class Solution {
    public String addStrings(String num1, String num2) {
        int carry = 0;
        int length = num1.length() > num2.length() ? num1.length() : num2.length();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            carry += num1.length() > i ? (num1.charAt(num1.length() - 1 - i) - '0') : 0;
            carry += num2.length() > i ? (num2.charAt(num2.length() - 1 - i) - '0') : 0;
            sb.append(carry % 10);
            carry /= 10;
        }
        if (carry > 0) sb.append("1");
        // 记得最后将字符串反转
        sb.reverse();
        return sb.toString().isEmpty() ? "0" : sb.toString();
    }
}

执行结果：

其他人的解答都大抵与之相似！

3. 不用加号的加法

解体思路：

二进制位异或运算相当于对应位相加，不考虑进位
比如： 1 ^ 1 = 0 —> 1 + 1 = 0 (当前位值为0，进一位)
1 ^ 0 = 1 —> 1 + 0 = 1 (当前位值为1)
0 ^ 0 = 0 —> 0 + 0 = 0 (当前位值为0)

二进制位与运算相当于对应位相加之后的进位
比如： 1 & 1 = 1 —> 1 + 1 = 0 (当前位的值进一位)
1 & 0 = 0 —> 1 + 0 = 1 (当前位的值不进位)
0 & 0 = 0 —> 0 + 0 = 0 (当前位的值不进位)

两个数相加：对应二进制位相加的结果 + 进位的结果
比如：3 + 2 –> 0011 + 0010
0011 ^ 0010 = 0001
0011 & 0010 = 0010 需要进位变成 0100 也就是<<1
当进位之后的结果为0时，相加结束。

作者：ba-xiang
链接：https://leetcode-cn.com/problems/add-without-plus-lcci/solution/go-wei-yun-suan-by-ba-xiang/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现：

递归

class Solution {
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        int sum = a ^ b;
        int carry = (a & b) << 1;
        return add(sum,carry);
    }
}

循环

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int sum = (a ^ b);
            int carry = (a & b) << 1;
            a = sum;
            b = carry;
        }

        return a;
    }
}

4. 数组形式的整数加法

我的思路：

大体思路与前面做过的 二进制加法 、 字符串相加 一致，稍作改动

返回值是 List<Integer> ，所以我们可以直接用 LinkedList 存储新的数组！

我的代码：

class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int carry = 0;
        LinkedList list = new LinkedList(); 
        int len = A.length > String.valueOf(K).length() ? A.length : String.valueOf(K).length();
        for (int i = 0; i < len; i++) {
            carry += i < A.length ? A[A.length - i -1] : 0;
            carry += K % 10;
            list.addFirst(carry % 10);
            K /= 10;
            carry /= 10;
        }
        if (carry > 0) list.addFirst(1);
        return list;
    }
}

执行结果：

官方解法：

class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int N = A.length;
        int cur = K;
        List<Integer> ans = new ArrayList();

        int i = N;
        // 退出循环条件为：数组越界、整数除尽
        while (--i >= 0 || cur > 0) {
            if (i >= 0)
                cur += A[i];
            ans.add(cur % 10);
            cur /= 10;
        }

        Collections.reverse(ans);
        return ans;
    }
}

/**
作者：LeetCode
链接：https://leetcode-cn.com/problems/add-to-array-form-of-integer/solution/shu-zu-xing-shi-de-zheng-shu-jia-fa-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/