[Go版]算法通关村第十三关白银——数字数学问题之数组实现加法、幂运算

news/2024/3/4 10:54:12

目录

数组实现加法专题

题目:数组实现整数加法

题目链接:LeetCode-66. 加一
在这里插入图片描述

思路分析:数组末尾开始,逐个元素+1,=10就进位,!=10就退出

复杂度:时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( n ) O(n) O(n)

Go代码

func plusOne(digits []int) []int {length := len(digits)for i:= length-1; i>=0; i-- {digits[i]++digits[i] = digits[i]%10if digits[i] != 0 {return digits}}ret := make([]int, length+1)ret[0] = 1copy(ret[1:], digits)return ret
}

题目:字符串加法

题目链接:LeetCode-415. 字符串相加
在这里插入图片描述

思路分析:定义两指针分别指向两byte数组末尾,从后往前相加,十进制相加余数=%10,进位=/10

复杂度:时间复杂度 O ( m a x ( n , m ) ) O(max(n,m)) O(max(n,m))、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func addStrings(num1 string, num2 string) string {length1, length2 := len(num1), len(num2)ret := ""for i, j, sign := length1-1, length2-1, 0; i >=0 || j >= 0 || sign>0; i,j = i-1,j-1 {var n1, n2 intif i >= 0 {n1 = getNum(num1[i])}if j >= 0 {n2 = getNum(num2[j])}v := n1 + n2 + signret = strconv.Itoa(v%10) + retsign = v/10}return ret
}
func getNum(str byte) int {return int(str-'0')
}

题目:二进制加法

题目链接:LeetCode-LCR 002. 二进制求和
在这里插入图片描述

思路分析:定义两指针分别指向两byte数组末尾,从后往前相加,二进制相加余数=%2,进位=/2

复杂度:时间复杂度 O ( m a x ( n , m ) ) O(max(n,m)) O(max(n,m))、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func addBinary(a string, b string) string {length1, length2 := len(a), len(b)str := ""for i,j,sign := length1-1, length2-1, 0; i>=0 || j>=0 || sign>0; i,j = i-1,j-1{var n1, n2 intif i >= 0 {n1 = int(a[i]-'0')}if j >= 0 {n2 = int(b[j]-'0')}v := n1 + n2 + signstr = strconv.Itoa(v%2) + strsign = v/2}return str
}

幂运算专题

题目:求2的幂

题目链接:LeetCode-231. 2 的幂
在这里插入图片描述

解法1:试除法:循环除2,判断最后值是否==1

复杂度:时间复杂度 O ( l o g n ) O(log n) O(logn)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfTwo(n int) bool {if n <= 0 {return false}for n%2==0 {n = n/2}return n==1
}

解法2:n&(n-1)==0 或者n&(-n)==n

如果存在非负整数k使得 n=2^k,则n的二进制表示为1后面跟k0
所以,正整数n2的幂,当且仅当n的二进制表示中只有最高位是1,其余位都是0,此时满足 n&(n-1)=0

复杂度:时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfTwo(n int) bool {return n>0 && n&(n-1)==0
}
func isPowerOfTwo(n int) bool {return n>0 && n&(-n)==n
}

解法3:判断n能否被最大2的幂整除(判断n是否为最大2的幂的约数)

复杂度:时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfTwo(n int) bool {max := 1<<30return n>0 && max%n == 0
}

题目:求3的幂

题目链接:LeetCode-326. 3 的幂
在这里插入图片描述

解法1:试除法:循环除3,判断最后是否==1

复杂度:时间复杂度 O ( l o g n ) O(log n) O(logn)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfThree(n int) bool {if n <= 0 {return false}for n%3==0 {n = n/3}return n == 1
}

解法2:判断n能否被最大3的幂整除(判断n是否为最大3的幂的约数)

在32位有符号整数的范围内,最大的3的幂为3^19=1162261467,判断n是否能被该数整除,即n是否是该数的约数即可。

复杂度:时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfThree(n int) bool {return n>0 && 1162261467%n==0
}

题目:求4的幂

题目链接:LeetCode-342. 4的幂
在这里插入图片描述

解法1:试除法:循环除4,判断最后是否==1

复杂度:时间复杂度 O ( l o g n ) O(log n) O(logn)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfFour(n int) bool {if n <= 0 {return false}for n%4 == 0 {n = n/4}return n==1 
}

解法2:必然是2的幂,二进制时1必然在奇数位上n&0xaaaaaaaa==0

