[Go版]算法通关村第十三关青铜——数字数学问题之统计问题、溢出问题、进制问题

这里写自定义目录标题


很多数学相关算法的关键在于找到怎么通过最简洁的方式来解决问题,而不是硬算。

数字统计专题

题目:数组元素积的符号

题目链接:LeetCode-1822. 数组元素积的符号
在这里插入图片描述

思路分析:无需真计算,只需判断负数个数是奇是偶

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

Go代码

func arraySign(nums []int) int {ret := 1for _, v := range nums {if v == 0 {return 0}if v < 0 {ret = -ret}}return ret
}

题目:阶乘尾数0的个数

题目链接:LeetCode-面试题 16.05. 阶乘尾数
在这里插入图片描述

思路分析:2和5能凑出1个0,而2出现的次数一定多于5,所以统计5的出现次数即可

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

Go代码

func trailingZeroes(n int) int {num := 0for n > 0 {n = n/5num += n}return num
}

溢出问题专题

题目:整数反转

题目链接:LeetCode-7. 整数反转
在这里插入图片描述

思路分析:依次除10得到余数进行值组装,注意溢出问题

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

Go代码

func reverse(x int) int {res := 0for x != 0 {// 获得末尾数字num := x%10// 判断是否大于最大整数if res > 0 && res > (math.MaxInt32-num)/10 {return 0 }// 判断是否小于最小整数if res <0 && res < (math.MinInt32-num)/10 {return 0}res = res*10 + numx = x/10}return res
}

题目:字符串转换整数 (atoi)

题目链接:LeetCode-8. 字符串转换整数 (atoi)
在这里插入图片描述

思路分析:去除空格 + 确定正负 + 读取数值 + 判断溢出

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

Go代码

func myAtoi(s string) int {if len(s) == 0 {return 0}// 去除前面空格for i, v := range s {if v != ' ' {s = s[i:]break}}if len(s) == 0 {return 0}// 确定正负sign := 1if s[0] == '-' || s[0] == '+' {if s[0] == '-' {sign = -1}s = s[1:]}res, v := 0, 0length := len(s)// 读取数值for i:=0; i<length; i++ {if s[i] < '0' || s[i] > '9' {return res}v = int(s[i]-'0')// 判断越界if res > (math.MaxInt32-v)/10 {return math.MaxInt32}if res < (math.MinInt32+v)/10 {return math.MinInt32}res = res * 10 + sign * v}return res
}

题目:回文数

题目链接:LeetCode-9. 回文数
在这里插入图片描述

解法1:反转数字后对比是否一致,反转过程注意溢出问题

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

Go代码

func isPalindrome(x int) bool {if x < 0 {return false}num := 0oldx := xnewx := 0for x != 0 {num = x%10  //尾数if newx > (math.MaxInt32-num)/10 || newx < (math.MinInt32-num)/10 {return false}newx = newx*10 + numx = x/10}if newx == oldx {return true}return false
}

解法2:仅反转一半位数后对比是否一致,对比过程注意奇数位数的问题,但不用考虑溢出问题了(优化解法1)

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

Go代码

func isPalindrome(x int) bool {// 负数 和 余数是0但是本身不是0 时if x < 0  || (x%10==0 && x != 0) {return false}num := 0// 反转一半for x > num {num = num*10 + x%10x = x/10}// 考虑奇位数时,忽略中间数,比如12321 中的3if x == num || x == num/10 {return true}return false
}

进制专题

题目:七进制数

题目链接:LeetCode-504. 七进制数
在这里插入图片描述

思路分析:依次出7的余数,拼接后反转,注意拼接时负号要追加上

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

Go代码

func convertToBase7(num int) string {if num == 0 {return "0"}sign := 1if num < 0 {sign = -1// 绝对值numnum = -1 * num}res := make([]byte, 0)var v bytefor num != 0 {// 余数依次是反转的原值v = byte(num%7 + '0')res = append(res, v)num = num/7}if sign < 0 {res = append(res, '-')}reverseArr(res, 0, len(res)-1)return string(res)
}
func reverseArr(arr []byte, left int, right int) {if left >= right {return}for left <= right {arr[left], arr[right] = arr[right], arr[left]left++right--}
}

题目:数字转换为十六进制数

题目链接:LeetCode-405. 数字转换为十六进制数
在这里插入图片描述

思路分析:使用&15将每4位二进制转16位进制数 + 反转数组

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

  • 时间复杂度是 O ( 1 ) O(1) O(1),因为循环迭代的次数是固定的,最多只有 8 次。
  • 空间复杂度是 O ( 1 ) O(1) O(1),res 数组的大小固定为 8(因为最多只处理 8 位),所以额外的空间消耗是常数级别的。

Go代码

func toHex(num int) string {byteArr := [16]byte{'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'}if num == 0 {return "0"}res := []byte{}var v bytefor i:=0;i<8;i++ {v = byteArr[num&15]res = append(res, v)num = num>>4if num == 0 {break}}reverse(res, 0, len(res)-1)return string(res)
}
func reverse(arr []byte, left int, right int) {if left >= right {return}for left <= right {arr[left], arr[right] = arr[right], arr[left]left++right--}
}

题目:十进制转换为指定进制

给定一个十进制数Num,以及需要转换的进制数N,将十进制数Num转化为N进制数。Num是32为整数,2<=N<=16。

思路分析:准备16进制的字符Map,依次除N得到余数,映射Map得到对应字符,追加到数组,注意负号的追加,反转数组,转为string

复杂度:时间复杂度 O ( l o g n u m ) O(log num) O(lognum)、空间复杂度 O ( l o g n u m ) O(log num) O(lognum)

Go代码

func convert(num int, n int) string {byteArr := [16]byte{'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'}if num == 0 {return "0"}sign := 1if num < 0 {sign = -1num = -num}res := []byte{}var v bytefor num != 0 {v = byteArr[num%n]res = append(res, v)num = num/n}if sign == -1 {res = append(res, '-')}reverse(res, 0, len(res)-1)return string(res)
}
func reverse(arr []byte, left int, right int) {if left >= right {return}for left <= right {arr[left], arr[right] = arr[right], arr[left]left++right--}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/104828.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CPU、MCU、MPU、SOC、SOCPC、概念解释之在嵌入式领域常听到的名词含义

CPU、MCU、MPU、SOC等几个在嵌入式领域学习过程中会涉及到的几个名词。我们来学习一下&#xff0c;资料从网上搜集的&#xff0c;有错的地方可以指出。。。 CPU、MCU、MPU、SOC、SOCPC、 1. CPU2. MPU3.MCUMPU和MCU的区别&#xff1a;4.SOC5. SoPC 1. CPU CPU&#xff0c;即中…

iis站点备份以及端口号查找

文件地址 %windir%\system32\inetsrv\config

iOS 17 及 Xcode 15.0 Beta7 问题记录

1、iOS 17 真机调试问题 iOS 17之后&#xff0c;真机调试Beta版本必须使用Beta版本的Xcode来调试&#xff0c;用以前复制DeviceSupport 方式无法调试&#xff0c;新的Beta版本Xcode中&#xff0c;已经不包含 iOS 17目录。如下图&#xff1a; 解决方案&#xff1a; 1&#x…

Nodejs-nrm:快速切换npm源 / npm官方源和其他自定义源之间切换

一、理解 Nodejs nrm Nodejs nrm 是一个管理 npm 源的工具。由于 npm 在国内的速度较慢&#xff0c;很多开发者会使用淘宝的 npm 镜像源&#xff0c;但是也会遇到一些问题&#xff0c;例如某些包在淘宝镜像源中不存在&#xff0c;或者淘宝镜像源本身也会有问题。 Nodejs nrm …

SpringCloud教程 | 第六篇: 分布式配置中心(Spring Cloud Config)

在上一篇文章讲述zuul的时候&#xff0c;已经提到过&#xff0c;使用配置服务来保存各个服务的配置文件。它就是Spring Cloud Config。 一、简介 在分布式系统中&#xff0c;由于服务数量巨多&#xff0c;为了方便服务配置文件统一管理&#xff0c;实时更新&#xff0c;所以需…

根据源码,模拟实现 RabbitMQ - 虚拟主机设计(5)

目录 一、虚拟主机设计 1.1、需求分析 1.1.1、核心 API 1.1.2、虚拟主机的是用来干什么的&#xff1f; 1.1.3、如何表示 交换机和虚拟主机 之间的从属关系&#xff1f; 二、实现 VirtualHost 类 2.1、属性 2.2、锁对象 2.3、公开实例 2.4、虚拟主机构造方法 2.5、交…

语言、习俗与成功:海外网红营销的文化敏感性

随着全球互联网的普及和社交媒体的兴起&#xff0c;海外网红营销正成为越来越多品牌和企业的选择。然而&#xff0c;要在海外市场取得成功&#xff0c;单纯的翻译内容和机械式的推广已经远远不够&#xff0c;文化敏感性成为海外网红营销的关键。本文Nox聚星将深入探讨语言、习俗…

算法与数据结构(十)--图的入门

一.图的定义和分类 定义&#xff1a;图是由一组顶点和一组能够将两个顶点连接的边组成的。 特殊的图&#xff1a; 1.自环&#xff1a;即一条连接一个顶点和其自身的边; 2.平行边&#xff1a;连接同一对顶点的两条边&#xff1b; 图的分类&#xff1a; 按照连接两个顶点的边的…

Linux 压缩解压(归档管理):tar命令

计算机中的数据经常需要备份&#xff0c;tar是Unix/Linux中最常用的备份工具&#xff0c;此命令可以把一系列文件归档到一个大文件中&#xff0c;也可以把档案文件解开以恢复数据。 tar使用格式 tar [参数] 打包文件名 文件 tar命令很特殊&#xff0c;其参数前面可以使用“-”&…

java八股文面试[java基础]——异常

自定义异常&#xff1a; 异常Exception 是指程序运行时&#xff0c; 由于输入错误、网络、程序逻辑等原因导致运行时出现的问题。出现异常时&#xff0c;程序会暂时中断执行&#xff0c;并根据产生异常的原因&#xff0c;创建对应异常类型的异常对象&#xff0c;并抛出给JVM捕…

七大排序算法详解

1.概念 1.排序的稳定性 常见的稳定的排序有三种&#xff1a;直接插入排序&#xff0c;冒泡排序&#xff0c;归并排序 对于一组数据元素排列&#xff0c;使用某种排序算法对它进行排序&#xff0c;若相同数据之间的前后位置排序后和未排序之前是相同的&#xff0c;我们就成这种…

数学建模(五)非线性规划

课程推荐&#xff1a; 13 非线性规划算法在数学建模中的应用与编程实现_哔哩哔哩_bilibili 一、非线性规划模型 如果目标函数或约束条件中包含非线性函数&#xff0c;就称这种规划问题为非线性规划问题。一般说来&#xff0c;解非线性规划要比解线性规划问题困难得多。而且&am…

cs231n assignment3 q4 Generative Adversarial Networks

文章目录 嫌墨迹直接看代码Q4 :Generative Adversarial Networkssample_noise题面解析代码输出 discriminator题面解析代码输出 generator题面解析代码输出 discriminator_loss题面解析代码输出 generator_loss题面解析代码 get_optimizer题面解析代码输出 ls_discriminator_lo…

c语言函数指针和指针函数的区别,以及回调函数的使用。

函数指针是什么&#xff0c;函数指针本质也是指针&#xff0c;不过是指向函数的指针&#xff0c;存储的是函数的地址。 指针函数是什么,指针函数其实就是返回值是指针的函数&#xff0c;本质是函数。 函数指针是如何定义的呢&#xff0c;如下 void (*pfun)(int a,int b) 这…

服务器的介绍

1.服务器概述 1.1 服务器的基本概念 服务器是计算机的一种&#xff0c;是网络中为客户端计算机提供各种服务的高性能计算机&#xff1b; 服务器在网络操作系统的控制下&#xff0c;将与其相连的硬盘、磁带、 打印机及昂贵的专用通讯设备提供给网络上的客户站点共享&#xf…

2023年国赛 高教社杯数学建模思路 - 案例:最短时间生产计划安排

文章目录 0 赛题思路1 模型描述2 实例2.1 问题描述2.2 数学模型2.2.1 模型流程2.2.2 符号约定2.2.3 求解模型 2.3 相关代码2.4 模型求解结果 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 最短时…

HTTP协议初识·上篇

目录 认识URL urlencode和urldecode 如何编码解码和验证过程 一个基本的网络服务器的流程 代码验证请求与响应 准备工作 HTTPServer.hpp Protocol.hpp makefile 1请求 HTTPServer.hpp 1.0函数handlerHttp-基本流程 再次处理 HttpServer.cc(新建文件) 测试1 -- 请…

iOS开发之查看静态库(.a/.framework)中包含的.o文件和函数符号(ar,nm命令)

.a/.framework其实是把编译生成的.o文件&#xff0c;打包成一个.a/.framework文件。a的意思是archive/归档的意思。 查看静态库.a文件包含的内容用下面的命令解压&#xff1a; ar x xxx.a 用ar命令打包静态库&#xff1a; 参数r是将后面的*.o或者*.a文件添加到目标文件中 参数…

031 - 浮点类型(近似值 FLOAT,DOUBLE)

-FLOAT&#xff0c;DOUBLE&#xff1a; FLOAT和DOUBLE类型代表近似数字数据值。MySQL将四个字节用于单精度值&#xff0c;并将八个字节用于双精度值。 对于FLOAT&#xff0c;SQL标准允许对FLOAT括号中的关键字后面的位以精度&#xff08;而不是指数的范围&#xff09;进行可选规…

全流程R语言Meta分析核心技术高阶应用

查看原文>>>全流程R语言Meta分析核心技术高阶应用 目录 专题一、Meta分析的选题与检索 专题二、Meta分析与R语言数据清洗及统计方法 专题三、R语言Meta分析与作图 专题四、R语言Meta回归分析 专题五、R语言Meta诊断分析 专题六、R语言Meta分析的不确定性 专题…