Leetcode Top 100 Liked Questions（序号75~104）

75. Sort Colors

 题意：红白蓝的颜色排序，使得相同的颜色放在一起，不要用排序

我的思路

哈希

代码 Runtime 4 ms Beats 28.23% Memory 8.3 MB Beats 9.95%

class Solution {
public:void sortColors(vector<int>& nums) {vector<int> ans; int n=nums.size();int vis[3]={0};for(int i=0;i<n;i++) vis[nums[i]]++;int v=0;for(int i=0;i<3;i++){for(int j=0;j<vis[i];j++){nums[v++]=i;}}}
};

标答

Dutch National Flag Problem荷兰国旗问题；

代码 计数排序 Runtime 0 ms Beats 100% Memory 8.3 MB Beats 41.44%

感觉和我之前做的差不多

class Solution {
public:void sortColors(vector<int>& nums) {int num0 = 0;int num1 = 0;int num2 = 0;for (int num:nums) {if( num==0 ) num0++;else if (num == 1)  num1++; else if (num == 2)  num2++; }for (int i=0; i< nums.size(); i++) {if( num0>0 ) {nums[i] = 0; num0--;} else if( num1>0 ) {nums[i] = 1;  num1--;} else if( num2>0 ) {nums[i] = 2; num2--;}}}
};

代码 双指针 Runtime 0 ms Beats 100% Memory 8.3 MB Beats 41.44%

如果nums[mid]是0，low和mid交换，因为low负责0的部分，low++保证指针前面的都是0，low指针指到的就只有0或者1；如果nums[mid]是1，那么是正确的；如果nums[mid]是2，high指向的和mid指向的交换，high--来确保high的右边都是2，为什么mid不++？因为mid这时可能是0，所以需要循环一次在判断

class Solution {
public:void sortColors(vector<int>& nums) {int low = 0, mid = 0, high = nums.size()-1;while(mid <= high){if(nums[mid] == 0){swap(nums[low], nums[mid]); low++; mid++;}else if(nums[mid] == 1) mid++;else{swap(nums[mid], nums[high]);  high--;}}}
};

76. Minimum Window Substring

题意：给出两个字符串s和t，找到minimum window substring

我的思路

不会

标答

用滑动窗口，窗口的开头在s字符串的初始位置，结尾在所有t的字符都在里面；当上面的窗口有了，就可以改变头指针来缩小窗口，步骤为：

1. 如果s比t小，那么直接返回；2. 记录t中的字母数量

3. 初始化；4. 尾指针遍历s

5. 一边遍历的时候一遍计算t中的字母数量；6. 如果数量剪完了，说明窗口形成了，现在要通过移动头指针实现窗口缩小了

7. 记录下最小的窗口长度和起始位置；8. 返回答案

注意：如何在头指针移动中判断当前节点是或否是t中的？在每个end指针移动的时候会把mp中的字母--，这时候就只有在t中的字母是大于等于0的了

代码 Runtime 7 ms Beats 92.29% Memory7.9 MB Beats 79.63%

