[C++知识库]【解题报告】《九日集训》诺亚方舟(第一天)

?
语言：C++

很难自己想出中等题题解，两数相除还有点问题，过后补

目录

371. 两整数之和

面试题 17.01. 不用加号的加法

剑指 Offer 65. 不用加减乘除做加法

面试题 08.05. 递归乘法

29. 两数相除

30. Pow(x, n)]

31. Sqrt(x)]

面试题 16.07. 最大数值

371. 两整数之和
372. 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2 输出：3

循环之前：

c=a ^ b 用c记录a与b异或的值（不进位的和）

tmp = a & b 用tmp记录a与b的值 （进位时的和，因为有进位，计算的时候记得左移一位）

进入循环（有进位）：

用x记录下c的值，再去更新c的值

c = c ^ (tmp << 1) 更新c：记录c与进位tmp<<1异或的值（不进位的和）

tmp = x & (tmp << 1) 更新进位tmp：记录x与进位tmp<<1与的值（进位的和）

tmp必须设置成无符号型整数：如果左移的数的最高位是符号位，有的编译器会报错

runtime error: left shift of negative value -2147483648 (solution.cpp)

int getSum(int a, int b)
{
int c = a ^ b;
unsigned int tmp = a & b;
int x = c;
while (tmp)
{
x = c;
c = c ^ (tmp << 1);
tmp = x & (tmp << 1);
}
return c;
}
理解上述过程后，简化得以下结果

int getSum(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
面试题 17.01. 不用加号的加法
面试题 17.01. 不用加号的加法

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:

输入: a = 1, b = 1 输出: 2

同上

int add(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
剑指 Offer 65. 不用加减乘除做加法
剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1 输出: 2

同上

int add(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
面试题 08.05. 递归乘法
面试题 08.05. 递归乘法

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

输入：A = 1, B = 10 输出：10

A、B两数相乘（均非0）的实质就是A相加B次

采用递归实现

class Solution
{
public:
int multiply(int A, int B)
{
if (A == 0 || B == 0)
return 0;
return A + multiply(A, B - 1);
}
};
29. 两数相除
29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333…) = truncate(3) = 3

先附上 超时 的代码（用了long）

流程：

1.被除数为0返回0

2.判断除数、被除数的正负，只有当其一为负，才会在都变为绝对值除之后的结果变号

3.除数为1返回被除数，在此就会有溢出的问题，INT_MIN/1会溢出

4.循环（被除数>=除数）：被除数不停的减除数

5.return 结果

class Solution
{
public:
int divide(int dividend, int divisor)
{
if (dividend == 0)
return 0;
long a = dividend;
long b = divisor;
int tmp = 0;
if (dividend < 0 || divisor < 0)
{
if (!(dividend < 0 && divisor < 0))
tmp = 1;
a = abs(a);
b = abs(b);
}
?
if (b == 1)
{
if (tmp == 1)
{
return -a;
}
return a > INT_MAX ? INT_MAX : a;
}
?
int num = 0;
while (a >= b)
{
a -= b;
num++;
}
return tmp ? -num : num;
}
};
50. Pow(x, n)]
50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即x^n）。

示例 1：

输入：x = 2.00000, n = 10 输出：1024.00000

自己想的是 x*myPow(x, n-1) ，结果stack-overflow

法一 ：

评论区看到的一个绝妙思路

和官解二类似

每个二进制数位都有一个权值，权值如下图所示，最终结果就等于所有二进制位为1的权值之积，, 例如上述 x^77次方对应的二进制 (1001101) 和每个二进制位的权值如下

1 ? ? ?0 ? ? ?0 ? ? 1 ? ?1 0 ? 1
x^64 x^32 x^16 x^8 ? x^4 x^2 ?x^1
?
最终结果就是所有二进制位为1的权值之积：x^1 * x^4 * x^8 * x^64 = x^77
而且我们不必预先把每一个二进制位的权值计算出来，我们可以一边计算结果，一边计算权值

class Solution
{
public:
? ?double myPow(double x, int n)
? {
? ? ? ?if (x == 0)
? ? ? {
? ? ? ? ? ?return 0;
? ? ? }
? ? ? ?else if (n == 1)
? ? ? {
? ? ? ? ? ?return x;
? ? ? }
?
? ? ? ?long power = n;// 为了保证-n不溢出->INT_MIN，先转换成long类型
? ? ? ?if (n < 0)
? ? ? { ? ? ? ? // 如果n小于0， 求1/x的-n次方
? ? ? ? ? ?power = abs(power);
? ? ? ? ? ?x = 1 / x;
? ? ? }
? ? ? ?double weight = x; ?// 权值初值为x, 即二进制位第1位的权值为x^1
? ? ? ?double res = 1;//保存结果
? ? ? ?while (power)
? ? ? {
? ? ? ? ? ?// 如果当前二进制位为1， 让结果乘上这个二进制位上的权值,
? ? ? ? ? ?// 该位权值在上一轮迭代中已经计算出来了
? ? ? ? ? ?if ((power & 1) == 1)
? ? ? ? ? {
? ? ? ? ? ? ? ?res *= weight;
? ? ? ? ? }
? ? ? ? ? ?weight *= weight; ? // 计算下一个二进制位的权值
? ? ? ? ? ?power >>= 1;
? ? ? }
? ? ? ?return res;
? }
};
法二：

官方题解:快速幂 + 递归

如果我们要计算 x^77，我们可以按照： x→x ^2→x ^4 →x ^9 →x ^19 →x ^38→x 77的顺序

在 x→x ^2，x ^2→x ^4 ，x ^19→x ^38 这些步骤中，我们直接把上一次的结果进行平方；

而在 x^4→x9 ，x^9 →x 19 ，x^38→x77 这些步骤中，把上一次的结果进行平方后，还要额外乘一个x。

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：

当我们要计算 x^n 时，我们可以先递归地计算出 y = x^?n/2?，其中 ?a? 表示对 a 进行下取整；

根据递归计算的结果，如果 n为偶数，那么 x^n = y^2x n=y2；

如果 n 为奇数，那么 x^n = y^2 * 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);
? }
};
法三：

