[数据结构与算法]剑指数组c++

??

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

??经典的哈希表问题。我们用哈希表记录每个值的下标，当合适的数值出现时我们就能直接获得该数值的下标。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> hashmap;
        for(int i=0;i<nums.size();i++){
            if(hashmap.count(target-nums[i])!=0){
                res.push_back(i);
                res.push_back(hashmap[target-nums[i]]);
                break;
            }
            hashmap[nums[i]] = i;
        }
        return res;
    }
};

剑指 Offer 03. 数组中重复的数字

??同哈希表问题，贴一个答案就好了。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> hashset;
        for(int i=0;i<nums.size();i++){
            if(hashset.count(nums[i])==0){
                hashset.insert(nums[i]);
            }else{
                return nums[i];
            }
        }
        return 0;
    }
};

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
??三数之和是很经典的题了，该题目考察了双指针以及双指针中的去重操作。
??首先，如果我们对数组进行了排序，那么我们肯定abc是顺序出现的，a最小,b其次，c最大。
??每次循环，我们先定位出a，由于我们三个数之和是0，最小的数肯定是负数，再加上不允许重复，我们就必须要保证a是负数并且是相同的数里面的最后一个。
??定位好a之后我们去a的后面找b和c。
??bc使用双指针进行定位，b起始是a的后一位，c起始是数组最后一位。
??根据abc的和不断修正bc的位置，这里要注意，如果找到了一个答案之后，我们要检测b的右边是不是和b一样，c的左边是不是和c一样，为了避免重复，我们应当跳过这些元素。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.empty()||nums.size()<3) return result; 
        sort(nums.begin(), nums.end());//abc肯定是顺序的，不多说直接排序遍历
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0){//如果当前起点成正数就不想了，因为a肯定是负数！
                return result;
            }
            if(i>0&&nums[i-1]==nums[i]){//如果有相同的起点就跳到最后一个相同的数当起点！
                continue;
            }
            //好了，i就是a了，我们去找b和c
            int left = i+1;//双指针！
            int right = nums.size()-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right] == 0){//关键，找到b和c了再怎么办
                    result.push_back({nums[i],nums[left],nums[right]});//先把答案记录了
                    while(left<right&&nums[left]==nums[left+1]){//{1,1,0,2,2}出现这种情况怎么办？为了防止有重复答案我们要跳过第二个1和倒数第二个2！
                        left++;
                    }
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;//注意还要再移动一位才能完全摆脱和之前相同的值
                    right--;
                }else if(nums[i]+nums[left]+nums[right] >0){//如果超了，右边往里缩
                    right--;
                }else{//如果少了，左边往里走
                    left++;
                }
            }
        }
        return result;
    }
};

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
??我们还是用简单一些的方法处理这个问题，我们新建一个数组，把nums1和nums2按顺序放进去，然后直接按下标找中位数。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        int length = len1 + len2;
        vector<int> target(length,0);//用一个数组存下nums1 和 nums2
        int i=0,j=0;
        int index = 0;
        while(i<len1&&j<len2){//如果有一个到头了就不能这样算了
            if(nums1[i]<nums2[j]){
                target[index++] = nums1[i++];
            }else{
                target[index++] = nums2[j++];
            }
        }
        if(i==len1){//如果nums1到头
            for(int k=j;k<len2;k++){//把nums2的都加上
                target[index++] = nums2[k];
            }
        }else if(j==len2){//如果nums2到头
            for(int k=i;k<len1;k++){//把nums1的都加上
                target[index++] = nums1[k];
            }
        }
        if(length%2 == 0){
            int mid = (length-1)/2;
            return (double)(target[mid] + target[mid+1])/2;
        }else{
            int mid = (length)/2;
            return (double)target[mid];
        }
    }
};

接雨水

??接雨水的核心在于，怎么去计算雨水的体积。
??一个纵向单位的雨水体积 = 右侧最高高度和左侧最高高度的最小值 - 自己的滴珠高度。
??所以我们创建两个数组，分别记录所有单位左侧最高高度和右侧最高高度就好了。

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        vector<int> maxleft(height.size(),0);//记录对于每个点来说，最大的左侧高度
        vector<int> maxright(height.size(),0);//记录对于每个点来说，最大的右侧高度
        maxleft[0] = height[0];
        for(int i=1;i<height.size();i++){//左边最大值是从左往右递推
            maxleft[i] = max(height[i],maxleft[i-1]);//递推求最大，拿自己和前一个位置的最大值比！
        }
        maxright[height.size()-1] = height[height.size()-1];
        for(int i = height.size()-2;i>=0;i--){//右边最大值是从右往左递推
            maxright[i] = max(height[i],maxright[i+1]);//拿自己和后一个位置的最大值比！
        }
        
        for(int i=0;i<height.size();i++){
            int count = min(maxleft[i],maxright[i]) - height[i];//计算每个纵向单位的雨水体积
            if(count>0) sum += count;
        }
        return sum;
    }
};

