【算法学习】剑指 Offer 64. 求1+2+…+n(java / c / c++ / python / go / rust)

二当家的白帽子 2021-10-27 00:35:46
学习 offer 算法 法学 1+2+

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~



剑指 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://le-yi.blog.csdn.net/article/details/120614668

  1. python编写程序, 先输入一组10个元素,再输出数组中比平均值小的所有奇数。
  2. 《用python写网络爬虫》完整版+源码
  3. python中的小问题,友友们来看一下
  4. python自定义函数CircleArea求圆面积
  5. 判断年月日问题python 不知道自己哪里写错了
  6. 关于Python语言表达的问题
  7. Python代码阅读(第23篇):将变量名称转换为短横线连接式命名风格
  8. Python 用ARIMA、GARCH模型预测分析股票市场收益率时间序列
  9. 云计算开发:Python3-encode()方法详解
  10. python编写程序自动计算个人总分平均分各科最高最低平均分
  11. 在不同python版本下的python代码可以集成到一个应用中吗?
  12. 吹弹牛皮之Unity 工具制作常用交互bat ini python
  13. 手动新建和pycharm新建Djagno项目时候,Django项目的文件夹和虚拟环境文件夹venv的位置有所不同
  14. python课提的求解答一下,是什么意思
  15. python画图X轴太密集了,为什么加了代码也没用
  16. 用PYTHON实现EXCEL数据改动的cell高亮显示
  17. Python Type Hints 从入门到实践
  18. 求一个python大大( •︠ˍ•︡ )(想哭)如果可以的话可以开课,我可以去听课
  19. 真香!值得收藏的30道Python练手题(附详细答案)
  20. django+uwsgi+nginx 前后端分离部署配置
  21. 用python实现千图成像工具,快给你的男/女神弄一张吧~
  22. python csv中dwlimiter用不了,有没有大咖能解释一下
  23. 新手学Python要打好哪些基础?从软件安装到全面基础讲解,就它了!
  24. Python中字符串子串的输出
  25. python判断是否一个序列是超增序列
  26. Python爬虫框架的读取和创建
  27. python对数据框中两列进行判断, 得到新的列的
  28. Python做一个模仿文本进度条的编程
  29. python 中使用MS SQL问题 怎样解决
  30. python有没有类似传送门功能的代码,,就是比如这边运行完然后输入一些指令然后可以跳转到程序里的某个地方
  31. Python基操教学!不会?(熟能生巧)
  32. python画图,有没有初学者的代码
  33. 朋友股票亏惨了,我一怒用Python爬取了证券最新数据
  34. 被称之为永远的神!就这6个Python爬虫开源项目?
  35. python Qtreeview 如何选择子行,选择第一行下面的行数
  36. Python随机生成100个1~200之间的不重复数字
  37. 关于#python#的问题,请各位专家解答!
  38. Python编写程序先输入一组10个元素,再输入数组中比平均值小的所有奇数
  39. Ubuntu终端下安装Python需要import的库
  40. 为什么下载pandas和xlwings运行不了,出现No system module pywintypes(系统查不到pywin32具体位置)(又不能重新下载pywin32)
  41. python求带我脱离苦海,哎_
  42. Python 数据分析里面轴的问题
  43. python初学者,请问使用openpyxl库读取文件后出现图片中的报错要怎么解决?
  44. 大学毕业论文写有关python
  45. 授人以鱼吧友友python编写程序自动计算个人总分平均分各科最高最低平均分
  46. python怎么将四行代码换成一行啊
  47. 用Python如何编写啊 真不会啊?
  48. 这个布尔变化怎么做啊(Python
  49. PYTHON求集合交集需要用户手动输入集合名
  50. Python运行哈姆雷特词频统计时出错(如图),是哪方面的问题?
  51. 【Python表白代码合集】”我还是很喜欢你,像风走了八千里,不问归期”!!
  52. python实现学生信息管理系统(含代码)
  53. wxpython中如何按键停止死循环?
  54. python 类的问题?不懂这种方法的作用?不是继承那是什么作用?
  55. Python 题目不会写 求帮助!
  56. Python,turtle制图,要求使用for,while编写
  57. Python题目不会 求帮助! 谢谢您!
  58. Python题目不会!求帮助!
  59. Python这个看不太懂,,大神们帮个忙
  60. 安装拓展库pandas失败怎么解决