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

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

目录

数组实现加法专题

题目:数组实现整数加法

题目链接: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
}

相关文章:

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

目录 数组实现加法专题题目&#xff1a;数组实现整数加法思路分析&#xff1a;数组末尾开始&#xff0c;逐个元素1&#xff0c;10就进位&#xff0c;!10就退出复杂度&#xff1a;时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( n ) O(n) O(n)Go代码 题目&#xff1a;字符串加法…...

【 OpenGauss源码学习 —— 列存储(Insert)】

列存储&#xff08;Insert&#xff09; 概述相关函数ExecInsertRelationData 结构体FormData_pg_class 结构体HeapInsertCStore函数InsertArg 结构体CStoreInsert 类CStoreInsert::InitInsertArg函数heap_deform_tuple 函数bulkload_rows 结构体append_one_tuple 函数bulkload_…...

Android 13.0 framework中实现默认长按电源键弹出关机对话框功能

1.前言 在13.0的系统定制化开发中,在12.0的系统之前默认的都是长按电源键弹出关机对话框,而在13以后 就改成音量+电源键弹出对话框,由于使用不方便,所以就改成默认长按弹出关机对话框功能 2.framework中实现默认长按电源键弹出关机对话框功能的核心类 frameworks/base/s…...

微信小程序,封装身高体重选择器组件

wxml代码&#xff1a; // 微信小程序的插值语法不支持直接使用Math <wxs src"./ruler.wxs" module"math"></wxs> <view class"ruler-container"><scroll-view scroll-left"{{scrollLeft}}" enhanced"{{tru…...

深度学习调参技巧

写完代码—> 小数据上降loss无nan—> 大数据没爆卡速度可以—> 实验log完好可视化loss稳步下降—>回头看实验结果 写完代码后&#xff0c;不要只是在小数据上降loss无nan&#xff0c;还要检查一下模型的输出是否符合预期&#xff0c;比如是否有明显的偏差或者异常值…...

图论基础和表示(Java 实例代码)

目录 图论基础和表示 一、概念及其介绍 二、适用说明 三、图的表达形式 Java 实例代码 src/runoob/graph/DenseGraph.java 文件代码&#xff1a; src/runoob/graph/SparseGraph.java 文件代码&#xff1a; 图论基础和表示 一、概念及其介绍 图论(Graph Theory)是离散数…...

各种数据库查询报错问题

文章目录 前言一、约束条件是自增&#xff0c;不能直接添加数据二、使用步骤1.引入库2.读入数据 总结 前言 记录常见的数据库使用问题&#xff0c;以及对应解决思路 一、约束条件是自增&#xff0c;不能直接添加数据 消息 8101&#xff0c;级别 16&#xff0c;状态 1&#xf…...

人效九宫格城市沙龙暨《人效九宫格白皮书》发布会 —上海站,圆满结束

8月11日&#xff0c;在上海龙之梦万丽酒店&#xff0c;由盖雅工场主办的人效九宫格城市沙龙暨《人效九宫格白皮书》发布会 —上海站&#xff0c;圆满结束。 近百位来自多个行业的企业管理者及人力资源从业者汇聚一堂&#xff0c;共同探讨企业如何将盈利模式从数量增长转为质量增…...

【C语言】文件操作 -- 详解

一、什么是文件 磁盘上的文件是文件。 1、为什么要使用文件 举个例子&#xff0c;当我们想实现一个 “通讯录” 程序时&#xff0c;在通讯录中新建联系人、删除联系人等一系列操作&#xff0c;此时的数据存储于内存中&#xff0c;程序退出后所有数据都会随之消失。为了让通讯录…...

飞天使-k8s基础组件分析-持久化存储

文章目录 emptyDirhostpathpv和pvc介绍nfs作为静态pv案例nfs作为动态pv案例使用本地文件夹作为pv改变默认存储类及回收策略参考文档 emptyDir 重启文件还有&#xff0c;但是如果杀了进程&#xff0c;则会丢失文件 创建pod # kubectl apply –f redis.yaml校验pod是否处于运行&…...

