分享程序员开发的那些事...
更新时间：2022-10-02 20:32:55
int getSum(int a, int b){ return a + b; }
预备知识：有符号的整数通常使用补码来表示和存储。补码具有以下特性：
异或相当于一次无进位加法。来看一个例子
a ^ b得到了一个无进位加法运算结果，如果要得到 a + b 的结果的最终值，我们还要找到进位的数，把这二者相加
我们可以用与操作获得进位
由计算结果可见，0100 并不是我们想要的进位，1 + 1所获得的进位应该放在它的更高位，即在左侧位上，因此我们还要将 0100 左移一位，这才是我们所要的进位结果
总结一下：
int getSum(int a, int b){ int c = 0; while(b) { c = (unsigned int)(a & b) << 1; a ^= b; b = c; } return a; }
面试题 17.01. 不用加号的加法 - 力扣（LeetCode） (leetcode-cn.com)
int Add(int a, int b){ int c = 0; while(b) { c = (unsigned int)(a & b) << 1; a ^= b; b = c; } return a; }
思路参考第一题
剑指 Offer 65. 不用加减乘除做加法 - 力扣（LeetCode） (leetcode-cn.com)
此题的解法也类似上面两道题
对于这一题，我们可以采用暴力的方法直接 return a * b
不过，我们也可以按照题目的意思来操作一下下。
int multiply(int A, int B){ int result; if (B > 1) result = multiply(A, B - 1) + A; else result = A; return result; }
递归使用乘法函数，相当于b次的a相加
基本情况：
考虑B为偶数的情况
res = A * ( B / 2) + A * ( B / 2)
当B为奇数时，只要在原本的结果上再加上 A 即可
int multiply(int A, int B){ if(B == 0) return 0; if(B == 1) return A; int C = 0; if(B & 1 > 0) //表示B为奇数 { C = A; } return multiply(A , B >> 1) + multiply(A , B >> 1) + C; }
题目规定了【只能存储32位整数】，如果我们使用64位整数，可以极大地方地方便我们的代码，但这是违反题目规则的。
如果除法结果溢出，我们需要返回 2（31）- 1
于是，年幼的我们选择了
向大佬学习
int divide(int dividend, int divisor){ int cnt = 0; int sign = 1; if ((dividend ^ divisor) < 0) { // 两数任意一个为负数 sign = -1; } if (divisor == INT_MIN) { // 除数边界值特殊处理 if (dividend == INT_MIN) { return 1; } else { return 0; } } if (dividend == INT_MIN) { // 被除数边界值特殊处理 if (divisor == -1) { return INT_MAX; } else if (divisor == 1) { return INT_MIN; } dividend += abs(divisor); // 先执行一次加操作，避免abs转换溢出 cnt++; } int a = abs(dividend); int b = abs(divisor); while (a >= b) { int c = 1; int s = b; // 需指数级快速逼近，以避免执行超时 while (s < (a >> 1)) { // 逼近至一半，同时避免溢出 s += s; c += c; } cnt += c; a -= s; } return (sign == -1) ? -cnt : cnt; }
我尝试使用了常规的思路如下
double myPow(double x, int n){ double sum = 1; int i = 0; if(n == 0) return 1.0; if(n > 0) { for(i = 1;i <= n;i++) sum *= x; } if(n < 0) { x = 1.0 / x; for(i = 1;i <= -n;i++) sum *= x; } return sum; }
不过时间复杂度太高，运行超时。后来去学习了大佬的解法如下：
double myPow(double x, int n){ if (n == 0) return 1; if (n == 1) return x; if (n ==-1) return 1/x; double temp = myPow(x, n / 2); return temp * temp * myPow(x, n % 2); }
double myPow(double x, int n){ double res = 1.0; if (n < 0) x = 1/x; while (n) { if (n & 1) res = res * x; //括号内等同(n % 2) x = x * x; n = n / 2; } return res; }
快速幂的本质是分治算法 。
举个例子：
从x开始，直接将上一次的结果进行平方，计算6次就能得到x（64）次方，而不需要对x*63次x从左到右进行推导看上去比较困难，因为在每一步中，我们不知道在将上一次的结果平方后是否还需要*x。如果我们从右往左看，分治的思想就很明显了。
当我们要计算 时，我们可以先递归计算出 y = ,其中[n /2 ]表示对a进行向下取整
根据递归的结果，如果n为偶数，你们 = ;如果n为奇数，那么 = * x
递归的边界为 n = 0,任意数的 0次方 为1
class Solution { public: double quickMul(double x, long long N) { if (N == 0) { return 1.0; } double y = quickMul(x, N / 2); return N % 2 == 0 ? y * y : y * y * x; } double myPow(double x, int n) { long long N = n; return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N); } };
(卷不动了)
面试题 16.07. 最大数值 - 力扣（LeetCode） (leetcode-cn.com)没什么好说的了，三目操作符yyds
今天的LeetCode之旅到此结束，希望能跟英雄哥继续努力学习，不断提高自己！！