[数据结构与算法]剑指offer-整数相关题目整理

剑指 Offer II 001. 整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’ 。
注意：
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231, 231?1]。本题中，如果除法结果溢出，则返回 231 ? 1

解题关键

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
2. 左移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;
        }
        //全部转成了负数，因为INT的范围是 -2^31 ~ 2^31 -1 变负数可防止溢出
        unsigned int ret = divideCore(a, b);
        return negative == 1 ? -ret : ret;
    }

    unsigned int divideCore(int a, int b) {
        int ret = 0;
        // 注意a, b都是负数，所以a <= b就是还可以继续除
        while (a <= b) {
            int value = b;
            unsigned int quo = 1;
            while (value >= 0xc0000000 && a <= value + value) {   //0xc0000000是-2^30
                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” ，就都不含前导零。

解题关键

1. 纯数字用位运算求和: 异或用来求不进位的和，进位用（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. 对于这种要算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为数字的位数
2. 根据第一步的原理，其实就可以发现数据相互之间的关系，使用动态规划的思想。即，数字i和数字i&(i-1)之间相差一个1，或者可以利用奇偶性，如果数字i右移一位，如果i是偶数，那么最后一位本来就是0，右移后1的个数不变，如果i为奇数，右移后1的个数会少一个。

class Solution {
public:
    vector<int> countBits(int n) {
        //计算每个数二进制形式时1的个数： i&(i-1) 利用这个可每次消去一个1
        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) {
        //计算每个数二进制形式时1的个数： i&(i-1) 利用这个可每次消去一个1
        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 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解题关键：

1. 一种比较通用解法是只看32位中，每一位得到了多少的贡献。数组的每一个数相加之后，每一位数上，1的总个数一定是3N，或者3N+1.只要把每一位对3求余，如果哪一个余数为1就说明多出来的那一个数在这一位上多贡献了一个1. 如果题目改成其他数重复了k次，把3变成k即可。时间复杂度为O(32n)=O(n)
2. 还有一种数字电路的方式，见力扣大佬的解答

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;  //统计每个数字的每一位是否为1， 如果为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] 仅包含小写字母
解题关键：

1. 因为只有26个小写字母，所以可以把他们对应的放到一个32位的int整数中，如果对应位置有字母，那么那一位就为1. 之后检查是否有重复的字母时，就可以看按位与运算的结果是否为0，为0则没有重复字母。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        //每一个字符串都可以用一个26位的二进制数表示，a对应第0位，z对应第25位 也对应一个十进制数
        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 。

解题思路：

1. 看到排序数组，其实应该很快能联想到双指针方法。然后对于这道题，双指针放两头，和大了，左移right指针；和小了，右移left指针。注意这里的left和right都是取的闭区间。
2. 如果不是排序数组，对于两数之和问题就用map来解决。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        //排序数组用双指针 如果sum大于target右移left指针，如果小于target则左移right指针
        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;
    }
};