当前位置: 首页 > news >正文

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 &#xff0c;要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句&#xff08;A?B:C&#xff09;。 示例 1&#xff1a; 输入: n 3 输出: 6 限制&#xff1a; 1 < n < 10000 解法一&#xff1a;利用逻辑运算符的短路&#xf…...

Mapper代理开发

MyBatis快速开发https://blog.csdn.net/weixin_51882166/article/details/129204439?spm1001.2014.3001.5501 使用Mapper代理方式完成 定义与SQL映射文件同名的Mapper接口 &#xff0c;将Mapper接口和SQL映射文件放置同一目录结构 新建接口和包&#xff1a; 将Mapper接口和…...

为什么在连接mysql时,设置 SetConnMaxIdleTime 没有作用

目录测试1go 1.15.15go 1.17.12测试2go 1.15.15go 1.17.12参考在使用golang 连接 mysql时&#xff0c;为了节省连接资源&#xff0c;在连接使用过后&#xff0c;希望在指定长度时间不再使用后&#xff0c;自动关闭连接。 这时&#xff0c;经常会使用SetConnMaxLifetime()&#…...

嵌入式开发利器

前言 俗话说&#xff0c;工欲善其事必先利其器&#xff0c;做嵌入式开发首先需要选择好的工具&#xff0c;对的工具&#xff0c;工具选对了能事半功倍&#xff0c;节省很多时间&#xff0c;那些开发大佬一般都会使用各种各样的工具&#xff0c;不同的环节使用不同的工具&#…...

Qt 的QString类的使用

Qt的QString类提供了很方便的对字符串操作的接口。 使某个字符填满字符串&#xff0c;也就是说字符串里的所有字符都有等长度的ch来代替。 QString::fill ( QChar ch, int size -1 ) 例&#xff1a; QString str "Berlin";str.fill(z);// str "zzzzzz"…...

django项目部署(腾讯云服务器centos)

基本步骤&#xff1a; 购买腾讯云服务器并配配置好 >> 本地项目依赖收集准备 >> 上传项目等文件到服务器 >> 服务器安装部署软件和python环境 >> 开始部署&#xff08;全局来看就这5个步骤&#xff09; 目录 目录 1. 购买腾讯云服务器并配配置好 …...

计算机网络笔记、面试八股(一)——TCP/IP网络模型

Note&#xff1a;【计算机网络笔记、面试八股】系列文章共计5篇&#xff0c;现已更新3篇&#xff0c;剩余2篇&#xff08;TCP连接、Web响应&#xff09;会尽快更新&#xff0c;敬请期待&#xff01; 本章目录1. TCP/IP网络模型1.1 应用层1.1.1 应用层作用1.1.2 应用层有哪些常用…...

51单片机入门 - 简短的位运算实现扫描矩阵键盘

介绍 例程使用 SDCC 编译、 stcgal 烧录&#xff0c;如果你想要配置一样的环境&#xff0c;可以参考本专栏的第一篇文章“51单片机开发环境搭建 - VS Code 从编写到烧录”&#xff0c;我的设备是 Windows 10&#xff0c;使用普中51单片机开发板&#xff08;STC89C52RC&#xf…...

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 操作时都需要输入账号和密码&#xff0c;可以使用 SSH 鉴权&#xff0c;具体步骤如下&#xff1a;生成 SSH key在本地计算机上使用命令 ssh-keygen -t rsa -b 4096 生成 SSH key。这个命令将在 ~/.ssh 目录下生成两个文件&#xff1a;id_rsa 和 id_rsa.pub&am…...

【Spring 基础】

【Spring 基础】 一、 Spring 介绍 1. 简述 Spring 技术是 JavaEE 开发必备技能&#xff0c;企业开发技术选型专业角度 简化开发&#xff0c;降低企业级开发的复杂性 IoCAOP 事务处理 框架整合&#xff0c;高效整合其他技术&#xff0c;提高企业级应用开发与运行效率 MyBat…...

2023年全国最新机动车签字授权人精选真题及答案5

百分百题库提供机动车签字授权人考试试题、机动车签字授权人考试预测题、机动车签字授权人考试真题、机动车签字授权人证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 四、多选题 1.以下哪些气体属于排放污染物&#xff08…...

5138: 数字游戏

描述爸爸、妈妈还有YuYu一起玩一个数字游戏&#xff0c;玩家从某个数开始挨个轮流报数&#xff0c;当数字里含有4或7时&#xff0c;不能报出该数字&#xff0c;只能拍一下手。报数的顺序总是从YuYu开始&#xff0c;然后妈妈、爸爸&#xff0c;最后回到YuYu&#xff0c;以此类推…...

阅读笔记9——DenseNet

一、DenseNet DenseNet的网络结构如图1-1所示&#xff0c;其核心是Dense Block模块&#xff0c;Dense Block中的一个黑点就代表一个卷积模块&#xff08;不是一个卷积层&#xff0c;而是DenseNet提出的一个BottleNeck模块&#xff0c;后文有讲解&#xff09;&#xff0c;每条黑…...

PowerAutomation获取邮件附件并删除这个邮件方法

这个文章是怎么来的呢&#xff1f;现在不是低代码开发平台启蒙阶段嘛&#xff1f;笔者也有幸在工作中进行了尝试&#xff0c;目前也已经在实际工作中结合Python进行了使用&#xff0c;当然&#xff0c;是可以提高IT的工作效率的。需求是这样的&#xff0c;想从公司的EBS平台报表…...

websocket报错集锦-不断更新中

问题1&#xff1a;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的服务订阅机制&#xff0c;大家会觉得比较难理解&#xff0c;那我们就来详细分析一下&#xff0c;那我们先从Nacos订阅的概述说起 Nacos订阅概述 ​ Nacos的订阅机制&#xff0c;如果用一句话来描述就是&#xff1a;Nacos客…...

【华为OD机试模拟题】用 C++ 实现 - 对称美学(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 获得完美走位(2023.Q1) 文章目录 最近更新的博客使用说明对称美学题目输入输出示例一输入输出说明示例二输入输出说明备注Code使用说明 参加华为od机试,一定要注意不要完全背诵代码࿰...

Go语言内存管理详解-学习笔记

1 自动内存管理 1.1 相关概念 Mutator&#xff1a;业务线程&#xff0c;分配新对象&#xff0c;修改对象指向关系Collector&#xff1a;GC线程&#xff0c;找到存活对象&#xff0c;回收死亡对象的内存空间Serial GC&#xff1a;只有一个collector&#xff08;需要暂停&#…...

Geospatial Data Science (4): Spatial weights

Geospatial Data Science (4): Spatial weights 在本节中,我们将学习空间分析中关键部分之一的来龙去脉:空间权重矩阵。这些是结构化的数字集,用于形式化数据集中观测值之间的地理关系。本质上,给定地理的空间权重矩阵是维度 N N N 乘以 N N N 的正定矩阵,其中...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...