面试题64 求1+2+...+n

发表于 | 分类于 |

面试题64 求1+2+...+n

难度：中等

平台：leetcode

Description

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3 输出: 6 示例 2：

输入: n = 9 输出: 45

限制：

1 <= n <= 10000

https://leetcode-cn.com/problems/qiu-12n-lcof

MySolution

这道题算是一股清流，所以记录下来。刚看到题有点懵，先想到的是求和公式n*(n+1)/2但是不能用乘除法，除2操作可以用>>=1代替，但是n*(n+1)一下子没有想到代替的办法（后来在题解中找到，本文作为其他解法给出）在公式法无法进行时想到了递归法，因为递归出口可以用&&的一个性质实现——如果左边为假便不判断右边表达式（后来在题解里发现这个称为逻辑运算符的短路性质,||也有类似性质）

1
2
3
4
5
6
7
class Solution {
    public int sumNums(int n) {
        boolean f;
        f = n > 0 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

OtherSolutions

接之前讲的公式法，在实现n*(n+1)时用到了俄罗斯农民乘法，原理简单来说就是若A*B，我们将A*2作为新A的同时B/2作为新B，如果原B为偶数则由于乘法交换律结果不变，如果原B为奇数由于自动取下界我们则丢失了一个原A，需要在最后结果补上一个原A。如此反复到B为1，此时补上所有中途丢失的数即为结果。对应到2进制，我们可以用左移一位和右移一位代替*2与/2操作，B的二进制展开是否为1作为是否需补的标志，同时由于不能使用循环，结合数据范围，我们需要手动展开14位最终实现求和公式n*(n+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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    public int sumNums(int n) {
        int ans = 0, A = n, B = n + 1;
        boolean flag;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        return ans >> 1;
    }
}

来源：LeetCode-Solution

有的没的

通过这道题，发现自己对于位运算的知识不熟悉，解题时不能及时想到。可见还有许多这样平时不常常接触但是有用的知识点需要我去熟悉。