剑指Offer数组专题

剑指 Offer II 002. 二进制加法（二进制+字符串转整型）

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

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:
输入: a = “11”, b = “10”
输出: “101”

class Solution {
public:
    string addBinary(string a, string b) {
        //竖式模拟二进制加法
        string res="";
        int i1=a.size()-1,i2=b.size()-1;
        int carry=0;
        int x=0,y=0,sum=0;
        while(i1>=0||i2>=0){
            x=i1>=0?a[i1]-'0':0;
            y=i2>=0?b[i2]-'0':0;
            sum=x+y+carry;
            res.push_back('0'+sum%2);//这里会自动把int转换成string
            carry=sum/2;
            i1--;
            i2--;
        }
        if(carry>0) res.push_back('0'+carry);
        reverse(res.begin(),res.end());
        return res;

    }
};

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数(动态规划 +位运算）

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

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

对于所有的数字，只有奇数和偶数两种：

奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。

偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。

因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。

所以我们可以得到如下的状态转移方程：

dp[i] = dp[i-1]，当i为奇数
dp[i] = dp[i/2]，当i为偶数
上面的方程还可进一步合并为：
dp[i] = dp[i/2] + i % 2

通过位运算进一步优化：

i / 2 可以通过 i >> 1 得到；
i % 2 可以通过 i & 1 得到；

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n+1,0);
        for(int i=0;i<=n;i++){
            res[i]=res[i/2]+(i%2);
        }
        return res;
    }
};

剑指 Offer II 004. 只出现一次的数字 (map使用）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。

请你找出并返回那个只出现了一次的元素。

示例 1：
输入：nums = [2,2,3,2]
输出：3

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int,int> m;
        for(int num:nums){
            m[num]++;
        }
        int ans;
        for(auto [num,occ]:m){
            if(occ==1){
                ans=num;
                break;
            }

        }
        return ans;
    }
};

剑指 Offer II 005. 单词长度的最大乘积(位运算）

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。

假设字符串中只包含英语的小写字母。

如果没有不包含相同字符的一对字符串，返回 0。

示例 1:
输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。

它们不包含相同字符，且长度的乘积最大。

采用哈希集合的暴力法会超时
定义一个masks数组来记录每个字符串的位掩码，对整个字符串数组进行位运算处理，对字符串数组的里的字符串进行两两按位与，若结果为0则说明两个字符串里没有相同字符，然后去更新答案
要注意&的优先级小于==

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n=words.size();
        vector<int> mask(n);//存储每个字符串的二进制位表示
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<words[i].size();j++){
                mask[i] |=1<<(words[i][j]-'a');//字母第几位就向左移几位
            }
        }
        for(int i=0;i<n-1;i++){
            for(int j=1;j<n;j++){
                if((mask[i]&mask[j])==0) //对两个单词进行按位与判断是否有相同单词
                    ans=max(ans,(int)(words[i].size()*words[j].size()));
            }
        }
        return ans;
    }
};

剑指 Offer II 006. 排序数组中两个数字之和(双指针）

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。

因此 index1 = 1, index2 = 3 。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n=numbers.size();
        int l=0,r=n-1;
        vector<int>ans(2,0);
        while(l<r){
            if(numbers[l]+numbers[r]==target) {
                ans[0]=l;
                ans[1]=r;
                break;
            }
            else if(numbers[l]+numbers[r]<target){
                l++;
            }
            else{
                r--;
            }
        }
        return ans;
    }
        
    
};

剑指 Offer II 007. 数组中和为 0 的三个数（双指针）

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

首先排序，固定一个数，然后双指针。

有两个地方需要去重。

首先外层循环选择那个固定的数字时，如果出现当前数字和前一个数字相等的情况，需要跳过。

