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

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

数字统计专题

题目：数组元素积的符号

题目链接：LeetCode-1822. 数组元素积的符号

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

复杂度：时间复杂度$O(n)$、空间复杂度$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(logn)$、空间复杂度$O(1)$

Go代码

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

溢出问题专题

题目：整数反转

题目链接：LeetCode-7. 整数反转

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

复杂度：时间复杂度$O(logn)$、空间复杂度$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(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(logn)$、空间复杂度$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(logn)$、空间复杂度$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(log|n|)$、空间复杂度$O(log|n|)$

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-

思路分析：

复杂度：时间复杂度$O(logn)$、空间复杂度$O(1)$

Go代码

在这里插入代码片