成都网站建设哪家便宜,域名注册阿里云,南昌网站seo技术,网页美工设计教案网页元素设计文章目录 前言数组实现加法专题数组实现整数加法字符串加法二进制加法 幂运算专题求2的次幂求3的次幂求4的次幂 总结 前言 提示#xff1a;人心本易趋死寂#xff0c;苦难之后#xff0c;焕然重建#xff0c;激荡一阵#xff0c;又趋麻木。 --苏枕书《有鹿来》 我们继续看… 文章目录 前言数组实现加法专题数组实现整数加法字符串加法二进制加法 幂运算专题求2的次幂求3的次幂求4的次幂 总结 前言 提示人心本易趋死寂苦难之后焕然重建激荡一阵又趋麻木。 --苏枕书《有鹿来》 我们继续看几个数学与数字相关的重要题目数学的问题有很多力扣上面也有很多练习通过这些练习你可以掌握很多技巧真的如果你不练习你真的不知道其实还可以这么做。所以算法也是一个累计的过程积累经验才能以后游刃有余。 数组实现加法专题
数字加法可以说是老生常谈了但是让你用数组表示一个数你需要如何去实现呢今天我们就来挑战一下。
这里提前说一下你会遇到很多棘手的问题例如A[0]位置时发现如果进位要怎么办
再拓展一下如果给定两个数一个数用数组存储另外一个是普通的整数又该如何处理呢
在拓展如果两个整数是用字符串表示的呢 如果是二进制表示的呢加法的规则怎么处理
数组实现整数加法
参考题目介绍66. 加一 - 力扣LeetCode 这个看似很简单从后向前一次加就行了如果有进位就标记一下但是如果到头了也要进位要怎么办
例如digits[9,9,9]从后面向前加的时候到了A[0]的位置计算为0需要再次进位但是数组却不能保存这里该怎么办
这里的关键是A[0] 在什么时候出现进位的情况我们直到此时一定是9 99 999 …这样的结构才会出现加1之后再次进位而进位之后的结果一定是101001000这样的结构由于Java中数组默认初始化为0所以我们此时只需要再次申请一个空间比A[]大一个数的数组B[],然后将B[0]设置为1就可以。代码写起来也很简洁。 /*** 整数加一* param digits* return*/public static int[] plusOne(int[] digits) {int len digits.length;for (int i len - 1; i 0; i--) {digits[i];digits[i] % 10;// 注意这里 提前出去的条件if (digits[i] ! 0) {return digits;}}// 9 99 999等 // 这里比较巧妙digits new int[len 1];digits[0] 1;return digits;}字符串加法
我们继续看将数组存储再字符串中的情况字符串加法就是使用字符串表示数字然后计算他们的和。具体要求如下给定两个字符串形式的非负整数num1和num2计算他们的和并同样以字符串形式返回。你不能使用内建的用于处理大整数的库比如BigInteger也不能直接将输入的字符串转换成整数形式。
我们写个例子
例如
输入num1 456 , num2 77
输出533我们先想一下小学里面的加法是如何实现两个数的计算的。经典的竖式加法 从低位到高位逐步相加如果当前位和超过10则向高位进一位。
因此我们只要将这个过程用代码表示出来就可以了。先定义两个指针 i 和 j 分别指向 num1 和num2 的末尾也就是最低位同样定义一个变量 add 维护当前是否需要进位然后从末尾到开头诸位累加。
这里有个问题两个数字位数不同该怎么处理很简单补0就可以了我们看看具体要怎么做吧 /*** 两个字符串相加* param num1* param num2* return*/public static String addStrings(String num1, String num2) {// 准备工作int len1 num1.length(), len2 num2.length();StringBuffer ans new StringBuffer();int add 0;// 注意循环条件处理while(len1 0||len2 0 || add ! 0){// 缺位补0int x len1 0 ? num1.charAt(len1) - 0 : 0;int y len2 0 ? num2.charAt(len2) - 0 : 0;int result x y add;ans.append(result % 10);add result / 10;len1--;len2--;}// 计算完毕后记得反转ans.reverse();return ans.toString();}二进制加法
参考题目介绍67. 二进制求和 - 力扣LeetCode 我们看看二进制怎么处理吧这个题目也是用字符串表示数据的也要先转为字符数组。我们熟悉的十进制是从个位开始逐步到高位达到10就进位而对于二进制判断相加之后是否为2就可以决定是否发生进位了。如果是就进位。所以思路大致一样也是由于字符串的操作原因不确定左后移位是否出现进位这里提供两个办法处理
第一种在进行计算时直接拼接字符串得到一个反向字符最后再翻转回来。10进制一样第二种按照位置给结果字符赋值最后如果有进位则在前方进行字符串拼接加进位
我们这里就采用第二种做 /*** 两个字符串二进制相加* param a* param b* return*/public static String addBinary(String a, String b) {// 准备工作int len1 a.length(), len2 b.length();StringBuffer ans new StringBuffer();int add 0;for (int i len1 - 1, j len2 - 1; i 0 || j 0; i--, j--) {int sum add;sum i 0 ? a.charAt(i) - 0 : 0;sum j 0 ? b.charAt(j) - 0 : 0;ans.append(sum % 2);add sum / 2;}ans.append(add 1 ? add : );return ans.reverse().toString();}当然有人回想这里转成十进制计算完成后再转成二进制不也行吗这么实现很容易而且可以使用语言的特性直接转换但是面试的时候也不行用不了但是工程里可以这么做稳定算法不行不能这么干
幂运算专题 幂运算也是常见的数学运算其形式为ab也就是a的b次方呗其中a称为底数b称为指数ab的合法运算不会出现a 0 且 b 0 的情况。幂运算满足底数和指数都是实数。根据具体情况底数和指数的数据类型和取值范围也各不相同例如有的说是底数是正整数指数为非负数有的问题中底数为实数指数是整数。 力扣中幂运算相关的问题主要判断一个数是不是特定正整数的整数次幂以及快速处理幂。
求2的次幂
参考题目介绍231. 2 的幂 - 力扣LeetCode 本题目的解决思路还是很清晰的我们可以用除的方法来逐步缩小n的值另外一个就是使用位运算。
逐步缩小的方法就是如果n是2的幂数 则 n 0且存在非负整数 k 是的 n 2 ^ k。
首先判断 n 是否是正整数如果 n 是 0 或者 负整数则 n 一定不是 2 的幂。
当 n 是整数时为了判断 n 是否是 2 的幂 可以连续对 n 进行除以 2 的操作直到 n 不能被 2 整除。此时如果 n 1那么 n 就是 2 的幂数否则 n 不是 2 的幂。
代码如下 /*** 是否为2的幂* param n* return*/public static boolean isPowerOfTwo(int n) {if ( n 0){return false;}while (n % 2 0){n / 2;}return n 1;}当然这种方法效率不高容易超时。但是我们有法宝 位运算加强
如果采用位运算该方法与我们之前说的统计数字转换二进制数以后1的个数思路一致。当 n 0 时考虑 n 的二进制表示。如果存在非负整数k 使得 n 2 ^ k 则n 的二进制表示为 1 后面跟着 k 个 0 。由此可以看出正整数 n 是 2 的幂当且仅当 n 的二进制表示中只有最高位是 1 其余位 都是 0 此时满足 n n - 1) 0。此时代码就简单多了。 public boolean isPowerOfTwo(int n) {return (n 0) (n (n - 1)) 0;}注意考虑优先级问题
求3的次幂
参考题目介绍326. 3 的幂 - 力扣LeetCode 逐步缩小的方法对此也适用
如果n是 3 的幂数 则 n 0且存在非负整数 k 是的 n 3 ^ k。
首先判断 n 是否是正整数如果 n 是 0 或者 负整数则 n 一定不是 3 的幂。
当 n 是整数时为了判断 n 是否是 3 的幂 可以连续对 n 进行除以3 的操作直到 n 不能被 2 整除。此时如果 n 1那么 n 就是 3 的幂数否则 n 不是 3 的幂。 public boolean isPowerOfThree(int n) {if(n 0){return false;}while(n % 3 0){n / 3;}return n 1;}这个技巧和上面的一样这里提供另一个思路
由于输入 n 是 int 型 其最大值为 2 ^ 31 - 1。因此在int 型的数据范围内存在最大的 3 的幂不会超过2 ^ 31 - 1最大的 3 的幂是 3 ^ 19 1162261467。所以在 1 ~ 2 ^ 31 - 1内的数如果是 3 的幂数那么一点是1162261467的除数所以这里就可以这样写 public boolean isPowerOfThree(int n) {return n 0 1162261467 % n 0;}当然这个解法只是扩展思路的没必要记住这个1162261467这个数字。
思考一下这里换成456789可以嘛如果不可以那如果只是针对素数35711 13 可以嘛
求4的次幂
参考题目介绍342. 4的幂 - 力扣LeetCode 上述同样的方法这里也可行推荐换一种判断负数的方式 public boolean isPowerOfFour(int n) {while(n ! 0 n % 4 0){n / 4;}return n 1;}试想一下这个题还能怎么优化是否可以利用2的次幂呢
这里留一个作业
当然除了幂运算指数计算的思路与之类似感兴趣也可以尝试下
50. Pow(x, n) - 力扣LeetCode
那这个题练练手 总结
提示数组加法专题字符串加法二进制加法幂运算幂运算优化 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
