day4

33.二叉搜索树的后序遍历序列

思路:运用递归，不断判断左右子树的后序遍历序列(最后一个数字是根节点，前面可以分为两部分)是否真正符合二叉搜索树的定义(左子树的所有节点都小于根节点，右子树的所有节点都大于根节点)
代码：

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int start=0,end=postorder.size()-1;
        return helper(start,end,postorder);
    }

    bool helper(int s,int e,vector<int>& postorder){
        if(s>=e){ //不要写成s<=e..
            return true;
        }
        int mid=e;//重点，因为如果没有postorder[i]>postorder[e]，说明e左边全为左子树，则右子树为空。
        for(int i=s;i<e;i++){
            if(postorder[i]>postorder[e]){
                mid=I;
                break;
            }
        }
        for(int i=mid+1;i<e;i++){
            if(postorder[i]<postorder[e]){
                return false;
            }
        }
        return helper(s,mid-1,postorder)&&helper(mid,e-1,postorder);
    }
};

可以看看课本p181的代码，自己实现一下？

总结：如果面试题需要处理一棵二叉树的遍历序列，则可以先找到二叉树的根节点，在基于根节点把二叉树的遍历序列拆分成基于左子树对应的子序列和右子树对应的子序列，然后递归处理整两个子序列即可。

新颖非常规思路2:使用栈
没看，没实现
两条链接的方法2
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/di-gui-he-zhan-liang-chong-fang-shi-jie-jue-zui-ha/
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/
失火的夏天在评论区

34.二叉树中和为某一值的路径

思路1：深度优先搜索，遍历每一条路径。无法剪枝，因为题目说是整数，所以有可能有负数。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ans;
        vector<int> path;
        //if(root==NULL) return ans;
        int cur_sum=0;
        dfs(ans,path,sum,root,cur_sum);
        return ans;
    }

    void dfs(vector<vector<int>> &ans,vector<int> &path,int &sum,TreeNode* root, int cur_sum){
        if(root==NULL){
            if(cur_sum==sum){
                ans.push_back(path);
            }
            return;
        }
        path.push_back(root->val);
        dfs(ans,path,sum,root->left,cur_sum+root->val);
        if(root->left!=NULL || root->right!=NULL ){ //当root不是叶子结点的时候才再次执行，不然当该叶子节点满足条件时，path进入了两次ans，导致输出的结果重复。
            dfs(ans,path,sum,root->right,cur_sum+root->val);
        }
        path.pop_back();
    }
};

失败的case：

• 之前代码的疏漏之处，导致重复输出。
  输入：
  [5,4,8,11,null,13,4,7,2,null,null,5,1]
  22
  输出：
  [[5,4,11,2],[5,4,11,2],[5,8,4,5],[5,8,4,5]]
  预期结果：
  [[5,4,11,2],[5,8,4,5]]
• 树为空。
  输入：
  []
  0
  输出：
  [[]]
  预期结果：
  []
• 不是叶子节点但和却满足了，说明原先的代码不缜密，是错误的代码。
  输入：
  [1,2]
  1
  输出：
  [[1]]
  预期输出：
  []

经过上述case后，修改之后的代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ans;
        vector<int> path;
        if(root==NULL) return ans;
        int cur_sum=0;
        dfs(ans,path,sum,root,cur_sum);
        return ans;
    }

    void dfs(vector<vector<int>> &ans,vector<int> &path,int &sum,TreeNode* root, int cur_sum){
        if(root->right==NULL&&root->left==NULL){
            //必须是到达叶子节点才可以，原先的写法，root为空，并不意味着调用他的那个结点为叶子结点。
            //所以即使和满足，也不能够将path加入ans！
            if(cur_sum+root->val==sum){
                path.push_back(root->val);
                ans.push_back(path);
                path.pop_back();
            }
            return;
        }
        path.push_back(root->val);
        if(root->left){
            dfs(ans,path,sum,root->left,cur_sum+root->val);
        }
        if(root->right){
            dfs(ans,path,sum,root->right,cur_sum+root->val);
        }
        path.pop_back();
    }
};

