求1+2+...+n

发表于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，面试题64.求 1 + 2 + … + n

先看题目描述

题目描述的很清楚，就不赘述了

一开始我想的是用平均计算法，用移位运算符代替乘除运算，但发现还是有问题，后来看了题解才知道可以利用短路，用递归运算的方法解决

算法和思路

计算 1 + 2 + … + n的计算方法主要有三种：平均计算，迭代，递归

方法一：平均计算

问题：此计算必须使用乘除法，不可取

1
2
3
public int sumNums(int n) {
    return (1 + n) * n / 2;
}

方法二：迭代

问题：此计算需用到 for，while 等关键字，不可取

1
2
3
4
5
6
public int sumNums(int n) {
    int res = 0;
    for(int i = 1; i <= n; i++)
        res += i;
    return res;
}

方法三：递归

问题：终止递归条件需要使用 if 或 switch等判断语句，不可取

思考：除了 if 或 switch等判断语句，能不能用其他方法来终止递归

1
2
3
4
5
public int sumNums(int n) {
    if(n == 1) return 1;
    n += sumNums(n - 1);
    return n;
}

这里可以利用逻辑运算符的短路效应来终止递归

常见的逻辑运算符有三种，即 &&，|| 和 !，而其有重要的短路效应，如下所示：

A && B，当 A 为 false 时，则 B 不会执行，直接判断 A && B 的结果为 false

A || B，当 A 为 true 时，则 B 不会执行，直接判断 A || B 的结果为 true

那么我们想实现当 n = 1时，终止递归，n > 1时，递归不终止的需求，可以利用 

1
n > 1 && n += sumNums(n - 1) > 0

也可以利用

1
n == 1 || n += sumNums(n - 1) > 0

算法源码

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

用 boolean x = n == 1 || (n += sumNums(n - 1)) > 0 也可以