【算法】剑指 Offer 64. 求1+2+…+n（java / c / c++ / python / go / rust）

2021-08-11 05:13:52

剑指 Offer 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

分析

  • 常规做法就是乘法，循环，递归。
  • 题目不让用乘法和循环，那就用递归替代；递归需要有终止条件，题目不然用条件判断，我们可以用短路逻辑运算符替代。
  • 递归太慢了，我们可以用等差数列求和公式，就成了计算n * (n + 1) / 2。
  • 除以2可以用向右移位替代。
  • 乘法，我们可以考虑小学时候算乘法的的步骤，a × b，我们就是用b的每一位数去乘以a × 10i，i表示b的第几位数，再把结果加起来。那如果b是2进制的每一位，就变成看b的每一位是0还是1，如果是1就加上1 × a × 2i，用移位替代就变成a << i。
  • 限制里n最大是10000，214就够了。

题解

java

class Solution {
    public int sumNums(int n) {
        // 2的14次正好超过10000
        // 等差数列求和公式n * (n + 1) / 2
        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;

        return ans >> 1;
    }
}

c

int sumNums(int n){
    // 2的14次正好超过10000
    // 等差数列求和公式n * (n + 1) / 2
    int ans = 0, a = n, b = n + 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);
    a <<= 1;
    b >>= 1;

    (b & 1) && (ans += a);

    return ans >> 1;
}

c++

class Solution {
public:
    int sumNums(int n) {
        // 2的14次正好超过10000
        // 等差数列求和公式n * (n + 1) / 2
        int ans = 0, a = n, b = n + 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);
        a <<= 1;
        b >>= 1;

        (b & 1) && (ans += a);

        return ans >> 1;
    }
};

python

class Solution:
    def sumNums(self, n: int) -> int:
        # 2的14次正好超过10000
        # 等差数列求和公式n * (n + 1) / 2
        ans = 0
        a = n
        b = n + 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)
        a <<= 1
        b >>= 1

        (b & 1) and (ans := ans + a)

        return ans >> 1

go

func sumNums(n int) int {
    // 2的14次正好超过10000
    // 等差数列求和公式n * (n + 1) / 2
    ans, a, b := 0, n, n + 1
    addGreatZero := func() bool {
        ans += a
        return ans > 0
    }

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()
    a <<= 1
    b >>= 1

    _ = ((b & 1) > 0) && addGreatZero()

    return ans >> 1
}

rust

impl Solution {
    pub fn sum_nums(n: i32) -> i32 {
        let mut ans = 0;
        let mut a = n;
        let mut b = n + 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;

        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);
        a <<= 1;
        b >>= 1;
        
        ((b & 1) > 0) && Solution::add_great_zero(&mut ans, a);

        ans >> 1
    }

    fn add_great_zero(ans: &mut i32, n: i32) -> bool {
        *ans += n;
        *ans > 0
    }
}

【算法】剑指 Offer 64. 求1+2+…+n（java / c / c++ / python / go / rust）

原题传送门：https://leetcode-cn.com/problems/qiu-12n-lcof/

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
上一篇：Introduction to the Keras Tuner


下一篇：一文带你玩转 CODE CHINA 的开源广场｜Code China