2020-05-04

• 最长连续序列
• 3SUM
• 923. 三数之和的多种可能
• 300. 最长上升子序列
• 333. 最大 BST 子树
• 33. 搜索旋转排序数组
• 153. 寻找旋转排序数组中的最小值
• 545. 二叉树的边界
• 679. 24点游戏
• 312. 戳气球
• 1246. 删除回文子数组
• 772. 基本计算器 III
• 727. 最小窗口子序列
• 642. 设计搜索自动补全系统
• 702. 搜索长度未知的有序数组
• 146. LRU缓存机制
• 490. 迷宫
• 340. 至多包含 K 个不同字符的最长子串
• 240. 搜索二维矩阵 II
• 428. 序列化和反序列化 N 叉树
• 253. 会议室 II
• 1236. 网络爬虫
• 727. 最小窗口子序列
• 694. 不同岛屿的数量
• 295. 数据流的中位数
• 140. 单词拆分 II
• 138. 复制带随机指针的链表
• 510. 二叉搜索树中的中序后继 II
• 545. 二叉树的边界
• 314. 二叉树的垂直遍历
• 722. 删除注释

最长连续序列

class Solution{
    public:
        int longestConsecutive(vector<int> &nums){
            unordered_map<int , int> map;
            int size = nums.size();
            int l = 1;
            for(int i = 0; i < size ; i++){
                if(map.find(nums[i] != map.end())){
                    continue;
                }
                map[nums[i]] = 1;
                if(map.find(nums[i]-1) != map.end()){
                    l = max(l, mergeCluster(map, nums[i] - 1, nums[i]));
                }
                if(map.find(nums[i]+1) != map.end()){
                    l = max(l, mergeCluster(map, nums[i], nums[i] + 1));
                }
            }
            return size == 0 ? 0 : l;
        }
    private:
        int mergeCluster(unordered_map<int, int>& map, int left ,int right){
            int upper = right + map[right] - 1;
            int lower = left - map[left] + 1;
            int leghth = upper - lower + 1;
            map[upper] = length;
            map[lower] = length;
            return length;
        }
}

3SUM

class So;ution{
    public: 
    vetcor<vector<int>> threeSum(vector<int>& nums, const int target){
        vector<vector<int>> result;
        if(nums.size() < 3) return result;
        sort(nums.begin(), nums.end());
        auto last = nums.end();
        for(auto i = nums.begin(); i < last - 2; i++){
            auto j = i + 1;
            if(j > nums.beigin() && *i == *(i-1)){
                continue;
            } 
            auto k = last - 1;
            while(j < k){
                if(*i + *j + *k < target){
                    ++j;
                    while(*j  == *(j+1) && j < k){
                        j++;
                    }
                }else if(*i + *j + *k > target){
                    k--;
                    while(*k == *(k+1) && j < k){
                        k--;
                    }
                }else{
                    result.push_back({*i, *j ,*k});
                    j++;
                    k--;
                    while(*j == *(j-1) )
                }
            }
        }

    }
}

923. 三数之和的多种可能

class Solution {
public:
    const long D = 1e9 + 7;
    int threeSumMulti(vector<int>& nums, int target) {
        int res = 0;
        if(nums.size() < 3) return res;
        int size = nums.size();
        sort(nums.begin(), nums.end());
        for(auto i = 0; i < size - 2; ++i){
            if(target < 3 * nums[i]) break;
            int j = i + 1;
            int k = size - 1;
            while(nums[j] < nums[k]){
                if (nums[i] + nums[j] + nums[k] < target){
                    ++j;
                } else if(nums[i] + nums[j] + nums[k] > target){
                    --k;
                } else {
                    int tmpJ = j;
                    int sameJ = 1;
                    int sameK = 1;
                    while(j + 1 <= k && nums[tmpJ] == nums[++j]){//不用tmpJ的写法可能会死循环，为什么？
                        sameJ++;
                    }
                    int tmpK = k;
                    while(k - 1 >= j && nums[tmpK] == nums[--k]){
                        sameK++;
                    }
                    res += (sameJ * sameK);
                    res = res % D;
                }
            }
            if(nums[j] == nums[k] && nums[i] + nums[j] + nums[k] == target){
                long d = k -j + 1;
                res += (d * (d-1)) / 2;
                res = res%D;
            }
        }
        return res%D;
    }
};