然后就是移动双指针时，左指针需要跳过其右侧所有相等的数，右指针也需要跳过其左侧所有相等的数。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > ans;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-2;i++){
            if(i>0&&nums[i]==nums[i-1]) continue;//当前数字和前一个数字相等，跳过,注意
            int j=i+1,k=n-1;
            while(j<k){
                int sum=nums[j]+nums[k];
                if(sum==-nums[i]){
                    ans.push_back({nums[i],nums[j],nums[k]});
                    while (j < k && nums[j] == nums[j + 1]) j++;//跳过右侧所有相等的数
                    j++;
                    while (j < k && nums[k] == nums[k - 1]) k--;//跳过左侧所有相等的数
                    k--;
                }
                else if(sum<-nums[i]) j++;
                else k--;
            }
        }
        return ans;
    }
};

剑指 Offer II 008. 和大于等于 target 的最短子数组（滑动窗口）

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。

如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

当前滑窗内的所有项的和大于等于target 的时候，则往右移动滑窗左边界，缩小滑窗内的和
当当前滑窗内所有项的和小于target的时候，则往右移动滑窗右边界，增加滑窗内各项和
在不断右移的过程中，找到长度最小的那个区间即可

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum=0;
        int start=0,end=0;
        int n=nums.size();
        int ans=n;//这个初始值要设大
        bool flag=false;
        while(end<n){
            sum+=nums[end];
            while(sum>=target&&start<=end){
                flag=true;
                ans=min(ans,end-start+1);
                sum-=nums[start];
                start++;
            }
            end++;
        }
        if(flag==false) return 0;
        return ans;
    }
};

剑指 Offer II 009. 乘积小于 K 的子数组(滑动窗口）

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。

需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1)return 0;//要加上这句
        int left = 0;
        int right = 0;
        int res = 0;
        int count = 1;
        while(right<nums.size()){
            count*=nums[right];
            while(count>=k){
                count/=nums[left];
                left++;
            }
            res+=right-left+1;//注意这个不好想
            right++;
        }
        return res;
    }
};

剑指 Offer II 010. 和为 k 的子数组（前缀和+哈希）

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

(数组中有负数）

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

滑动窗口的力所不及
在套模板的同时，大家是否考虑过，假设题目同样是求连续的子数组，但是在数组中出现了负数，那这种情况下还可以使用滑动窗口么？

答案是不行的，为什么？

我们窗口滑动的条件是什么，while窗口内元素超过或者不满足条件时移动，但如果数组存在负数，遇到不满足题意的时候，我们应该移动窗口左边界，还是扩大窗口右边界从而寻找到符合条件的情况呢？

 // 法二：前缀和 O(N^2)
        int n = nums.size();
        vector<int> preSum(n + 1, 0);//preSum[0]=0,所以有n+1个
        // 构建前缀和
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int cnt = 0;
        // 枚举前缀和 区间和=前缀和端点之差
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (preSum[j] - preSum[i] == k) {
                    ++cnt;
                }
            }
        }
        return cnt;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n=nums.size();
        int preSum=0;
        unordered_map<int,int> map;//记录前缀和的次数
        map[0]=1;
        int ans=0;
        for(int i=0;i<n;i++){
            preSum+=nums[i];
            if(map.find(preSum-k)!=map.end())//这里表示如果前缀和的差等于k
                ans+=map[preSum-k];
            map[preSum]++;
        }
        return ans;
    }
};

剑指 Offer II 012. 左右两边子数组的和相等(前缀和）

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。

这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。

如果数组不存在中心下标，返回 -1 。

输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。

左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum=0,cur=0;
        for(int i:nums) sum+=i;
        for(int i=0;i<nums.size();i++){
            sum-=nums[i];
            if(cur==sum) return i;
            cur+=nums[i];
        }
        return -1;
    }
};

剑指 Offer II 013. 二维子矩阵的和(前缀和）

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

先根据原矩阵，求出前缀和矩阵，然后通过观察得知公式
sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1]

举例来说上图红框中的和，就是上面第三图当中黄色圈出来的数字28-8-9+3 = 14

class NumMatrix {
public:
    vector<vector<int> > preSum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        preSum.resize(m+1,vector<int>(n+1));
        for(int i=0;i<m;i++){
            int count=0;
            for(int j=0;j<n;j++){
                count+=matrix[i][j];
                preSum[i+1][j+1]=preSum[i][j+1]+count;
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1]+preSum[row1][col1]-preSum[row2+1][col1]-preSum[row1][col2+1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */