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;}
};
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;}
};