300. 最长上升子序列

长度为 i(下标) + 1 的递增子序列末尾的最小数字。

很具小巧思。新建数组 cell，用于保存最长上升子序列。
对原序列进行遍历，将每位元素二分插入 cell 中。
如果 cell 中元素都比它小，将它插到最后
否则，用它覆盖掉比它大的元素中最小的那个。

尝试left + 1 < right 模板

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return 1;
        int len  = nums.size();
        vector<int> dp(len , 0);
        int index = 0;
        dp[index] = nums[0];
        for(int i = 1; i < len; i++){
            if(nums[i] > dp[index]){
                dp[++index] = nums[i];
            } else {
                int l = 0;
                int r = index;
                while(l + 1 < r){
                    int mid = l + (r - l)/2;
                    if(nums[i] >= dp[mid] ){//nums[i] <= dp[mid] 也行
                        l = mid;
                    } else if(nums[i] < dp[mid]){
                        r = mid;
                    }
                }
                if (dp[l] > nums[i] && nums[i] != dp[r]){
                    dp[l] = nums[i];
                } else if(dp[r] > nums[i] && dp[l] != nums[i]){
                    dp[r] = nums[i];
                }
            }
        }
        return index + 1;
    }
};

333. 最大 BST 子树

helper函数返回了一个一维数组，里面有三个数字，分别是以当前结点为根结点的树的最小值，最大值，以及最大的 BST 子树的结点个数。

class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        vector<int> res = help(root);
        return res[2];
    }

    vector<int> help(TreeNode* node){
        if(node == nullptr){
            return {INT_MAX, INT_MIN, 0};
        }
        vector<int> left = help(node->left);
        vector<int> right = help(node->right);
        if(node->val > left[1] && node->val < right[0]){
            return {min(node->val, left[0]), max(node->val, right[1]), left[2] + right[2] + 1};
        }else{
            return {INT_MIN, INT_MAX, max(left[2], right[2])};
        }
    }
};

33. 搜索旋转排序数组

先锁定mid的区间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()){
            return -1;
        }
        int len = nums.size();
        int l = 0;
        int r = nums.size() - 1;
        while(l + 1 < r){
            int mid = l + (r - l)/2;
            if(nums[mid] == target) return mid;
            if(nums[0] <= nums[mid]){
                if(nums[0] <= target && target <= nums[mid]){
                    r = mid;
                } else {
                    l = mid;
                }
            } else {
                if(nums[len - 1] >=target && target >= nums[mid]){
                    l = mid;
                }else{
                    r = mid;
                }
            }
        }
        if(nums[l] == target){
            return l;
        }else if(nums[r] == target){
            return r;
        }else{
            return -1;
        }
    }
};

153. 寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()){
            return -1;
        }
        int len = nums.size();
        int l = 0;
        int r = len - 1;
        while(l + 1 < r){
            int mid = l + (r - l)/2;
            if(nums[0] > nums[len-1]){
                if(nums[mid] >= nums[0]){
                    l = mid;
                }
                else if(nums[mid] <= nums[len -1 ]){
                    r = mid;
                }
            }else{
                return nums[0]; // 注意不旋转的情况
            }
        }
        return min(nums[l], nums[r]);
    }
};

545. 二叉树的边界

class Solution {
public:
    void dfs(TreeNode* root, int dir, vector<int>& res){
        if(root == nullptr) return;
        if(dir == 0){
            //无方向，寻找叶子节点
            if(root->left == nullptr && root->right == nullptr){
                res.push_back(root->val);
            }else{
                dfs(root->left, 0, res);
                dfs(root->right, 0, res);
            }
            return;
        }

        if(dir == -1){
            //左方向，先序遍历
            res.push_back(root->val);
            if(root->left){
                dfs(root->left, dir, res);
                dfs(root->right, 0, res);
            }else{
                dfs(root->right, dir, res);
            }
        }else{
            //右方向，后序遍历
            if(root->right){
                dfs(root->left, 0, res);
                dfs(root->right, dir, res);
            }else{
                dfs(root->left, dir, res);
            }
            res.push_back(root->val);
        }
    }
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if(root == nullptr) return{};
        vector<int> res{root->val};
        dfs(root->left, -1, res);
        dfs(root->right, 1, res);
        return res;
    }
};

