每日两题 / 46. 全排列 && 41. 缺失的第一个正数（LeetCode热题100）

46. 全排列 - 力扣（LeetCode）

经典回溯题，每次搜索选择未选择数字中的一个
当选择了n个数时，将已经选择的数加入答案

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> a;
        vector<vector<int>> ans;
        vector<int> st(nums.size(), 0);
        function<void()> dfs = [&](){
            if (a.size() == nums.size())
            {
                ans.push_back(a);
                return;
            }
            for (int i = 0; i < nums.size(); ++ i)
            {
                if (!st[i]) 
                {
                    a.push_back(nums[i]);
                    st[i] = 1;
                    dfs();
                    st[i] = 0;
                    a.pop_back();
                }
            }
        };
        dfs();
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

41. 缺失的第一个正数 - 力扣（LeetCode）

题目要求使用常数空间解决问题，也就是可以使用题目传入的数组
若数组长度为n，那么答案最多为n + 1
利用数组下标记录值为（值为数组下标+1）的数是否出现过
若是出现了，将其乘以-1（如果是正数），而数组中原本就存在负数，这些负数不影响答案，将它们先设置为n + 1
接着遍历整个数组，对于每个数取绝对值，若该数>n，则跳过
否则将（该数的值 - 1）作为数组下标，将该位置上的数置为负数
最后从头开始遍历数组，出现的第一个正数的（下标+1）则为答案

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++ i)
            if (nums[i] <= 0) nums[i] = n + 1;
        for (int i = 0; i < n; ++ i)
        {
            int num = abs(nums[i]);
            if (num <= n && num >= 1 && nums[num - 1] >= 0) 
                 nums[num - 1] *= -1;
        }
        for (int i = 0; i < n; ++ i)
            if (nums[i] >= 0)
                return i + 1;
        return n + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18