LeetCode剑指offer专项（一）整数

001. 整数除法

题目：给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’ 。

注意：
1）整数除法要截取小数部分
2）环境只能存储 32 位有符号整数，如果溢出输出2³¹ − 1

方法：
都要先对符号进行处理，取a的绝对值A和b的绝对值B。
1）暴力逼近：找到最大B×Z<=A，通过不断加B来逼近A，加B的次数Z就是答案。考虑最极端的情况，也就是A=2³¹ − 1、B=1，会超时。
2）二进制模拟除法：找到(B<<i)<= A<(B<<(i+1))，就可以知道商的第i位是1，再让A=(A-B<<i)后重复前面的步骤，无法左移得到就意味着有小数。
3）二分查找：力扣官方给的方法，在方法一的暴力逼近基础上，做了个二分查找的优化找Z，但是每次得到的Z需要通过乘法来判断偏大还是偏小。因为不能使用乘号 “ * ”，可以要用“ 快速乘 ”来实现乘法。

快速乘：其实就是二进制模拟乘法

//快速乘,计算x乘y的积
long long ksc(long long x,long long y,long long p){
    
	long long res=0;
	while(y){
    
		if(y&1)res=(res+x)%p;
		x=(x<<1)%p; 
		y>>=1;
	}return res;
}

代码：用了方法二，二进制模拟除法。

class Solution {
    
public:
    long long divide(long long a, long long b) {
    //用long long，因为是负数绝对值化会超出int
        //符号处理
        bool flag=false;
        if((a>=0&&b>=0)||(a<0&&b<0))
            flag=true;
        //绝对值化
        a=(a<0?-a:a);
        b=(b<0?-b:b);
        //模拟二进制除法
        long long ans=0;
        while(a>=b){
    
            long long x=0,tmp=1;
            while((b<<x)<=a){
    
                x++;
            }
            x--;
            a=a-(b<<x);
            ans=ans+(tmp<<x);
        }
        //结果符号处理
        if(flag==false)
            ans=-ans;
        //按题目要求进行溢出处理
        if(ans>2147483647||ans<-2147483648)
            ans=2147483647;
        return ans;
    }
};

002. 二进制加法

题目：给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

注意：关键在于处理加法进位，尤其是最高位进位。

方法：
1）有些语言可以把10⁴位的二进制数转成是进制计算，例如python和java。
2）用C++语言只能去模拟二进制加法了。

