「算法刷题」回溯算法的基础题目

本博客是记录作者做回溯算法的中等难度的题的笔记，主要是排列问题等。

一、回溯算法的排列问题

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
46	全排列（中等难度）			https://leetcode-cn.com/problems/permutations/
47	全排列II（中等难度）			https://leetcode-cn.com/problems/permutations-ii/

46 全排列

本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后在按照另一个维度重新排列。

按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

那么只需要按照k为下标重新插入队列就可以了，为什么呢？

以图中{5,2} 为例：

代码如下：

	static bool cmp(vector<int> &a,vector<int> &b){
        if(a[0]==b[0])// 如果身高相同则按照k从小到大排列
        {
            return a[1]<b[1];
        }
        return a[0]>b[0];//默认将身高按照从大到小排列
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        /*输入一个二维数组，输出一个二维数组*/
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> que;
        // 按照k调整队列
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }

按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。

但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。

所以使用vector（动态数组）来insert，是费时的

二、回溯算法的其他题目

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
491	递增子序列（中等难度）			https://leetcode-cn.com/problems/increasing-subsequences/
332	重新安排行程（中等难度）			https://leetcode-cn.com/problems/reconstruct-itinerary/

491 递增子序列

代码如下：