679. 24点游戏

class Solution {
public:
    vector<char> ops{'+', '-', '*', '/'};
    double eps = 0.001;        

    bool judgePoint24(vector<int>& nums) {
        vector<double> arr(nums.begin(), nums.end());
        return helper(arr);
    }
    bool helper(vector<double>& nums) {
        if (nums.size() == 1) return abs(nums[0] - 24) < eps;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < nums.size(); ++j) {
                if (i == j) continue;
                vector<double> t;
                for (int k = 0; k < nums.size(); ++k) {
                    if (k != i && k != j) t.push_back(nums[k]);
                }
                for (char op : ops) {
                    if ((op == '+' || op == '*') && i > j) continue;
                    if (op == '/' && nums[j] < eps) continue;
                    switch(op) {
                        case '+': t.push_back(nums[i] + nums[j]); break;
                        case '-': t.push_back(nums[i] - nums[j]); break;
                        case '*': t.push_back(nums[i] * nums[j]); break;
                        case '/': t.push_back(nums[i] / nums[j]); break;
                    }
                    if (helper(t)) return true;
                    t.pop_back();
                }
            }
        }
        return false;
    }
};

312. 戳气球

https://leetcode-cn.com/problems/burst-balloons/

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        int n=nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));//dp[i][j]表示第i至第j个元素这个区间能获得的最大硬币数
        for(int r=2;r<n;r++)            //r为区间长度
            for(int i=0;i<n-r;i++){    //i为左区间
                int j=i+r;            //j为右区间
                for(int k=i+1;k<j;k++)
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j]);
            }
        
        return dp[0][n-1];
    }
};

1246. 删除回文子数组

class Solution {
public:
  int minimumMoves(vector<int>& arr) {
        int dp[arr.size()][arr.size()];
        for(int i = 0; i < arr.size(); i++)
            dp[i][i] = 1;
        for(int i = 0; i < arr.size() - 1; i++)
            if(arr[i] == arr[i + 1])
                dp[i][i + 1] = 1;
            else
                dp[i][i + 1] = 2;
        for(int len = 2; len < arr.size(); len++){
            for(int i = 0; i < arr.size() - len; i++) {
                dp[i][i + len] = len + 1;
                for(int k = 0; k < len; k++){
                    if(dp[i][i + len] > dp[i][i + k] + dp[i + k + 1][i + len]){
                        dp[i][i + len] = dp[i][i + k] + dp[i + k + 1][i + len];
                    }
                }   
                if(arr[i] == arr[i + len] && dp[i][i + len] > dp[i + 1][i + len - 1]){
                    dp[i][i + len] = dp[i + 1][i + len - 1];
                }
            }
        }
        return dp[0][arr.size() - 1];
    }
};

772. 基本计算器 III

class Solution {
public:
    int calculate(string s) {

    }
};

727. 最小窗口子序列

class Solution {
public:
    string minWindow(string S, string T) {
        if (S.size() < T.size()) return "";
        int NS = S.size();
        int NT = T.size();
        string res;
        int resLen = NS;
        for (int i = 0; i <= NS - NT; ++i) {
            if (S[i] != T[0]) continue;
            // 正向匹配
            int j = 0;
            while (i < NS && j < NT) {
                if (S[i] == T[j]) ++j;
                ++i;
            }
            if (j != NT) break;
            // 反向匹配
            int r = i;
            j = NT - 1;
            --i;
            while (j >= 0) {
                if (S[i] == T[j]) --j;
                --i;
            }
            ++i;
            if (r - i < resLen) {
                res = S.substr(i, r - i);
                resLen = r - i;
            } else {
                i = r - resLen;
            }
        }
        return res;
    }
};

642. 设计搜索自动补全系统

