如何通过算法练习-day24掌握长尾词的运用技巧？

本文共计1361个文字，预计阅读时间需要6分钟。

回溯算法 + 491. 递增子序列 + 题意：给你一个整数数组 nums，找出所有该数组中不同的递增子序列，至少有两个元素。你可以按任意顺序返回答案。

示例：数组 nums 中可能包含重复元素。

答案示例：[ [2, 3], [3, 4], [2, 4], [2, 3, 4], [3, 4, 5] ]

回溯算法

491. 递增子序列

题意：给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例：

思路：本题其实和数组的组合很像，只是我们不会无脑的存储组合数组了，而是有两个条件：

1. 数组大小必须大于1
2. 数组必须为递增数组

为了满足以上两个条件，我们分别对存储和组合操作进行限制

存储时，组合数组tmp必须大于1；组合操作时，当待加入元素小于组合数最后一个元素时，或待加入元素已经被使用时，出现重复组合时，跳过。

此外，我们还创建了一个数组，用于标记已经被使用的元素，同层无法使用已经被标记的元素

C++代码：

vector<vector<int>> arr; vector<int> tmp; void IncreaseSequence(vector<int>& nums,int begin) { if(tmp.size()>=2)//这里不需要返回，因为我们还有更大的组合需要保存；如果返回，那就只能返回大小为2的组合了 { arr.push_back(tmp); } vector<int> s; for(int i=begin;i<nums.size();i++) { if(!tmp.empty()&&nums[i]<tmp.back()||find(s.begin(),s.end(),nums[i])!=s.end())//排除两种方法不成组合：1.下一个元素小于最后一个元素 2.该元素已经被使用 { continue; } tmp.push_back(nums[i]); s.push_back(nums[i]);//这里是同层的元素被使用的标记，不用回溯 IncreaseSequence(nums,i+1); tmp.pop_back(); } } vector<vector<int>> findSubsequences(vector<int>& nums) { IncreaseSequence(nums,0); return arr; }

46. 全排列

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

示例：

思路：由于本题给出的数组中的元素是不重复的，因此，我们只需要考虑每个元素只拿一次就可以。

所以我们需要定一个block数组标记数组每层可以使用的元素，只要为0，那就是还没有被使用；为1就是被使用，直接跳过。最终在回溯终止条件中，只要有组合元素大小等于nums的大小即可存储

C++代码：

vector<vector<int>> arr; vector<int> tmp; void AllPermut(vector<int>& nums,vector<bool> block) { if(tmp.size()==nums.size())//组合数组的大小必须等于nums的大小 { arr.push_back(tmp); return; } for(int i=0;i<nums.size();i++) { if(block[i]==true)//该元素被使用过直接跳过 { continue; } tmp.push_back(nums[i]); block[i]=true;//用于记录每一层被使用过的元素 AllPermut(nums,block); block[i]=false; tmp.pop_back(); } } vector<vector<int>> permute(vector<int>& nums) { vector<bool> block(nums.size(),false); AllPermut(nums,block); return arr; }

47. 全排列 II

题意：给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。

示例：

思路：本题的思路，其实和46.全排序几乎一样，就是在存储数组时不会那么无脑，需要判断组合数组是否已经被存储即可。还有一种思路是在形成组合数时进行操作，先将nums进行排序，然后在变量nums时，如果当前元素等于前一个元素，并且前一个元素未被使用，就说明该位置的元素已经在之前使用过了，去一层上的相同元素

C++代码：

vector<vector<int>> arr; vector<int> tmp; void AllPermut2(vector<int>& nums,vector<bool> block) { if(tmp.size()==nums.size()) { if(find(arr.begin(),arr.end(),tmp)==arr.end())//再次判断，存储的组合必须是未保存的 { arr.push_back(tmp); } return; } for(int i=0;i<nums.size();i++) { if(block[i]==true) { continue; } tmp.push_back(nums[i]); block[i]=true; AllPermut2(nums,block); block[i]=false; tmp.pop_back(); } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<bool> block(nums.size(),false); AllPermut2(nums,block); return arr; }

vector<vector<int>> arr; vector<int> tmp; void AllPermut2(vector<int>& nums,vector<bool> block) { if(tmp.size()==nums.size()) { arr.push_back(tmp); return; } for(int i=0;i<nums.size();i++) { if(i>0&&nums[i-1]==nums[i]&&block[i-1]==false) { continue; } if(block[i]==false) { tmp.push_back(nums[i]); block[i]=true; AllPermut2(nums,block); block[i]=false; tmp.pop_back(); } } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<bool> block(nums.size(),false); sort(nums.begin(),nums.end()); AllPermut2(nums,block); return arr; }