学习下别人的写法，反思为什么第一套代码失败。
解题思路：
本问题是典型的二叉树方案搜索问题，使用回溯法解决，其包含先序遍历 + 路径记录两部分。

• 先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。
• 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。
  当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。

dfs(root, sum) 函数：

• 递推参数： 当前节点 root ，当前目标值 tar。
• 终止条件： 若节点 root 为空，则直接返回。
• 递推工作：
  1.路径更新： 将当前节点值 root.val 加入路径 path ；
  2.目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 0 ）；
  3.路径记录： 当 ① root 为叶节点 且 ② 路径和等于目标值 ，则将此路径 path 加入 res 。
  4.先序遍历： 递归左 / 右子节点。
  5.路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ret;
        vector<int> temp;
        dfs(temp, root, sum, ret);
        return ret;
    }
    void dfs(vector<int>& cur, TreeNode* node, int target,  vector<vector<int>>& ret)
    {
        if(node==NULL)return;
        cur.push_back(node->val);
        target -= node->val; //按前面的思路用加法累加来判断也可以
        //关键在于下面判断是否要将满足结果的cur加入ret。必须是叶子结点才可
        if(!target && !node->left && !node->right)ret.push_back(cur);
        
        dfs(cur, node->left, target, ret);
        dfs(cur, node->right, target, ret);
        cur.pop_back();
    }
};

35.复杂链表的复制(重点)

题意：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

思路1:p187-188 时间复杂度o(n^2)

思路2:遍历两次原始链表。
第一次建立新链表：完成val和next的部分以及新旧链表节点之间的hashmap映射关系，第二次完成新链表random部分。
p188

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* dum=new Node(0);
        Node* cur=new Node(0),*pre=dum,*temp=head;
        map<Node*,Node*> hashmap;
        while(temp){
            cur->val=temp->val;
            pre->next=cur;
            hashmap[temp]=cur;
            temp=temp->next;
            pre=cur;
            cur=new Node(0);
        }
        temp=head;
        cur=dum->next;
        while(temp){
            cur->random=hashmap[temp->random];
            temp=temp->next;
            cur=cur->next;
        }
        return dum->next;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        // 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != nullptr) {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        // 构建新链表的 next 和 random 指向
        while(cur != nullptr) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        // 返回新链表的头节点
        return map[head];
    }
};

思路3:不实用辅助空间的情况下实现o(n)的时间效率
p188-191(没有亲手实现)
同样思路的代码：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != nullptr) {
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3. 拆分两链表
        cur = head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }
};

总结：

• 链表常用的套路是在遍历中解决问题。
• 为了减少寻找某一结点的遍历次数，常见的思维是把地址保存下来，以空间换时间。
• 链表常用的节约空间的套路是在原链表上直接修改。

36.二叉搜索树与双向链表

思路1:因为bst的中序遍历为递增序列，所以利用中序遍历完成二叉搜索树向双向链表的转化。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        Node* pre=NULL,*head=NULL;
        dfs(root,pre,head);
        if(pre&&head){ //完成头节点前驱和尾结点的后继
        //pre是尾结点，head是头节点
            pre->right=head;
            head->left=pre;
        }
        return head;
    }

    void dfs(Node *root,Node *&pre,Node *&head){
        //注意参数是传引用!!!
        if(root==NULL){
            return;
        }

        dfs(root->left,pre,head);

        if(head==NULL){//找到头节点
            head=root;
            pre=root;
        }
        else{
            pre->right=root;
            root->left=pre;
            pre=root;
        }

        dfs(root->right,pre,head);
    }
};

37.序列化二叉树(重点!!)

题意：
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构 。

不会写

思路1:dfs
p194-196
关键：因为前序遍历是从根节点开始，所以可以根据前序遍历的顺序来序列化二叉树。