python连接PostgreSQL 数据库

执行如下命令安装 pip3 install psycopg2 python代码 Author: tkhywang 2810248865qq.com Date: 2023-08-21 11:42:17 LastEditors: tkhywang 2810248865qq.com LastEditTime: 2023-08-21 11:51:56 FilePath: \PythonProject02\PostgreSQL 数据库.py Description: 这是默认设置…...

数字图像处理—— Lab、YCbCr、HSV、RGB之间互转

Lab “Lab” 图像格式通常指的是 CIELAB 色彩空间&#xff0c;也称为 Lab 色彩空间。它是一种用于描述人类视觉感知的颜色的设备无关色彩空间&#xff0c;与常见的 RGB 和 CMYK 色彩空间不同。CIELAB 由国际照明委员会&#xff08;CIE&#xff09;于1976年定义&#xff0c;用于…...

自动驾驶SLAM技术第四章习题2

在g2o的基础上改成ceres优化&#xff0c;高博都写好了其他的部分, 后面改ceres就很简单了. 这块我用的是ceres的自动求导&#xff0c;很方便&#xff0c;就是转化为模板仿函数的时候有点麻烦&#xff0c; 代码部分如下 ceres_type.h : ceres优化核心库的头文件 这个文件写的内…...

vue拖拽div盒子实现上下拖动互换

vue拖拽div盒子实现上下拖动互换 <div v-for"(item, index) in formList" :key"index" draggable"true"dragstart"handleDragStart($event, item)"dragenter"handleDragEnter($event, item)"dragover.prevent"han…...

Visual Studio 2022 右键单击项目没有出现View | View Class Diagram(Visual Studio 无法使用类设计器)

文章目录 问题描述原因.NET Core项目.NET Framework项目 问题描述 当我们在Solution Explorer窗口右键单击项目时&#xff0c;快捷菜单中没有出现“查看”&#xff0c;或者出现了“查看”&#xff0c;但是“查看”里没有View Class Diagram。 原因 首先你要确保你安装了类设…...

EFCore常见用法

EFCore官方文档置顶&#xff0c;看这个就行。下面的内容只是总结&#xff0c;算是备忘录。 一、创建和删除 //1、创建数据库和表 db.Database.EnsureCreated();//将创建数据库&#xff08;如果不存在&#xff09;并初始化数据库架构。 如果存在任何表 (包括另一 DbContext 类)…...

概率论与数理统计:第六章:数理统计

文章目录 Ch6. 数理统计(一) 总体与样本(二) 统计量 (5个)2.5个常用统计量3.矩的概念 (三) 抽样分布 (3个)0.上α分位点1.χ分布2.t分布3.F分布 (四) 抽样分布定理1.单个正态总体2.两个正态总体 Ch6. 数理统计 (一) 总体与样本 1.概念&#xff1a; (1)总体 (2)样本 简单随机…...

拥塞控制(TCP限制窗口大小的机制)

拥塞控制机制可以使滑动窗口在保证可靠性的前提下&#xff0c;提高传输效率 关于滑动窗口的属性以及部分机制推荐看TCP中窗口和滑动窗口的含义以及流量控制 拥塞控制出现的原因 看了上面推荐的博客我们已经知道了&#xff0c;由于接收方接收数据的能力有限&#xff0c;所以要通…...

校园供水系统智能管理

import pandas as pd data1pd.read_excel("C://Users//JJH//Desktop//E//附件_一季度.xlsx") data2pd.read_excel("C://Users//JJH//Desktop//E//附件_二季度.xlsx") data3pd.read_excel("C://Users//JJH//Desktop//E//附件_三季度.xlsx") data4…...

Flask-SocketIO和Flask-Login联合开发socketio权限系统

设置 Flask, Flask-SocketIO, Flask-Login: 首先&#xff0c;确保安装了必要的库: pip install Flask Flask-SocketIO Flask-Login基础设置: from flask import Flask, render_template, redirect, url_for, request from flask_socketio import SocketIO, emit from flask_…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...