AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2022-02-21 232
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

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

在这里插入图片描述

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

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
文章标签：
Java
C++
Python
Go
机器学习/深度学习
安全
算法
Rust
关键词：
Python算法
算法java
算法剑指offer
算法python
Java C++
二当家的白帽子
目录
相关文章
计算机程序设计Y2013070224
|
1月前
|
算法 搜索推荐 JavaScript
基于python智能推荐算法的全屋定制系统
本研究聚焦基于智能推荐算法的全屋定制平台网站设计，旨在解决消费者在个性化定制中面临的选择难题。通过整合Django、Vue、Python与MySQL等技术，构建集家装设计、材料推荐、家具搭配于一体的一站式智能服务平台，提升用户体验与行业数字化水平。
计算机程序设计Y2013070224
146 11
荔枝科研社
|
2月前
|
存储 算法 调度
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略（Python代码实现）
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略（Python代码实现）
荔枝科研社
183 26
胖咕噜的稞达鸭
|
1月前
|
存储 算法 编译器
算法入门：剑指offer改编题目：查找总价格为目标值的两个商品
给定递增数组和目标值target，找出两数之和等于target的两个数字。利用双指针法，left从头、right从尾向中间逼近，根据和与target的大小关系调整指针，时间复杂度O(n)，空间复杂度O(1)。找不到时返回{-1,-1}。
胖咕噜的稞达鸭
137 4
爱吃烤鸡翅的酸菜鱼
|
1月前
|
存储 人工智能 算法
从零掌握贪心算法Java版：LeetCode 10题实战解析（上）
在算法世界里，有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择，寄希望于通过局部最优达成全局最优。这种思想就是贪心算法，它以其简洁高效的特点，成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想，并通过10道LeetCode经典题目实战演练，带你掌握这种"步步为营"的解题思维。
爱吃烤鸡翅的酸菜鱼
241 0
游客wkqymr43luqiu
|
2月前
|
存储 Java Go
对比Java学习Go——函数、集合和OOP
Go语言的函数支持声明与调用，具备多返回值、命名返回值等特性，结合`func`关键字与类型后置语法，使函数定义简洁直观。函数可作为一等公民传递、赋值或作为参数，支持匿名函数与闭包。Go通过组合与接口实现面向对象编程，结构体定义数据，方法定义行为，接口实现多态，体现了Go语言的简洁与高效设计。
游客wkqymr43luqiu
101 4
荔枝科研社
|
2月前
|
机器学习/深度学习 编解码 算法
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划（Python代码实现）
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划（Python代码实现）
荔枝科研社
315 4
荔枝科研社
|
2月前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于A*算法的机器人路径规划研究（Python代码实现）
【机器人路径规划】基于A*算法的机器人路径规划研究（Python代码实现）
荔枝科研社
441 4
荔枝科研社
|
2月前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于D*算法的机器人路径规划（Python代码实现）
【机器人路径规划】基于D*算法的机器人路径规划（Python代码实现）
荔枝科研社
181 0
荔枝科研社
|
2月前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于改进型A*算法的机器人路径规划（Python代码实现）
【机器人路径规划】基于改进型A*算法的机器人路径规划（Python代码实现）
荔枝科研社
216 0
荔枝科研社
|
1月前
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
荔枝科研社
195 0

热门文章

最新文章

  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
  • 2
    百宝箱开放平台 ✖️ Java SDK
  • 3
    【Azure Storage Account】Java Code访问Storage Account File Share的上传和下载代码示例
  • 4
    Java 设计模式之策略模式：灵活切换算法的艺术
  • 5
    Java 设计模式之状态模式：让对象的行为随状态优雅变化
  • 6
    java零基础学习者入门课程
  • 7
    Java 设计模式之观察者模式：构建松耦合的事件响应系统
  • 8
    Java 设计模式之责任链模式：优雅处理请求的艺术
  • 9
    Visual C++运行库、.NET Framework和DirectX运行库的作用及常见问题解决方案，涵盖MSVCP140.dll丢失、0xc000007b错误等典型故障的修复方法
  • 10
    给我介绍一些C++中引用的使用注意事项
  • 1
    Python中的列表推导式：简洁高效的数据处理艺术
    329
  • 2
    Python字符串格式化利器：f-strings入门指南
    336
  • 3
    Python列表推导式：简洁高效的数据处理利器
    328
  • 4
    Python高效字符串格式化：f-strings的魅力
    237
  • 5
    掌握Python装饰器：轻松统计函数执行时间
    377
  • 6
    Python f-strings：让字符串格式化更简洁高效！
    286
  • 7
    Python爬取招标信息并生成可视化分析报告
    552
  • 8
    用 Python 制作简单小游戏教程：手把手教你开发猜数字游戏
    636
  • 9
    Python3.14正式支持Free Threaded版本！
    720
  • 10
    Python web Django快速入门手册全栈版，共2590字，短小精悍
    234

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    阿里云弹性公网IP线路类型【BGP(多线)_精品】是什么意思？