专栏首页五分钟学算法漫画:贼简单的题目,但百分之99%的人都不会

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

作者 | 程序员浩哥

来源 | 小浩算法

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

01

PART

简单的题目

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

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

示例 1:

输入: n = 3 输出: 6

示例 2:

输入: n = 9 输出: 45

限制:

  • 1 <= n <= 10000

(瞪一瞪就全部掌握)

02

PART

题目分析

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

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

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

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

  • 如果A为true,返回B的布尔值(继续往下执行)
  • 如果A为false,直接返回false(相当于短路)

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

(我就说这个是图....我没有偷懒)

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

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

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

python就是下面这样:

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

Go怎么搞?

//go
func plus(a *int, b int) bool {
    *a += b
    return true
}

func sumNums(n int) int {
        _ = n > 0 && plus(&n, sumNums(n - 1)) 
        return n
}

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

//PHP
class Solution {
    function sumNums($n) {
        $n > 0 && $n += $this->sumNums($n - 1);
        return $n;
    }
}

郑重申明(读我的文章必看):

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

03

PART

额外福利

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

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

(爱了...)

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 位运算中异或的常见用法总结

    异或(^) 这个位操作运算符相信大家一定都不陌生,这个运算符可以用来解决很多普通算法解决不了的问题,而且位运算是直接对二进制码做运算,相对普通的加减乘除运算符来...

    五分钟学算法
  • 几道和散列(哈希)表有关的面试题

    散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到...

    五分钟学算法
  • 盘点今年秋招那些“送命”的算法面试题

    随着 2019 年校招结束,“金九银十”的跳槽季也已经接近尾声,不知道在裁员、消减HC、只招中高级岗位等等“悲观”情绪下,你是否已经如愿入职心意的企业?或者还是...

    五分钟学算法
  • 漫画:贼简单的题目,但百分之99%的人都不会

    今天是小浩算法“365刷题计划”第53天。为大家分享一道本应很简单的题目,但是却因增加了特殊条件,而大幅增加了难度。话不多说,直接看题。

    程序员小浩
  • C++二分图代码实现

    #include <iostream> #include <cstdio> #include <vector> using namespace std; #d...

    kalifa_lau
  • Leetcode Golang 1. Two Sum.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88866806

    anakinsun
  • LeetCode Contest 181

    遍历除数的时候从1到sqrt(nums[i]) 10000*sqrt(100000) 是不会超时的

    ShenduCC
  • 【leetcode刷题】T159-爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • Codeforces Round #463 C.Permutation Cycle

    一、题目 http://codeforces.com/contest/932/problem/C 二、分析 (一)何谓Permutation Cycle 以例1...

    海天一树
  • 如何比较?Comparable还是Comparator

    我家开了个小卖店,为了实现数字化管理,我准备写个后台程序来对所有货物进行管理。首先定义了这个实体类,这个类就是“货物”类,num指的是他的编号,s指他的名称或描...

    naget

扫码关注云+社区

领取腾讯云代金券