反序列化部分的代码有点难想，可以参考如下。
最关键在于：

• 定义函数 buildTree 构建树，接收由序列化字符串转成的 list 数组。
• 依次弹出 list 的首项，构建当前子树的根节点，顺着 list 数组，就会先构建根节点、构建左子树、构建右子树。

反序列化

总结：递归完成前序遍历，序列化成字符串，再转化回树。

运用流stringstream处理字符串，与课本的代码实现 思想一致，甚至更简单。课本的反序列化函数由于返回值是void？总之，涉及到指针的指针，头都晕了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "";
        ostringstream out;//与ostream略有不同，没研究，好像是继承关系
        serializeCore(root,out);
        return out.str();
        //将stringstream中的全部数据输出则是使用成员函数str()
        //https://blog.csdn.net/shs1992shs/article/details/83051298
    }

    void serializeCore(TreeNode* root,ostringstream& out) {
        if(root==NULL){
            out<<"$ ";
            return;
        }
        out<<root->val<<" ";
        //out << to_string(root->val) <<" ";//也可以
        serializeCore(root->left,out);
        serializeCore(root->right,out);
        return;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;

        istringstream in(data);
        return deserializeCore(in);
    } 

    TreeNode* deserializeCore(istringstream& in){
        string val;
        in >> val; //默认按照空格分割
        if (val == "$") return nullptr;

        //把数字字符串转换成int输出，与atoi()方法参数不同
        auto root = new TreeNode(stoi(val));
        root->left  = deserializeCore(in);
        root->right = deserializeCore(in);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

关于流

课本反序列化部分涉及到指针的操作：
空指针的地址为什么不同？https://bbs.csdn.net/topics/340220145

如果不想使用默认的空格分割，运用getline函数即可。
代码只修改了一句： in >> val; //默认按照空格分割

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "";
        ostringstream out;//与ostream略有不同，没研究，好像是继承关系
        serializeCore(root,out);
        return out.str();
        //将stringstream中的全部数据输出则是使用成员函数str()
        //https://blog.csdn.net/shs1992shs/article/details/83051298
    }

    void serializeCore(TreeNode* root,ostringstream& out) {
        if(root==NULL){
            out<<"$,";
            return;
        }
        out<<root->val<<",";
        //out << to_string(root->val) <<" ";
        serializeCore(root->left,out);
        serializeCore(root->right,out);
        return;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;

        istringstream in(data);
        return deserializeCore(in);
    } 

    TreeNode* deserializeCore(istringstream& in){
        string val;
        
        //代码修改这里即可
        getline(in, val, ',');
        if (val == "$") return nullptr;

        //把数字字符串转换成int输出，与atoi()方法参数不同
        auto root = new TreeNode(stoi(val));
        root->left  = deserializeCore(in);
        root->right = deserializeCore(in);
        return root;
    }
    

};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

关于流主要参考：
https://blog.csdn.net/qq_24279775/article/details/107536238

将字符串绑定到输入流istringstream，然后使用getline的第三个参数，自定义使用什么符号进行分割就可以了。
https://www.cnblogs.com/dingxiaoqiang/p/8228390.html
https://www.cnblogs.com/flix/p/13594908.html

在序列化的时候也可以不使用流,直接构造string。

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "#";
        return to_string(root->val) + " " + serialize(root->left) + " " + serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream is(data);
        return dfs(is);
    }

    TreeNode* dfs(istringstream& s) {
        string t;
        s >> t;
        if (t == "#") return NULL;
        TreeNode * node = new TreeNode(stoi(t));
        node->left = dfs(s);
        node->right = dfs(s);
        return node;
    }
};

思路2:bfs
不应该当成完全二叉树来处理，因为这里的序列化表示居然和完全二叉树不一样。因为之前我想利用完全二叉树的这个性质：某节点x，则左孩子2x，右孩子2x+1。
但比如：

表示为[1,null,2,3] 而非[1,null,2,null,null,3]

