84. 柱状图中最大的矩形
给定n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
class Solution { public: int largestRectangleArea(vector<int>& heights) { int n=heights.size(); vector<int> left(n),right(n); stack<int> stk; for(int i=0;i<n;i++){ while(stk.size()&&heights[stk.top()]>=heights[i]) stk.pop(); if (stk.empty()) left[i]=-1; else left[i]=stk.top(); stk.push(i); } while(stk.size()) stk.pop(); for(int i=n-1;i>=0;i--){ while(stk.size()&&heights[stk.top()]>=heights[i]) stk.pop(); if (stk.empty()) right[i]=n; else right[i]=stk.top(); stk.push(i); } int res=0; for(int i=0;i<n;i++) res=max(res,(right[i]-left[i]-1)*heights[i]); return res; } };
85. 最大矩形
给定一个仅包含 0 和 1 、大小为rowsxcols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
class Solution { public: int largestRectangleArea(vector<int>& heights) { int n=heights.size(); vector<int> left(n),right(n); stack<int> stk; for(int i=0;i<n;i++){ while(stk.size()&&heights[stk.top()]>=heights[i]) stk.pop(); if (stk.empty()) left[i]=-1; else left[i]=stk.top(); stk.push(i); } while(stk.size()) stk.pop(); for(int i=n-1;i>=0;i--){ while(stk.size()&&heights[stk.top()]>=heights[i]) stk.pop(); if (stk.empty()) right[i]=n; else right[i]=stk.top(); stk.push(i); } int res=0; for(int i=0;i<n;i++) res=max(res,(right[i]-left[i]-1)*heights[i]); return res; } int maximalRectangle(vector<vector<char>>& matrix) { if(matrix.empty()||matrix[0].empty()) return 0; int n=matrix.size(); int m=matrix[0].size(); vector<vector<int>> h(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if (matrix[i][j]=='1'){ if (i) h[i][j]=h[i-1][j]+1; else h[i][j]=1; } } } int res=0; for(int i=0;i<n;i++) res=max(res,largestRectangleArea(h[i])); return res; } };
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
/** * 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: void inorder(TreeNode *root,vector<int> &res){ if (root==NULL) return; inorder(root->left,res); res.push_back(root->val); inorder(root->right,res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root,res); return res; } };
96. 不同的二叉搜索树
给你一个整数n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
class Solution { public: int numTrees(int n) { vector<int> f(25,0); f[0]=0; f[1]=1; f[2]=2; if (n<3) return f[n]; f[0]=1; for(int i=3;i<=n;i++){ for(int j=0;j<=i-1;j++) f[i]+=f[j]*f[i-j-1]; } return f[n]; } };
98.验证二叉搜索树
class Solution { public: long long pre=LONG_MIN; bool isValidBST(TreeNode* root) { if(root==NULL) return true; if (!isValidBST(root->left)) return false; if(root->val<=pre) return false; pre=root->val; return isValidBST(root->right); } };
101.对称二叉树
class Solution { public: bool dfs(TreeNode* p, TreeNode* q) { if (p==NULL&&q==NULL) return true; else if(p==NULL||q==NULL) return false; else if (p->val!=q->val) return false; else return (dfs(p->left,q->right)&&dfs(p->right,q->left)); } bool isSymmetric(TreeNode* root) { return dfs(root,root); } };
102. 二叉树的层序遍历
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if (root==NULL) return res; queue<TreeNode *>q; q.push(root); while(!q.empty()){ int qsize=q.size(); res.push_back(vector<int>()); for(int i=0;i<qsize;i++){ auto node=q.front(); q.pop(); res.back().push_back(node->val); if (node->left!=NULL) q.push(node->left); if (node->right!=NULL) q.push(node->right); } } return res; } };
104. 二叉树的最大深度
class Solution { public: int maxDepth(TreeNode* root) { if (root!=NULL) return max(maxDepth(root->left),maxDepth(root->right))+1; else return 0; } };
105. 从前序与中序遍历序列构造二叉树
class Solution { public: unordered_map<int,int> num2idx; vector<int> preorder; vector<int> inorder; int n; TreeNode *buildTree(int pl,int pr,int il,int ir){ if (pl>pr) return NULL; int rval=preorder[pl]; TreeNode *root=new TreeNode(rval); int rootpos=num2idx[rval]; int len=rootpos-il; root->left=buildTree(pl+1,pl+len,il,rootpos-1); root->right=buildTree(pl+len+1,pr,rootpos+1,ir); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { this->preorder=preorder; this->inorder=inorder; n=preorder.size(); for(int i=0;i<inorder.size();i++) num2idx[inorder[i]]=i; TreeNode *root=buildTree(0,n-1,0,n-1); return root; } };
114. 二叉树展开为链表
class Solution { public: void flatten(TreeNode* &root) { while(root){ TreeNode *p=root->left; if (p){ while(p->right) p=p->right; p->right=root->right; root->right=root->left; root->left=NULL; } root=root->right; } } };
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第i ii个元素prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
class Solution { public: int maxProfit(vector<int>& prices) { stack<int> stk; int n=prices.size(); int res=0; for(int i=0;i<n;i++){ if (stk.empty()||prices[i]<stk.top()) stk.push(prices[i]); res=max(res,prices[i]-stk.top()); } return res; } };
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
class Solution { int res=-0x3f3f3f3f; public: int maxgain(TreeNode* root){ if (root==NULL) return 0; int maxleft=max(maxgain(root->left),0); int maxright=max(maxgain(root->right),0); int curres=maxleft+maxright+root->val; res=max(curres,res); return root->val+max(maxleft,maxright); } int maxPathSum(TreeNode* root) { maxgain(root); return res; } };
128. 最长连续序列
给定一个未排序的整数数组nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为O(n) 的算法解决此问题。
class Solution { public: int longestConsecutive(vector<int>& nums) { set<int> st; for(auto num:nums) st.insert(num); int res=0; for(auto num:nums){ if (st.count(num)&&!st.count(num-1)){ int x=num; int y=x; st.erase(x); while(st.count(y+1)){ y++; st.erase(y); } res=max(res,y-x+1); } } return res; } };
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
class Solution { public: int singleNumber(vector<int>& nums) { int res=0; for(auto num:nums){ res^=num; } return res; } };
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int n=s.size(); vector<int> f(n+1); f[0]=1; for(int i=1;i<=n;i++){ for(string word:wordDict){ int len=word.size(); if (i>=len){ if (s.substr(i-len,len)==word) f[i]|=f[i-len]; } } } return f[n]; } };
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
class Solution { public: bool hasCycle(ListNode *head) { if (!head || !head->next) return 0; ListNode *first = head, *second = first->next; while (first && second) { if (first == second) return true; first = first->next; second = second->next; if (second) second = second->next; } return false; } };
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
class Solution { public: ListNode *detectCycle(ListNode *head) { set<ListNode*> st; while(head){ if (st.count(head)) return head; st.insert(head); head=head->next; } return NULL; } };
146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
(int capacity) 以 正整数 作为容量capacity 初始化 LRU 缓存
(int key) 如果关键字key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以O(1)的平均时间复杂度运行。
class LRUCache { public: struct Node{ int key,val; Node *left,*right; Node():key(0),val(0),left(NULL),right(NULL){} }; Node *hu,*hr,*tu,*tr; int n; unordered_map<int,Node *>hash; void delete_node(Node *p){ p->left->right=p->right; p->right->left=p->left; } void insert_node(Node *head,Node *p){ p->right=head->right; head->right=p; p->left=head; p->right->left=p; } LRUCache(int capacity) { n=capacity; hu=new Node(),hr=new Node(),tu=new Node(),tr=new Node(); hu->right=tu,tu->left=hu; hr->right=tr,tr->left=hr; for(int i=0;i<n;i++){ Node *p=new Node(); insert_node(hr,p); } } int get(int key) { if (hash[key]){ Node *p=hash[key]; delete_node(p); insert_node(hu,p); return p->val; } return -1; } void put(int key, int value) { if (hash[key]){ Node *p=hash[key]; delete_node(p); insert_node(hu,p); p->val=value; return; } if (!n){ n++; Node *p=tu->left; hash[p->key]=0; delete_node(p); insert_node(hr,p); } n--; Node *p=hr->right; p->key=key,p->val=value,hash[key]=p; delete_node(p); insert_node(hu,p); } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
class Solution { public: ListNode* sortList(ListNode* head) { if(head==NULL) return head; int n=0; for(auto p=head;p;p=p->next) n++; auto dummy=new ListNode (-1); dummy->next=head; for(int i=1;i<n;i*=2){ auto cur=dummy; for(int j=1;j+i<=n;j+=i*2){ auto p=cur->next,q=p; for(int k=0;k<i;k++) q=q->next; int x=0,y=0; while(x<i&&y<i&&p&&q){ if (p->val<=q->val){ cur=cur->next=p; p=p->next; x++; } else{ cur=cur->next=q; q=q->next; y++; } } while(x<i&&p){ cur=cur->next=p; p=p->next; x++; } while(y<i&&q){ cur=cur->next=q; q=q->next; y++; } cur->next=q; } } return dummy->next; } };
152. 乘积最大子数组
给你一个整数数组nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
class Solution { public: int maxProduct(vector<int>& nums) { int res=nums[0],f=nums[0],g=nums[0]; for(int i=1;i<nums.size();i++){ int num=nums[i]; int fa=f*num; int ga=g*num; f=max(num,max(fa,ga)); g=min(num,min(fa,ga)); res=max(res,f); } return res; } };
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
class MinStack { stack<int> stk; stack<int> minstk; public: MinStack() { minstk.push(INT_MAX); } void push(int val) { stk.push(val); if (val<=minstk.top()) minstk.push(val); } void pop() { if (stk.top()==minstk.top()) minstk.pop(); stk.pop(); } int top() { return stk.top(); } int getMin() { if (minstk.size()==1) return 0; return minstk.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int len1=0,len2=0; ListNode *p1=headA; while(p1->next!=NULL){ len1++; p1=p1->next; } ListNode *p2=headB; while(p2->next!=NULL){ len2++; p2=p2->next; } if (len1>len2) return getIntersectionNode(headB,headA); p2=headB; p1=headA; for(int i=0;i<len2-len1;i++) p2=p2->next; while(p1!=NULL&&p2!=NULL&&p1!=p2){ p1=p1->next; p2=p2->next; } if (p1==p2) return p1; else return NULL; } };
169. 多数元素
给定一个大小为n 的数组nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊n/2⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution { public: int majorityElement(vector<int>& nums) { int r=0,c=0; for(auto num:nums){ if (c==0) r=num; if (num!=r) c--; else c++; } return r; } };
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
class Solution { public: int dp[105]; int rob(vector<int>& nums) { int len=nums.size(); if (len==0) return 0; if (len == 1) return nums[0]; dp[0]=nums[0]; dp[1]=max(nums[0],nums[1]); for(int i=2;i<len;i++) dp[i]=max(dp[i-1],dp[i-2]+nums[i]); return dp[len-1]; } };
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
class Solution { public: int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int numIslands(vector<vector<char>>& grid) { int m=grid.size(); int n=grid[0].size(); vector<vector<bool>> st(m,vector<bool>(n,0)); int res=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if (!st[i][j]&&grid[i][j]=='1'){ st[i][j]=1; res++; queue<pair<int,int>> q; q.push({i,j}); while(!q.empty()){ auto [px,py]=q.front(); q.pop(); int tx,ty; for (int k=0;k<4;k++){ tx=px+dx[k]; ty=py+dy[k]; if (tx<0||tx>=m||ty<0||ty>=n) continue; if (st[tx][ty]) continue; if (grid[tx][ty]!='1') continue; q.push({tx,ty}); st[tx][ty]=1; } } } } } return res; } };
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
class Solution { public: ListNode* reverseList(ListNode* head) { if (head==NULL) return head; ListNode *p2=head->next; ListNode *p1=head; p1->next=NULL; while(p2!=NULL){ ListNode *ptemp=p2->next; p2->next=p1; p1=p2; p2=ptemp; } return p1; } };
207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
class Solution { vector<int> G[100005]; int indegree[100005]; public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { int n=numCourses; queue<int> q; for (auto node:prerequisites){ G[node[0]].push_back(node[1]); } memset(indegree,0,sizeof indegree); for(int i=0;i<n;i++) for(auto node:G[i]) indegree[node]++; int count=0; for (int i=0;i<n;i++) if (indegree[i]==0) q.push(i); while(!q.empty()){ int p=q.front(); q.pop(); count++; for (auto node:G[p]){ indegree[node]--; if (indegree[node]==0){ q.push(node); } } } return count==n; } };
208. 实现 Trie (前缀树)
class Trie { public: bool isword[300005]; int ne[300005][26]; int idx=0; Trie() { memset(isword,0,sizeof isword); idx=0; memset(ne,0,sizeof ne); } void insert(string word) { int n=word.size(); int p=0; for(int i=0;i<n;i++){ int u=word[i]-'a'; if (!ne[p][u]){ ne[p][u]=++idx; } p=ne[p][u]; } isword[p]=1; } bool search(string word) { int n=word.size(); int p=0; for(int i=0;i<n;i++){ int u=word[i]-'a'; if (!ne[p][u]) return false; p=ne[p][u]; } return isword[p]; } bool startsWith(string prefix) { int n=prefix.size(); int p=0; for(int i=0;i<n;i++){ int u=prefix[i]-'a'; if (!ne[p][u]) return false; p=ne[p][u]; } return true; } }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */
