Permutations II 再分析

时间:2021-11-20 21:29:22

  记得第一遍做这题的时候其实是没什么思路的,但是第二次的时候,我已经有"结果空间树"的概念了。这时候再看https://oj.leetcode.com/problems/permutations-ii/,觉得那样理解未免过于繁,因此重新写下新的思路。以前的文章总是花了时间写,删了可惜,且留着吧。(废话太多了)。

  怎么理解结果空间树?当我们用dfs去寻找结果的时候,实际上是构造了一棵树。我们通常会有如下的代码结构:

  

    void dfs()
{
if(expression1)
do something
for(int i=0;i<N;i++)
{
if(expression2)
do something
dfs();
}
}

  expression1通常是终止条件。expression2通常是剪枝条件。

  以本题为例,我最终代码是:

class Solution {
public:
vector<vector<int>> res;
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(),num.end());
bool *visits=new bool[num.size()];
memset(visits,0,sizeof(bool)*num.size());
vector<int> intermediate;
dfs(num,intermediate,visits);
return res;
} void dfs(vector<int>& num,vector<int> &intermediate, bool* visits)
{
if(intermediate.size()==num.size())
res.push_back(intermediate);
for(int i=0;i<num.size();i++)
{
if(visits[i]||(i>0&&num[i]==num[i-1]&&!visits[i-1]))
continue;
visits[i]=true;
intermediate.push_back(num[i]);
dfs(num,intermediate,visits);
intermediate.pop_back();
visits[i]=false;
}
}
};

  假设输入如下:[1,1,1,1,2],则树形状如下:

  Permutations II 再分析

  红色叉的部分表示剪枝。从上述图来看,或者称为森林还恰当一些,先不管这个。这里关键要理解一点,如何去重?比如第三层的后面两个1是如何去掉的?关键的代码在于这里:

  

i>0&&num[i]==num[i-1]&&!visits[i-1]

 也就是说,要满足以下两个条件:1. 与前一个相等;2. 前一个没有被访问。这样就能保证相同的元素按顺序每层只访问一个。

 说白了,实在没什么高难度的东西。