class Solution {
public:string minWindow(string s, string t) {if(t.size()>s.size())return "";unordered_map<char,int>mp;for(int i=0;i<t.size();i++)mp[t[i]]++;int st=0,en=0,minli=99999,minst=0,coun=0;//st是头指针，en是尾指针，minli是最短的字符串长度，minst是头指针位置，coun是t字符个数for(;en<s.size();en++){if(mp[s[en]]>0) coun++;//属于字符串t的字母数量mp[s[en]]--;//无论它是不是字符串t中的字符，都要减减，这样子剪完就说明t字符都没了//变成负数就说明它减多了if(coun==t.size()){//字符串数量已经over了for(;st<en && (mp[s[st]]<0);){//注意这里是小于0，如果是大于0就说明减多了mp[s[st]]++;st++;//先加加，恢复mp原来的个数，之后st前进}if(en-st<minli){//看看头指针改变过后，最小字符串长度是否更新了minst=st;minli=en-st;}mp[s[st]]++;st++;//更新头指针，使得目前的字符串不合法coun--;//这时coun--，让尾指针可以接着更新}}string ans="";if (minli!=99999)ans= s.substr(minst,minli+1);return ans;}
};

78. Subsets

题意：给出一个数字集，输出所有的子集（包括空集）

我的思路

用递归？就像之前一样；有想过要不要用循环，但是发现用循环的话答案不对，就把循环消去了

代码 Runtime 0 ms Beats 100% Memory 7 MB Beats 78.17%

class Solution {
public:void sol(vector<int>& nums,int nxt,vector<int>& pol,vector<vector<int>> &ans){if(nxt==nums.size()){ans.push_back(pol);return ;}pol.push_back(nums[nxt]);//因为拿或者不拿sol(nums,nxt+1,pol,ans);pol.pop_back();sol(nums,nxt+1,pol,ans);}vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans={};    vector<int> pol={};sol(nums,0,pol,ans);return ans;}
};

79. Word Search

题意：

我的思路

把所有可能性的都遍历一遍，如果是BFS的话，先把起点找到，之后环顾四周看看有没有（？

首先要准备一个队列，把（位置，第几个英文字母）找到的都放到队列里，之后bfs上下左右的看，如果在周围找不到下一个就return false，但是做到最后 超时了TLE

代码 超时代码

class Solution {
public:struct node{int x,y,id;vector<vector<bool> > vis=vector(6 , vector<bool>(6,0));};bool exist(vector<vector<char>>& board, string word) {queue<node>st,q;int n=board.size(),m=board[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]==word[0]){node temp;temp.x=i;temp.y=j;temp.id=0;temp.vis[i][j]=1;st.push(temp);}}}int dx[]={1,-1,0,0};int dy[]={0,0,1,-1};while(!st.empty()){while(!q.empty())q.pop();//清空node te=st.front();st.pop();q.push(te);while(!q.empty()){node now=q.front(); int nx,ny;if(now.id==word.size()-1)return 1;q.pop();for(int i=0;i<4;i++){nx=now.x+dx[i];ny=now.y+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m&&!now.vis[nx][ny]){if(board[nx][ny]==word[now.id+1]){node ans;ans.x=nx;ans.y=ny;ans.id=now.id+1;ans.vis=now.vis;ans.vis[nx][ny]=1;q.push(ans);}}}}}return 0;}
};

标答

首先得到n和m，遍历地图，如果地图是第一个字符，那么就可以开始递归了

代码 Runtime 774 ms Beats 47.25% Memory 7.9 MB Beats 74.74%

在递归条件中先判断是不是这个字母，然后递归下去

class Solution {
public:bool solve(vector<vector<char>>& board,int x,int y,int c,int m,int n,string word){if(c==word.size())return 1;if(x<0||y<0||x>=m||y>=n)return 0;if(board[x][y]!=word[c])return 0;char ch=board[x][y];board[x][y]='#';//这一手就不会来回走了！if(solve(board,x+1,y,c+1,m,n,word)||solve(board,x,y+1,c+1,m,n,word)||solve(board,x-1,y,c+1,m,n,word)||solve(board,x,y-1,c+1,m,n,word))return 1;board[x][y]=ch;return 0;}bool exist(vector<vector<char>>& board, string word) {int m=board.size(), n=board[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(solve(board,i,j,0,m,n,word))return 1;}}return 0;}
};

优化代码 Runtime 0 ms Beats 100% Memory8.1 MB Beats 42.63%

优化途径

1. 不要把递归放在判断if里面，这样会费时

2. 先把字符串倒过来，如果最后一个字符的数量大于第一个字符的数量，再把字符串倒转回去；也就是先把字符数量少的先递归【但是我不知道为什么】

class Solution {
public:bool ispres(vector<vector<char>>& board, int i, int j, const string &word,int c,int m, int n){if(c==word.length()){return true;}if(i < 0 || j < 0 || i >= m || j >= n || board[i][j]!=word[c]){return false;}char ch = board[i][j];board[i][j] = '*';bool flag = ispres(board,i+1,j,word,c+1,m,n) || ispres(board,i-1,j,word,c+1,m,n) || ispres(board,i,j+1,word,c+1,m,n) || ispres(board,i,j-1,word,c+1,m,n);board[i][j] = ch;return flag;}bool exist(vector<vector<char>>& board, string word) {int m = board.size();int n = board[0].size();reverse(word.begin(), word.end());if (count(word.begin(), word.end(), word[0]) > count(word.begin(), word.end(), word[word.size() - 1])) reverse(word.begin(), word.end());for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j]==word[0]){if(ispres(board,i,j,word,0,m,n)){return true;}}}}return false;}
};