但实质上，只要序列化和反序列化属于可逆的操作即可。只是你没必要利用层序遍历，序列化成一个完全二叉树，然后再反序列化。很浪费空间和时间，因为空节点或许会很多。

下面的代码，相比于题目给定的 "[1,2,3,null,null,4,5]" 会多输出 null 。 但本题的测试的是 序列化 和 反序列化是否可逆，因此 “序列化列表的形式” 并未限制，只要两个函数可以互逆就好啦

思路讲解：
序列化：

• 维护一个队列，初始让根节点入列，考察出列的节点：
  1.如果出列的节点是 null，将'#'推入 res 数组。
  2.如果出列的节点不是 null，将节点值推入数组 res，并将它的左右子节点入列。
  3.注意，子节点 null 也入列，它对应'#'，需要被记录，只是它没有子节点可入列!!
• 入列、出列…直到队列为空，所有节点遍历完，res 数组也好了，转成字符串，即序列化结果。

反序列化：获得了上述的序列后如何反序列化建树呢？
反序列化——也是BFS
下图是BFS得到的序列化字符串，和DFS得到的不同，它是一层层的。除了第一个是根节点的值，其他节点值都是成对的，对应左右子节点。

• 先将序列化的字符串转成数组list，用一个 cursor 从第二项开始扫描，每次考察两个节点值。
• 起初，用list[0]值构建根节点，并让根节点入列。
• 节点出列，考察，此时 cursor 指向它的左子节点值，cursor+1 指向它的右子节点值。
  1.如果子节点值是数值，则创建节点，并认了出列的父亲，并且自己也是父亲，入列。
  2.如果子节点值为 '$'，什么都不用做，因为出列的父节点的 left 和 right 本来就是 null！
