[小玄的刷题日记]《LeetCode零基础指南》(第二讲) 函数

2022-04-11 241

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： [小玄的刷题日记]《LeetCode零基础指南》(第二讲) 函数

371.两整数之和

1.两整数之和

intgetSum(inta, intb){
returna + b;
}

2，位运算

预备知识：有符号的整数通常使用补码来表示和存储。补码具有以下特性：

正整数的补码与原码相同；负整数的补码为其原码除符号位外的所有位取反后+1
可以将减法运算转换为补码的加法运算来实现
符号位与数值位可以一起参与运算

异或相当于一次无进位加法。来看一个例子

a ^ b得到了一个无进位加法运算结果，如果要得到 a + b 的结果的最终值，我们还要找到进位的数，把这二者相加

我们可以用与操作获得进位

由计算结果可见，0100 并不是我们想要的进位，1 + 1所获得的进位应该放在它的更高位，即在左侧位上，因此我们还要将 0100 左移一位，这才是我们所要的进位结果

总结一下：

a + b 的问题拆分为（a + b 的无进制位结果） 和 （ a + b 的进制位结果）
无进位加法使用异或计算得出
进位结果使用与运算和移位运算得出
循环此过程，直到进位为 0

intgetSum(inta, intb){
intc = 0;
while(b)
    {
c = (unsignedint)(a & b) << 1;
a ^= b;
b = c;
    }
returna;
}

面试题 17.01. 不用加号的加法 - 力扣（LeetCode） (leetcode-cn.com)

1，正常做法 2，位运算

intAdd(inta, intb){
intc = 0;
while(b)
    {
c = (unsignedint)(a & b) << 1;
a ^= b;
b = c;
    }
returna;
}

思路参考第一题

剑指 Offer 65. 不用加减乘除做加法 - 力扣（LeetCode） (leetcode-cn.com)

此题的解法也类似上面两道题

面试题 08.05. 递归乘法 - 力扣（LeetCode） (leetcode-cn.com)

对于这一题，我们可以采用暴力的方法直接 return a * b

不过，我们也可以按照题目的意思来操作一下下。

intmultiply(intA, intB){
intresult; 
if (B > 1)
result = multiply(A, B-1) + A;
elseresult = A;
returnresult;
}

递归使用乘法函数，相当于b次的a相加

方法二

基本情况：

B = 0 , 结果 == 0
B = 1 , 结果 == A

考虑B为偶数的情况

res = A * ( B / 2) + A * ( B / 2)

当B为奇数时，只要在原本的结果上再加上 A 即可

intmultiply(intA, intB){
if(B == 0) return0;
if(B == 1) returnA;
intC = 0;
if(B & 1 > 0) //表示B为奇数
    {
C = A;
    }
returnmultiply(A , B >> 1) + multiply(A , B >> 1) + C;
}

29. 两数相除 - 力扣（LeetCode） (leetcode-cn.com)

题目规定了【只能存储32位整数】，如果我们使用64位整数，可以极大地方地方便我们的代码，但这是违反题目规则的。

如果除法结果溢出，我们需要返回 2（31）- 1

当除数为32位有符号整数的最小值-2（31） - 1时，如果除数为1，我们直接返回 -2（31） || 如果除数为-1，那么答案为 2（31），产生了溢出，我们需要返回的值为2（31） - 1
当被除数为0时，我们可以直接返回0

于是，年幼的我们选择了

向大佬学习

intdivide(intdividend, intdivisor){
intcnt = 0;
intsign = 1;
if ((dividend ^ divisor) < 0) { // 两数任意一个为负数
sign = -1;
    }
if (divisor == INT_MIN) { // 除数边界值特殊处理
if (dividend == INT_MIN) {
return1;
        } else {
return0;
        }
    }
if (dividend == INT_MIN) { // 被除数边界值特殊处理
if (divisor == -1) {
returnINT_MAX;
        } elseif (divisor == 1) {
returnINT_MIN;
        }
dividend += abs(divisor); // 先执行一次加操作，避免abs转换溢出
cnt++;
    } 
inta = abs(dividend);
intb = abs(divisor);
while (a >= b) {
intc = 1;
ints = b;
        // 需指数级快速逼近，以避免执行超时
while (s < (a >> 1)) { // 逼近至一半，同时避免溢出
s += s;
c += c;
        }
cnt += c;
a-= s;
    }
return (sign == -1) ? -cnt : cnt;
}

50. Pow(x, n) - 力扣（LeetCode） (leetcode-cn.com)

我尝试使用了常规的思路如下

doublemyPow(doublex, intn){
doublesum = 1;
inti = 0;
if(n == 0)
return1.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;
    }
returnsum;
}

不过时间复杂度太高，运行超时。后来去学习了大佬的解法如下：

方法一：递归

doublemyPow(doublex, intn){
if (n == 0) return1;
if (n == 1) returnx;
if (n ==-1) return1/x;
doubletemp = myPow(x, n / 2);
returntemp * temp * myPow(x, n % 2);
}

方法二：迭代

doublemyPow(doublex, intn){
doubleres = 1.0;
if (n < 0) x = 1/x;
while (n) {
if (n & 1) res = res * x;   //括号内等同(n % 2)
x = x * x;
n = n / 2;
    }
returnres;
}

方法三：快速幂

快速幂的本质是分治算法。

举个例子：

从x开始，直接将上一次的结果进行平方，计算6次就能得到x（64）次方，而不需要对x*63次x 从左到右进行推导看上去比较困难，因为在每一步中，我们不知道在将上一次的结果平方后是否还需要*x。如果我们从右往左看，分治的思想就很明显了。

当我们要计算时，我们可以先递归计算出 y = ,其中[n /2 ]表示对a进行向下取整

根据递归的结果，如果n为偶数，你们 = ;如果n为奇数，那么 = * x

递归的边界为 n = 0,任意数的 0次方为1

classSolution {
public:
doublequickMul(doublex, longlongN) {
if (N == 0) {
return1.0;
        }
doubley = quickMul(x, N / 2);
returnN % 2 == 0 ? y * y : y * y * x;
    }
doublemyPow(doublex, intn) {
longlongN = n;
returnN >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};