LeetCode 剑指 Offer 64. 求1+2+…+n
求 1+2+…+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
示例 1:
输入: n = 3
输出: 6
限制:
1 <= n <= 10000
解法一:利用逻辑运算符的短路:
class Solution {
public:int sumNums(int n) {n && (n += sumNums(n - 1));return n;}
};
此算法时间复杂度为O(n),空间复杂度为O(n)。
解法二:利用虚函数求解:
class base;
vector<base *> arr;class base {
public:virtual int plus(int i) {return 0;}
};class derived : public base {
public:virtual int plus(int i) override {return i + arr[!!i]->plus(i - 1);}
};class Solution {
public:int sumNums(int n) {arr.push_back(new base());arr.push_back(new derived());return arr[!!n]->plus(n);}
};
此算法时间复杂度为O(n),空间复杂度为O(n)。
解法三:纯C环境下没有虚函数,可以使用函数指针代替:
vector<int (*)(int)> funcArr;int sum(int i) {return i + funcArr[!!(i - 1)](i - 1);
}int sumTerminator(int i) {return i;
}class Solution {
public:Solution() {funcArr.push_back(sumTerminator);funcArr.push_back(sum);}int sumNums(int n) {return funcArr[!!n](n);}
};
此算法时间复杂度为O(n),空间复杂度为O(n)。
解法四:利用static成员:
class Solution {
public:Solution() {sum += i;++i;}int sumNums(int n) {i = 1;sum = 0;vector<Solution *> temp;for (int i = 0; i < n; ++i) {temp.push_back(new Solution);}return sum;}static int i;static int sum;
};int Solution::i = 1;
int Solution::sum = 0;
此算法时间复杂度为O(n),空间复杂度为O(n)。
解法五:利用模板,在编译期计算出结果,但这种方式需要输入是constexpr的:
class Solution {
public:template<int N> struct ans {enum {sum = N + ans<N - 1>::sum};};template<> struct ans<1> {enum {sum = 1};};int sumNums() {return ans<5>::sum; // 模板参数需要是constexpr的}
};
此算法时间复杂度为O(1),空间复杂度为O(1)。
解法六:将enum改为const static int,在较老的不支持类内const static的编译器上,常用enum代替const static,这种方法也需要模板参数是constexpr的:
class Solution {
public:template<int N> struct ans {const static int sum = N + ans<N-1>::sum;};template<> struct ans<1> {const static int sum = 1;};int sumNums() {return ans<3>::sum;}
};
此算法时间复杂度为O(1),空间复杂度为O(1)。
解法七:利用数组大小,根据求和公式sum = i(i+1)/2:
class Solution {
public:int sumNums(int i) {bool arr[i][i+1];return sizeof(arr) >> 1;}
};
此算法时间复杂度为O(n),空间复杂度为O(n)。
解法八:对于相乘的两个数A和B,将B转换为二进制,如果B中的第i位为1,这位1对结果的贡献为A * (1 << i),这个方法也被称作俄罗斯农民乘法,经常被用于两数相乘取模的场景,如果两数相乘已经超过数据范围,但取模后不会超过,我们就可以利用这个方法来拆位取模计算贡献,保证每次运算都在数据范围内。将其应用到求和公式:
class Solution {
public:int sumNums(int i) {int a = i, b = i + 1;int ans = 0;while (b) {if (b & 1) {ans += a;}b >>= 1;a <<= 1;}return ans >> 1;}
};
但是题目要求不能使用while循环,由于题目要求中对输入有限制,n最大为10000,因此最多循环14次,我们把循环中内容写14次即可:
class Solution {
public:int sumNums(int i) {int a = i, b = i + 1;int ans = 0;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;return ans >> 1;}
};
此算法时间复杂度为O(lgn),空间复杂度为O(1)。
相关文章:
LeetCode 剑指 Offer 64. 求1+2+…+n
求 12…n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 示例 1: 输入: n 3 输出: 6 限制: 1 < n < 10000 解法一:利用逻辑运算符的短路…...
Mapper代理开发
MyBatis快速开发https://blog.csdn.net/weixin_51882166/article/details/129204439?spm1001.2014.3001.5501 使用Mapper代理方式完成 定义与SQL映射文件同名的Mapper接口 ,将Mapper接口和SQL映射文件放置同一目录结构 新建接口和包: 将Mapper接口和…...
为什么在连接mysql时,设置 SetConnMaxIdleTime 没有作用
目录测试1go 1.15.15go 1.17.12测试2go 1.15.15go 1.17.12参考在使用golang 连接 mysql时,为了节省连接资源,在连接使用过后,希望在指定长度时间不再使用后,自动关闭连接。 这时,经常会使用SetConnMaxLifetime()&#…...
嵌入式开发利器
前言 俗话说,工欲善其事必先利其器,做嵌入式开发首先需要选择好的工具,对的工具,工具选对了能事半功倍,节省很多时间,那些开发大佬一般都会使用各种各样的工具,不同的环节使用不同的工具&#…...
Qt 的QString类的使用
Qt的QString类提供了很方便的对字符串操作的接口。 使某个字符填满字符串,也就是说字符串里的所有字符都有等长度的ch来代替。 QString::fill ( QChar ch, int size -1 ) 例: QString str "Berlin";str.fill(z);// str "zzzzzz"…...
django项目部署(腾讯云服务器centos)
基本步骤: 购买腾讯云服务器并配配置好 >> 本地项目依赖收集准备 >> 上传项目等文件到服务器 >> 服务器安装部署软件和python环境 >> 开始部署(全局来看就这5个步骤) 目录 目录 1. 购买腾讯云服务器并配配置好 …...
计算机网络笔记、面试八股(一)——TCP/IP网络模型
Note:【计算机网络笔记、面试八股】系列文章共计5篇,现已更新3篇,剩余2篇(TCP连接、Web响应)会尽快更新,敬请期待! 本章目录1. TCP/IP网络模型1.1 应用层1.1.1 应用层作用1.1.2 应用层有哪些常用…...
51单片机入门 - 简短的位运算实现扫描矩阵键盘
介绍 例程使用 SDCC 编译、 stcgal 烧录,如果你想要配置一样的环境,可以参考本专栏的第一篇文章“51单片机开发环境搭建 - VS Code 从编写到烧录”,我的设备是 Windows 10,使用普中51单片机开发板(STC89C52RC…...
Mr. Cappuccino的第45杯咖啡——Kubernetes之部署SpringBoot项目
Kubernetes之部署SpringBoot项目创建一个SpringBoot项目将SpringBoot项目打成Jar包使用Dockerfile制作镜像部署SpringBoot项目创建一个SpringBoot项目 pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache…...
vscode在远程服务器提交git的时候无需每次都要输入账号密码的配置
要避免在每次 git 操作时都需要输入账号和密码,可以使用 SSH 鉴权,具体步骤如下:生成 SSH key在本地计算机上使用命令 ssh-keygen -t rsa -b 4096 生成 SSH key。这个命令将在 ~/.ssh 目录下生成两个文件:id_rsa 和 id_rsa.pub&am…...
【Spring 基础】
【Spring 基础】 一、 Spring 介绍 1. 简述 Spring 技术是 JavaEE 开发必备技能,企业开发技术选型专业角度 简化开发,降低企业级开发的复杂性 IoCAOP 事务处理 框架整合,高效整合其他技术,提高企业级应用开发与运行效率 MyBat…...
2023年全国最新机动车签字授权人精选真题及答案5
百分百题库提供机动车签字授权人考试试题、机动车签字授权人考试预测题、机动车签字授权人考试真题、机动车签字授权人证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 四、多选题 1.以下哪些气体属于排放污染物(…...
5138: 数字游戏
描述爸爸、妈妈还有YuYu一起玩一个数字游戏,玩家从某个数开始挨个轮流报数,当数字里含有4或7时,不能报出该数字,只能拍一下手。报数的顺序总是从YuYu开始,然后妈妈、爸爸,最后回到YuYu,以此类推…...
阅读笔记9——DenseNet
一、DenseNet DenseNet的网络结构如图1-1所示,其核心是Dense Block模块,Dense Block中的一个黑点就代表一个卷积模块(不是一个卷积层,而是DenseNet提出的一个BottleNeck模块,后文有讲解),每条黑…...
PowerAutomation获取邮件附件并删除这个邮件方法
这个文章是怎么来的呢?现在不是低代码开发平台启蒙阶段嘛?笔者也有幸在工作中进行了尝试,目前也已经在实际工作中结合Python进行了使用,当然,是可以提高IT的工作效率的。需求是这样的,想从公司的EBS平台报表…...
websocket报错集锦-不断更新中
问题1:Failed to construct ‘WebSocket’: An insecure WebSocket connection may not be initiated from a page loaded over HTTPS. 问题描述 Mixed Content: The page at https://AAAAAA.com was loaded over HTTPS, but attempted to connect to the insecur…...
Spring Cloud Nacos源码讲解(七)- Nacos客户端服务订阅机制的核心流程
Nacos客户端服务订阅机制的核心流程 说起Nacos的服务订阅机制,大家会觉得比较难理解,那我们就来详细分析一下,那我们先从Nacos订阅的概述说起 Nacos订阅概述 Nacos的订阅机制,如果用一句话来描述就是:Nacos客…...
【华为OD机试模拟题】用 C++ 实现 - 对称美学(2023.Q1)
最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 获得完美走位(2023.Q1) 文章目录 最近更新的博客使用说明对称美学题目输入输出示例一输入输出说明示例二输入输出说明备注Code使用说明 参加华为od机试,一定要注意不要完全背诵代码...
Go语言内存管理详解-学习笔记
1 自动内存管理 1.1 相关概念 Mutator:业务线程,分配新对象,修改对象指向关系Collector:GC线程,找到存活对象,回收死亡对象的内存空间Serial GC:只有一个collector(需要暂停&#…...
Geospatial Data Science (4): Spatial weights
Geospatial Data Science (4): Spatial weights 在本节中,我们将学习空间分析中关键部分之一的来龙去脉:空间权重矩阵。这些是结构化的数字集,用于形式化数据集中观测值之间的地理关系。本质上,给定地理的空间权重矩阵是维度 N N N 乘以 N N N 的正定矩阵,其中...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