84. Largest Rectangle in Histogram

 题意：

我的思路

如果是双指针的话，min（a[i],…,a[j]）*（j-i+1）

那就首先是On^2的时间复杂度，但是预处理的话二维数组会爆栈

不会做

标答

代码 单调栈 Runtime 125 ms Beats 88.36% Memory77.3 MB Beats 73.1%

st里面从小到大的放置，相等的留下，ran是最近的比当前的要大的高度，height的数组最后加上0。求面积是弹出的最大值*（当前的位置减去栈中目前的位置-1）

为什么是当前的位置减去栈中目前的位置-1？

因为设这一轮被弹出的位置为x，高位h[x]，弹出后的栈顶位置为y，因为h[y]小于等于h[x]，也就是说，（y，x]的位置之间的高都是大于h[x]；

【不然为什么（y，x]的位置之间的高要被弹出去呢】

同时（x，i)的位置之间的高也都是大于h[x]

【不然x就被弹出去了】

所以(y，i)之间，x是最小的；因此面积是h[ x ] * ( i - y - 1 )

注意：初始化ran，初始化h数组

为什么栈一开始不把-1放入？【就像32. Trapping Rain WaterLeetCode Top100 Liked 题单（序号19~33）】

因为32是栈，而这个是单调栈，需要比较站内的元素来决定是否弹出

相关:42. Trapping Rain WaterLeetCode Top100 Liked 