合并两个有序数组

??这个题是上个题的子集。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=0,j=0;
        vector<int> sorted(m+n,0);
        int index = 0;
        while(i<m&&j<n){
            if(nums1[i]>nums2[j]){
                sorted[index++] = nums2[j++];
            }else{
                sorted[index++] = nums1[i++];
            }
        }
        if(i==m){
            for(int k=j;k<n;k++){
                sorted[index++] = nums2[k];
            }
        }else if(j==n){
            for(int k=i;k<m;k++){
                sorted[index++] = nums1[k];
            }
        }
        for(int i=0;i<m+n;i++){
            nums1[i] = sorted[i];
        }
    }
};

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
??同枝剪枝的回溯问题，回溯模板题。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,vector<bool>& used){
        if(path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]==true) continue;//在当前的分支里就不能用这个数字了
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums,used);
            path.pop_back();//回溯操作
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        backtracking(nums,used);
        return result;
    }
};

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
??我们这里用动态规划处理一下这个题。
??dp[i]表示到达下标i时连续子数组的最大和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];//第一个元素不用比
        int ans = nums[0];//保底是第一个元素，当然设成int最小值也没问题
        for(int i=1;i<nums.size();i++){
            dp[i] = max(nums[i],dp[i-1]+nums[i]);//要么是之前的累加+当前元素，要么只选当前元素放弃之前累加
            ans = max(dp[i],ans);//随时记录最大值
        }
        return ans;
    }
};

岛屿数量

??岛屿数量太经典dfs了，直接说代码吧。
??可以注意一下在dfs代码中，我们没有显式使用return来结束搜索，为什么呢？
??因为我们在遍历一个陆地后会将其改成海，搜索着总有一天就没陆地了，到时候dfs里的四个方向判断都不成立，自然就停止搜索了。

class Solution{
public:
    void dfs(vector<vector<char>>& grid,int i,int j){
        int rows = grid.size();
        int colomns = grid[0].size();
        grid[i][j] = '0';//改成海洋，不会重复搜索
        if(i+1<rows&&grid[i+1][j] == '1') dfs(grid,i+1,j);//因为有方向的判断，所以会自动结束搜索
        if(i-1>=0&&grid[i-1][j] == '1') dfs(grid,i-1,j);
        if(j+1<colomns&&grid[i][j+1] == '1') dfs(grid,i,j+1);
        if(j-1>=0&&grid[i][j-1] == '1') dfs(grid,i,j-1);
    }

    int numIslands(vector<vector<char>>& grid){
        if(grid.empty()){
            return 0;
        }
        int rows = grid.size();
        int colomns = grid[0].size();
        int landsnum = 0;
        for(int i=0;i<rows;++i){
            for(int j=0;j<colomns;++j){
                if(grid[i][j] =='1'){
                    landsnum++;
                    dfs(grid,i,j);
                }
            }
        }
        return landsnum;
    }
};

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

??我们只能遍历一次数组，并且不能额外开辟和数组一样长的空间。
??所以不能用暴力方法，建哈希表法和枚举遍历（也太暴力了）都不行。
??这里使用了一手置换法。
??我们可以想到，如果调整原数组的排列，使其尽力恢复成正数排序，但是会有一些位置上的数是错误的，每一个错误的位置就代表一个缺失的正数。
??这样，我们遍历数组，将遇到的在【1，n】范围内的数，都通过交换的方式移动到它应该在的位置上！然后再遍历寻找第一个不合适的就可以了。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n;++i){
            while(nums[i]>=1&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){//最后一个条件是防止死循环
                swap(nums[i],nums[nums[i]-1]);//将该元素交换到该元素-1的下标处
            }
        }
        for(int i=0;i<n;++i){
            if(nums[i] != i+1){
                return i+1;
            }
        }
        return n+1;
    }
};