漫画：贼简单的题目，但百分之99%的人都不会

客官°小女子只卖身不卖艺 2023-07-13 03:31 47阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

作者 | 程序员浩哥

来源 | 小浩算法

![20.png][]

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

PART

简单的题目

![11.png][]

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

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

示例 1：

输入: n = 3 输出: 6

示例 2：

输入: n = 9 输出: 45

限制：

*  `1 <= n <= 10000`

![瞪眼.gif][.gif]

（瞪一瞪就全部掌握）

PART

题目分析

![38.png][]

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

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

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

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

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

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

![format_png 2][]

（我就说这个是图....我没有偷懒）

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

![format_png 3][]

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

1//c++
    2int sumNums(int n) {
    3    n && (n += sumNums(n-1));
    4    return n;
    5}

python就是下面这样：

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

Go怎么搞？

1//go
     2func plus(a *int, b int) bool {
     3    *a += b
     4    return true
     5}
     6
     7func sumNums(n int) int {
     8        _ = n > 0 && plus(&n, sumNums(n - 1)) 
     9        return n
    10}

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

1//PHP
    2class Solution {
    3    function sumNums($n) {
    4        $n > 0 && $n += $this->sumNums($n - 1);
    5        return $n;
    6    }
    7}

郑重申明（读我的文章必看）：

*  本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用各语言纯属本人爱好。
 *  作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
 *  算法思想才是最重要的。

PART

额外福利

![38.png][]

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

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

![format_png 4][]

（爱了...）

![format_png 5][]

推荐阅读：
    五分钟学算法：动手写一个双向链表
    
    当初我要是这么学习「进程和线程」就好了（附带思维导图）
    
    当初我要是这么学习操作系统就好了（附带思维导图）
    
    啥是布隆过滤器算法？

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9ENjdwZWNlaWJlSVJiTkp1c21LYU5tck9QRTdjeDA3bUF3SWVDd1VmenY4T1RCWElOakNOaWJ6aGJJSGhjaWNmMkI5aWFXUUtEZDdkbjZwaWNPaWNZVVpwWUVwZy82NDA?x-oss-process=image/format,png
[20.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFya0NXbjVQaWFjSzJKOWFxdFJjV3FRZW5lNDdacG5wcTk2NTdOWU14Z29tc2liUko0ME1lenNzdENHdDI1MmtyWGdpYXZXMzMycWhTWHZoZy82NDA?x-oss-process=image/format,png
[11.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybG5hM0JHODhmTDdEY3Q5RVZaZXYydjB0UmliZWtDRU9CazZ1U0tLeFAyZ1JFQk56WHJPRkRVQ3FRUE1OcXdCN2ljOEZUYXFSRXh2T2RnLzY0MA?x-oss-process=image/format,png
[.gif]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9jWG9hMDdJOXFybTgyUkp5dXMzb1lXdWlhOW1ITmVzc3VqUkNrSG41MHJ1bjhzYVdUaWFJbzE2TEpUelh4bVJneGljbHdpYVg1aWFmVWljSW5pYU52a2RncjAwRXcvNjQw?x-oss-process=image/format,png
[38.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybG5hM0JHODhmTDdEY3Q5RVZaZXYydnJmYkdsTGljUXA4MTd3ZkVBaFVadlhtMzNUd1RUeXg5OFBvaWJuQnBpYnVQQmJyRFozZWpSZTBSdy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybHlqQ1FuUlZKaWFVazd5NURZRmN4WVd5djVxWWE5OWdQOElWVGFBYThwd0JTUHUyOGpDWUZBbGNLZTBySktGb3pWN2xrVzFpY3EwN0JRLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybHlqQ1FuUlZKaWFVazd5NURZRmN4WVd6Z2pxM2JGQmc4YlVPbkwxNDg1UE9pYXNiZWY1T1F2VnJ3b2Zrc3ZQWXhPUEEwemljbDVENDR2dy82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybHlqQ1FuUlZKaWFVazd5NURZRmN4WVdkdkR4RUp4dFBIVFlUUWliUm0xNjFwSFVYQVNXTTI5ZXNTMHJsZmV2WG42Y0ZtSGV1OGljV3BCUS82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9jWG9hMDdJOXFybHlqQ1FuUlZKaWFVazd5NURZRmN4WVdMWHVqWE85dUhpYVh3bTQ0b3hhMmdsNkRQYXNVcnZiN051M1ptYzQ2azR3WEJ4aHRkZldhRzB3LzY0MA?x-oss-process=image/format,png