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

数组实现加法专题

题目：数组实现整数加法

题目链接：LeetCode-66. 加一

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

复杂度：时间复杂度$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(max(n,m))$、空间复杂度$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(max(n,m))$、空间复杂度$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(logn)$、空间复杂度$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后面跟k个0。
所以，正整数n是2的幂，当且仅当n的二进制表示中只有最高位是1，其余位都是0，此时满足 n&(n-1)=0

复杂度：时间复杂度$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)$

Go代码

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

题目：求3的幂

题目链接：LeetCode-326. 3 的幂

解法1：试除法：循环除3，判断最后是否==1

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

Go代码

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

题目：求4的幂

题目链接：LeetCode-342. 4的幂

解法1：试除法：循环除4，判断最后是否==1

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

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)$

Go代码

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