滤芯网站怎么做,宜昌最权威网站建设公司,做性的视频网站,自建域名目录 数组实现加法专题题目#xff1a;数组实现整数加法思路分析#xff1a;数组末尾开始#xff0c;逐个元素1#xff0c;10就进位#xff0c;!10就退出复杂度#xff1a;时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( n ) O(n) O(n)Go代码 题目#xff1a;字符串加法… 目录 数组实现加法专题题目数组实现整数加法思路分析数组末尾开始逐个元素110就进位!10就退出复杂度时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( n ) O(n) O(n)Go代码 题目字符串加法思路分析定义两指针分别指向两byte数组末尾从后往前相加十进制相加余数%10进位/10复杂度时间复杂度 O ( m a x ( n , m ) ) O(max(n,m)) O(max(n,m))、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目二进制加法思路分析定义两指针分别指向两byte数组末尾从后往前相加二进制相加余数%2进位/2复杂度时间复杂度 O ( m a x ( n , m ) ) O(max(n,m)) O(max(n,m))、空间复杂度 O ( 1 ) O(1) O(1)Go代码 幂运算专题题目求2的幂解法1试除法循环除2判断最后值是否1复杂度时间复杂度 O ( l o g n ) O(log n) O(logn)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法2n(n-1)0 或者n(-n)n复杂度时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法3判断n能否被最大2的幂整除判断n是否为最大2的幂的约数复杂度时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目求3的幂解法1试除法循环除3判断最后是否1复杂度时间复杂度 O ( l o g n ) O(log n) O(logn)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法2判断n能否被最大3的幂整除判断n是否为最大3的幂的约数复杂度时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目求4的幂解法1试除法循环除4判断最后是否1复杂度时间复杂度 O ( l o g n ) O(log n) O(logn)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法2必然是2的幂二进制时1必然在奇数位上n0xaaaaaaaa0复杂度时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法3必然是2的幂对3取余为1 n%31复杂度时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 数组实现加法专题
题目数组实现整数加法
题目链接LeetCode-66. 加一
思路分析数组末尾开始逐个元素110就进位!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; i0; i-- {digits[i]digits[i] digits[i]%10if digits[i] ! 0 {return digits}}ret : make([]int, length1)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 || sign0; 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; i0 || j0 || sign0; 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%20 {n n/2}return n1
}解法2n(n-1)0 或者n(-n)n
如果存在非负整数k使得 n2^k则n的二进制表示为1后面跟k个0。 所以正整数n是2的幂当且仅当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 n0 n(n-1)0
}func isPowerOfTwo(n int) bool {return n0 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 : 130return n0 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%30 {n n/3}return n 1
}解法2判断n能否被最大3的幂整除判断n是否为最大3的幂的约数
在32位有符号整数的范围内最大的3的幂为3^191162261467判断n是否能被该数整除即n是否是该数的约数即可。
复杂度时间复杂度 O ( 1 ) O(1) O(1)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
func isPowerOfThree(n int) bool {return n0 1162261467%n0
}题目求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 n1
}解法2必然是2的幂二进制时1必然在奇数位上n0xaaaaaaaa0
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%31
一个整数 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%31
}
