LeetCode C++ 剑指 Offer 64. 求1+2+…+n【Bit Manipulation】中等
发布日期:2021-07-01 02:58:19
浏览次数:2
分类:技术文章
本文共 657 字,大约阅读时间需要 2 分钟。
求 1+2+…+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
示例 1:
输入: n = 3输出: 6
示例 2:
输入: n = 9输出: 45
限制: 1 <= n <= 10000
解法1 直接乘除
class Solution { public: int sumNums(int n) { return n * (n + 1) / 2; }};
运行效率如下:
执行用时:4 ms, 在所有 C++ 提交中击败了30.48% 的用户内存消耗:6.2 MB, 在所有 C++ 提交中击败了37.91% 的用户
解法2 快速乘和右移
class Solution { public: int sumNums(int n) { //乘法改为快速乘函数,除法换为>>1 int a = n, b = n + 1, ans = 0; while (b) { if (b & 1) ans += a; a <<= 1; b >>= 1; } return ans >> 1; }};
运行效率如下:
执行用时:4 ms, 在所有 C++ 提交中击败了30.48% 的用户内存消耗:6.3 MB, 在所有 C++ 提交中击败了28.12% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/111399616 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月25日 06时47分57秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
KVM 实现机制
2019-05-02
KVM的虚拟化研究及应用
2019-05-02
linux下crontab的使用方法
2019-05-02
Sed 的使用方法
2019-05-02
sed与Awk教程入门与实例练习
2019-05-02
awk教程
2019-05-02
电脑的启动流程
2019-05-02
libvirt(virsh命令介绍)
2019-05-02
im 编辑命令总结
2019-05-02
KVM客户机使用主机USB设备
2019-05-02
RUN文件编译与解包
2019-05-02
xen虚拟机管理工具xm与virsh用法
2019-05-02
Ubuntu 中软件的安装、卸载以及查看的方法总结
2019-05-02
使用SecureCRT远程连接Ubuntu及汉字乱码问题
2019-05-02
ubuntu 搜索文件方法(find命令)
2019-05-02
locate 和 find:两个查找文件的命令
2019-05-02
开机启动vnc服务
2019-05-02
能上QQ无法打开网页
2021-07-05
中国linux论坛
2021-07-05