Good questions —— 数组篇

概述：本文记录了我在Leetcode刷题过程中遇到的与数组相关的优质题目及解题思路

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

思路：

使用dfs+回溯。比较经典的回溯题。

//dfs(回溯)
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<int> vis(n,0);
        dfs(nums,vis);
        return res;
    }

    void dfs(vector<int>& nums,vector<int>& vis){
        if(path.size()==nums.size())
            res.push_back(path);
        for(int i=0;i!=nums.size();++i){
            if(vis[i]==0){
                vis[i]=1;
                path.push_back(nums[i]);
                dfs(nums,vis);
                path.pop_back();
                vis[i]=0;
            }
        }
    }
};

非递归版本：

思路：

（1）通过实现下一个排列函数来实现找到全部排列

（2）下一个排列：从后往前搜索数组，找到第一个逆序对。如<3,4,7,6,5>中4是第一个出现逆序的。将4置换为<7,6,5>中比4大且最小的那个数（即5），数组变为<3,5,7,6,4>。再将<7,6,4>部分升序排列（实际上反转就是排序）即可，变为<3,5,4,6,7>即为下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        int flag=0;
        for(int i=nums.size()-1;i>0;i--){
            if(nums[i]<=nums[i-1]){
                if(i-1==0)      //已经为最大的排列（全降序），那么下一个即为最小的排列（全升序）
                    reverse(nums.begin(),nums.end());
            }
            //找到第一个逆序发生的索引i-1
            else{
                for(int j=nums.size()-1;j>i-1;--j){
                    if(nums[j]>nums[i-1]){
                        swap(nums[j],nums[i-1]);
                        reverse(nums.begin()+i,nums.end());
                        break;
                    }
                }
                break;
            }
        } 
    }
};

给定一个可包含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路：

（1）相较于上一题，这题需要多考虑去重的问题，即在同一层中，如果可选择的范围（未被访问过的范围）包含重复的数字，那么只能选择第一个，跳过重复的部分。

（2）另外要预先对nums进行排序，保证重复的数字都是相邻的

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());//为了使重复的数都相邻
        int n = nums.size();
        vector<int> vis(n,0);
        dfs(nums,vis);
        return res;
    }

    void dfs(vector<int>& nums,vector<int>& vis){
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i!=nums.size();++i){
            //要保证在同一层中使用的是不同的数
            //对于有重复的数，要找到第一个未被使用过的
            if(i>0 && nums[i]==nums[i-1] && vis[i-1]==0)
                continue;
            if(vis[i]==0){
                vis[i]=1;
                path.push_back(nums[i]);
                dfs(nums,vis);
                path.pop_back();
                vis[i]=0;
            }
        } 
    }
};

最长递增子序列问题

题目来源：最长递增子序列LIS问题及 变体

给定一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

（1）动态规划方法，时间复杂度O(n^2)

//动态规划：dp[i]=max(dp[i],dp[j]+1)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        for(int i=0;i!=nums.size();++i)
        {
            for(int j=0;j!=i;++j)
            {
                if(nums[j]<nums[i])
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};

（2）维护一个记录长度为i时递增子序列末尾元素的最小值，时间复杂度O(n)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //维护一个数组 temp[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值，temp[0] = nums[0]
        vector<int> temp;
        temp.emplace_back(nums[0]);
        for(int i=1;i!=nums.size();++i)
        {
            if(nums[i]>temp.back())
            temp.emplace_back(nums[i]);
            else
            {
                //注意这里要使用lower_bound
                auto it=lower_bound(temp.begin(),temp.end(),nums[i]);
                //if(it==temp.end())
                //continue;
                temp[it-temp.begin()]=nums[i];
            }
        }
        return temp.size();
    }
};

原地哈希

（1）要求在数组中找出所有出现两次的整数，时间复杂度O(n)，空间复杂度O(1)

思想：原地哈希

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n=nums.size();
        //思想，将nums[nums[i]-1]位置的数值加上n（由于是出现两次，直接取反也行）
        for(int i=0;i!=n;++i){
            nums[(nums[i]-1)%n]+=n;
        }
        for(int i=0;i!=n;++i){
            if((nums[i]-1)/n==2)
                res.push_back(i+1);
        }
        return res;
    }
};

（2）要求在长度为n的数组中[找到没有出现在[1,n]范围内的数字

思想：将nums中出现过的数字作为索引，将对应位置取反

打印螺旋矩阵

题目来源：打印螺旋矩阵：

思路：

（1）想到按层来遍历可以省去空间复杂度

（2）定义四个变量（left，right，top，bottom）来控制每一层的边界