剑指 Offer II 001. 整数除法
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’ 。
注意：
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231, 231?1]。本题中，如果除法结果溢出，则返回 231 ? 1
解题关键
- 初始思路可以是用循环每一次都在被除数的基础上减去除数，然后统计次数。但是如果除数为1，被除数特别大时，复杂度就会太大；所以就要转到第二种方法，相当于循环去找当前一个最大的除数（这个除数可以是原来除数的2/4/8/16.等等倍数，对应左移1/2/3/4位等等），比如19/2，2可以左移3位（左移3位，就相当于在原数基础上乘以8），此时的除数是2 * 8（小于19的情况下能取的最大值）。19-16=3， 3/2时，被除数最大为2（即2 * 1），左移0位，最后的结果就是8+1=9
- 左移1位，相当于乘以2，也相当于对原数字做自加操作（力扣程序会报错不能对负数做左移，可以改成自加）
class Solution {
public:
int divide(int a, int b) {
if (a == INT_MIN && b == -1) {
return INT_MAX;
}
int negative = 2;
if (a > 0) {
negative--;
a = -a;
}
if (b > 0) {
negative--;
b = -b;
}
unsigned int ret = divideCore(a, b);
return negative == 1 ? -ret : ret;
}
unsigned int divideCore(int a, int b) {
int ret = 0;
while (a <= b) {
int value = b;
unsigned int quo = 1;
while (value >= 0xc0000000 && a <= value + value) {
value += value;
}
ret += quo;
a -= value;
}
return ret;
}
};
剑指 Offer II 002. 二进制加法
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “10”
输出: “101”
示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”
提示：每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。 1 <= a.length, b.length <= 10^4。 字符串如果不是 “0” ，就都不含前导零。
解题关键
- 纯数字用位运算求和: 异或用来求不进位的和，进位用（a&b）<<1,注意左移一位，然后在把不进位和与进位相加（异或操作），循环。这个题目是对字符串，思路其实也类似。代码更像是模拟整个加法的过程，设置了一个up变量作为进位的记录。进位的英文是carry
class Solution {
public:
string addBinary(string a, string b) {
string res;
int lenA = a.size();
int lenB = b.size();
int maxSize = max(lenA, lenB);
res.resize(maxSize);
if(lenA > lenB){
string tmp(lenA - lenB, '0');
b = tmp + b;
}else if(lenA < lenB){
string tmp(lenB - lenA, '0');
a = tmp + a;
}
int up = '0';
for(int i=a.size() - 1; i >= 0; i--){
if(a[i]=='1' && b[i]=='1'){
if(up == '0'){
res[i] = '0';
up = '1';
}else{
res[i] = '1';
}
}else if((a[i]-'0') ^ (b[i]-'0')){
if(up == '0'){
res[i] = '1';
}else{
res[i] = '0';
}
}else{
if(up == '0'){
res[i] = '0';
}else{
res[i] = '1';
}
up = '0';
}
}
return up=='0'? res : '1' + res;
}
};
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
示例 1:
输入: n = 2
输出: [0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:
输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
说明 :
0 <= n <= 105
进阶:
给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
要求算法的空间复杂度为 O(n) 。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。
解题关键：
- 对于这种要算1的个数的题目，要马上想到 i&(i-1) 这个式子。举一个例子，如果数字14，也就是1110，i&(i-1) = 1110 & 1101 = 1100.最终效果就是把原数中二进制的1减少一个。具体理解一下：i-1的作用是把原二进制数中最右边的0变成1，最右边的1变成0，所以再求与运算的时候，相当于在原数基础上减少了一个数字1. 对于每一个数字，都可以用while循环做这个运算，并统计最后数字变为0时，运算的次数a（相当于进行了a次这个运算，也就是减少了a个1后数字变为0，即这个二进制数有a个1）。复杂度为O(kn)，n为数字个数，k为数字的位数
- 根据第一步的原理，其实就可以发现数据相互之间的关系，使用动态规划的思想。即，数字i和数字i&(i-1)之间相差一个1，或者可以利用奇偶性，如果数字i右移一位，如果i是偶数，那么最后一位本来就是0，右移后1的个数不变，如果i为奇数，右移后1的个数会少一个。
class Solution {
public:
vector<int> countBits(int n) {
vector<int> res(n+1, 0);
for(int i=1; i<=n; i++){
res[i] = res[i&(i-1)] + 1;
}
return res;
}
};
class Solution {
public:
vector<int> countBits(int n) {
vector<int> res(n+1, 0);
for(int i=1; i<=n; i++){
res[i] = res[i>>1] + (i&1);
}
return res;
}
};
剑指 Offer II 004. 只出现一次的数字
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,100]
输出：100
提示：
1 <= nums.length <= 3 * 104
-2^31 <= nums[i] <= 2^31 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解题关键：
- 一种比较通用解法是只看32位中，每一位得到了多少的贡献。数组的每一个数相加之后，每一位数上，1的总个数一定是3N，或者3N+1.只要把每一位对3求余，如果哪一个余数为1就说明多出来的那一个数在这一位上多贡献了一个1. 如果题目改成其他数重复了k次，把3变成k即可。时间复杂度为O(32n)=O(n)
- 还有一种数字电路的方式，见力扣大佬的解答
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
int k = 3;
for(int i=0; i<32; i++){
int cnt = 0;
for(auto num : nums){
cnt += (num>>(31-i))&1;
}
res = (res <<1) + (cnt%k!=0);
}
return res;
}
};
剑指 Offer II 005. 单词长度的最大乘积
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
示例 1:
输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。
示例 3:
输入: words = [“a”,“aa”,“aaa”,“aaaa”]
输出: 0
解释: 不存在这样的两个单词。
提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母
解题关键：
- 因为只有26个小写字母，所以可以把他们对应的放到一个32位的int整数中，如果对应位置有字母，那么那一位就为1. 之后检查是否有重复的字母时，就可以看按位与运算的结果是否为0，为0则没有重复字母。
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> nums(words.size(), 0);
for(int i=0; i<words.size(); i++){
for(auto w : words[i]){
nums[i] |= (1<<(w-'a'));
}
}
int res = 0;
for(int j=0; j<nums.size()-1; j++){
for(int k=j+1; k<nums.size(); k++){
if( (nums[j] & nums[k]) ==0){
int tmp = words[j].length() * words[k].length();
res = res > tmp ? res : tmp;
}
}
}
return res;
}
};
剑指 Offer II 006. 排序数组中两个数字之和
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
示例 1：
输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
解题思路：
- 看到排序数组，其实应该很快能联想到双指针方法。然后对于这道题，双指针放两头，和大了，左移right指针；和小了，右移left指针。注意这里的left和right都是取的闭区间。
- 如果不是排序数组，对于两数之和问题就用map来解决。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size()-1;
vector<int> res;
while(left < right){
if(numbers[left] + numbers[right] > target){
right--;
}else if(numbers[left] + numbers[right] < target){
left++;
}else{
res.push_back(left);
res.push_back(right);
return res;
}
}
return res;
}
};
|