21_0108写了不少leetcode 代码合集 100-150之间的题目大概

#include <iostream>
#include <time.h>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <stack>
#include <queue>
#include <unordered_set>
#include <math.h>

using namespace std;


struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    ListNode(int x,ListNode* p) : val(x), next(p) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//leetcode 138 复制随机指针链表
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

//leetcode 133
class NodeGraph {
public:
    int val;
    vector<NodeGraph*> neighbors;
    NodeGraph() {
        val = 0;
        neighbors = vector<NodeGraph*>();
    }
    NodeGraph(int _val) {
        val = _val;
        neighbors = vector<NodeGraph*>();
    }
    NodeGraph(int _val, vector<NodeGraph*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

//1229 leetcode 116
class NodeTwo {
public:
    int val;
    NodeTwo* left;
    NodeTwo* right;
    NodeTwo* next;

    NodeTwo() : val(0), left(NULL), right(NULL), next(NULL) {}

    NodeTwo(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    NodeTwo(int _val, NodeTwo* _left, NodeTwo* _right, NodeTwo* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};


int* pAll = new int(11);
class Solution
{
public:

    //1218 非递归解法前序遍历
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        while (!s.empty() || p)
        {
            while (p)
            {
                //cout<<"cur val is "<<p->val<<endl;
                res.push_back(p->val);
                s.push(p);
                p = p->left;
            }
            if(!s.empty())
            {
                TreeNode* tmp = s.top();
                s.pop();
                p = tmp->right;
            }
            
        }
        
        return res;
    }

    vector<int> middleTravel(TreeNode* root)
    {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        while (!s.empty() || p != NULL)
        {
            while (p != NULL)
            {
                s.push(p);
                p = p->left;
            }

            if(!s.empty())
            {
                TreeNode* tmp = s.top();
                s.pop();
                res.push_back(tmp->val);
                p = tmp->right;
            }
        }
        return res;
    }

    //1218 二叉树层序遍历
    vector<vector<int>> travelTreeNodeByFloor(TreeNode* root)
    {
        vector<vector<int>> res;
        if(root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int size = q.size();
            int count = 0;
            vector<int> curFloor;
            while (count < size)
            {
                TreeNode* curTreeNode = q.front();
                q.pop();
                curFloor.push_back(curTreeNode->val);
                count++;
                if(curTreeNode->left != NULL) q.push(curTreeNode->left);
                if(curTreeNode->right != NULL) q.push(curTreeNode->right);
            }
            for_each(curFloor.begin(),curFloor.end(),[](auto& x){cout<<x<<" ";});
            cout<<endl;
            res.push_back(curFloor);
        }

        return res;
    }

    //1221 leetcode 143
    void reorderList(ListNode* head) {
        
        if(!head) return;
        vector<ListNode*> l;
        ListNode* dummyHead = head;
        while(dummyHead){
            l.push_back(dummyHead);
            dummyHead = dummyHead->next;
        }
        int left = 0, right = l.size()-1;
        while(left < right){
            l[left]->next = l[right];
            l[right--]->next = l[++left];
        }
        if(left==right || left > right)
            l[left]->next = nullptr;
    }

    //1221 tmp
    void travelListNode(ListNode* root)
    {
        if(root == NULL) return;
        cout<<"cur val is "<<root->val<<endl;
        travelListNode(root->next);
    }

    //1214 临时加一个 链表快速排序
    //尾插法创建链表 2 3 1 9 8 10
    ListNode* headInsertListNode()
    {
        vector<int> nums = {1,2,3,4};
        ListNode* dumy = new ListNode(0); //先建一个首节点，方便后续尾插法插入数据
        ListNode* cur = dumy;
        for(int i = 0;i<nums.size();i++)
        {
            ListNode* tmp = new ListNode(nums[i]);
            cur->next = tmp;
            tmp->next = NULL;
            cur = tmp;
        }
        return dumy->next;
    }

    void test(int *p)
    {
        cout<<"before *p is "<<*p<<endl;
        int* p1 = new int(12);
        p = p1;
        cout<<"*p1 is "<<*p1<<endl;
        p = pAll;
        cout<<"after *p is "<<*p<<endl;
    }

    //1222 链表非递归反转
    ListNode* reverseListNode(ListNode* head)
    {
        if(head == NULL || (head != NULL && head->next == NULL)) return head;

        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        ListNode* cur = NULL;
        while (head)
        {
            ListNode* tmp = head;
            head = head->next; //head 应该放在前面，不然放后面就退出了
            pre->next = tmp;
            tmp->next = cur;
            cur = tmp;    
        }
        
        return dummy->next;
    }

    //1222 leetcode 139
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        unordered_set<string> words(wordDict.begin(),wordDict.end());
        vector<bool> dp(len+1,false);

        dp[0] = true;
        for(int i=1;i<=len;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(dp[j] && words.find(s.substr(j,i-j)) != words.end())
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[len];

        /*
        vector<vector<bool>> isTure(len+1,vector<bool>(len+1,false));
        for(int i=1;i<=len;i++)
        {
            for(int j= i;j<=len;j++)
            {
                cout<<s.substr(i-1,j-(i-1))<<" ";
                if(words.find(s.substr(i-1,j-(i-1))) != words.end())
                {
                    isTure[i][j] = true;
                }
            }
            cout<<endl;
        }
        */


        return true;
    }

    //1222 leetcode 140
    /*
    给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
    说明：
    分隔时可以重复使用字典中的单词。
    你可以假设字典中没有重复的单词。
    示例 1：
    输入:
    s = "catsanddog"
    wordDict = ["cat", "cats", "and", "sand", "dog"]
    输出:
    [
      "cats and dog",
      "cat sand dog"
    ]
    */
    vector<string> wordBreak_2(string s, vector<string>& wordDict) {
        //暂时不会 先不写    
    }

    //1222 leetcode 141
    bool hasCycle(ListNode *head) 
    {
        ListNode* fast = head, *slow = head;
        if(!head) return false;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) 
            {
                return true;
            }
        }
        return false;
    }

    //1222 leetcode 142
    ListNode *detectCycle(ListNode *head) {
        
        ListNode* fast = head, *slow = head;
        if(!head || (head != NULL && head->next == NULL)) return NULL; //单个节点需要考虑

        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) 
            {
                break;
            }
        }
        