class Solution {
    
public:
    string addBinary(string a, string b) {
    
        //C++ string的相关函数的使用，reverse转置
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int i=0,j=0,c=0;//i遍历a，j遍历b，c记录进位
        string ans;
        while(i<a.size()||j<b.size()||c){
    
            //计算当前位总和，存放在ch中
            char ch=c+'0';
            if(i<a.size())
                ch+=a[i]-'0';
            if(j<b.size())
                ch+=b[i]-'0';
            //处理进位，得出该位合适结果
            if(ch>'1'){
    
                c=1;
                ans.insert(ans.end(),ch-2);
            }
            else{
    
                c=0;
                ans.insert(ans.end(),ch);
            }
            i++;j++;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

003. 前 n 个数字二进制中 1 的个数

题目：给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

方法：
1）暴力，通过不断除2取余来计算每个数字中1的个数，时间复杂度在nlogn。
2）动态规划，对于奇数，一定比上个偶数多一个1；对于偶数，1的个数和除2的数是一样多的，除2只是抹掉地位的0。时间复杂度可以降到O(n)。

代码：方法二

class Solution {
    
public:
    vector<int> countBits(int n) {
    
        vector<int>dp;
        dp.push_back(0);
        for(int i=1;i<=n;i++){
    
            int num=i%2==0?dp[i>>1]:dp[i-1]+1;
            dp.push_back(num);
        }
        return dp;
    }
};

004. 只出现一次的数字

题目：给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

方法：
1）用数组，统计二进制每位出现1次数然后余3就是答案。
2）用map，统计不同数出现的次数，最后遍历一遍map输出只出现一次的数。
3）用数字电路设计，在1）的基础上，从有限状态自动机角度思考。每个二进制位上1的个数余3，存在三种状态，即为0、1、2。用二进制来表示三个状态需要两位，即为00、01、10，分别用two和one来表示高位和低位。通过画出状态转图，再用卡诺图得到状态方程。
$\overline{next-one}=two\ast \overline{one}+\overline{one}\ast \overline{num}+one\ast num$
$\overline{next-two}=\overline{two}\ast \overline{one}+\overline{two}\ast \overline{num}+two\ast num$

two one\输入num	0	1
00	00	01
01	01	10
11(无效)	11	00
10	10	00

代码：方法三

class Solution {
    
public:
    int singleNumber(vector<int>& nums) {
    
        int one=0,two=0;
        for(int i=0;i<nums.size();i++){
    
            int next_one=(two&(~one))|((~one)&(~nums[i]))|(one&nums[i]);
            int next_two=((~two)&(~one))|((~two)&(~nums[i]))|(two&nums[i]);
            one=~next_one;
            two=~next_two;
        }
        return one;
    }
};

扩展：如果是某个元素出现奇数次，而其它元素出现偶数次，则可以用异或来解决。异或是相同为0，不同为1。

005. 单词长度的最大乘积

题目：给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

方法：
1）暴力，判断每对两两不相同的字符中是否满足条件，满足条件后计算长度的乘积，然后看是否需要更新乘积最大值。由于字符串长度和个数最大范围是3000，最坏的时间复杂度会超时。
2）位运算优化：题目要求比较的是不同字符串小写字母的种类，以及计算满足条件的字符串对长度的乘积，所以每个字符串的有效信息可以记录成26位比特（每位比特01表示对应小写字母是否存在），加上其字符串长度。两个字符串有没有相同字符，可以对比特串进行与操作，如果同一位有同为1，则与后必定不为0，则说明有相同的字符。
3）在2）上用map优化：会存在不同字符串有相同的字符种类情况，但是我们只需要保留长度最长的，可以用map匹配不同字符种类含有情况对应的最大长度。这样可以节省多余判断。

代码：方法三

class Solution {
    
public:
    int maxProduct(vector<string>& words) {
    
        //map匹配不同字母种类对应最大字符串长度
        map<int,int>mp;
        for(int i=0;i<words.size();i++){
    
            //存储字符串26字母出现情况，false表示没有，true表示有
            bool w[26]={
    false};
            for(int j=0;j<words[i].length();j++){
    
                w[words[i][j]-'a']=true;
            }
            //把bool数组存储转成int
            int num=0;
            for(int j=0;j<26;j++){
    
                if(w[j])
                    num+=1<<j;
            }
            //记录最大字符串长度
            if(mp[num]<words[i].length())
                mp[num]=words[i].length();
        }
        //遍历两两不同字母组合，找出满足不含相同字符的最大长度乘积
        map<int,int>::iterator iter1,iter2;
        int ans=0;
        for (iter1=mp.begin(); iter1!=mp.end(); iter1++){
    
            for(iter2=iter1;iter2!=mp.end(); iter2++){
    
                if((iter1->first&iter2->first)==0){
    
                    ans=max(ans,iter1->second*iter2->second);
                }
            }
        }
        return ans;
    }
};

感想：
1）关于思考算法的心态，一开始以为要特殊的算法才能降低复杂度，就放弃直接看答案了。实际上，不断优化暴力解法，就能解决。遇到算法题目前，如果没有思路，可以常试先用暴力再慢慢优化，之后再从特殊算法角度思考。

006. 排序数组中两个数字之和

题目：给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

方法：
1）双指针，左指针left从最左边开始，右指针right从最右边开始，如果numbers[left]+numbers[right]>target，那么right–；如果numbers[left]+numbers[right]<target，那么left++;如果numbers[left]+numbers[right]==target,left、right就是答案。

class Solution {
    
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
    
        vector<int>ans;
        int len=numbers.size();
        int fst=0,lst=len-1;
        while(numbers[fst]+numbers[lst]!=target){
    
            if(numbers[fst]+numbers[lst]<target){
    
                fst++;
            }
            else{
    
                lst--;
            }
        }
        ans.push_back(fst);
        ans.push_back(lst);
        return ans;
    }
};