• 可见，所有的真实节点都会在队列里走一遍，出列就带出儿子入列

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) { 
        if(!root) return "";
        string s;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* temp=q.front();
            q.pop();
            if(temp){
                s+=to_string(temp->val)+",";
                q.push(temp->left);
                q.push(temp->right);
            }
            else{
                s+="$,";
            } 
            //可是这样末尾的也会带“，”呀，和题目给的输入不一样。但事实上多出来也没关系，或许反而是好事呢！
            //每一个数字都带一个“，”挺好的，末尾的没必要去掉，好处看下面
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return NULL;

        //将序列化的字符串转成数组
        string num;
        vector<string> nodes;
        for(int i=0;i<data.size()-1;i++){
            num+=data[i];
            if(data[i+1]==','){ //上面末尾多出了，的好处在这里呀！
                nodes.push_back(num);
                num="";
                i++;//跳过接下来的“，”，不然num+=data[i]，会把“，”存进去
            }
        }

        //层序遍历建树
        TreeNode* root=new TreeNode(stoi(nodes[0]));
        queue<TreeNode*> q;
        q.push(root);
        int cursor=1;
        //while(!q.empty()){都可以，因为每个结点都会入队
        while(cursor<nodes.size()){
            TreeNode* temp=q.front();
            q.pop();
            if(nodes[cursor]!="$"){
                temp->left=new TreeNode(stoi(nodes[cursor]));
                q.push(temp->left);
            }
            if(nodes[cursor+1]!="$"){
                temp->right=new TreeNode(stoi(nodes[cursor+1]));
                q.push(temp->right);
            }
            cursor+=2;// 一次考察一对儿子，指针加2
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

删去上述代码中的将序列化的字符串建vector数组部分，直接使用流。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) { 
        if(!root) return "";
        string s;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* temp=q.front();
            q.pop();
            if(temp){
                s+=to_string(temp->val)+",";
                q.push(temp->left);
                q.push(temp->right);
            }
            else{
                s+="$,";
            } 
            //可是这样末尾的也会带“，”呀，和题目给的输入不一样。但事实上多出来也没关系，或许反而是好事呢！
            //每一个数字都带一个“，”挺好的，末尾的没必要去掉，好处看下面
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return NULL;

        //将序列化的字符串转成数组
        string val;
        istringstream in(data);
        getline(in, val, ',');

        //层序遍历建树
        TreeNode* root=new TreeNode(stoi(val));
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* temp=q.front();
            q.pop();
            getline(in, val, ',');
            if(val!="$"){
                temp->left=new TreeNode(stoi(val));
                q.push(temp->left);
            }
            getline(in, val, ',');
            if(val!="$"){
                temp->right=new TreeNode(stoi(val));
                q.push(temp->right);
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

时间复杂度 和 空间复杂度 O(n)

ps：
// res = res + "#"; //用这一行，内存用到了700M！
res.push_back('#');//但注意，push_back参数是char

38.字符串的排列(重点)

思路1：联想到数字的全排列问题，利用递归完成深度优先搜索dfs，遍历所有可能的答案路径。因为 对于一个长度为 n 的字符串（假设字符互不重复），其排列共有 n×(n−1)×(n−2)…×2×1 种方案。

每一次递归都从s中取任意一个字符，如果该字符前面使用了(需要一个visited数组)，就不取。
递归结束条件是构建的字符串长度==s.size()

由于题目要求去除重复的答案，利用set不包含重复元素的性质，先用set最后再转换为vector。参考了给vector去重的三种方法：https://blog.csdn.net/xiangxianghehe/article/details/90637998

想利用sort函数完成剪枝，减少重复的递归，可是没有成功。而且也没有意识到剪枝不仅加快了速度，还顺便去除了重复方案。
没成功的原因在于缺少了!visited[i-1] !!!!!!!!!!
if(i>0&&nums[i]==nums[i-1]&&!visited[i-1])//剪枝，三个条件
continue;

重复方案 与 剪枝的思路： 当字符串存在重复字符时，排列方案中也存在重复方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时直接跳过。
所以当你剪枝了，就不会出现重复方案！！不必再考虑去重问题。

class Solution {
public:
    vector<string> permutation(string s) {
        set<string> temp_ans;
        string temp;
        vector<bool> visited(s.size(),false);
        permutationCore(s,temp_ans,temp,visited);
        vector<string> ans(temp_ans.begin(),temp_ans.end());
        return ans;
    }

    void permutationCore(string &s,set<string> &ans,string &temp,vector<bool> &visited){
        if(temp.size()==s.size()){
            ans.insert(temp);
            return ;
        }
        for(int i=0;i<s.size();i++){
            if(!visited[I]){
                temp.push_back(s[I]);
                visited[i]=true;
                permutationCore(s,ans,temp,visited);
                temp.pop_back();
                visited[i]=false;
            }
        }
    }
};

剪枝版本1

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ans;
        string temp;
        vector<bool> visited(s.size(),false);
        permutationCore(s,ans,temp,visited);
        return ans;
    }

    void permutationCore(string &s,vector<string> &ans,string &temp,vector<bool> &visited){
        if(temp.size()==s.size()){
            ans.push_back(temp);
            return ;
        }
        set<char> charset;
        for(int i=0;i<s.size();i++){
            if(!visited[I]){
                if(charset.find(s[i])!=charset.end()){
                    continue;
                }
                charset.insert(s[I]);
                temp.push_back(s[I]);
                visited[i]=true;
                permutationCore(s,ans,temp,visited);
                temp.pop_back();
                visited[i]=false;
            }
        }
    }
};

剪枝版本2,前提 字符串s有序，需要sort。

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ans;
        string temp;
        vector<bool> visited(s.size(),false);
        sort(s.begin(),s.end());
        permutationCore(s,ans,temp,visited);
        return ans;
    }

    void permutationCore(string &s,vector<string> &ans,string &temp,vector<bool> &visited){
        if(temp.size()==s.size()){
            ans.push_back(temp);
            return ;
        }
        for(int i=0;i<s.size();i++){
            if(!visited[I]){
                if(i>0&&s[i]==s[i-1]&&!visited[i-1]){
                    continue;
                }
                temp.push_back(s[I]);
                visited[i]=true;
                permutationCore(s,ans,temp,visited);
                temp.pop_back();
                visited[i]=false;
            }
        }
    }
};

