潍坊市建设局门户网站,WordPress怎么文章连号,关键词网站建设推广,装修网站vr全景图怎么做有很多解题技巧#xff0c;需要持续积累
1.数组实现加法专题
如果让你用数组来表示一个数#xff0c;如何实现加法呢#xff1f; 理论上仍然从数组末尾向前挨着计算就行了#xff0c;但是实现的时候会发现很多问题#xff0c;例如需要进位该怎么办#xff1f;
进一步拓…有很多解题技巧需要持续积累
1.数组实现加法专题
如果让你用数组来表示一个数如何实现加法呢 理论上仍然从数组末尾向前挨着计算就行了但是实现的时候会发现很多问题例如需要进位该怎么办
进一步拓展两个数相加一个用数组存储另一个是普通的整数如何处理
再拓展如果两个整数使用字符串表示呢如果是要按照二进制加法的规则来呢
1.1数组实现整数加法
LeetCode66 https://leetcode.cn/problems/plus-one/
思路分析
从后向前一直加就行如果有进位就需要进位 重点关注当进位导致数组长度变化的情况如 [9,9,9]加1后变为[1,0,0,0]数组长度发生变化
代码实现
Java中巧妙处理数组长度变化
digits new int[len1];
digits[0] 1def plusOne(digits):n len(digits)for i in range(n - 1, -1, -1):digits[i] 1digits[i] % 10if digits[i] ! 0:return digitsreturn [1] digits
def plusOne(digits):n len(digits)for i in range(n - 1, -1, -1):if digits[i] 9:digits[i] 1return digitsdigits[i] 0digits.insert(0, 1)return digits1.2字符串加法
给定两个字符串形式的非负整数 num1 和 num2计算它们的和并同样以字符串形式返回
思路分析
从低到高逐位相加如果当前和超过10则向高位进一位
通过代码写出来 定义两个指针i和j分别指向num1和num2的末尾即最低位 定义一个变量add维护当前是否有进位 从末尾到开头逐位相加
注两个数组位数不同补0处理
代码实现
def addString(num1, num2):i, j len(num1) - 1, len(num2) - 1,ans add 0while i 0 or j 0 or add:x num1[i] if i 0 else 0y num2[j] if j 0 else 0result int(x) int(y) addans str(result % 10) ansadd result // 10i - 1j - 1return ans1.3二进制加法
LeetCode67 https://leetcode.cn/problems/add-binary/
思路分析 方法1中规中矩参考上面字符串加法
方法2先将其转换成十进制加完之后转换成二进制 这么做实现非常容易而且可以使用语言提供的方法直接转换 工程里可以这么干稳定可靠但是算法里不行太简单了
代码实现
方法1
def addBinary(a, b):i, j len(a) - 1, len(b) - 1,ans []add 0while i 0 or j 0 or add:result addresult int(a[i]) if i 0 else 0result int(b[j]) if j 0 else 0ans.append(str(result % 2))add result // 2i - 1j - 1ans.reverse()return .join(ans)if __name__ __main__:print(addBinary(100, 111))
2.幂运算
形式 a^b a的b次方a为底数b为指数 合法不会出现a0且b0的情况
关注底数和指数的数据类型和取值范围 如有的问题中底数是正整数指数是非负整数 有的问题中底数是实数指数是整数
LeetCode中幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂以及快速幂的处理
2.1求2的幂
LeetCode 231 2 的幂 https://leetcode.cn/problems/power-of-two/
思路分析
如果存在一个整数x使得 2^x n则认为n是2的幂次方
方法1除法 用除法逐步缩小n的值 首先判断 n 是否是正整数n为0或者为负整数返回false n 是正整数连续对n进行除以2的操作直到n不能被2整除如果 n1返回true否则返回false
方法2位运算 该方法与前面统计数字转换成二进制之后1的个数思路一致 当 n0 时考虑 n 的二进制表示 如果 n 2^k则n的二进制表示为1后面跟 k 个0 仅当 n 的二进制表示中只有最高位是1其余位都是0此时满足 n(n-1)0
代码实现
class Solution:def isPowerOfTwo(self, n: int) - bool:# 方法1除法if n 0:return Falsewhile n % 2 0:n // 2return n 1class Solution:def isPowerOfTwo(self, n: int) - bool:# 方法2位运算return n0 and n(n-1) 02.2求3的幂
LeetCode326 https://leetcode.cn/problems/power-of-three/
思路分析
方法1除法 同上面求2的幂
方法2技巧 给定的n是int型其最大值为 2^31-1 不超过 2^31 的最大的3的幂是 3^19 1162261467 如果在 1~2^31-1内的数如果是3的幂则一定是能被 1162261467 整除
代码实现
方法1除法
class Solution:def isPowerOfThree(self, n: int) - bool:# 方法1除法if n0:return Falsewhile n%30:n//3return n 1方法2技巧
class Solution:def isPowerOfThree(self, n: int) - bool:# 方法2技巧return n0 and 3**19 % n 0拓展思考
这里将3换成 456789可以吗如果不可以那如果只针对素数 3571113可以吗
2.4求4的幂
LeetCode342 https://leetcode.cn/problems/power-of-four/submissions/
思路分析
方法1除法 与求2的幂思路一致数学方法一直除
方法2利用2的次幂进行拓展来优化 如果n是4的幂那么n一定是2的幂 满足 n(n-1)0 如果n是4的幂n的二进制表示只有1个11后面必须有偶数个0且1出现在从低位开始从0开始的第偶数个二进制位上
如 16 的二进制表示 10000
n为32为有符号整数构建辅助二进制数 MASK 1010 1010 1010 1010 1010 1010 1010 1010 MASK AAAAAAAA 16进制
方法3取模
4^x≡(31) ^x ≡1^x≡1(mod 3)
如果 n是2的幂却不是 2 的幂那么它可以表示成 4^× * 2它除以3的余数一定为2。 因此我们可以通过n除以 3 的余数是否为 1来判断 n 是否是 4 的幂。
代码实现
方法1
class Solution:def isPowerOfFour(self, n: int) - bool:# 方法1除法if n 0:return Falsewhile n % 4 0:n // 4return n 1方法2
class Solution:def isPowerOfFour(self, n: int) - bool:# 方法22的幂的拓展return n0 and n(n-1)0 and n(0xaaaaaaaa) 0方法3
class Solution:def isPowerOfFour(self, n: int) - bool:# 方法3:取模return n0 and n(n-1)0 and n % 3 1
