轻拔琴弦|剑指 Offer 64. 求1+2+…+n-leetcode
【轻拔琴弦|剑指 Offer 64. 求1+2+…+n-leetcode】题目难度: 中等
原题链接[1]
今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述求 1+2+...+n， 要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C） 。
- 1 <= n <= 10000
- 输入: n = 3
- 输出: 6
- 输入: n = 9
- 输出: 45
- 除了 for 和 while, 还有哪些方式可以达到循环的目的?
- 时间复杂度可以小于 O(N)吗?
- 题目限制很多, 条件判断/循环/乘除法都不能用, 常规高斯公式或者迭代循环的方案直接 GG 了
- 既然显式循环 for/while 不能用, 试试隐式循环?
- 我们可以利用递归的思路, 每次传入 n-1 递归调用, 这样也达到了循环的目的
- 但是这又引入一个新问题, 递归出口怎么办呢? 正常情况下应该是到 n=1 就直接返回 1, 但需要 if 判断, 如何在不使用 if 的情况下达到同样目的呢?
- 其实条件判断还可以用逻辑运算符来实现, 它们具有短路特性, 也就是说如果前面的条件已经构成最终结果了, 就不再判断后面的条件 (比如 and 的前面条件是 False,以及 or 的前面条件是 True)
- 所以这里我们可以将递归出口改为判断 n 是否为 0, 然后与后面的递归调用 and 起来即可, 这样就做到调用到 0 的时候就不再执行递归调用了
- 对于 python 3 而言, and 会返回第一个为 0/False/None 的结果, 如果每一项都不是的话则返回最后一项, 所以这里直接返回 and 表达式的结果即可
- 时间复杂度 O(N): 需要遍历 N 个数字
- 空间复杂度 O(N): 递归栈的消耗
class Solution:def sumNums(self, n: int) -> int:# 方法1: 递归 + and的短路特性# python 3 中 a and b and c 会返回第一个为0/None/False的变量, 如果都不是则返回最后的变量return n and n + self.sumNums(n - 1)方案 2思路- 回顾方案 1, 虽然代码很简洁, 但是还是需要 O(N)时间和空间, 有没有更高效的方案呢?
- 答案也是肯定的, 回忆高斯公式 n*(n+1)/2, 唯一不满足条件的是乘法, 因为除以 2 可以用右移代替, 所以我们只要找到乘法的替代方案即可, 这就是方案 2 的核心
- 求 A*B 的时候, 我们可以利用位运算的思路, 将 B 按照二进制展开, 然后对于它的第 i 位来说, 如果它是 1, 就在最终乘积中加上A*(1<
- 而循环部分, 我们仍然可以采用方案 1 的思路, 利用递归来代替显式的 for/while 循环, 来处理 B 的每一位
- 以上就是经典的快速乘算法, 显然我们只需要遍历logN位即可, 相比方案 1 效率有很大提升
- 下面代码对必要的步骤有详细的解释, 特别是不太好理解的循环转递归的过程, 方便大家参考.相应的, 我也把正常的显式循环快速乘法写了下来, 可读性会好很多, 大家可以对比两种实现方式~
- 时间复杂度 O(logN): 需要遍历 logN 位
- 空间复杂度 O(logN): 递归栈的消耗
class Solution:def sumNums(self, n: int) -> int:# 方法2: 快速乘法, 二进制移位乘法A, B = n, n + 1def quickMultiply(i):# i表示当前处理到B的二进制第i位# B>>i作为递归出口, 为0后表示当前的i已经超过了B的最高位(B是正数, 所以可以这样..), 就不再继续递归# quickMultiply(i + 1)得到第i+1位以及之后的和# 而对于B的当前第i位, 需要判断其是否为0, 仍然利用and短路特性, 得到A(该位是1)或者0(该位是0), 然后左移i位累加到结果中即可return B >> i and (quickMultiply(i + 1) + ((B &(1
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 冲击|单月冲击1000亿，恒大7折卖房剑指金九银十
- 促销|单月冲击1000亿，恒大7折卖房剑指金九银十
- 轻拔琴弦|非常强大，硬核！微软云K8S学习指南免费领取了
- 轻拔琴弦|荣耀新机Magic 3遭曝光，八曲面显示屏，鸿蒙系统登场
- 轻拔琴弦|给你一个反悔的机会
- 朱芳雨|广东宏远内线引援三选一！朱芳雨放大招 剑指三连冠
- 轻拔琴弦|网友使用小米10后发表感想，仅供参考
- 素手烹茶|爱了！阿里技术官亲笔的Java快速面试指南，熬夜啃完剑指大厂
- |末节输27分，雄鹿惨遭逆转！巴特勒末节爆发，热火七连胜剑指东决
- 枝江酒业经销商新政出炉，“真年份”系列招商剑指300家
![[生肖]家有此3大生肖，贵人助力，富足旺财，6月下旬，职场风生水起](http://img88.010lm.com/img.php?https://image.uc.cn/s/wemedia/s/2020/6713007d388380cdc720a75fc79f7b37.jpg)