不调用sort函数也可以

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> res;

        dfs(res,s,0);
       
        return res;
    }

    void  dfs(vector<string> &res,string &s,int pos){
        if(pos == s.size())
            res.push_back(s);

        for(int i=pos;i<s.size();i++){
            bool flag = true;
            for(int j = pos;j<i;j++)//字母相同时，等效，剪枝
                if(s[j] == s[I])
                    flag = false;
            if(flag){
                swap(s[pos],s[I]);
                dfs(res,s,pos+1);
                swap(s[pos],s[I]);

            }
        }
    }
};

思路2:思路1很好理解，但是思路2运用了巧妙的交换。
课本p197-198，不使用visted数组。
具体概括为：把该复杂问题分为两步解决
1.轮流当天选之子(所以要互换位置,轮流上岗)
2.递归，求后面的所有字符的排列

同样的思路：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
讲得比课本好，尤其注意理解递推参数： 当前固定位x 与递推工作！！！

两个版本代码实现在下面了。

class Solution {
public:
    vector<string> permutation(string s) {
        set<string> temp_ans;
        int index=0;
        permutationCore(s,temp_ans,index);
        vector<string> ans(temp_ans.begin(),temp_ans.end());
        return ans;
    }

    void permutationCore(string &s,set<string> &ans,int index){
        if(index==s.size()){
            ans.insert(s);
            return ;
        }
        for(int i=index;i<s.size();i++){
                // 思路的第一步：轮流当天选之子
                //本质：swap(s[index],s[i]); ！！！
                char cur=s[index];
                s[index]=s[I];
                s[i]=cur;

                // 思路的第二步：求后面字符的全排列
                permutationCore(s,ans,index+1);

                cur=s[index];
                s[index]=s[I];
                s[i]=cur;
        }
    }
};

剪枝：

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ans;
        int index=0;
        permutationCore(s,ans,index);
        return ans;
    }

    void permutationCore(string &s,vector<string> &ans,int index){
        if(index==s.size()){
            ans.push_back(s);
            return ;
        }
        set<char> charset;
        for(int i=index;i<s.size();i++){

                if(charset.find(s[i])!=charset.end()){
                    continue;
                }
                charset.insert(s[i]);    

                // 思路的第一步：轮流当天选之子
                //本质：swap(s[index],s[i]); ！！！
                char cur=s[index];
                s[index]=s[I];
                s[i]=cur;

                // 思路的第二步：求后面字符的全排列
                permutationCore(s,ans,index+1);

                cur=s[index];
                s[index]=s[I];
                s[i]=cur;
        }
    }
};

39.数组中出现次数超过一半的数字

思路1:该数字肯定出现在排序后数组的中间位置。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
       sort(nums.begin(),nums.end());
       int mid=nums.size()/2;
       return nums[mid]; 
    }
};

时间O(nlogn)，空间O(1)

思路2:建立哈希表法
时间O(n)，空间O(n/2)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> hash;
        int res = 0, len = nums.size();
        for(int i = 0; i < len; i++){
            hash[nums[i]]++;
            //不必等到哈希表完全建立再进行此判断
            if(hash[nums[i]] > len/2)
                res = nums[I];
        }
        return res;
    }
};

思路3:摩尔投票法
也可以理解成混战 极限一换一，不同的两者一旦遇见就同归于尽，最后活下来的值都是相同的，即要求的结果。

课本p208同样的思路

时间O(n)，空间O(1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = 0, count = 0;
        for(int i = 0; i < nums.size(); i++){
            if(count == 0){
                res = nums[I];
                count++;
            }
            else
                res==nums[i] ? count++:count--;
        }
        return res;
    }
};