struct TrieNode {
    int val = 0;
    map<char, TrieNode*> children;
};
class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        ans = "";
        cur = root = new TrieNode();
        // 构建trie树
        for(int i=0;i<sentences.size();i++) {
            add(sentences[i], times[i]);
        }
    }

    void add(string& s, int time) {
        TrieNode* node = root;
        for(char c: s) {
            if(node->children.find(c)==node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->val += time;
    }
    
    vector<string> input(char c) {
        // 输入结束时复位
        if (c == '#') {
            cur->val++;
            cur = root;
            ans = "";
            return {};
        }
        // 更新当前节点
        if(cur->children.find(c)==cur->children.end()) {
            cur->children[c] = new TrieNode();
        }
        cur = cur->children[c];
        ans += c;
        // 查找所有符合条件的候选集及出现次数
        vector<pair<string, int>> vec;
        find(cur, ans, vec);
        // 按次数及字典序排序
        sort(vec.begin(), vec.end(), [this](pair<string, int>& p1, pair<string, int>& p2){
            return p1.second == p2.second ? compare(p1.first, p2.first) : p1.second > p2.second; 
        });
        // 取top 3
        vector<string> res;
        for(auto& p: vec) {
            res.push_back(p.first);
            if(res.size()>=3) break;
        }
        return res;
    }
    // 字典序比较
    bool compare(string& s1, string& s2) {
        int i = 0, m = s1.size(), n = s2.size();
        while(i<m&&i<n) {
            if(s1[i] != s2[i]) {
                return s1[i] < s2[i];
            }
            i++;
        }
        return m <= n;
    }
    // dfs查找所有候选集及次数
    void find(TrieNode* node, string ans, vector<pair<string, int>>& vec) {
        if(node->val>0) {
            vec.push_back({ans, node->val});
        }
        for(auto& it: node->children) {
            find(it.second, ans+it.first, vec);
        }
    }
private:
    TrieNode* root;
    TrieNode* cur;  // 当前节点
    string ans = "";  // 历史输入
};

702. 搜索长度未知的有序数组

class ArrayReader;

class Solution {
  public:
  int search(const ArrayReader& reader, int target) {
    if (reader.get(0) == target) return 0;

    // search boundaries
    int left = 0, right = 1;
    while (reader.get(right) < target) {
      left = right;
      right <<= 1;
    }

    // binary search
    int pivot, num;
    while (left <= right) {
      pivot = left + ((right - left) >> 1);
      num = reader.get(pivot);

      if (num == target) return pivot;
      if (num > target) right = pivot - 1;
      else left = pivot + 1;
    }

    // there is no target element
    return -1;
  }
};

146. LRU缓存机制

class LRUCache {
private:
    int cap;
    // 双链表：装着 (key, value) 元组
    list<pair<int, int>> cache;
    // 哈希表：key 映射到 (key, value) 在 cache 中的位置
    unordered_map<int, list<pair<int, int>>::iterator> map;
public:
    LRUCache(int capacity) {
        this->cap = capacity; 
    }
    
    int get(int key) {
        auto it = map.find(key);
        // 访问的 key 不存在
        if (it == map.end()) return -1;
        // key 存在，把 (k, v) 换到队头
        pair<int, int> kv = *map[key];
        cache.erase(map[key]);
        cache.push_front(kv);
        // 更新 (key, value) 在 cache 中的位置
        map[key] = cache.begin();
        return kv.second; // value
    }
    
    void put(int key, int value) {

        /* 要先判断 key 是否已经存在 */ 
        auto it = map.find(key);
        if (it == map.end()) {
            /* key 不存在，判断 cache 是否已满 */ 
            if (cache.size() == cap) {
                // cache 已满，删除尾部的键值对腾位置
                // cache 和 map 中的数据都要删除
                auto lastPair = cache.back();
                int lastKey = lastPair.first;
                map.erase(lastKey);
                cache.pop_back();
            }
            // cache 没满，可以直接添加
            cache.push_front(make_pair(key, value));
            map[key] = cache.begin();
        } else {
            /* key 存在，更改 value 并换到队头 */
            cache.erase(map[key]);
            cache.push_front(make_pair(key, value));
            map[key] = cache.begin();
        }
    }
};

490. 迷宫

class Solution {
public:
  bool BFS(vector<vector<int>>& maze, vector<vector<bool>> &visit, vector<int> start, vector<int> end, int matrix_r, int matrix_c) {
        queue<pair<int, int>> q;
        // 队首元素入队
        q.push(make_pair(start[0], start[1]));
        visit[start[0]][start[1]] = true;
        while (!q.empty()) {
            pair<int, int> top = q.front();
            q.pop();
            // 取队列首元素，确定下是否到达终点
            if (top.first == end[0] && top.second == end[1]) {
                return true;
            }
            int x[4] = {0, 0, 1, -1};
            int y[4] = {1, -1, 0, 0};
            for (int i = 0; i < 4; i++) {
                int row = top.first;
                int col = top.second;
                // 球回沿着一个方向一直滚动， 除非遇到墙才会停下来选择别的方向
                while ((row + x[i]) >= 0 && (row + x[i]) < matrix_r && (col + y[i]) >= 0 && (col +y[i]) < matrix_c &&
                        maze[row + x[i]][col + y[i]] == 0) {
                    row += x[i];
                    col += y[i];
                }
                // 等到碰到墙壁，需要更换方向前，需要将此点入队，并标志已经访问
                // 队列中存放的是碰到墙壁的点或者边界点（可以理解为墙壁点）
                if (visit[row][col] == false) {
                    q.push(make_pair(row, col));
                    visit[row][col] = true;
                }
            }
        }
        return false;
    }
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int matrix_r = maze.size();
        int matrix_c = maze[0].size();
        vector<vector<bool>> visit(matrix_r, vector<bool>(matrix_c, false));
        bool res = BFS(maze, visit , start, destination, matrix_r, matrix_c);
        return res;
    }
};

