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

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

2022-02-21 139
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 求 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算法
C++ rust
C++ python
算法python
算法java
二当家的白帽子
目录
相关文章
拓端数据部落
|
2天前
|
机器学习/深度学习 自然语言处理 算法
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
拓端数据部落
22 0
sumith
|
3天前
|
算法 机器人 Python
Python实现教程：平面最短路径算法
Python实现教程：平面最短路径算法
sumith
10 1
桃李春风一杯酒
|
9天前
|
机器学习/深度学习 运维 算法
【Python机器学习专栏】异常检测算法在Python中的实践
【4月更文挑战第30天】本文介绍了异常检测的重要性和在不同领域的应用，如欺诈检测和网络安全。文章概述了四种常见异常检测算法：基于统计、距离、密度和模型的方法。在Python实践中，使用scikit-learn库展示了如何实现这些算法，包括正态分布拟合、K-means聚类、局部异常因子(LOF)和孤立森林(Isolation Forest)。通过计算概率密度、距离、LOF值和数据点的平均路径长度来识别异常值。
桃李春风一杯酒
31 0
桃李春风一杯酒
|
9天前
|
机器学习/深度学习 数据可视化 算法
【Python机器学习专栏】t-SNE算法在数据可视化中的应用
【4月更文挑战第30天】t-SNE算法是用于高维数据可视化的非线性降维技术，通过最小化Kullback-Leibler散度在低维空间保持数据点间关系。其特点包括：高维到二维/三维映射、保留局部结构、无需预定义簇数量，但计算成本高。Python中可使用`scikit-learn`的`TSNE`类实现，结合`matplotlib`进行可视化。尽管计算昂贵，t-SNE在揭示复杂数据集结构上极具价值。
桃李春风一杯酒
17 1
桃李春风一杯酒
|
9天前
|
机器学习/深度学习 算法 数据挖掘
【Python机器学习专栏】关联规则学习：Apriori算法详解
【4月更文挑战第30天】Apriori算法是一种用于关联规则学习的经典算法，尤其适用于购物篮分析，以发现商品间的购买关联。该算法基于支持度和置信度指标，通过迭代生成频繁项集并提取满足阈值的规则。Python中可借助mlxtend库实现Apriori，例如处理购物篮数据，设置支持度和置信度阈值，找出相关规则。
桃李春风一杯酒
23 2
桃李春风一杯酒
|
9天前
|
机器学习/深度学习 算法 数据挖掘
【Python机器学习专栏】层次聚类算法的原理与应用
【4月更文挑战第30天】层次聚类是数据挖掘中的聚类技术，无需预设簇数量，能生成数据的层次结构。分为凝聚（自下而上）和分裂（自上而下）两类，常用凝聚层次聚类有最短/最长距离、群集平均和Ward方法。优点是自动确定簇数、提供层次结构，适合小到中型数据集；缺点是计算成本高、过程不可逆且对异常值敏感。在Python中可使用`scipy.cluster.hierarchy`进行实现。尽管有局限，层次聚类仍是各领域强大的分析工具。
桃李春风一杯酒
33 3
桃李春风一杯酒
|
9天前
|
机器学习/深度学习 算法 数据挖掘
【Python 机器学习专栏】K-means 聚类算法在 Python 中的实现
【4月更文挑战第30天】K-means 是一种常见的聚类算法，用于将数据集划分为 K 个簇。其基本流程包括初始化簇中心、分配数据点、更新簇中心并重复此过程直到收敛。在 Python 中实现 K-means 包括数据准备、定义距离函数、初始化、迭代和输出结果。虽然算法简单高效，但它需要预先设定 K 值，且对初始点选择敏感，可能陷入局部最优。广泛应用在市场分析、图像分割等场景。理解原理与实现对应用聚类分析至关重要。
桃李春风一杯酒
14 1
电力程序小学童
|
1天前
|
算法
【免费】基于ADMM算法的多微网电能交互分布式运行策略（matlab代码）
【免费】基于ADMM算法的多微网电能交互分布式运行策略（matlab代码）
电力程序小学童
8 1
简简单单做算法
|
1天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于有序抖动块截断编码的水印嵌入和提取算法matlab仿真
这是一个关于数字图像水印嵌入的算法介绍。使用MATLAB2022a，该算法基于DOTC，结合抖动和量化误差隐藏，确保水印的鲁棒性和隐蔽性。图像被分为N*N块，根据水印信号进行二值化处理，通过调整重建电平的奇偶性嵌入水印。水印提取是嵌入过程的逆操作，通过重建电平恢复隐藏的水印比特。提供的代码片段展示了从块处理、水印嵌入到噪声攻击模拟及水印提取的过程，还包括PSNR和NC的计算，用于评估水印在不同噪声水平下的性能。
简简单单做算法
7 0
电力程序小学童
|
1天前
|
机器学习/深度学习 算法 数据挖掘
基于改进ISODATA算法的负荷场景曲线聚类（matlab代码）
基于改进ISODATA算法的负荷场景曲线聚类（matlab代码）
电力程序小学童
8 0

热门文章

最新文章

  • 1
    阿里云 MaxCompute MaxFrame 开启免费邀测，统一 Python 开发生态
  • 2
    Python与NoSQL数据库（MongoDB、Redis等）面试问答
  • 3
    流畅的 Python 第二版（GPT 重译）（一）(1)
  • 4
    【Python】python天气数据抓取与数据分析（源码+论文）【独一无二】
  • 5
    流畅的 Python 第二版（GPT 重译）（十一）(1)
  • 6
    【python】Python航空公司客户价值数据分析（代码+论文）【独一无二】
  • 7
    Python 数据分析（PYDA）第三版（三）（1）
  • 8
    Python速成篇（基础语法）上
  • 9
    流畅的 Python 第二版（GPT 重译）（九）(2)
  • 10
    流畅的 Python 第二版（GPT 重译）（十二）(1)
  • 1
    Rust语言在员工屏幕监控系统中的应用指南
    140
  • 2
    拜登：“一切非 Rust 项目均为非法”，开发界要大变天？
    35
  • 3
    【Rust】——package、crate、定义Module
    18
  • 4
    【Rust】——切片
    18
  • 5
    【Rust】——结构体struct
    30
  • 6
    【Rust】——函数（所有权）以及借用或引用
    22
  • 7
    【Rust】——所有权规则、内存分配
    26
  • 8
    【Rust】——所有权：Stack（栈内存）vs Heap（堆内存）（重点）
    25
  • 9
    【Rust】——控制流（if-else,循环）
    32
  • 10
    【Rust】——猜数游戏
    29

    • 相关课程

    更多
  • Python爬虫实战
  • Python开发基础入门
  • Python常用数据科学库
  • Python网络爬虫实战
  • Python完全自学手册图文教程
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce

    • 相关实验场景

    更多
  • 用Python画圣诞树
  • 使用Python完成RDS数据开发及分析
  • 阿里云平台上进行Java程序的编译与运行
  • TLS1.3的后量子算法集成
  • RSA非对称加密算法
  • 云端Python及基本操作
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）