面试题1：整数除法
基础知识：整数的数据类型包括 32位int(-2^31 ~ 2^31 -1) ， 16位short (-2^15 ~ 2^15 -1)
思路：
一个很直观的想法是基于减法实现除法。例如，为了求 19/2 可以从 19 中不断减去 2，那么减去 9 个 2 以后就剩下 1，可以得到 19/2 = 9，但是效率很低，当被除数是 n,除数是 1 的时候，算法复杂度最差为 O(n)。如果将上述解法做一些调整，当被除数大于除数时，继续判断是不是大于除数的 2 倍？ 4 倍？ 8 倍？....如果被除数大于除数的 2^k 倍，那么将被除数减去除数的 2^ k 倍，之后再重复以上步骤。
举个例子 19/2，19 大于 2，也大于 4 (2 * 2 ^ (1))，也大于 8 (2 * 2 ^ (2))，也大于 16 (2 * 2 ^ (3))，但是小于 32 (2 * 2 ^ (4))，于是将 19 - 16 得到 3，并记录此时的答案 8，此时被除数变为 3，除数还是 2，重复上述结果得到此时答案为 1，剩下被除数 1，已经小于 2，最终结果为 8 + 1 = 9。算法复杂度为 O(logn)。
基于被除数和除数都是正整数，如果存在负整数则可以将他们先转化为正整数进行计算，最后根据符号调整结果。但是对于 32 位 int 来讲，最大的正数为 2^31-1,最小的负数为 -2^31,如果将负数转化为正数会溢出，所以可以将正数都转化为负数计算，核心部分就是对两个负数进行除法，返回的结果可以用无符号数返回，最后进行正负号调整。另外所有的结果中存在一种情况无法用 int 表示结果，那就是被除数为 -2^31，除数为 -1，这时候直接特殊判断输出 INT_MAX 就行。
class Solution {
public:
// 整数相除
// 1: a 被除数 b 除数
// 方法： 2的倍数法
int divide(int a, int b) {
// 对于有符号整型 （-2^-31 ~ 2 ^ 31 -1 ） 要考虑边界问题
if (a == INT_MIN && b == -1) {
// -2^-31 / -1 = 2^31 -1
return INT_MAX;
}
// 有符号类型正数的绝对值都小于负数,所以都转化为负数求解, 保证相除不会出现溢出
// 需要记录被除数和除数的正负号
int negative = 2;
if (a > 0) {
negative--;
a = a * (-1);
}
if (b > 0) {
negative--;
b = b * (-1);
}
// 倍数二分法求相除的结果
unsigned int ret = divideCore(a, b); // 注意一定要写成无符号的
return negative == 1 ? -ret : ret;
}
int divideCore(int& a, int& b) {
int res = 0;
// 除数大于被除数则返回0
while (a <= b) {
int value = b; // value 表示当前的除数累加值
unsigned int cur = 1; // 当前的倍数 注意一定要写成无符号的
// 二分法 让被除数一直去二分比较
while (value >= 0xc0000000 && a <= value + value) {
cur += cur; // 倍数累加
value += value; // 除数累加
}
res += cur; // 能除几倍, 商就是几
a -= value; // 被除数更新 （减去被除的数）
}
return res;
}
};
面试题2： 二进制加法
思路： 从低位 按位求和，计算进位。之后字符串去反。
class Solution {
public:
string addBinary(string a, string b) {
// 模拟字符串相加,逢2进1
string res;
int cur_sum = 0; // 当前位求和值
int flag = 0; // 进位标志位
int m = a.size() - 1;
int n = b.size() - 1;
while (m >=0 || n >= 0) {
cur_sum += flag;
if (m >= 0) {
cur_sum += a[m] - '0';
m--;
}
if (n >= 0) {
cur_sum += b[n] - '0';
n--;
}
flag = cur_sum / 2; // 计算当前位的进位值
res += (cur_sum % 2) + '0'; // 字符串追加
cur_sum = 0;
}
if (flag > 0) {
res += (flag % 2) + '0'; // 字符串追加
}
reverse(res.begin(), res.end()); // 反转字符串
return res;
}
};
3: 找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
思路： hash
class Solution {
public:
int findRepeatNumber(vector& nums) {
unordered_map hash_map;
for (int i = 0; i < nums.size(); i++) {
hash_map[nums[i]]++;
if (hash_map[nums[i]] >= 2)
return nums[i];
}
return nums[nums.size() - 1];
}
};
面试题4：二维数组中的查找
思路：从后往前看。
class Solution {
public:
bool findNumberIn2DArray(vector>& matrix, int target) {
int rows = matrix.size();
if (rows == 0) return false;
int cols = matrix[0].size();
int i = 0;
int j = cols - 1;
while (i < rows && j >= 0) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j = j - 1; // 向前看一列
} else {
i = i + 1; // 向下看一行
}
}
return false;
}
};