340. 至多包含 K 个不同字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int cnt[256] = {0};
        int used = 0;
        int len = 0, start = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if(0 == cnt[s[i]]) used++;
            cnt[s[i]]++;

            while(used > k)
            {
                cnt[s[start]]--;
                if(0 == cnt[s[start]]) used--;
                start++;
            }
            len = max(len, i - start + 1);
        }
        return len;
    }
};

240. 搜索二维矩阵 II

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return false;
        int i = matrix.size() - 1;
        int j = 0;
        while(i >= 0 && j < matrix[0].size()){
            if(matrix[i][j] > target)
                --i;
            else if(matrix[i][j] < target)
                ++j;
            else return true;
        }
        return false;
    }
};

428. 序列化和反序列化 N 叉树

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(Node* root) {
        if (root == NULL)
            return "";
        string res = to_string(root->val) + "[";
        for (auto node : root->children) {
            res += serialize(node) + ",";
        }
        if (res.back() == ',')
            res.pop_back();
        res += "]";
        return res;
    }

    // Decodes your encoded data to tree.
    Node* deserialize(string data) {
        cout << data << endl;
        string value;
        Node* head = NULL;
        stack<Node*> s;
        for (int i = 0; i < data.size(); ++i) {
            const char& c = data[i];
            if ((c >= '0' && c <= '9') || c == '+' || c == '-') {
                value += c;
            } else if (c == '[') {
                Node* node = new Node(stoi(value));
                if (head == NULL)
                    head = node;
                s.push(node);
                value.clear();
            } else if (c == ']') {
                Node* node = s.top();
                s.pop();
                if (!s.empty()) {
                    Node* prev_node = s.top();
                    prev_node->children.push_back(node);
                }
            }
        }
        return head;
    }
};

253. 会议室 II

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

默认是大顶堆，本题使用小顶堆

结束时间最小的是否满足接下来要开始的

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.size() == 0)
            return 0;

        // 根据会议开始时间排序
        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> rooms;
        for (const auto& range : intervals) {
            const int& s = range[0];
            const int& e = range[1];
            if (rooms.empty()) {            // 第一个会议结束时间来初始堆
                rooms.push(e);
                continue;
            } else if (rooms.top() <= s) {  // 有空余房间
                rooms.pop();
                rooms.push(e);
            } else rooms.push(e);           // 没有空余房间
        }
        return rooms.size();                // 返回房间个数
    }
};

1236. 网络爬虫

class Solution {
public:
    string getHostname(string& url) {
        int pos = url.find('/', 7);
        if (pos == string::npos) {
            return url.substr(7);
        }
        return url.substr(7, pos - 7);
    }
    vector<string> crawl(string startUrl, HtmlParser htmlParser) {
        set<string> visited;
        deque<string> q;
        q.push_back(startUrl);
        vector<string> res;
        string hostname = getHostname(startUrl);

        while (!q.empty()) {
            string url = q.front();
            q.pop_front();
            if (visited.find(url) != visited.end()) {
                continue;
            }
            visited.insert(url);
            if (getHostname(url) != hostname) {
                continue;
            }
            res.push_back(url);
            vector<string> urls = htmlParser.getUrls(url);
            for (string& s : urls) {
                q.push_back(s);
            }
        }
        return res;
    }
};

