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荷蘭國旗問題；
代碼 計數(shù)排序?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，所以需要循環(huán)一次在判斷
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中的字母數(shù)量
3. 初始化；4. 尾指針遍歷s
5. 一邊遍歷的時候一遍計算t中的字母數(shù)量；6. 如果數(shù)量剪完了，說明窗口形成了，現(xiàn)在要通過移動頭指針實現(xiàn)窗口縮小了
7. 記錄下最小的窗口長度和起始位置；8. 返回答案
注意：如何在頭指針移動中判斷當前節(jié)點是或否是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字符個數(shù)
for(;en<s.size();en++){
if(mp[s[en]]>0) coun++;//屬于字符串t的字母數(shù)量
mp[s[en]]--;//無論它是不是字符串t中的字符，都要減減，這樣子剪完就說明t字符都沒了
//變成負數(shù)就說明它減多了
if(coun==t.size()){//字符串數(shù)量已經(jīng)over了
for(;st<en && (mp[s[st]]<0);){//注意這里是小于0，如果是大于0就說明減多了
mp[s[st]]++;st++;//先加加，恢復mp原來的個數(shù)，之后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
題意：給出一個數(shù)字集，輸出所有的子集（包括空集）
我的思路
用遞歸？就像之前一樣；有想過要不要用循環(huán)，但是發(fā)現(xiàn)用循環(huán)的話答案不對，就把循環(huán)消去了
代碼?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的話，先把起點找到，之后環(huán)顧四周看看有沒有（？
首先要準備一個隊列，把（位置，第幾個英文字母）找到的都放到隊列里，之后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;
}
};優(yōu)化代碼?Runtime 0 ms Beats 100% Memory8.1 MB Beats 42.63%
優(yōu)化途徑
1. 不要把遞歸放在判斷if里面，這樣會費時
2. 先把字符串倒過來，如果最后一個字符的數(shù)量大于第一個字符的數(shù)量，再把字符串倒轉回去；也就是先把字符數(shù)量少的先遞歸【但是我不知道為什么】
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的時間復雜度，但是預處理的話二維數(shù)組會爆棧
不會做
標答
代碼?單調棧 Runtime 125 ms Beats 88.36% Memory77.3 MB Beats 73.1%
st里面從小到大的放置，相等的留下，ran是最近的比當前的要大的高度，height的數(shù)組最后加上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數(shù)組
為什么棧一開始不把-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]也會判斷成正確的，所以不可以
既然是遞歸，那就要讓左子樹的左子樹 和 右子樹的右子樹對稱；左子樹的右子樹 和 右子樹的左子樹對稱
但是不會寫
標答
遞歸函數(shù)的參數(shù)是左子樹指針和右子樹指針，然后判斷左的值和右的值是否相同
然后判斷左的左和右的右? 左的右和右的左
這樣遞歸下去
代碼?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
題意：層序遍歷
我的思路
一層的結尾放一個空指針，每次循環(huán)到空指針的時候，就在結尾放一個空指針；當循環(huán)彈出空指針同時隊列為空的時候，就停止放入空指針
代碼?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;
}
};標答
用一層的隊列大小得出一層有多少個，來循環(huán)
代碼 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?
題意：求樹的最大深度
我的思路
用層序遍歷看看有幾層或者用遞歸無線向下，那就先用層序遍歷向下文章來源：http://www.zghlxwxcb.cn/news/detail-685815.html
代碼 層序遍歷?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文章來源地址http://www.zghlxwxcb.cn/news/detail-685815.html
代碼 遞歸 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;
}
};到了這里，關于Leetcode Top 100 Liked Questions（序號75~104）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
