每天题解:[LeetCode] :面试题64. 求1+2+…+n

Author Avatar
清水雅然君 05月 24,2020

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

题目地址

题目描述

面试题64. 求1+2+…+n
求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

示例 1:

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

输入: n = 9
输出: 45
 

限制:

1 <= n <= 10000

解法

public class Solution {
    public int sumNums(int n) {
        int res= n;
        boolean x=res>0 && (res += sumNums(n-1))>0;
        return res;
    }

  /*  public static void main(String[] args) {
        System.out.println(new Solution().sumNums(5));
    }*/
}

解题思路

短路效应

  1. 首先分析题目

要求一: 不能使用乘除法,意味着以下写法不能用

(1+n)*n/2

要求二:不能使用 for、while、if、else、switch、case

 int res = 0;
 for(int i = 1; i <= n; i++)
 res += i;
return res

要求三:条件判断语句(A?B:C)

 public int sumNums(int n) {
        int res= n;
        res+= n>0? sumNums(n-1):n;
        return res;
}

以上这三种写法都不能使用!!
2. 思考能不能从其他方式达到我们想要的递归
分析 第三个要求写的三元表达式

res+= n>0? sumNums(n-1):n;

我们换一种写法

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

在Java中逻辑运算符&& 和 ||,它们都存在短路效应

对于a && b,只有当a和b同时为true时,整个表达式才为true;
如果表达式a为false,那么整个表达式肯定为false,所以表达式b不会被执行

于是我们便可以a为ture,使得这个方法第二块进行递归运算

当 n = 1 时, n > 1 不成立 ,sumNums(n-1)>0不进行运算

同时需要返回sum,我们设置一个变量作为返回值,累加 sumNums(n-1)的结果

int res= n;
boolean x=res>0 && (res += sumNums(n-1))>0;
return res;