4 的一些幂次的二进制表示:

4^0 = 1,二进制表示:0001
4^1 = 4,二进制表示:0100
4^2 = 16,二进制表示:10000
4^3 = 64,二进制表示:1000000

这些幂次的二进制表示中,只有一个位是 1,而且这个 1 总是出现在奇数的位置上(从右数,从 0 开始计数)

复杂度:时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfFour(n int) bool {return n > 0 && n & (n-1) == 0 && (n & 0xaaaaaaaa) == 0
}

解法3:必然是2的幂,对3取余为1 n%3==1

一个整数 n 对 3 取余的结果只可能是 0、1 或 2。如果一个数的二进制表示中只有一个位是 1,并且这个 1 出现在奇数的位置上,那么这个数对 3 取余的结果就是 1。

复杂度:时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func isPowerOfFour(n int) bool {return n > 0 && n & (-n)==n && n%3==1
}

http://www.ppmy.cn/news/1059332.html

相关文章

算法训练Day59|● 503.下一个更大元素II ● 42. 接雨水

LeetCode: 503.下一个更大元素II 503. 下一个更大元素 II - 力扣&#xff08;LeetCode&#xff09; 1.思路 暴力求解间接。 构建单调栈&#xff0c;栈中存放着数组元素对应的索引。单调栈通过取模操作在原数组的基础上实现循环遍历。 2.代码实现 // 暴力求解&#xff1a;创…

汽车电子笔记之:AUTOSA架构下的多核OS操作系统

目录 1、AUTOSAR多核操作系统 1.1、OS Application 1.2、多核OS的软件分区 1.3、任务调度 1.4、核间任务同步 1.5、计数器、报警器、调度表 1.6、自旋锁与共享资源 1.7、核间通信IOC 1.8、OS Object中元素交互 1.9、多核OS的启动与关闭 2、多核OS注意事项 2.1、最小…

mac电脑免费垃圾清理软件有哪些?CleanMyMac好用不好用?

CleanMyMac是一款功能强大的mac垃圾清理软件&#xff0c;它可以帮助我们快速扫描和删除mac上的垃圾文件&#xff0c;释放磁盘空间&#xff0c;提升系统速度。本文将为你介绍CleanMyMac这款mac垃圾清理软件&#xff0c;以及CleanMyMac怎么关闭开机启动。 mac垃圾清理软件有很多…

idea新建Java-maven项目时,出现Dependency ‘ xxx(jar包名)‘ not found的解决方案

项目场景&#xff1a; 项目场景&#xff1a;使用idea创建maven项目时&#xff0c;导入简单依赖时&#xff08;本文以mysql-connector-java为例&#xff09;。 问题描述 问题&#xff1a; 首先&#xff0c;在创建新的maven项目中&#xff0c;出现下列两种情况&#xff1a; &am…

用Idea把SpringBoot项目打包镜像上传至docker

1、设置docker把2375端口开起来 命令查看docker装在哪里 vim docker.service 新增 -H tcp://0.0.0.0:2375 -H unix://var/run/docker.sock 2、配置Dockerfile 我在跟pom同一层 3、配置docker-maven-plugin <plugin><groupId>com.spotify</groupId><arti…

springboot整合modbus4J(一)

springboot整合modbus4J 1. 介绍 (1) modbus poll&#xff1a;modbus主机仿真器&#xff0c;用于测试和调试modbus从设备。该软件支持modbus rtu、ASCII、TCP/IP。用来帮助开发人员测试modbus从设备&#xff0c;或者其它modbus协议的测试和仿真。它支持多文档接口&#xff0c…

c++使用zlib对字符串进行压缩和解压

官网下载zlib库编译后就能使用 #include <string> #include <iostream> #include <memory> #include <assert.h> #include <cstring> #include "zlib.h"#define CHUNK 16384/* Compress from file source to file dest until EOF on …

高通 A12 设置-存储 存储总大小显示不正确问题

总存储大小计算原理&#xff1a; 系统获取存储大小是通过获取”/system”和”/data” 两个Directory 的和来计算的&#xff0c;即Environment.getDataDirectory().getTotalSpace() Environment.getRootDirectory().getTotalSpace() 问题一 &#xff1a;实际存储大小大于等于1…

VSCode配置终端默认为cmd命令行方式

1、新建终端 2、点击默认配置文件 3、选择第一个即可&#xff01;

【三维重建】【深度学习】NeRF代码Pytorch实现--数据加载(上)

【三维重建】【深度学习】NeRF代码Pytorch实现–数据加载(上) 论文提出了一种5D的神经辐射场来作为复杂场景的隐式表示&#xff0c;称为NeRF&#xff0c;其输⼊稀疏的多⻆度带pose的图像训练得到⼀个神经辐射场模型。简单来说就是通过输入同一场景不同视角下的二维图片和相机位…

controller层如何接收带参数的查询

在控制器&#xff08;Controller&#xff09;层接收带参数的查询可以通过多种方式实现。以下是几种常见的方法&#xff1a; 使用 URL 路径参数&#xff1a;将参数作为 URL 的一部分&#xff0c;例如 /users/{userId}。在 Spring MVC 中&#xff0c;您可以使用 PathVariable 注解…

ShowMeBug X 国信证券 | 提升金融企业技术人才识别效率,实现高效团队搭建

国信证券股份有限公司&#xff08;以下称国信证券&#xff09;与ShowMeBug完成签约。ShowMeBug 技术测评平台助力国信证券将招聘流程部分线上化&#xff0c;HR大幅减少了人才出筛时间&#xff0c;加速了整体招聘进程&#xff0c;提升了人才识别效率&#xff0c;推动建设更加坚实…

vue 简单实验 v-bind 变量与html属性绑定

1.代码 <script src"https://unpkg.com/vuenext" rel"external nofollow" ></script> <div id"bind-attribute"><span v-bind:title"message">鼠标悬停几秒钟查看此处动态绑定的提示信息&#xff01;</sp…

pnpm无法加载文件 (解决方法 )

现在要运行一个TS的项目&#xff0c;我的电脑上没有安装pnpm&#xff0c;导致我的vscode一直报错无法加载。 pnpm安装&#xff1a; npm install -g pnpm pnpm : 无法加载文件 pnpm : 无法加载文件 C:\Users\HP\AppData\Roaming\npm\pnpm.ps1&#xff0c;因为在此系统上禁止运…

泡泡玛特上半年收入超28亿元 净利润超去年全年

8月22日&#xff0c;泡泡玛特发布2023中期业绩。数据显示&#xff0c;上半年实现营收28.14亿元&#xff0c;经调整净利润5.35亿元&#xff0c;同比增长42.3%&#xff0c;其中净利润4.77亿元&#xff0c;超去年全年净利润。海外业务延续高速增长态势并首次披露利润情况&#xff…

【android12-linux-5.1】【ST芯片】驱动移植后编译不通过

ST传感器芯片驱动移植后&#xff0c;编译报错timespec_to_ns未定义&#xff0c;这应该是内核版本的差异引起的。驱动的适配版本是4.19y&#xff0c;我实际使用的内核linux版本是5.1。 处理方法是使用timespec64_to_ns&#xff0c;如下图&#xff1a; 新代码如下&#xff1a; s…

浅谈Python网络爬虫应对反爬虫的技术对抗

在当今信息时代&#xff0c;数据是非常宝贵的资源。而作为一名专业的 Python 网络爬虫程序猿&#xff0c;在进行网页数据采集时经常会遭遇到各种针对爬虫行为的阻碍和限制&#xff0c;这就需要我们掌握一些应对反爬机制的技术手段。本文将从不同层面介绍如何使用 Python 进行网…

软考高级系统架构设计师系列论文八十九:论软件需求分析方法和工具的选用

软考高级系统架构设计师系列论文八十九:论软件需求分析方法和工具的选用 一、软件需求相关知识点二、摘要三、正文四、总结一、软件需求相关知识点 软考高级系统架构设计师:论软件需求管理

Unity中的Unistorm3.0天气系统笔记

Unistorm是Unity中的一个天气系统&#xff0c;它功能强大&#xff0c;效果优美。本文所述UniStorm为3.0版本&#xff0c;仅用于学习之用。 一、如何设置【白天】、【黑夜】和【天气类型】&#xff1f; 在Running模式下&#xff0c;按下Esc按键&#xff0c;会【弹出】或者【隐…

【LeetCode 】数组简介

集合列表和数组 本文中介绍的概念为适用于所有编程语言的抽象理论&#xff0c;具体实现会由编程语言的不同而稍有差别。 具体介绍数组之前&#xff0c;我们先来了解一下集合、列表和数组的概念之间的差别。 集合 集合一般被定义为&#xff1a;由一个或多个确定的元素所构成的…
最新文章