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

zangdaiyang 2020-05-15

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 面试题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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/qiu-12n-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路1-利用短路&&的特性来实现前后部分的执行逻辑

思路解析: 对于a&&b,若a为真b才会执行,a为假则b连执行的机会都没有,所以a部分可以作为递归的终止条件判断,而b部分可以作为递归的计算逻辑部分;
详见代码;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ 递归栈的深度所占空间

算法源码示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年5月15日 下午10:59:33 
 * @Description: 面试题64. 求1+2+…+n
 *
 */
public class LeetCode_Offer_64 {

}

class Solution_Offer_64 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月15日 下午10:59:57 
	 * @param: @param n
	 * @param: @return
	 * @return: int
	 * @Description: 1-利用短路&&的特性来决定前后部分的执行逻辑;
	 *
	 */
	public int sumNums_1(int n) {
		@SuppressWarnings("unused")
		boolean f = n > 0 && (n += sumNums_1(n - 1)) > 0;
		return n;
	}
}

相关推荐