一、整数1、整数除法
题目描述：给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
解题思路：利用减号“-”进行处理，利用不断减去除数的倍数来进行算法优化。
（1）需考虑边界及溢出情况：
①int型取值范围为-2^31到2^31-1
②INT_MIN/-1溢出为INT_MAX
③abs(INT_MIN)=INT_MIN
（2）主要算法描述（while循环部分）：
①初始化value及k，其中value为每次从被除数a中“加上”的值，k为当前内层while循环中value为除数b的倍数；
②如果被除数a的值“小于等于”value+value，那么令value与k均变为原来的2倍，重复此步骤直至被除数a的值“大于”value+value；
③令被除数a“减去”当前的value值，并且令结果res+=k；
④重复 ①~③步直至a>b。
代码参考：
int divide(int a, int b) {
//int型取值范围为-2^31到2^31-1,INT_MIN/-1溢出为INT_MAX
if (a == INT_MIN && b == -1) return INT_MAX;
//利用异或预算把结果符号单独计算
int sign = (a > 0) ^ (b > 0) ? -1 : 1;
//不用abs()函数原因：abs(INT_MIN)=INT_MIN，故把二者均转化为负数计算，不存在溢出问题
if (a > 0) a = -a;
if (b > 0) b = -b;
//如果不用unsigned的话，那么当 a = -2147483648, b = 1 的时候，k会越界,res也会跟着越界
unsigned int res = 0;
while (a <= b) {
int value = b;
// 如果不用 unsigned 的话，那么当 a = -2147483648, b = 1 的时候，k 会越界
unsigned int k = 1;
// 0xc0000000 是十进制 -2^30 的十六进制的表示
// 判断 value >= 0xc0000000 的原因：保证 value + value 不会溢出
// 可以这样判断的原因是：0xc0000000 是最小值 -2^31 的一半，
// 而 a 的值不可能比 -2^31 还要小，所以 value 不可能比 0xc0000000 小
while (value >= 0xc0000000 && a <= value + value) {
k += k;
value += value;
}
a -= value;
res += k;
}
//结果加上符号返回
return sign == 1 ? res : -res;
}
2、二进制加法
题目描述：给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。输入为 非空 字符串且只包含数字 1 和 0。
解题思路：利用位运算解决
注意：从尾部向前计算and进位问题。
代码参考：
string addBinary(string a, string b) {
int aSize=a.size(),bSize=b.size();
stack tempRes;
int cur=0,partial=0;
while(bSize>0 && aSize>0)
{
int curA=a[aSize-1]-'0',curB=b[bSize-1]-'0';
cur=curA ^ curB ^ partial;
tempRes.push(cur);
if(curA==1 && curB==1 || curA==1 && partial==1 || curB==1 && partial==1 )
partial=1;
else partial=0;
aSize--;bSize--;
}
while(aSize>0)
{
int curA=a[aSize-1]-'0';
cur=curA ^ partial;
tempRes.push(cur);
if(curA==1 && partial==1)
partial=1;
else partial=0;
aSize--;
}
while(bSize>0)
{
int curB=b[bSize-1]-'0';
cur=curB ^ partial;
tempRes.push(cur);
if(curB==1 && partial==1)
partial=1;
else partial=0;
bSize--;
}
if(partial==1)
tempRes.push(partial);
string res;
int stSize=tempRes.size();
for(int i=0;i
3、前n个数字二进制中1的个数
题目描述：给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
解题思路：动态规划and位运算
对于所有的数字，只有奇数和偶数两种：
（1）奇数：二进制中，奇数比前一个偶数多一个 1（多的1为最低位的 1）。
（2）偶数：二进制中，偶数中 1 的个数一定和除以 2 之后的那个数一样多（最低位是 0，除以 2 就是右移一位，即抹掉最低位的0，故 1 的个数不变）。
代码参考：
vector countBits(int n) {
vector res(n+1,0);
for(int i=0;i<=n;++i)
{
if(i%2==0)
res[i]=res[i>>1];
else
res[i]=res[i-1]+1;
}
return res;
// vector res;
// res.push_back(0);
// for(int i=1;i<=n;++i)
// {
// int num=i;
// int tempRes=0;
// if(num%2==1)
// {
// tempRes=1;
// num--;
// }
// int m=0;
// while(num-pow(2,m)>0) m++;
// for(int j=m;j>0;--j)
// {
// if(num-pow(2,j)>=0)
// {
// tempRes++;
// num-=pow(2,j);
// }
// }
// res.push_back(tempRes);
// }
// return res;
}
4、只出现一次的数字
题目描述：给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。（进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？）
解题思路：位运算
看到该题，我们能想到的第一思路就是利用 哈希表 遍历一遍，再搜索，线性时间即可解决，但是却无法满足进阶要求中的“不使用额外空间”条件，故转变思路利用 位运算 ，下给出算法思路：
（1）一个 int型 整数是由 32 个 0 或者 1 组成的，将数组中所有数字的同一个位置的数位相加，若将出现 3 次的数字单独拿出来，那么这些出现 3 次的数字的任意第 i 个数位之后都能被 3 整除；
（2）若数组中所有数字的第 i 个数位相加之后能被整除，那么只出现一次的数字的第 i 个数位一定为 0 ，若数组中所有数字的第 i 个数位相加之后被 3 除余 1 ，那么只出现一次的数字的第 i 个数位一定为 1 ；
（3）故只出现一次的第 i 个数位可以由整个数组的第 i 个数位共同推算出来，当我们知道一个整数任意一位是 0 还是 1 之后，即可推算出它的数值。
- 举一反三
（1）对照力扣 136题 ：除某个元素仅出现 1 次外，其余每个元素恰出现 2 次；
（2）如果输入一个整数数组，数组中只有一个数字出现 m 次，其它数字都出现 n 次，请找出那个唯一出现 m 次的数字（假设m不能被n整除）。
上述问题解法思路：
（1）采用异或 *** 作，相同的二进制异或为 0 ，反之为 1 。故将数组挨个异或后的结果，即为所求只出现一次的数字；
（2）如果数组中的所有数字的第 i 个数位相加之和能被 n 整除，那么出现 m 次的数字的第i个数位一定是0；否则出现 m 次的数字的第i个数位一定是 1 。
代码参考：
class Solution {
public:
int singleNumber(vector& nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int num: nums) {
total += ((num >> i) & 1);//计算32位中每 i 位的和
}
if (total % 3) {
ans |= (1 << i);//利用或运算把结果中对 3 取余结果为 1 的对应位数置为 1
}
}
return ans;
}
};
5、单词长度的最大乘积
题目描述：给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
解题思路：位运算的又一利用【判重】
最重要的工作即为如何判断两个字符串是否包含相同字符，刚拿到这个题目，我采取了一种极为低效的判重方法，直接对每个 string 进行了 sort ，也 pass 了，详情可参考代码 1 ，不赘述。
下描述位运算的解决思路（代码 2 ）：
（1）一个 int型 数据可表示 32 个二进制位，故一个 int型 整数完全可以cover26 个英文字母；
（2）先利用 |= 运算计算每个 string 对应的判重数组 bitArr ， int型 数的第 0-25 位二进制数表示 a-z ，字母存在对应位置1，否则为0；
（3）二重循环，利用 & 运算判重（bitArr[ i ] & bitArr[ j ] 为 0 表示不存在重复字母），后计算最大乘积。
代码参考：
int maxProduct(vector& words) {
int res=0;
for(int i=0;ires)
{
res=words[i].size()*words[j].size();
}
}
}
return res;
}
int maxProduct(vector& words) {
int bitArr[1000]={0};
//利用0-25位表示a-z，存在为1，否则为0
for(int i=0;i
6、排序数组中两个数字之和
题目描述：给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1]< numbers.length 。假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
解题思路：双指针解法
题目给定有序数组，故考虑双指针，左右指针分别定位数组的左边和右边，令sum = numbers[left] + numbers[right]，判断 sum 和 target 的大小关系：
(1)如果sum > target，right --；
(2)如果sum < target，left ++；
(3)如果sum == target，返回{ left , right }。
代码参考：
vector twoSum(vector& numbers, int target) {
int n=numbers.size();
int left=0,right=n-1;
vector res;
while(lefttarget) right--;
else left++;
}
return res;
}
7、
题目描述：
解题思路：
代码参考：
8、
题目描述：
解题思路：
代码参考：
9、
题目描述：
解题思路：
代码参考：
10、
题目描述：
解题思路：
代码参考：
11、
题目描述：
解题思路：
代码参考：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）