#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; }