837 字 13 分钟

本文最后更新于：4 个月前

来自《剑指Offer（第二版）》

题目描述

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

  • 1 <= n <= 10000

题解

逻辑(短路)与

看完标题，发现这是一道面试题！！！

看到第一行的“要求不能使用……”，我人傻了，没错，就是人傻了~~

想用“递归”，但是乘除法不能用、条件判断也不能用🤣🤣🤣

这要怎么做啊？！

等等，没说不能用运算符哦！！！

试试看呗~~

直接写写源码~~

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

思路吗？就直接看源码就懂了！！！

不懂，那就看多几次！！！

补充

逻辑运算符的短路效应：
常见的逻辑运算符有三种，即 “与 && ”，“或 ∣∣ ”，“非 ! ” ；
而其有重要的短路效应，如下所示：

if(A && B)  // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false

if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true

本题需要实现 “当 n = 1n=1 时终止递归” 的需求，可通过短路效应实现。

n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归

异常捕获


这个方法会超时，但是确实是可以。

class Solution {
    int[] test=new int[]{0};
    public int sumNums(int n) {
        try{
            return test[n];
        }catch(Exception e){
            return n+sumNums(n-1);
        }
    }
}

移位运算符

移位运算符确实可以解，但是好像不是很多人用它写。

class Solution {
    public int sumNums(int n) {
        int ans = 0, A = n, B = n + 1;
        boolean flag;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        return ans >> 1;
    }
}

我在题解区看到了“你是我见过最变态的题解”，不信就看👇
原帖是解过最变态的一道题

 目录