在知乎上看到的对摩尔投票法的理解：
核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。

思路4:
排序之后位于数组中间的数字一定就是答案，也就是第n/2大的数字。
有时间复杂度为o(n)的算法得到无序数组中第k大的数字。

基于partition函数的时间复杂度为o(n)的算法：
p206-207
除了用在快速排序,partition还可以用O(n)的平均时间复杂度从无序数组中寻找第k大的值.和快排一样,这里也用到了分而治之的思想.思路是,首先对数组进行一次Partition,得到坐标nPos:

• 如果nPos+1 == k,返回array[nPos];
• 如果nPos+1 > k,对数组左半部分继续进行Partition;
• 如果nPos+1 < k, 对数组右半部分继续进行Partition.

没有亲手敲代码,看课本

补充知识点：
1.顺便复习一下快速排序，需要写出完整的代码
2.partition函数的两种常见实现方式:第一个位于算法笔记：利用双指针 第二个是剑指课本的，讲解如下。

/*
Partition实现

快速排序中用到的partion算法思想很简单,首先从无序数组中选出枢轴点pivot,然后通过一趟扫描,以pivot为分界线将数组中的元素分为两部分:使得左边的数小于等于枢轴,右边的数大于等于枢轴(左右部分可能为空),最后返回枢轴在新数组中的位置.

Partition的一个直观简单实现如下(取数组第一个元素为pivot):
*/

 int partition(vector<int>&arr, int nStart, int nEnd)
{
    int pivot = arr[nStart];//选第一个元素作为枢纽元
    int nPos = nStart; 

    // 从第二个数开始和基准值比较，比枢纽元小的元素依次放在前半部分
    for (int i = nStart+1; i<=nEnd; i++)
    {
        if (array[I]<= pivot) //因为可能有重复的元素，小于等于都放在枢纽元的前面
        {
            nPos++;
            Swap(arr[i], arr[nPos]);
        }
    }
    Swap(arr[nPos], arr[nStart]);//可以保证交换到头部nStart的元素比pivot小
    return nPos;
}

/*
同样可以选择最后一个元素作为枢纽元pivot，但是当对链表快排时，选择上面的做法
*/

int partition(vector<int>&arr, int nStart, int nEnd)
{
    int pivot = arr[nEnd];//选最后一个元素作为枢纽元
    int nPos = nStart-1;

    for(int i = nStart; i < nEnd; i++)//比枢纽元小的元素依次放在前半部分
       if(arr[i] <= pivot){
            nPos++;
            swap(arr[i], arr[nPos]);
       }
    swap(arr[nEnd], arr[nPos+1]);
    return nPos+1;
}

40.最小的k个数

思路1:排序后，取前k个数字。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(),arr.end());
        return vector<int> (arr.begin(),arr.begin()+k);
    }
};

时间复杂度o(nlogn)

思路2:利用partition()函数找出第k大的数字，然后返回他和他前面的数(不一定有序)。
partition的代码写得磕磕绊绊的，随便挑了一个写法来练习，标注!表示代码经过调试才发现错误。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.empty() || k<=0 || k>arr.size()) return vector<int>();
        int l=0,r=arr.size()-1;//!
        int index=partition(arr,l,r);//!
        while(index!=k-1){
            if(index<k-1){
                l=index+1;//!
                index=partition(arr,l,r);
            }
            else{
                r=index-1;//!
                index=partition(arr,l,r);
            }
        }
        return vector<int>(arr.begin(),arr.begin()+k);
    }
    int partition(vector<int>& arr,int l,int r){
        int pivot=arr[r];
        int pos=l-1;//不是l-1是l也可以，只是后面代码要跟着变动下
        for(int i=l;i<r;i++){//!
            if(arr[i]<=pivot){//!
                pos++;
                swap(arr[i],arr[pos]);
            }
        }
        swap(arr[r],arr[++pos]);//!
        return pos;
    }
};