class Solution {
public:int largestRectangleArea(vector<int>& h) {stack<int> st;int ans=0;h.push_back(0); int n=h.size();for(int i=0;i<n;i++){while(!st.empty()&&h[st.top()]>h[i]){//找到了高的int x=st.top(),y;st.pop();if(st.empty()) y=-1;else y=st.top();ans=max(ans,h[x]*(i-y-1));}st.push(i);}return ans;}
};

代码 Runtime 86 ms Beats 99.54% Memory74.7 MB Beats 99.53%

感觉和单调栈的原理差不多，但是没有看懂

class Solution {
public:int largestRectangleArea(const vector<int>& heights) {int end=-1;int n=heights.size();int maxArea=0;int counts[10001] = {};int sortedIndexes[10001] = {};for (int i=0;i<=n;++i) {int count = 1;while(true){if(end<0)break;const int index=sortedIndexes[end];if(i!=n&&heights[index]<heights[i])break;count+=counts[end];int area=(counts[end]+i-index-1)*heights[index];if(area>maxArea)maxArea=area;--end;}sortedIndexes[++end] = i;counts[end] = count;}return maxArea;}
};

94. Binary Tree Inorder Traversal

题意：输出二叉树中序排序

我的思路

就直接中序递归就可以了

注意：当root为空的时候要特判！！！

代码 Runtime0 ms Beats 100% Memory 8.2 MB Beats 97.70%

class Solution {
public:void p(TreeNode* root,vector<int>& ans){if(root->left !=NULL)p(root->left,ans);ans.push_back(root->val);if(root->right!=NULL)p(root->right,ans);}vector<int> inorderTraversal(TreeNode* root) {if(root==NULL)return {};vector<int> ans;p(root,ans);return ans;}
};

98. Validate Binary Search Tree

题意：判断树是不是平衡搜索树BST，左子树比中间的小，右子树比中间的大

我的思路

还是递归，就像前面的79 word search一样搜索，然后判断ans的顺序大小

注意：等于也不行！！！

注意：int&的时候不要传const int 进去

代码 Runtime13 ms Beats 42.85% Memory 21.7 MB Beats 33.33%

class Solution {
public:bool P(TreeNode* root,long long & r){if(root->left!=NULL){if(!P(root->left,r))return 0;}if(r>=root->val) return 0;r=root->val;if(root->right!=NULL){if(!P(root->right,r))return 0;}return 1;}bool isValidBST(TreeNode* root) {long long ans=-2147483649;return P(root,ans);}
};

标答

确实更加简洁快速

代码 Runtime4 ms Beats 94.78% Memory21.7 MB Beats 33.33%

class Solution {
public:bool isValidBST(TreeNode* root,long min,long max){if(root==NULL)return true;if(root->val>=max or root->val<=min)return false;return isValidBST(root->left,min,root->val)&&isValidBST(root->right,root->val,max);}bool isValidBST(TreeNode* root) {long max=LONG_MAX;long min=LONG_MIN;return isValidBST(root,min,max);}
};

101. Symmetric Tree

题意：看是不是对称的

我的思路

中序序列ans，两个指针从两端向中间核对

答案不正确，因为[1,2,2,2,null,2]也会判断成正确的，所以不可以

既然是递归，那就要让左子树的左子树 和 右子树的右子树对称；左子树的右子树 和 右子树的左子树对称

但是不会写

标答

递归函数的参数是左子树指针和右子树指针，然后判断左的值和右的值是否相同

然后判断左的左和右的右  左的右和右的左

这样递归下去

代码 Runtime 0 ms Beats 100% Memory 16.2 MB Beats 91.71%

class Solution {
public:bool p(TreeNode* l,TreeNode* r){if(l==NULL&&r==NULL)return 1;else if (l==NULL||r==NULL)return 0;if(l->val!=r->val)return 0;return p(l->left,r->right)&&p(l->right,r->left);//递归}bool isSymmetric(TreeNode* root) {if(root==NULL)return 1;return p(root->left,root->right);}
};

102. Binary Tree Level Order Traversal

题意：层序遍历

我的思路

一层的结尾放一个空指针，每次循环到空指针的时候，就在结尾放一个空指针；当循环弹出空指针同时队列为空的时候，就停止放入空指针

代码 Runtime 6 ms Beats 52.11% Memory13.3 MB Beats 92.55%

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;queue <TreeNode *>q;if(root==NULL)return ans;q.push(root);q.push(NULL);vector<int> sol;while(!q.empty()){TreeNode * top;top=q.front();q.pop();if(top!=NULL){sol.push_back(top->val);if(top->left!=NULL)q.push(top->left);if(top->right!=NULL)q.push(top->right);}else{ans.push_back(sol);sol={};if(!q.empty())q.push(NULL);}}return ans;}
};

标答

用一层的队列大小得出一层有多少个，来循环

代码 Runtime 3 ms Beats 88.93% Memory13.6 MB Beats 51.20%

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>>ans; if(root == NULL) return ans; queue<TreeNode*>q;q.push(root);while(!q.empty()){int size =  q.size(); vector<int> level; for(int i =0;i<size;i++){TreeNode* node=q.front();q.pop();if(node->left!=NULL)q.push(node->left);if(node->right!=NULL)q.push(node->right);level.push_back(node->val);}ans.push_back(level);}return ans; }
};

104. Maximum Depth of Binary Tree 

题意：求树的最大深度

我的思路

用层序遍历看看有几层或者用递归无线向下，那就先用层序遍历向下

代码 层序遍历 Runtime 0 ms Beats 100% Memory19 MB Beats 9.46%

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> q; if(root==NULL)return 0;q.push(root);int deep=0;while(!q.empty()){deep++;int n=q.size();for(int i=0;i<n;i++){if(q.front()->left!=NULL)q.push(q.front()->left);if(q.front()->right!=NULL)q.push(q.front()->right);q.pop();}}return deep;}
};

标答 递归

树的高度=max(左子树的高度，右子树的高度）+1

代码 递归 Runtime 8 ms Beats 61.27% Memory19 MB Beats 9.46%

class Solution {
public:int maxDepth(TreeNode* root) {if(root==NULL)return 0;return max(maxDepth(root->left),maxDepth(root->right))+1;}
};