官解：快速幂 + 迭代

由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易的，因为我们不知道是否需要额外乘 x。但我们不妨找一找规律，看看哪些地方额外乘了 x，并且它们对答案产生了什么影响。

我们还是以 x^77 作为例子：x→x ^2→x ^4 →x ^9 →x ^19 →x ^38→x 77并且把需要额外乘 x的步骤打上了 + 标记。

可以发现：

我们把这些贡献相乘，x* x^4* x^8*x64恰好等于 x^77 。

而这些贡献的指数部分又是什么呢？

它们都是 2的幂次，这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1，4，8 和64，恰好就对应了 77 的二进制表示 (1001101) 中的每个 1！

因此我们借助整数的二进制拆分，就可以得到迭代计算的方法，一般地，如果整数 n 的二进制拆分为

class Solution
{
public:
? ?double quickMul(double x, long long N)
? {
? ? ? ?double ans = 1.0;
? ? ? ?// 贡献的初始值为 x
? ? ? ?double x_contribute = x;
? ? ? ?// 在对 N 进行二进制拆分的同时计算答案
? ? ? ?while (N > 0)
? ? ? {
? ? ? ? ? ?if (N % 2 == 1)
? ? ? ? ? {
? ? ? ? ? ? ? ?// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
? ? ? ? ? ? ? ?ans *= x_contribute;
? ? ? ? ? }
? ? ? ? ? ?// 将贡献不断地平方
? ? ? ? ? ?x_contribute *= x_contribute;
? ? ? ? ? ?// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
? ? ? ? ? ?N /= 2;
? ? ? }
? ? ? ?return ans;
? }
?
? ?double myPow(double x, int n)
? {
? ? ? ?long long N = n;
? ? ? ?return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
? }
};
69. Sqrt(x)]
69. Sqrt(x)

难度简单837

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4 输出：2

二分法查找符合mid^2<x的最大m的值

因为要返回的是<x的mid最大值，所以要在mid^2<x时用ans记录下此刻mid的值，以免mid增大后不符合

class Solution
{
public:
? ?int mySqrt(int x)
? {
? ? ? ?int left = 1;
? ? ? ?int right = x;
? ? ? ?int mid;
? ? ? ?int ans;
? ? ? ?while (left <= right)
? ? ? {
? ? ? ? ? ?mid= left + (right - left) / 2;
? ? ? ? ? ?long tmp = (long)mid * mid;
? ? ? ? ? ?if (tmp == x)
? ? ? ? ? {
? ? ? ? ? ? ? ?return mid;
? ? ? ? ? }
? ? ? ? ? ?if (tmp > x)
? ? ? ? ? {
? ? ? ? ? ? ? ?right = mid-1;
? ? ? ? ? }
? ? ? ? ? ?else
? ? ? ? ? {
? ? ? ? ? ? ? ?ans=mid;
? ? ? ? ? ? ? ?left = mid + 1;
? ? ? ? ? }
? ? ? }
? ? ? ?return ans;
? }
};
面试题 16.07. 最大数值
面试题 16.07. 最大数值

难度简单98

编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。

示例：

输入： a = 1, b = 2 输出： 2

法一：

可以转化为long类型来做

class Solution
{
public:
int maximum(int a, int b)
{
long c = a;
long d = b;
int k = 1 + ((c - d) >> 63);
return k * a + (!k) * b;
?
}
};
法二：位运算

关键点一：

可以使用位运算判断

b & ( (a-b)>>31 ) | a & ( ~(a-b)>>31 )

如果b大，则(a-b)>>31为-1，b&-1=b，或运算|第一个为真，结束运算，直接返回b；

如果a大，则(a-b)>>31为0，b&0=0，或运算|进入下一个判断，(~(a-b)>>31)=-1,a&-1=1，返回a

关键点二：

上述情况如果遇到a-b<INT_MIN，或者a-b>INE_MAX则不适用（溢出）

先加上此句判断：只有当a、b异号时，才会有溢出可能 if(a>>31^b>>31)return a>>31?b:a;

class Solution
{
public:
? ?int maximum(int a, int b)
? {
? ? ? ? if(a>>31^b>>31)
? ? ? ? ? ? return a>>31?b:a;
? ? ? ? return b & ( (a-b)>>31 ) | a & ( ~(a-b)>>31 );
? }
};
但为了不使用if语句，优化为：

tmp代表a的符号位，a为负责tmp=1，否则为0

&&：条件1成立，则不执行条件二

!(a >> 31 ^ b >> 31)&1：代表a、b同号，则tmp要赋值为(a - b) >> 31&1

class Solution
{
public:
int maximum(int a, int b)
{
int tmp = a >> 31&1;
(!(a >> 31 ^ b >> 31)&1)&&(tmp=((a - b) >> 31&1));
return a * (1 - tmp) + b * ?tmp;
}
};

?