网站正在维护中 模板怎么在建设厅网站报名

网站正在维护中 模板,怎么在建设厅网站报名,校园网站建设必要性,关于公示网站建设的计划书四十一#xff1a;买卖股票的最佳时期有点像打家劫舍#xff0c;可以分成四个状态#xff0c;一个是持有股票#xff0c;一个是未持有股票但可购买#xff0c;一个是冷静期#xff0c;一个是卖出股票的状态。还有一个是状态转移#xff0c;也就是我就只有两个状态一个是…四十一买卖股票的最佳时期有点像打家劫舍可以分成四个状态一个是持有股票一个是未持有股票但可购买一个是冷静期一个是卖出股票的状态。还有一个是状态转移也就是我就只有两个状态一个是持有股票状态一个是不持有股票状态持有股票买的时候需要从不持有股票的前2天转移就好了class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); if(n 1) { return 0; } std::vectorint has(n); std::vectorint un_has(n); has[0] -prices[0]; has[1] std::max(has[0],-prices[1]); un_has[1] std::max(has[0]prices[1],un_has[0]); for(int i 2 ; i n ; i) { has[i] std::max(un_has[i-2]-prices[i],has[i-1]); un_has[i] std::max(un_has[i-1],has[i-1]prices[i]); } return std::max(un_has[n-1],has[n-1]); } };四十二删除无效括号在晚上回去之前再看一次本质上就是先计算出来左括号数量右括号数量之后挨个删class Solution { private: std::vectorstd::string ret; bool isvaild(std::string s) { int lcnt 0; for(autoc : s) { if(c () { lcnt; } else if(c )) { --lcnt; if(lcnt 0) { return false; } } } return lcnt 0; } void dfs(std::string s , int start , int lcnt , int rcnt) { if(lcnt 0 rcnt 0) { if(isvaild(s)) { ret.push_back(s); } return ; } int n s.size(); for(int i start ; i n ; i) { if(i ! start s[i] s[i-1]) { continue; } if(lcnt rcnt n - i) { break; } if(lcnt 0 s[i] () { dfs(s.substr(0,i)s.substr(i1),i,lcnt-1,rcnt); } if(rcnt 0 s[i] )) { dfs(s.substr(0,i)s.substr(i1),i,lcnt,rcnt-1); } } } public: vectorstring removeInvalidParentheses(string s) { int lcnt 0 , rcnt 0; for(auto c : s) { if(c () { lcnt; } else if(c )) { if(lcnt 0) { --lcnt; } else { rcnt; } } } dfs(s,0,lcnt,rcnt); return ret; } };四十三最长递增子序列这里用两种方法一种好像的一种不好想的。好像的是直接动态规划记录以当前位置结尾最长的子字符串是多少。不好想的用贪心解二分class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); int max 0; if(n 1) { return n; } std::vectorint dp(n,1); for(int i 0 ; i n ; i) { for(int j 0 ; j i ; j) { if(nums[i] nums[j]) { dp[i] std::max(dp[i],dp[j]1); } } max std::max(dp[i],max); } return max; } };二贪心加二分查找class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); if(n 1) { return n; } int len 1; std::vectorint dp(n1); dp[len] nums[0]; for(int i 1 ; i nums.size() ; i) { if(nums[i] dp[len]) { dp[len] nums[i]; } else { int l 1 , r len , pos 0; while(l r) { int mid l ((r-l)1); if(dp[mid] nums[i]) { pos mid; l mid1; } else { r mid-1; } } dp[pos1] nums[i]; } } return len; } };四十四二叉树的序列化和反序列化。思路就是前序遍历之后反序列化的时候需要有额外的std::string辅助以及不要用ret ret这种会产生大量临时变量的问题。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: void ser_help(TreeNode* root , std::stringret) { if(!root) { retnull,; return; } ret std::to_string(root-val) ,; ser_help(root-left , ret); ser_help(root-right,ret); } // Encodes a tree to a single string. string serialize(TreeNode* root) { if(!root) { return ; } std::string ret; ser_help(root,ret); return ret; } TreeNode* deser_help(std::dequestd::string deq) { if(deq.front() null) { deq.pop_front(); return nullptr; } TreeNode* root new TreeNode(std::stoi(deq.front())); deq.pop_front(); root-left deser_help(deq); root-right deser_help(deq); return root; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if(data.empty()) { return nullptr; } std::dequestd::string deq; std::string tmp; for(int i 0 ; i data.size() ; i) { if(data[i] ,) { deq.push_back(tmp); tmp.clear(); } else { tmp.push_back(data[i]); } } if(tmp.size()) { deq.push_back(tmp); } return deser_help(deq); } }; // Your Codec object will be instantiated and called as such: // Codec ser, deser; // TreeNode* ans deser.deserialize(ser.serialize(root));四十五寻找重复数可以用二分或者快慢指针。这里二分的思想没有想明白所以这里重新说一下。二分的思想是这样的对于任何的i如果是不重复的小于等于i的数一定是i当第一个不等于i的地方就是重复的地方。所以可以二分写而且不需要排序因为mid就是mid数字不会超过n。一二分class Solution { public: int findDuplicate(vectorint nums) { int n nums.size(); int l 0 , r n - 1 , target -1; while(l r) { int mid l ((r-l)1); int cnt 0; for(int i 0 ; i n ; i) { cnt nums[i] mid; } if(cnt mid) { l mid 1; } else { target mid; r mid - 1; } } return target; } };二快慢指针class Solution { public: int findDuplicate(vectorint nums) { int fast 0 , slow 0; while(true) { fast nums[nums[fast]]; slow nums[slow]; if(fast slow) { break; } } fast 0; while(fast ! slow) { fast nums[fast]; slow nums[slow]; } return fast; } };四十六移动零思路就是快慢指针快指针找非零慢指针用于交换知道快指针找完。class Solution { public: void moveZeroes(vectorint nums) { int left 0; for(int i 0 ; i nums.size() ; i) { if(nums[i]) { std::swap(nums[i],nums[left]); } } } };四十七完全平方数暂时就只用动规来做因为另外一个数学方法是特例class Solution { public: int numSquares(int n) { if(n 1) { return n; } std::vectorint dp(n1); for(int i 1 ; i n ; i) { int min INT_MAX; for(int j 1 ; j*j i ; j ) { min std::min(min , dp[i - j*j]); } dp[i] min 1; } return dp[n]; } };四十八会议室二思路就是先把开始时间排序用一个数组记录空房间开始和结束时间每一次都遍历看看是不是有空能用不能用就申请新房间class Solution { public: int minMeetingRooms(vectorvectorint intervals) { std::sort(intervals.begin() , intervals.end() , [](const std::vectorint u ,const std::vectorint v){return u[0] v[0];}); std::vectorint rooms; for(auto interval : intervals) { bool find false; for(auto room : rooms) { if(room interval[0]) { room interval[1]; find true; break; } } if(!find) { rooms.push_back(interval[1]); } } return rooms.size(); } };四十九搜索二维矩阵从右上角开始搜索如果大于当前值就减列小于当前值就加行。class Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { int now_row 0 , now_col matrix[0].size() - 1; while(now_col 0 now_row matrix.size()) { if(matrix[now_row][now_col] target) { return true; } else if(matrix[now_row][now_col] target) { now_row; } else { --now_col; } } return false; } };五十滑动窗口的最大值注意要放入下标(值也能做但是不好)class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); std::vectorint ret; if(n 0) { return ret; } int left 0; std::dequeint deq; for(int i 0 ; i n ; i) { while(deq.size() nums[deq.back()] nums[i]) { deq.pop_back(); } deq.push_back(i); if(i - left 1 k) { if(left deq.front()) { deq.pop_front(); } left; } if(i 1 k) { ret.push_back(nums[deq.front()]); } } return ret; } };五十一括号生成回溯的时候用leftrightleft 0 与 right 0进行剪枝class Solution { public: std::vectorstd::string ret; void find(int left , int right , std::string tmp) { if(left right) { return; } if(left 0 right 0) { ret.push_back(tmp); return; } if(left 0) { tmp.push_back((); find(left-1,right,tmp); tmp.pop_back(); } if(right 0) { tmp.push_back()); find(left,right-1,tmp); tmp.pop_back(); } } vectorstring generateParenthesis(int n) { std::string tmp; find(n,n,tmp); return ret; } };五十二字母异位词分组思路还是哈希思路可以排序可以用std::string(26,0)之后再对应为来处理class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { std::unordered_mapstd::string , std::vectorstd::string count; std::vectorstd::vectorstd::string ret; for(auto str : strs) { std::string s(26,0); for(auto c : str) { s[c-a] 1; } count[s].push_back(str); } for(auto coun : count) { ret.push_back(coun.second); } return ret; } };五十三旋转图像注意旋转顺序四个角动class Solution { public: void rotate(vectorvectorint matrix) { int left 0 , right matrix.size()-1; while(left right) { for(int i 0 ; i right - left ; i) { int tmp matrix[left][lefti]; matrix[left][lefti] matrix[right-i][left]; matrix[right-i][left] matrix[right][right-i]; matrix[right][right-i] matrix[lefti][right]; matrix[lefti][right] tmp; } left; --right; } } };五十四全排列就是回溯通过一个一个比较来看所以时间是O(n*n!);class Solution { public: void find(std::vectorintnums , std::vectorint tmp , std::vectorstd::vectorint ret) { if(nums.size() tmp.size()) { ret.push_back(tmp); return; } for(int i 0 ; i nums.size() ; i) { int j ; for(j 0 ; j tmp.size() ; j) { if(tmp[j] nums[i]) { break; } } if(j tmp.size()) { tmp.push_back(nums[i]); find(nums,tmp,ret); tmp.pop_back(); } } } vectorvectorint permute(vectorint nums) { std::vectorstd::vectorint ret; std::vectorint tmp; find(nums,tmp,ret); return ret; } };五十五接雨水前几天做过思路就是两边往中间走找谁最大的最小谁往后走。class Solution { public: int trap(vectorint height) { int left 0 , right height.size() - 1; int ret 0; int left_max INT_MIN; int right_max INT_MIN; while(left right) { left_max std::max(left_max,height[left]); right_max std::max(right_max , height[right]); if(left_max right_max) { ret left_max - height[left]; } else { ret right_max - height[right--]; } } return ret; } };五十六组合总和这个题有一个问题就是剪枝问题因为如果每次都从0开始遍历223和2,3,2以及3,2,2会重复所以剪枝就是减掉当前这个数字之前的比如2就是下一次可以选2,3的话下一次只能从三开始了就是需要传递iclass Solution { public: void find(std::vectorintcandidates , int target , std::vectorint tmp,std::vectorstd::vectorintret , int curr) { if(target 0) { ret.push_back(tmp); return; } if(target 0) { return ; } for(int i curr ; i candidates.size() ; i) { if(candidates[i] target) { tmp.push_back(candidates[i]); find(candidates,target-candidates[i],tmp,ret,i); tmp.pop_back(); } } } vectorvectorint combinationSum(vectorint candidates, int target) { std::vectorstd::vectorint ret; std::vectorint tmp; find(candidates,target,tmp,ret,0); return ret; } };五十七二叉树直径记住计算一个节点的左右节点的时候不要加一/** * Definition for a binary tree node. * 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) {} * }; */ class Solution { public: int max 0; int dfs(TreeNode* root) { if(!root) { return 0; } int left_max dfs(root-left); int right_max dfs(root-right); max std::max(max,left_max right_max); return std::max(left_max,right_max) 1; } int diameterOfBinaryTree(TreeNode* root) { dfs(root); return max; } };五十八在排序数组中查找元素的第一个和最后一个元素注意一下这是二分查找不用递归class Solution { public: int find(std::vectorintnums , int l , int r , int target ,bool is_left) { int pos -1; while(l r) { int mid l ((r-l)1); if(nums[mid] target) { pos mid; if(is_left) { r mid - 1; } else { l mid 1; } } else if(nums[mid] target) { l mid1; } else { r mid - 1; } } return pos; } vectorint searchRange(vectorint nums, int target) { int n nums.size(); if(n 0) { return std::vectorint{-1,-1}; } return std::vectorint{find(nums,0,n-1,target,true),find(nums,0,n-1,target,false)}; } };五十九搜索旋转排序数组需要确定mid和target的位置两个都要确定之后画图来看变化class Solution { public: int search(vectorint nums, int target) { int n nums.size(); if(n 0) { return -1; } int l 0 , r n-1; while(l r) { int mid l ((r - l) 1); if(nums[mid] target) { return mid; } if(nums[0] target) { if(nums[0] nums[mid]) { if(nums[mid] target) { l mid 1; } else { r mid -1; } } else { l mid 1; } } else { if(nums[0] nums[mid]) { if(nums[mid] target) { r mid -1; } else { l mid 1; } } else { r mid - 1; } } } return -1; } };六十最长有效括号这里写两种做法一种是栈的就是底上放一个-1之后计算当前的max与stk.top()的距离第二种是两边遍历就是正遍历一遍负遍历一遍找一下leftright的时候如果right(正),left(负)大于对方了就返回。class Solution { public: int longestValidParentheses(string s) { int n s.size(); if(n 1) { return 0; } int max 0; std::stackint stk; stk.push(-1); for(int i 0 ; i n ; i) { if(s[i] () { stk.push(i); } else if(s[i] )) { stk.pop(); if(stk.size()) { max std::max(max,i-stk.top()); } else { stk.push(i); } } } return max; } };二两次遍历class Solution { public: int longestValidParentheses(string s) { int n s.size(); if(n 1) { return 0; } int left 0 , right 0; int max 0; for(int i 0 ; i n ; i) { if(s[i] () { left; } else if(s[i] )) { right; } if(left right) { max std::max(max,leftright); } else if(right left) { left right 0; } } left right 0; for(int i n - 1 ; i 0 ; --i) { if(s[i] )) { right; } else if(s[i] () { left; } if(left right) { max std::max(rightleft ,max); } else if(left right) { left right 0; } } return max; } };六十一下一个排列这道题好好写一下下一个排列需要从后往前遍历找到第一个后面的数据大于前面的数据用于替换。因为后面的数据是单调递增的(负责早就找到后面的数据比前面的数据大的了)所以比较当前和其后面的一位就是当当前小于后面的一位时就一定可以替换再逆序遍历找到最小的比他大的std::swap。之后剩下的还是逆序排列直接left和right把他整体搬过来class Solution { public: void nextPermutation(vectorint nums) { int n nums.size(); if(n 1) { return ; } int i; for(i n - 1 ; i 0 ; --i) { if(i1 n nums[i] nums[i1]) { for(int j n - 1 ; j i ; --j) { if(nums[j] nums[i]) { std::swap(nums[j],nums[i]); break; } } break; } } int left i1 , right n -1; while(left right) { std::swap(nums[left],nums[right]); left , --right; } } };六十二把二叉搜索树转换为累加树有一个空间复杂度为O(1)的方法但是没时间看了目的还是尽量都会做/** * Definition for a binary tree node. * 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) {} * }; */ class Solution { public: int cnt 0; void dfs(TreeNode* root) { if(!root) { return; } dfs(root-right); cnt root-val; root-val cnt; dfs(root-left); } TreeNode* convertBST(TreeNode* root) { dfs(root); return root; } };六十三合并K个升序链表不难注意两两合并为最佳/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeList(ListNode* headA , ListNode*headB) { if(!headA || !headB) { return !headA ? headB : headA; } ListNode* ret new ListNode(); ListNode* curr ret; while(headA headB) { if(headA-val headB-val) { curr-next headA; headA headA-next; } else { curr-next headB; headB headB-next; } curr curr-next; } if(headA || headB) { curr-next headA nullptr ? headB : headA; } headA ret-next; delete ret; return headA; } ListNode* mergeKLists(vectorListNode* lists) { int n lists.size(); if(n 0) { return nullptr; } while(lists.size() 1) { std::vectorListNode* tmp; for(int i 0 ; i lists.size() ; i 2) { ListNode* headA lists[i]; ListNode* headB nullptr; if(i1 lists.size()) { headB lists[i1]; } tmp.push_back(mergeList(headA,headB)); } lists tmp; } return lists[0]; } };六十四和为k的子数组应该是前缀和第一眼看成动规了但是动规做不了class Solution { public: int subarraySum(vectorint nums, int k) { int n nums.size(); if(n 0) { return 0; } std::unordered_mapint,int mp; int cnt 0; int ret 0; mp[0] 1; for(autonum : nums) { cnt num; if(mp.count(cnt - k)) { ret mp[cnt-k]; } mp[cnt]; } return ret; } };六十五合并两个有序链表/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if(!list1 || !list2) { return !list1 ? list2 : list1; } ListNode* ret new ListNode(); ListNode* curr ret; while(list1 list2) { if(list1-val list2-val) { curr-next list1; list1 list1-next; } else { curr-next list2; list2 list2-next; } curr curr-next; } if(list1 || list2) { curr-next !list1 ? list2 : list1; } list1 ret-next; delete ret; return list1; } };六十六有效括号简单题注意一下判断的时候是否是奇数偶数就好了。class Solution { public: bool isValid(string s) { int n s.size(); if(n 1) { return false; } std::unordered_mapchar,char mp{{),(},{],[},{},{}}; std::stackchar stk; for(autoc : s) { if(mp.count(c)) { if(stk.empty() || stk.top() ! mp[c]) { return false; } else { stk.pop(); } } else { stk.push(c); } } return stk.size() 0; } };六十七删除链表的倒数第N个节点需要新增一个头结点/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dump new ListNode(0,head); ListNode* left dump; ListNode* right head; while(n right) { right right-next; --n; } while(right) { left left-next; right right-next; } left-next left-next-next; head dump-next; delete dump; return head; } };六十八电话号码的字母组合递归就好了class Solution { public: void scord(std::unordered_mapchar,std::string mp ,std::vectorstd::string ret , std::string digits , int curr , std::stringtmp) { if(tmp.size() digits.size()) { ret.push_back(tmp); return; } if(curr digits.size()) { return; } for(auto c : mp[digits[curr]]) { tmp.push_back(c); scord(mp,ret,digits,curr1,tmp); tmp.pop_back(); } } vectorstring letterCombinations(string digits) { std::vectorstd::string ret; std::unordered_mapchar,std::string mp{{2,abc},{3,def},{4,ghi},{5,jkl},{6,mno},{7,pqrs},{8,tuv},{9,wxyz}}; std::string tmp; scord(mp,ret,digits,0,tmp); return ret; } };六十九三数之和不是相当于两数之和promax版本两数之和需要排序这个也是但是注意在里外两层遍历就是遍历固定值和计算两数之和的时候都需要去重。class Solution { public: vectorvectorint threeSum(vectorint nums) { std::vectorstd::vectorint ret; std::sort(nums.begin() , nums.end()); for(int i 0 ; i nums.size() ; i) { while(i 0 i nums.size() nums[i] nums[i-1]) { i; } int left i 1 , right nums.size() - 1; while(left right) { if(nums[i] nums[right] nums[left] 0) { ret.push_back({nums[i],nums[left],nums[right]}); left; while(left right nums[left] nums[left-1]) { left; } } else if(nums[i]nums[right]nums[left] 0) { left; } else { --right; } } } return ret; } };七十盛水最多的容器类似于小接雨水class Solution { public: int maxArea(vectorint height) { int n height.size(); if(n 0) { return 0; } int max INT_MIN; int l 0 , r n -1; while(l r) { max std::max(std::min(height[r],height[l])*(r - l),max); if(height[l] height[r]) { l; } else { max std::max(height[r]*(r - l),max); --r; } } return max; } };七十一正则表达式匹配很难但是不准备看了。准备快。dp[i][j]为两个字符串i,j是否匹配。class Solution { public: bool isMatch(string s, string p) { int n s.size() , m p.size(); std::vectorstd::vectorint dp(n1,std::vectorint(m1)); dp[0][0] 1; auto match [s,p](int i , int j){ if(i 0) { return false; } if(p[j-1] .) { return true; } return s[i-1] p[j-1]; }; for(int i 1 ; i m ; i) { for(int j 0 ; j n ; j) { if(p[i-1] *) { dp[j][i] | dp[j][i-2]; if(match(j,i-1)) { dp[j][i] | dp[j-1][i]; } } else { if(match(j,i)) { dp[j][i] | dp[j-1][i-1]; } } } } return dp[n][m]; } };七十二最长回文子串不知道为什么这道题似曾相识class Solution { public: string longestPalindrome(string s) { int left 0, len 0; for(int i 0 ; i s.size() ; i) { int l i , r i; while(l 0 r s.size() s[l] s[r]) { --l,r; } if(r - l - 1 len) { left l 1; len r - l - 1; } l i , r i 1; while(l 0 r s.size() s[l] s[r]) { --l,r; } if(r - l - 1 len) { left l 1; len r - l - 1; } } return s.substr(left,len); } };七十三寻找两个正序数组的中位数相当于拉两个绳子但是注意这里的分割条件为[0,n]left是i-1,j-1就相当于是i,j是绳尾第一个class Solution { public: double findMedianSortedArrays(vectorint nums1, vectorint nums2) { if(nums1.size() nums2.size()) { std::swap(nums1,nums2); } int n nums1.size() , m nums2.size(); int l 0 , r n; while(l r) { int i l ((r-l)1); int j (nm1)/2 - i; int left1 i 0 ? INT_MIN : nums1[i-1]; int right1 i n ? INT_MAX : nums1[i]; int left2 j 0? INT_MIN : nums2[j-1]; int right2 j m ? INT_MAX : nums2[j]; if(left1 right2 left2 right1) { if((nm)%2) { return std::max(left1,left2); } else { return (std::max(left1,left2)std::min(right1,right2))/2.00; } } else if(left1 right2) { r i -1; } else { l i 1; } } return 0; } };