801 - Hello Algorithm

使用位运算求和

date: 2020-06-19

今天为大家分享一道本应很简单的题目，但是却因增加了特殊条件，而大幅增加了难度。话不多说，直接看题。

01、题目示例

该题很容易出现在各大厂的面试中，属于必须掌握的题型。

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

示例 1：

输入: n = 3 输出: 6

示例 2：

输入: n = 9 输出: 45

限制：

1 <= n <= 10000

02、题目分析

这道题目出自《贱指offer》，因为比较有趣，就拿来分享给大家。

题目上手，因为不能使用公式直接计算（公式中包含乘除法），所以考虑使用递归进行求解，但是递归中一般又需要使用if来指定返回条件（这里不允许使用if），所以没办法使用普通的递归思路。那该怎么办呢？这里我们直接上代码（本题将展示多个语言），再进行分析。

java

//JAVA
class Solution {
    public int sumNums(int n) {
        boolean b = n > 0 && ((n  = sumNums(n - 1)) > 0);
        return n;
    }
}

首先我们了解一下 && 的特性，比如有 A&&B

如果A为true，返回B的布尔值（继续往下执行）
如果A为false，直接返回false（相当于短路）

利用这一特性，我们将递归的返回条件取非然后作为 && 的第一个条件，递归主体转换为第二个条件语句。我知道肯定有人又会懵圈了，所以我们绘图说明。假若这里n=3，大概就是下面这样：

这里还有一点要强调的就是，受制于各语言的语法规则，我们需要做一些额外的处理。比如Java，这里如果去掉前面的变量申明，就会直接报错。

但是如果是C 就没有这样的问题：

//c  
int sumNums(int n) {
    n && (n  = sumNums(n-1));
    return n;
}

python就是下面这样：

python

//py3
class Solution:
    def sumNums(self, n: int) -> int:
        return n and n  self.sumNums(n-1)

Go怎么搞？

//go 
func plus(a *int, b int) bool { 
    *a  = b 
    return true 
} 
func sumNums(n int) int {
    _ = n > 0 && plus(&n, sumNums(n - 1)) 
    return n10}

什么，还要我给一个PHP的？惹不起..惹不起...大佬请拿走...

php

//PHP
class Solution {
    function sumNums($n) {
        $n > 0 && $n  = $this->sumNums($n - 1);
        return $n;
    }
}

03、额外福利

另外，我还看到这样一个解法，感觉很有趣（思想很简单）。因为不是自己写的，所以这里得额外说明，咱不能白嫖，对不？（所以你们这些白嫖的不去给我点个star嘛...）

//go
func sumNums(n int) int {
    return (int(math.Pow(float64(n),float64(2))) n)>>1
}

执行结果：