727. 最小窗口子序列

1，从S的起点i先正向匹配找到符合条件的区间最小的终点j
2，从j反向匹配，找到最大的满足条件的新起点k

class Solution {
public:
    string minWindow(string S, string T) {
        if (S.size() < T.size()) return "";
        int NS = S.size();
        int NT = T.size();
        string res;
        int resLen = NS;
        for (int i = 0; i <= NS - NT; ++i) {
            if (S[i] != T[0]) continue;
            // 正向匹配
            int j = 0;
            while (i < NS && j < NT) {
                if (S[i] == T[j]) ++j;
                ++i;
            }
            if (j != NT) break;
            // 反向匹配
            int r = i;
            j = NT - 1;
            --i;
            while (j >= 0) {
                if (S[i] == T[j]) --j;
                --i;
            }
            ++i;
            if (r - i < resLen) {
                res = S.substr(i, r - i);
                resLen = r - i;
            } else {
                i = r - resLen;
            }
        }
        return res;
    }
};

694. 不同岛屿的数量

class Solution {
public:
    int row, col;
    void dfs(vector<int>& island, vector<vector<bool>>& visited, vector<vector<int>>& grid, int sr, int sc, int r,int c){
        if(r>=row || r<0 || c<0 || c>=col || visited[r][c] || grid[r][c] ==0) {
            return;
        }
        visited[r][c] = true;
        island.push_back((r-sr)*col + (c-sc));
        dfs(island, visited, grid, sr, sc, r-1, c);
        dfs(island, visited, grid, sr, sc, r+1, c);
        dfs(island, visited, grid, sr, sc, r, c-1);
        dfs(island, visited, grid, sr, sc, r, c+1);
    }
    int numDistinctIslands(vector<vector<int>>& grid) {
        row = grid.size();
        col = grid[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col,false));
        set<vector<int>> islands;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                vector<int> island;
                dfs(island, visited, grid, i, j, i, j);
                if(!island.empty()){
                    islands.insert(island);
                }
            }
        }
        return islands.size();
    }
};

295. 数据流的中位数

class MedianFinder {
    priority_queue<int> lo;                              // max heap
    priority_queue<int, vector<int>, greater<int>> hi;   // min heap

public:
    // Adds a number into the data structure.
    void addNum(int num)
    {
        lo.push(num);                                    // Add to max heap

        hi.push(lo.top());                               // balancing step
        lo.pop();

        if (lo.size() < hi.size()) {                     // maintain size property
            lo.push(hi.top());
            hi.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian()
    {
        return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
    }
};

140. 单词拆分 II

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string,vector<string> > m;
        return helper(m,wordDict,s);
    }
    vector<string> helper(unordered_map<string,vector<string> >& m,vector<string>& wordDict,string s){
        if(m.count(s)) return m[s];
        if(s.empty()) return {""};
        vector<string> res;
        for(auto word : wordDict){
            if(s.substr(0,word.size())!=word) continue;
            vector<string> tmp=helper(m,wordDict,s.substr(word.size()));
            for(auto itm:tmp){
                res.push_back(word+(itm.empty()?"":" "+itm));
            }
        }
        m[s]=res;
        return res;
    }
};

138. 复制带随机指针的链表

class Solution {
public:
    //方法1
    Node* copyRandomList1(Node* head)
    {
        if (head == nullptr)
            return head;

        //遍历原链表 创建新链表节点并建立映射关系
        unordered_map<Node*, Node*> map; //key: 原链表节点  value: 新创建节点 

        Node* cur = head;
        while (cur)
        {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }

        //遍历原链表 根据map找新链表的random
        cur = head;
        while (cur)
        {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }

        return map[head];
    }