        if(fast == slow)
        {
            ListNode* newHead = head;
            while(newHead != fast)
            {
                newHead = newHead->next; //第二次跑要一个指针从头开始，这个是有原理的，先记一下
                fast = fast->next;
            }
            return newHead;
        }

        return NULL;
    }


    //12223 leetcode 138
    Node* copyRandomList(Node* head) {
        if(head == NULL)    return NULL;

        vector<int> nums;
        map<int,Node*> mp;
        map<Node*,int> oldList;

        //尾插法建立新的链表
        Node* dummy = new Node(0);
        Node* pre = dummy;
        Node* cur = NULL;
        int i = 0;

        Node* head1 = head;
        Node* head2 = head;
        while (head1)
        {
            Node* tmp = new Node(head1->val);
            oldList[head1] = i;
            mp[i] = tmp;
            i++;

            pre->next = tmp;
            tmp->next = cur;
            pre = tmp;
            head1 = head1->next;
        }
        
        while (head2)
        {
            Node* tmp = head2->random;
            if(tmp == NULL) nums.push_back(-1);
            else
            {
                nums.push_back(oldList[tmp]);
            }
            head2 = head2->next;
        }
        

        Node* newHead = dummy->next;
        i = 0;
        while (newHead)
        {
            if(nums[i] == -1) newHead->random = NULL;
            else
            {
                newHead->random = mp[nums[i]];
            }
            newHead = newHead->next;   
            i++;     
        }
        
        return dummy->next;

    }

    //1223 leetcode 137
    int singleNumber(vector<int>& nums) {
        //已完成
    }
    
    //1223 leetcode 136已完成

    //1223 leetcode 135
    int candy(vector<int>& ratings) {
        if(ratings.size() == 0) return 0;
        vector<int> nums(ratings.size(),0);
        nums[0] = 1;

        //先从前往后 再从后往前

        //从前往后
        for(int i =1;i<ratings.size();i++)
        {
            if(ratings[i] > ratings[i-1]) nums[i] = nums[i-1] + 1;
            else nums[i] = 1;
        }
        //再从后往前
        for(int i = ratings.size()-1;i>=1;i--)
        {
            if(ratings[i-1] > ratings[i] && nums[i-1] <= nums[i]) nums[i-1] = nums[i]+1;
        }

        int res = 0;
        for(auto num : nums)
        {
            res +=num;
        }
        return res;
    }

    //1223 leetcode 134 加油站 
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int len = gas.size();//一共有多少个加油点
        if(len == 0 || cost.size() == 0) return -1;
        int count = 0;
        int pos = 0;
        int sum = 0;
        for(int i =0;i<len;i++)
        {
            sum = 0;
            count = 0;
            for(int j =i;j<len;j++)
            {
                count++;
                sum = sum + gas[j];
                sum = sum - cost[j];
                if(count == len && sum >= 0) return i;
                if(sum < 0)  break;
                if(j == len-1) j = -1; //下一次从0开始
            }
            if(sum < 0) continue;
        }
        return -1;
    }


    //1224 leetcode 133
    NodeGraph* cloneGraph(NodeGraph* node) {
        // 这个不会 参考自 https://blog.csdn.net/Bendaai/article/details/80985328?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control
        //后续学习下bfs和dfs专题
        map<int,NodeGraph*> mp;
        NodeGraph* p = new NodeGraph(node->val);
        mp[node->val] = p;
        for(auto & x: node->neighbors)
        {
            if(mp.find(x->val) == mp.end()) p->neighbors.push_back(cloneGraph(x));
            else p->neighbors.push_back(mp[x->val]);
        }
        return p;

    }

    void travelGraphWithoutDirection(NodeGraph* node)
    {
        /*
        NodeGraph* node1 = new NodeGraph(1);
        NodeGraph* node2 = new NodeGraph(2);
        NodeGraph* node3 = new NodeGraph(3);
        NodeGraph* node4 = new NodeGraph(4);

        node1->neighbors.push_back(node2);
        node1->neighbors.push_back(node4);
        node2->neighbors.push_back(node1);
        node2->neighbors.push_back(node3);
        node3->neighbors.push_back(node2);
        node3->neighbors.push_back(node4);
        node4->neighbors.push_back(node1);
        node4->neighbors.push_back(node3);
        NodeGraph* root = node1;
        */
    }

    //1224 leetcode 131
    vector<vector<string>> res_131;
    vector<string> tmp_131;

    vector<vector<string>> partition(string s) {
        if(s.size() == 0) return res_131;
        helper(s,0,s.size()-1);
        return res_131;
    }

    void helper(string s,int begin,int end)
    {
        if(begin > end) 
        {
            res_131.push_back(tmp_131);
            return;
        }
        for(int i =1;i<= end - begin + 1; i++)
        {
            
            if(isPalind(s.substr(begin,i)))
            {
                cout<<"This s.sub is "<<s.substr(begin,i)<<endl;
                tmp_131.push_back(s.substr(begin,i));
                helper(s,begin+i,end);
                tmp_131.pop_back(); //删除后用于下一次的循环
            }
        }
    }

    bool isPalind(string str)
    {
        if(str.size() == 1) return true;
        string str1 = str;
        std::reverse(str.begin(),str.end());
        return str == str1 ? true : false;
    }

    //1228 leetcode 130
    /*
        vector<char> v1 = {'X','X','X','X'};
        vector<char> v2 = {'X','O','O','X'};
        vector<char> v3 = {'X','X','O','X'};
        vector<char> v4 = {'X','O','X','X'};
        vector<vector<char>> areas;
        areas.push_back(v1);
        areas.push_back(v2);
        areas.push_back(v3);
        areas.push_back(v4);
        solution.solve(areas);
        cout<<"Final res is : "<<endl;
        for(int i=0;i<areas.size();i++)
        {
            for_each(areas[i].begin(),areas[i].end(),[](auto& x){cout<<x<<" ";});
            cout<<endl;
        }
    */
    void solve(vector<vector<char>>& board) {
        if(board.size() == 0) return;
        int row = 0, column = 0;
        row = board.size();
        column = board[0].size();
        for(int i=0;i<row;i++)
        {
            helperSolve(board,i,0);
            helperSolve(board,i,column-1);
        }

        for(int i=1;i<column-1;i++)
        {
            helperSolve(board,0,i);
            helperSolve(board,row-1,i);
        }

        cout<<"In function "<<endl;
        for(int i=0;i<board.size();i++)
        {
            for_each(board[i].begin(),board[i].end(),[](auto& x){cout<<x<<" ";});
            cout<<endl;
        }

        for(int i=0;i<row;i++)
        {
            for(int j=0;j<column;j++)
            {
                if(board[i][j] == 'A') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }


    }
    void helperSolve(vector<vector<char>>& board,int x,int y)
    {
        if(x < 0 || x >= board.size() || y >= board[0].size() || y < 0 || board[x][y] != 'O')  return;
        board[x][y] = 'A';
        helperSolve(board,x+1,y);
        helperSolve(board,x-1,y);
        helperSolve(board,x,y+1);
        helperSolve(board,x,y-1);
    }

    //1228 leetcode 129
    /*
        TreeNode* l4 = new TreeNode(4);
        TreeNode* l5 = new TreeNode(5);
        TreeNode* l6 = new TreeNode(6);
        TreeNode* l7 = new TreeNode(7);
        TreeNode* l2 = new TreeNode(2,l4,l5);
        TreeNode* l3 = new TreeNode(3,l6,l7);
        TreeNode* l1 = new TreeNode(1,l2,l3);
        TreeNode* root = l1;
        solution.travelTreeNodeByFloor(root);
        
        cout<<"res is "<<endl;
        vector<vector<int>> res = solution.getAllTreeNodePath(root);
        for(int i=0;i<res.size();i++)
        {
            for_each(res[i].begin(),res[i].end(),[](auto& x){cout<<x<<" ";});
            cout<<endl;
        }
    */
    int sumNumbers(TreeNode* root) {
        if(root == NULL) return 0;
        vector<vector<int>> res;
        vector<int> tmp;
        helperGetAllPath(root,res,tmp);
        int sum = 0;
        for(int i =0;i<res.size();i++)
        {
            int curSum = 0;
            for(int j =0;j<res[i].size();j++)
            {
                curSum = curSum * 10 + res[i][j];
            }
            sum = sum + curSum;
        }
        return sum;
    }

    //1228 tmp 求二叉树根节点到叶子结点所有的路径
    vector<vector<int>> getAllTreeNodePath(TreeNode* root)
    {
        vector<vector<int>> res;
        if(root == NULL) return res;
        vector<int> tmp;
        helperGetAllPath(root,res,tmp);
        return res;
    }

    void helperGetAllPath(TreeNode* root, vector<vector<int>>& res,vector<int> tmp)
    {
        if(root == NULL) return;
        if(root != NULL) tmp.push_back(root->val);
        if(root != NULL && root->left == NULL && root->right == NULL)
        {
            res.push_back(tmp);
        }
        helperGetAllPath(root->left,res,tmp);
        helperGetAllPath(root->right,res,tmp);
    }


    //1228 leetcode 125
    bool isPalindromeNew(string s) {
        if(s.size() == 0) return true;
        string s1;
        for(int i =0;i<s.size();i++)
        {
            if((s[i] >= '0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) 
                s1.push_back(s[i]);
        }
        string s2 = s1;
        std::reverse(s2.begin(),s2.end());
        cout<<"s1 is "<<s1<<" s2 is "<<s2<<endl;
        for(int i=0;i<s1.size();i++)
        {
            if(((s1[i] >= 'a' && s1[i] <= 'z') || (s1[i] >= 'A' && s1[i] <= 'Z')) && (s1[i] - s2[i] != 32) && (s1[i]-s2[i] != -32) && (s1[i] != s2[i]))
            return false;
            if((s1[i] >= '0' && s1[i] <= '9') && (s1[i] != s2[i])) return false;
        }
        //cout<<'A' - 'a'<<endl;
        return true;
    }

  
    //1228 leetcode 128
    int longestConsecutive(vector<int>& nums) {
		if(nums.size() == 0) return 0;

        vector<int> newNums = nums;
        std::sort(newNums.begin(),newNums.end());
		
		vector<int> unSameNums; //防止有重复的值
        int i = 0;
		for(i =0;i<newNums.size();i++)
		{
			while((i+1 < newNums.size()) && (newNums[i] == newNums[i+1]))
			{
				i++;
			}
			unSameNums.push_back(newNums[i]);
		}
		
        int len = unSameNums.size();
        
        int res = 1;
        i = 0;
        while (i < len)
        {
            int tmpCount = 0;
            while ((i+1 < len) && (unSameNums[i] + 1 == unSameNums[i+1]))
            {
                tmpCount++;
                i++;
            }
            res = max(tmpCount+1,res);
            i++;
        }
        

        return res;
    }

    //1229 leetcode 127
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //先不做
    }


    //1229 leetcode 120
    //这个不会 参考自官方题解
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size() == 0) return 0;
        int len = triangle.size();
        vector<vector<int>> dp(len,vector<int>(len,0));
        dp[0][0] = triangle[0][0];
        for(int i=1;i<len;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j == 0)
                {
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                }
                else if(j == i)
                {
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                }
                else
                {
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j];
                }
                
            }
        }
        auto p = min_element(dp[len-1].begin(),dp[len-1].end());
        return *p;
    }


    //1229 leetcode 118
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if(numRows <= 0) return res;
        vector<int> v1 = {1};
        res.push_back(v1);
        if(numRows == 1) return res;
        vector<int> v2 = {1,1};
        res.push_back(v2);
        if(numRows == 2) return res;

        for(int i=2;i<numRows;i++)
        {
            vector<int> tmp(i+1,0);
            for(int j=0;j<=i;j++)
            {
                if(j == 0 || j == i) tmp[j] = 1;
                else
                {
                    tmp[j] = res[i-1][j] + res[i-1][j-1];
                }
            }
            res.push_back(tmp);
        }
        return res;
    }

    //1229 leetcode 119
    vector<int> getRow(int rowIndex) {
        //参考118 已完成
    }

    //1229 leetcode 112
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) return false;
        vector<vector<int>> allPathRes;
        vector<int> tmp;
        helperGetAllPathSum(root,allPathRes,tmp);
        for(int i =0;i<allPathRes.size();i++)
        {
            int curSum = 0;
            for(int j=0;j<allPathRes[i].size();j++)
            {
                curSum +=allPathRes[i][j];
            }
            if(curSum == sum) 
            {
                return true;
            }
        }
        return false;
    }

    //1229 leetcode 113
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        vector<vector<int>> allPathRes;
        vector<int> tmp;
        helperGetAllPathSum(root,allPathRes,tmp);
        for(int i =0;i<allPathRes.size();i++)
        {
            int curSum = 0;
            for(int j=0;j<allPathRes[i].size();j++)
            {
                curSum +=allPathRes[i][j];
            }
            if(curSum == sum) res.push_back(allPathRes[i]);
        }
        return res;
    }

    void helperGetAllPathSum(TreeNode* root,vector<vector<int>>& res,vector<int> cur)
    {
        if(root == NULL) return;
        cur.push_back(root->val);
        if(root != NULL && root->left == NULL && root->right == NULL)
        {
            res.push_back(cur);
        }
        helperGetAllPathSum(root->left,res,cur);
        helperGetAllPathSum(root->right,res,cur);
    }

    //1229 leetcode 114
    void flatten(TreeNode* root) {
        if(root == NULL)    return;
        vector<TreeNode*> preOrderRes = preOrderTreeNode(root);
        for(int i=0;i<preOrderRes.size();i++)
        {
            cout<<preOrderRes[i]->val<<" ";
        }
        cout<<endl;
        
        for(int i=0;i<preOrderRes.size()-1;i++)
        {
            preOrderRes[i]->left = NULL;
            preOrderRes[i]->right = preOrderRes[i+1];
        }
        preOrderRes[preOrderRes.size()-1]->left = NULL;
        preOrderRes[preOrderRes.size()-1]->right = NULL;
        cout<<"cur Finish"<<endl;

    }

    vector<TreeNode*> preOrderTreeNode(TreeNode* root)
    {
        vector<TreeNode*> res;
        if(root == NULL) return res;
        res.push_back(root);
        vector<TreeNode*> leftNodes = preOrderTreeNode(root->left);
        vector<TreeNode*> rightNodes = preOrderTreeNode(root->right);
        for(int i=0;i<leftNodes.size();i++)
        {
            res.push_back(leftNodes[i]);
        }
        for(int i =0;i<rightNodes.size();i++)
        {
            res.push_back(rightNodes[i]);
        }
        return res;

    }

    //1229 leetcode 115
    int numDistinct(string s, string t) {
        //这个不会
        if(s.size() == 0 || t.size() == 0) return 0;
        int tLen = t.size(), sLen = s.size();

        //int型会溢出 需要使用long long
        vector<vector<long long>> dp(tLen+1, vector<long long>(sLen+1,0)); //dp[i][j] 代表 T 前 i 字符串可以由 S j 字符串组成最多个数.
        for(int i=0;i<=sLen;i++) 
        {
            dp[0][i] = 1;
        }

        //string s = "babgbag";
        //string t = "bag";
        for(int i=1;i<=tLen;i++)
        {
            for(int j=1;j<=sLen;j++)
            {
                if(s[j-1] == t[i-1]) dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                else dp[i][j] = dp[i][j-1];
            }
        }

        cout<<"dp raise : "<<endl;
        for(int i =0;i<dp.size();i++)
        {
            for_each(dp[i].begin(),dp[i].end(),[](auto& x){cout<<x<<" ";});
            cout<<endl;
        }

        return dp[tLen][sLen];
    }

    //1229 leetcode 116
    NodeTwo* connect(NodeTwo* root)
    {
        if(root == NULL) return NULL;
        queue<NodeTwo*> q;
        vector<vector<NodeTwo*>> allFloorNodes;
        q.push(root);
        while (!q.empty())
        {
            int qSize = q.size();
            int count = 0;
            vector<NodeTwo*> cur;
            while (count < qSize)
            {
                NodeTwo* tmp = q.front();
                q.pop();
                count++;
                cur.push_back(tmp);
                if(tmp->left != NULL) q.push(tmp->left);
                if(tmp->right != NULL) q.push(tmp->right);
            }
            allFloorNodes.push_back(cur);
        }
        for(int i=0;i<allFloorNodes.size();i++)
        {
            for(int j=0;j<allFloorNodes[i].size()-1;j++)
            {
                allFloorNodes[i][j]->next = allFloorNodes[i][j+1];
            }
            allFloorNodes[i][allFloorNodes[i].size()-1]->next = NULL;
        }
        return root;
    }

    //1230 leet117 
    Node* connect_Leetcode117(Node* root)
    {
        //已完成
    }

    //1230 leetcode 111
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        if(root->left == NULL) return 1 + minDepth(root->right);
        if(root->right == NULL) return 1 + minDepth(root->left);
        return 1 + min(minDepth(root->right),minDepth(root->left));
    }

    //1229 leetcode 104
    int treeNodeDepth(TreeNode* root)
    {
        if(root == NULL) return 0;
        if(root->left == NULL && root->right == NULL) return 1;
        return 1 + max(treeNodeDepth(root->left),treeNodeDepth(root->right));
    }

    //1230 leetcode 109 有序链表转换二叉搜索树
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == NULL)    return NULL;
        vector<int> nums;
        while (head)
        {
            nums.push_back(head->val);
            head = head->next;
        }
        TreeNode* newRoot = helpRebuildTreeNodeByListNodes(nums,0,nums.size()-1);
        return newRoot;

    }

    TreeNode* helpRebuildTreeNodeByListNodes(vector<int>& nums,int begin,int end)
    {
        if(begin > end) return NULL;
        int mid = (begin + end)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helpRebuildTreeNodeByListNodes(nums,begin,mid-1);
        root->right = helpRebuildTreeNodeByListNodes(nums,mid+1,end);
        return root;
    }

    //1230 leetcode 107
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int qSize = q.size();
            int count = 0;
            vector<int> cur;
            while (count < qSize)
            {
                TreeNode* tmp = q.front();
                q.pop();
                count++;
                cur.push_back(tmp->val);
                if(tmp->left != NULL) q.push(tmp->left);
                if(tmp->right != NULL) q.push(tmp->right);
            }
            res.push_back(cur);
        }
        std::reverse(res.begin(),res.end());
        return res;
    }

    //1230 leetcode 106
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //这个不会
    }

    TreeNode* rebuildTreeByMidAndPost(vector<int>& inorder, vector<int>& postorder,int midBegin,int midEnd,int postBegin,int postEnd)
    {

    }

    //210104 leetcode 105
    TreeNode* buildTreeByPreAndMid(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0) return NULL;
        int len = preorder.size();
        TreeNode* res = helpRebuild(0,len-1,0,len-1,preorder,inorder);
        return res;
    }

    TreeNode* helpRebuild(int leftPre,int rightPre,int leftIn,int rightIn,vector<int>& pre, vector<int>& in)
    {
        if(leftPre > rightPre || leftIn > rightIn) return NULL;
        TreeNode* root = new TreeNode(pre[leftPre]);
        int rootIn = leftIn;
        while(rootIn <= rightIn && in[rootIn] != pre[leftPre]) rootIn++;
        int left = rootIn - leftIn;
        root->left = helpRebuild(leftPre+1,leftPre+3,leftIn,rootIn-1,pre,in);
        root->right = helpRebuild(leftPre+1+left,rightPre,rootIn+1,rightIn,pre,in);
        return root;
    }

    //21_0104 leetcode 67
    string addBinary(string a, string b) {
        if(a.size() == 0 && b.size() == 0) return "";
        if(a.size() == 0) return b;
        if(b.size() == 0) return a;
        std::reverse(a.begin(),a.end());
        std::reverse(b.begin(),b.end());
        long long num1 = (long long)atoi(a.c_str());
        long long num2 = (long long)atoi(b.c_str());
        int lenA = a.size();
        int lenB = b.size();
        int i = 0;
        int cur = 0;//这个表示进位
        vector<int> nums;

        for(i=0;i<lenA || i <lenB;i++)
        {
            if(i >= lenA && i < lenB)
            {
                int val = 0;
                int tmp = cur + (b[i] - '0');
                if(tmp >= 2)
                {
                    val = tmp-2;
                    tmp = 1;
                }
                else
                {
                    val = tmp;
                    cur = 0;
                } 
                nums.push_back(val);
            }
            else if (i < lenA && i >= lenB)
            {
                int val = 0;
                int tmp = cur + (a[i] - '0');
                if(tmp >= 2)
                {
                    val = tmp-2;
                    cur = 1;
                }
                else
                {
                    val = tmp;
                    cur = 0;
                }
                nums.push_back(val);
            }
            else
            {
                int val = 0;
                int tmp = cur + (a[i] - '0') + (b[i] - '0');
                if(tmp >= 2)
                {
                    val = tmp-2;
                    cur = 1;
                }
                else
                {
                    val = tmp;
                    cur = 0;
                }
                nums.push_back(val);
                
            }

        }
        if(cur == 1) nums.push_back(cur); //最后一位进位
        for_each(nums.begin(),nums.end(),[](auto& x){cout<<x<<" ";});
        cout<<endl;
        string res = "";
        for(i=nums.size()-1;i>=0;i--)
        {
            res = res + to_string(nums[i]);
        }

        return res;
    }

    //21_0105 leetcode 98
    bool isValidBST(TreeNode* root) {
        //已完成
        //判断是否是二叉树 只要判断中序遍历是否是升序即可
        if(root == NULL) return true;
        vector<int> midTravelRes = getMidTravelTreeNode(root);
        for_each(midTravelRes.begin(),midTravelRes.end(),[](auto& x){cout<<x<<" ";});
        cout<<endl;
        for(int i=0;i<midTravelRes.size()-1;i++)
        {
            if(midTravelRes[i] >= midTravelRes[i+1]) return false;
        }
        return true;
    }

    vector<int> getMidTravelTreeNode(TreeNode* root)
    {
        vector<int> res;
        if(root == NULL) return res;
        vector<int> leftRes;
        vector<int> rightRes;
        leftRes = getMidTravelTreeNode(root->left);
        rightRes = getMidTravelTreeNode(root->right);

        for(int i=0;i<leftRes.size();i++) res.push_back(leftRes[i]);
        res.push_back(root->val);
        for(int i=0;i<rightRes.size();i++) res.push_back(rightRes[i]);
        
        return res;
    }

    //21_0105 leetcode 99
    void recoverTree(TreeNode* root) {
        if(root == NULL) return;
        vector<TreeNode*> midTravelRes = getMidTravelTreeNodes(root);
        TreeNode* firstNode = NULL, *secondNode = NULL;
        vector<int> actualNums;

        for(int i=0;i<midTravelRes.size();i++)
        {
            cout<<midTravelRes[i]->val<<" ";
            actualNums.push_back(midTravelRes[i]->val);
        }
        cout<<endl;

        std::sort(actualNums.begin(),actualNums.end());
        for_each(actualNums.begin(),actualNums.end(),[](auto& x){cout<<x<<" ";});
        cout<<endl;
        for(int i=0;i<midTravelRes.size();i++)
        {
            if(midTravelRes[i]->val != actualNums[i]) 
            {
                if(firstNode == NULL) firstNode = midTravelRes[i];
                else 
                {
                    secondNode = midTravelRes[i];
                    break;
                }
            }
        }

        if(firstNode && secondNode)
        {
            int tmp = firstNode->val;
            firstNode->val = secondNode->val;
            secondNode->val = tmp;
        }
        
    }

    vector<TreeNode*> getMidTravelTreeNodes(TreeNode* root)
    {
        vector<TreeNode*> res;
        if(root == NULL) return res;
        vector<TreeNode*> leftRes;
        vector<TreeNode*> rightRes;
        leftRes = getMidTravelTreeNodes(root->left);
        rightRes = getMidTravelTreeNodes(root->right);

        for(int i=0;i<leftRes.size();i++) res.push_back(leftRes[i]);
        res.push_back(root);
        for(int i=0;i<rightRes.size();i++) res.push_back(rightRes[i]);
        
        return res;
    }


    //21_0105 leetcode 96
    int numTrees(int n) {
        if(n == 0 || n == 1) return 1;
        if(n == 2) return 2;

        int res = 0;
        for(int i=1;i<=n;i++)
        {
            if(i == 1 || i == n) res = res + numTrees(n-1);
            else
            {
                int before = i-1;
                int after = n-i;
                res = res + (numTrees(before) * numTrees(after));
            }
            
        }
        return res;
    }

    //21_0105 leetcode 95
    vector<TreeNode*> generateTrees(int n) {
        //已完成
    }

    //leetcode 93 评论区参考答案
    vector<string> restoreString2(string s) {
        string temp;
        dfs2(s,temp,0);
        return res_Leetcode93;
    }
    
    void dfs2(string s, string& temp, int word_num){
        cout<<"cur begin s si "<<s<<endl;
        if(word_num == 4){
            cout<<"dfs2 s.size is "<<s.size()<<endl;
            if(s.empty()) res_Leetcode93.push_back(temp);
            return;
        }
        else{
            if(word_num > 0) temp += '.';
            for(int i = 1; i <= 3 && i <= s.length(); ++i){
                if(valid2(s.substr(0,i))){
                    cout<<"restore2 s.substr is "<<s.substr(0,i)<<" temp is "<<temp<<endl;
                    temp += s.substr(0,i);
                    dfs2(s.substr(i,s.length()-i),temp,word_num+1);
                    cout<<"erase tmp.lengh is "<<temp.substr(temp.length()-i,i)<<endl;
                    temp.erase(temp.length()-i,i);
                }
            }
            temp.pop_back();
        }
    }
    
    bool valid2(const string& s){
        if(s.empty() || (s[0] == '0' && s.size()>1) ) return false;
        int val = stoi(s);
        if(val >= 0 && val <= 255) return true;
        return false;
    }

    //21_0106 leetcode 93
    vector<string> res_Leetcode93;
    vector<string> restoreIpAddresses(string s) {
        // 这个不会，参考自leetcode 评论区 很有意思的一道题
        if(s.size() < 4 || s.size() >12) return res_Leetcode93;
        string cur = "";
        helpDfsRestoreIpAddress(s,cur,0);
        return res_Leetcode93;
    }

    void helpDfsRestoreIpAddress(string s,string& tmp,int count)
    {
        cout<<"begin s si "<<s<<endl;
        if(count == 4)
        {
            if(s.empty())
            {
                res_Leetcode93.push_back(tmp);
                return;
            }
        }
        else
        {
            if(count > 0) tmp = tmp + ".";
            for(int i=1;i<=3 && i<=s.size();i++)
            {
                if(validString(s.substr(0,i)))
                {
                    cout<<"This substri is "<<s.substr(0,i)<<" This tmp is "<<tmp<<endl;
                    tmp = tmp + s.substr(0,i);
                    helpDfsRestoreIpAddress(s.substr(i,s.size()-i),tmp,count+1);
                    cout<<"tmp erase is "<<tmp.substr(tmp.size()-1,i)<<endl;
                    tmp.erase(tmp.size()-i,i);  //这个是做什么的
                }
            }
            cout<<"before pop_back tmp is "<<tmp<<endl;
            tmp.pop_back(); //看下这个啥意思
        }
        
    }

    bool validString(string str)
    {
        if(str.size() > 3 || str.size() == 0) return false;
        if(str[0] == '0' && str.size()>1) return false;
        int res = atoi(str.c_str());
        if(res >=0 && res <= 255) return true;
        return false;
    }

    //21_0106 临时反转链表
    
    //第一种 使用额外空间 直接头插法 尾插法和原来一样，需要使用头插法就是正好是反转的
    ListNode* reverseList1(ListNode* head)
    {
        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        ListNode* cur = NULL;
        while (head)
        {
            ListNode* tmp = new ListNode(head->val);
            pre->next = tmp;
            tmp->next = cur;
            cur = tmp;

            head = head->next;
        }
        return dummy->next;
    }

    //第二种 不使用额外空间，直接一次遍历直接反转，改变原来的结构
    ListNode* reverseList2(ListNode* head)
    {

        /*
        //非递归做法
        if(head == NULL || head->next == NULL) return head;
        ListNode* pre = head;
        ListNode* cur = NULL;
        while (head)
        {
            ListNode* nextNode = head->next;
            head->next = cur;
            cur = head;
            head = nextNode;
        }
        return cur;
        */

        //递归解法
        if(head == NULL || head->next == NULL) return head;    

        ListNode* nextNode = head->next;
        ListNode* newListHead = reverseList2(nextNode);
        ListNode* head2 = head->next;
        head2->next = head;
        head->next = NULL;
        return newListHead;

    }

    //21_0106 leetcode 92
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(head == NULL || m <= 0 || n <= 0 || head->next == NULL) return head;
        //一趟遍历的已经提交通过，目前来试下这个不限制一趟的
        int count  = 0;
        ListNode* head1 = head;
        ListNode* newTail = NULL, *newHead = NULL;
        ListNode* pre = new ListNode(0);
        pre->next = head;
        ListNode* lastNode = NULL;
        while (head1)
        {
            count++;
            if(count < m) pre = pre->next;
            else if(count == m) newTail = head1;
            else if(count == n) 
            {
                newHead = head1;
                lastNode = head1->next;
                break;
            }
            head1 = head1->next;
        }
        newHead->next = NULL;
        ListNode* reverseNewHead = reverseList2(newTail);
        pre->next = reverseNewHead;
        newTail->next = lastNode;
        return head;
    }

    //21_0106 leetcode 91
    int numDecodings(string s) {
        // 这个不会，参考https://leetcode-cn.com/problems/decode-ways/comments/ 搜索"ChengMing"
        int cnt = 0;
        if(s.size() == 0 || (s.size() >= 1 && s[0] == '0')) return 0;
        if(s.size() == 1) return 1;
        vector<int> dp(s.size()+1,0);
        dp[0] = 1; //"12321"
        for(int i=0;i<s.size();i++)
        {
            dp[i+1] = (s[i] == '0' ? 0 : dp[i]);
            if(i > 0 && (s[i-1] == '1' || (s[i-1] == '2' && s[i] <= '6')))
            {
                dp[i+1] += dp[i-1];
            }
        }
        return dp.back();
    }
    
    //21_0107 leetcode 78
    vector<vector<int>> res_Leetcode78;
    vector<vector<int>> subsets(vector<int>& nums) {
        res_Leetcode78.push_back({});
        if(nums.size() == 0) return res_Leetcode78;
        int len = nums.size();
        vector<int> tmp;
        dfsHelpSubsets(nums,0,tmp,len);
        return res_Leetcode78;
    }

    void dfsHelpSubsets(vector<int>& nums,int index,vector<int> tmp,int len)
    {
        if(len == index) return;
        tmp.push_back(nums[index]);
        res_Leetcode78.push_back(tmp);
        dfsHelpSubsets(nums,index+1,tmp,len); //包含当前元素
        tmp.pop_back();
        dfsHelpSubsets(nums,index+1,tmp,len);
    }

    //21_0107 leetcode 90
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res_Leetcode78.push_back({});
        if(nums.size() == 0) return res_Leetcode78;
        int len = nums.size();
        vector<int> tmp;
        dfsHelpSubsets_new(nums,0,tmp,len);
        return res_Leetcode78;
    }

    void dfsHelpSubsets_new(vector<int>& nums,int index,vector<int> tmp,int len)
    {
        bool flag = false;
        if(len == index) return;
        tmp.push_back(nums[index]);

        for(int i =0;i<res_Leetcode78.size();i++)
        {
            int cnt = 0;
            if(tmp.size() != res_Leetcode78[i].size()) continue;
            vector<int> v1 = tmp;
            std::sort(v1.begin(),v1.end());
            vector<int> v2 = res_Leetcode78[i];
            std::sort(v2.begin(),v2.end());
            for(int j=0;j<v2.size();j++)
            {
                if(v1[j] != v2[j]) break;
                cnt++;    
            }
            if(cnt == tmp.size())
            {
                flag = true;
                break;
            }
        }
        if(true != flag) res_Leetcode78.push_back(tmp);

        dfsHelpSubsets_new(nums,index+1,tmp,len); //包含当前元素
        tmp.pop_back();
        dfsHelpSubsets_new(nums,index+1,tmp,len);
    }

    //21_0107 leetcode 89
    vector<int> grayCode(int n) {
        //已完成
    }

    //21_0107 leetcode 87  //先不做 不会这个
    bool isScramble(string s1, string s2) {
        if(s1.size() == 0 && s2.size() == 0) return true;
        if(s1.size() == 0 || s2.size() == 0 || s1.size() != s2.size()) return false;
        
    }

    //21_0107 leetcode 86
    /*
        ListNode* l6 = new ListNode(2);
        ListNode* l5 = new ListNode(5,l6);
        ListNode* l4 = new ListNode(2,l5);
        ListNode* l3 = new ListNode(3,l4);
        ListNode* l2 = new ListNode(4,l3);
        ListNode* l1 = new ListNode(1,l2);
        ListNode* head = l1;
        solution.travelListNode(head);
        cout<<"after change "<<endl;
        ListNode* res = solution.partition(head,3);
        solution.travelListNode(res);
    */
    ListNode* partition(ListNode* head, int x) {
        if(head == NULL) return NULL;
        vector<int> small;
        vector<int> big;
        ListNode* head1 = head;
        while (head1)
        {
            if(head1->val < x) small.push_back(head1->val);
            else big.push_back(head1->val);
            head1 = head1->next;
        }
        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        ListNode* cur = NULL;
        vector<int> nums;
        for(int i=0;i<small.size();i++) nums.push_back(small[i]);
        for(int i=0;i<big.size();i++) nums.push_back(big[i]);
        for(int i=0;i<nums.size();i++)
        {
            ListNode* tmp = new ListNode(nums[i]);
            cur = tmp;
            pre->next = cur;
            pre = cur;
            cur = NULL;
        }
        head = dummy->next;
        return head;

    }

    //21_0108 leetcode 85
    /*
        vector<char> v1 = {'1','0','1','0','0'};
        vector<char> v2 = {'1','0','1','1','1'};
        vector<char> v3 = {'1','1','1','1','1'};
        vector<char> v4 = {'1','0','0','1','0'};
        vector<vector<char>> matrix;
        matrix.push_back(v1);
        matrix.push_back(v2);
        matrix.push_back(v3);
        matrix.push_back(v4);
        int res = solution.maximalRectangle(matrix);
        //cout<<"res is "<<res<<endl;
    */
    int maximalRectangle(vector<vector<char>>& matrix) {
        //21_0108 不会 根据提示可以每一层分别转换为柱状图，然后转换为第84题的解法
        //参考自 https://leetcode-cn.com/problems/maximal-rectangle/comments/  搜索"追梦人"
        if(matrix.size() == 0) return 0;
        vector<vector<int>> areas(matrix.size(),vector<int>(matrix[0].size(),0));
        int res = 0;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[i].size();j++)
            {
                if(i == 0)
                {
                    if(matrix[i][j] == '1') areas[0][j] = 1;
                    else areas[0][j] = 0;
                }
                else
                {
                    if(matrix[i][j] == '0') areas[i][j] = 0;
                    else areas[i][j] = areas[i-1][j] + 1;
                }
            }
            int tmpRes = getCurMaxArea(areas[i]);
            res = max(res,tmpRes);
        }
        return res;
    } 

    //第84道题目算法
    int getCurMaxArea(vector<int>& nums)
    {
        if(nums.size() == 0) return 0;
        int maxArea = 0;
        int len = nums.size();
        for(int i = 0;i<len;i++)
        {
            if(len * nums[i] <= maxArea) continue;
            int left = i-1, right = i+1;
            while(left >= 0 && nums[left] >= nums[i]) left--;
            while(right < len && nums[right] >= nums[i]) right++;
            maxArea = max(maxArea,(right - left - 1) * nums[i]);
        }
        return maxArea;
    }

    //21_0108 leetcode 84
    int  largestRectangleArea(vector<int>& heights) {
        if(heights.size() == 0) return 0;
        //简单暴力法求解
        int res = 0;
        int len = heights.size();
        for(int i=0;i<heights.size();i++)
        {
            if(len * heights[i] <= res) continue;
            int left = i-1, right = i+1;
            while (left >= 0 && heights[left] >= heights[i]) left--;
            while (right < len && heights[right] >= heights[i]) right++;
            res = max(res,(right - left - 1) * heights[i]);
        }
        return res;
    }

    //21_0108 leetcode 82
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL || head->next == NULL)  return head;
        ListNode* head1 = head;
        vector<int> nums;
        vector<int> simplyNums;
        while(head1)
        {
            nums.push_back(head1->val);
            head1 = head1->next;
        }
        for(int i =0;i<nums.size()-1;i++)
        {
            int j = i;
            if(nums[j] != nums[j+1]) simplyNums.push_back(nums[j]);
            else
            {
                while(j < nums.size()-1 && nums[j] == nums[j+1]) j++;
                i = j;
            }
        }
        if(nums[nums.size()-1] != nums[nums.size()-2]) simplyNums.push_back(nums[nums.size()-1]);
        for_each(simplyNums.begin(),simplyNums.end(),[](auto& x){cout<<x<<" ";});
        cout<<endl;
        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        ListNode* cur = NULL;
        for(int i=0;i<simplyNums.size();i++)
        {
            ListNode* tmp = new ListNode(simplyNums[i]);
            cur = tmp;
            pre->next = cur;
            pre = cur;
            cur = NULL;
        }
        head = dummy->next;
        return dummy->next;
    }








};




int main()
{

    Solution solution;
    ListNode* l7 = new ListNode(5);
    ListNode* l6 = new ListNode(4,l7);
    ListNode* l5 = new ListNode(4,l6);
    ListNode* l4 = new ListNode(3,l5);
    ListNode* l3 = new ListNode(3,l4);
    ListNode* l2 = new ListNode(2,l3);
    ListNode* l1 = new ListNode(1,l2);
    ListNode* head = l1;
    solution.travelListNode(head);
    cout<<"after simplty"<<endl;





    time_t now_time = time(NULL);
    tm* thisLocalTime = localtime(&now_time);
    cout<<endl;
    cout<<asctime(thisLocalTime)<<endl;

    
    system("pause");
    return 0;
}