每次调用 partition 遍历的元素数目都是上一次遍历的 1/2，因此时间复杂度是 N + N/2 + N/4 + ... + N/N = 2N, 因此时间复杂度是 O(N)。
空间复杂度 O(logN) ，因为划分函数的平均递归深度为 O(logN) 。

思路1与思路2的时间空间复杂度一致。

思路3:时间复杂度为o(nlogk)的算法，适合处理海量数据
空间复杂度：O(k)，因为大根堆里最多 k 个数
p210-213

如果使用堆：使用大顶堆，而不是小顶堆。
由于每次从堆顶弹出的数都是堆中最大的，最小的 k 个元素一定会留在堆里。这样，把数组中的元素全部入堆之后，堆中剩下的 k 个元素就是最大的 k 个数了。

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/
看这里的方法2.

• 优先队列底层是堆。
  优先队列写法：

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

java这种，优先队列默认是小顶堆，因此我们要对数组中所有的数取其相反数，才能使用小根堆维护前 k 小值，或者改写优先队列。

// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
// 1. 若目前堆的大小小于K，将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
//    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }

        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
        //或者一行代码解决
        //return  pq.stream().mapToInt(Integer::intValue).toArray();
}

• 自己手写堆
  别人写的，没自己实现

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k == 0) return new int[0];
        int[] result = new int[k];
        int i = 0;
        while(i < k){
            result[i] = arr[i];
            i++;
        }
        buildHeap(result);
        while(i < arr.length){
            if(arr[i] < result[0]){
                result[0] = arr[i];
                adjust(result, 0);
            }
            i++;
        }
        return result;
    }
    public void buildHeap(int[] arr){
        for(int i = arr.length / 2 - 1; i >= 0; i--){
            adjust(arr, i);
        }
    }
    public void adjust(int[] arr, int i){
        int maxIndex = i;
        int len = arr.length;
        if(2*i+1 < len && arr[2*i+1] > arr[maxIndex]) maxIndex = 2*i+1;
        if(2*i+2 < len && arr[2*i+2] > arr[maxIndex]) maxIndex = 2*i+2;
        if(maxIndex != i){
            swap(arr, maxIndex, i);
            adjust(arr, maxIndex);
        }
    }
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

如果使用multiset/map(都是二叉搜索树bst，都基于红黑树)：
与之前的方法相比，这有一个好处是求得的前K大的数字是有序的。
ps:访问map/set中最后一个元素(即最大值)的方法

• *s.rbegin()
• *(--s.end())

当然map/set建立时也可以加上参数greater<int>,使得从大到小排序，这样begin()就是最大值了。
举例子：map<int,int,greater<int> >; set<int,greater<int> > ;

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.empty()|| k<1 || k>arr.size()) return vector<int>();
        multiset<int> topk;
        for(int i=0;i<arr.size();i++){
            if(topk.size()<k){
                topk.insert(arr[i]);
            }
            else{
                multiset<int>::iterator max = --topk.end();
                if(arr[i] < *max){
                    topk.erase(max);
                    topk.insert(arr[i]);
                }
            }
        }
        return vector<int>(topk.begin(),topk.end());
    }
};

另外，留意multiset与set删除操作的不同：使用迭代器和值作为erase的参数是不一样的。
https://www.cnblogs.com/lakeone/p/5600494.html

如果使用map(基于红黑树实现):
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/
链接里的方法三

思路4:
题目说0 <= arr[i] <= 10000。
数据范围有限时直接计数排序就好，时间复杂度O(N)

别人写的，自己没实现

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 统计每个数字出现的次数
        int[] counter = new int[10001];
        for (int num: arr) {
            counter[num]++;
        }
        // 根据counter数组从头找出k个数作为返回结果
        int[] res = new int[k];
        int idx = 0;
        for (int num = 0; num < counter.length; num++) {
            while (counter[num]-- > 0 && idx < k) {
                res[idx++] = num;
            }
            if (idx == k) {
                break;
            }
        }
        return res;
    }
}