    //方法2
    Node* copyRandomList(Node* head)
    {
        if (head == nullptr)
            return head;

        //遍历原链表 遍历过程中插入新副本节点
        Node* cur = head;
        while (cur)
        {
            Node* node = new Node(cur->val);
            Node* next = cur->next;
            node->next = next;
            cur->next = node;
            cur = next;
        }

        //遍历原链表 对新副本节点设置random指针
        cur = head;
        while (cur)
        {
            cur->next->random = cur->random ? cur->random->next : nullptr;
            cur = cur->next->next;
        }

        //分离出原链表与新副本链表
        cur = head;
        Node* new_cur = head->next;
        Node* res = new_cur;
        while (cur)
        {
            cur->next = cur->next->next;
            cur = cur->next;

            new_cur->next = cur ? cur->next : nullptr;
            new_cur = new_cur->next;
        }

        return res; //注意：不能再返回head->next了，head已经是分离后的原链表
    }
};

510. 二叉搜索树中的中序后继 II

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if (!node) return node;
        if (!node->right) {
            Node* head  = node->parent;
            while (head) {
                if (head->val > node->val) break;
                head = head->parent;
            }
            return head;
        }
        Node* head = node->right;
        while (head->left) {
            head = head->left;
        }
        return head;
    }
};

545. 二叉树的边界

class Solution {
public:
    void dfs(TreeNode* root, int dir, vector<int>& res){
        if(root == nullptr) return;
        if(dir == 0){
            //无方向，寻找叶子节点
            if(root->left == nullptr && root->right == nullptr){
                res.push_back(root->val);
            }else{
                dfs(root->left, 0, res);
                dfs(root->right, 0, res);
            }
            return;
        }

        if(dir == -1){
            //左方向，先序遍历
            res.push_back(root->val);
            if(root->left){
                dfs(root->left, dir, res);
                dfs(root->right, 0, res);
            }else{
                dfs(root->right, dir, res);
            }
        }else{
            //右方向，后序遍历
            if(root->right){
                dfs(root->left, 0, res);
                dfs(root->right, dir, res);
            }else{
                dfs(root->left, dir, res);
            }
            res.push_back(root->val);
        }
    }
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if(root == nullptr) return{};
        vector<int> res{root->val};
        dfs(root->left, -1, res);
        dfs(root->right, 1, res);
        return res;
    }
};

314. 二叉树的垂直遍历

class Solution {

private:
    map<int,int> hasht;
    vector<vector<int>> ans;


public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if(root == NULL) return ans;

        queue<TreeNode*> q;
        queue<int> state;
        q.push(root);
        state.push(0);

        while(q.size()!=0){
            auto temp = q.front();
            auto temp_state = state.front();
            q.pop();
            state.pop();

            if(hasht.find(temp_state) == hasht.end()){
                vector<int> ans_layer;
                ans_layer.push_back(temp->val);
                ans.push_back(ans_layer);
                hasht[temp_state] = ans.size()-1;
            }
            else{
                ans[hasht[temp_state]].push_back(temp->val);
            }
            if(temp->left != NULL){
                q.push(temp->left);
                state.push(temp_state - 1);
            }
            if(temp->right != NULL){
                q.push(temp->right);
                state.push(temp_state + 1);
            }           

        }

        vector<vector<int>> ordered_ans;
        for(auto &it:hasht){
            ordered_ans.push_back(ans[(it).second]);
        }
        return ordered_ans;
    }
};

722. 删除注释

class Solution {

private:
    map<int,int> hasht;
    vector<vector<int>> ans;


public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if(root == NULL) return ans;

        queue<TreeNode*> q;
        queue<int> state;
        q.push(root);
        state.push(0);

        while(q.size()!=0){
            auto temp = q.front();
            auto temp_state = state.front();
            q.pop();
            state.pop();

            if(hasht.find(temp_state) == hasht.end()){
                vector<int> ans_layer;
                ans_layer.push_back(temp->val);
                ans.push_back(ans_layer);
                hasht[temp_state] = ans.size()-1;
            }
            else{
                ans[hasht[temp_state]].push_back(temp->val);
            }
            if(temp->left != NULL){
                q.push(temp->left);
                state.push(temp_state - 1);
            }
            if(temp->right != NULL){
                q.push(temp->right);
                state.push(temp_state + 1);
            }           

        }

        vector<vector<int>> ordered_ans;
        for(auto &it:hasht){
            ordered_ans.push_back(ans[(it).second]);
        }
        return ordered_ans;
    }
};