每日一题 week02

day01

最大二叉树

排序

ps: clion + leetcode插件 真香

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
    最大二叉树
    2022-09-03 16:44:50
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;
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 submit region begin(Prohibit modification and deletion)

 //* Definition for a binary tree node.


class Solution {
public:
    map<int,int> mp;
    TreeNode* ans=nullptr;
    int l;
    void add(int x)
    {
        TreeNode* p=ans;
        while(1)
        {
            int xx=mp[p->val],yy=mp[x];
            if(xx>yy)
            {
                if(p->left== nullptr)
                {
                    p->left=new TreeNode(x);
                    break;
                }
                else
                p=p->left;
            }
            else
            {
                if(p->right== nullptr)
                {
                    p->right=new TreeNode(x);
                    break;
                }
                else p=p->right;
            }
        }
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

        l=nums.size();
        for(int i=0;i<l;i++)
            mp[nums[i]]=i;

        sort(nums.begin(),nums.end(),greater<int>() );

        ans=new TreeNode(nums[0]);
        for(int i=1;i<l;i++) add(nums[i]);
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
signed  main()
{
    Solution s;
    vector<int> cnm={3,2,1,6,0,5};
    s.constructMaximumBinaryTree(cnm);
    return 0;
}

这个时间复杂度大概在 $nlog(n)$ 的样子

然后..就被吊打了 嘤嘤嘤

最优解又是单调栈

笛卡尔树

时间复杂度 $o(n)$ 太不是人了

要做到两点

1.树的中序遍历是原序列

2.根节点大于所有儿子

那么,现在对于第i个数分类讨论:

1.大于前 i-1 个数的最大值

那么i为新的根节点,原树为左儿子

2.小于前 i-1 个数的最大值

由于i为中序遍历的最后一个数,所以他只能插在右子树的最右边一条链上

image-20220904104256717

怎么插入?

i 变为右儿子,原子树变为左子树

image-20220904104449314

怎么写代码?

用栈维护最右边那一条链

image-20220904110335824

i < top 直接入栈,成为top的右子树

否则就pop直到 empty或者 top > i ,然后i入栈

此时被pop掉的最后一个元素即为i的左子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
    最大二叉树
    2022-09-03 16:44:50
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;
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 submit region begin(Prohibit modification and deletion)

 //* Definition for a binary tree node.


class Solution {
public:

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        stack<TreeNode*> st;
        for(auto i:nums)
        {
            TreeNode* p= nullptr;
            TreeNode* x=new TreeNode(i);
            while(!st.empty()&&st.top()->val<i)
            {
                p=st.top();
                st.pop();
            }
            x->left=p;
            if(!st.empty()) st.top()->right=x;
            st.push(x);
        }
        while(st.size()>1) st.pop();
        return st.top();
    }

};
//leetcode submit region end(Prohibit modification and deletion)
signed  main()
{
    Solution s;
    vector<int> cnm={3,2,1,6,0,5};
    s.constructMaximumBinaryTree(cnm);
    return 0;
}

day02

在既定时间做作业的学生人数

因为保证数据合法,所以只要来了人就++

走了人就–

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
    在既定时间做作业的学生人数
    2022-09-04 11:28:17
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int ans=0;
        for(auto i:startTime) if(i<=queryTime) ans++;
        for(auto i:endTime) if(i<queryTime) ans--;
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    Solution s;
    return 0;
}

day03

最大相等频率

一开始以为是一个数据结构或者dp的题

没想到是分类讨论

用map记录所有数字出现次数和所有出现次数的频率

好绕啊

使用哈希表 count 记录数 x 出现的次数 count[x]，freq 记录出现次数为 f 的数的数目为 freq[f]

符合题意的情况

所有的出现次数都为1,则随意删掉一个

只有一种数字,则随意删一个

只有两种f

image-20220908171918597 image-20220908171926958

虽然写的丑但他跑过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
    最大相等频率
    2022-09-04 11:38:08
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    unordered_map<int,int> cnt,fre;
    bool ch1()
    {
        //只有一种数字
        if(cnt.size()==1) return 1;
        //所有的出现次数都为1
        for(auto i:cnt)
            if(i.second!=1) return 0;
        return 1;

    }
    bool ch2()
    {
        //只有一个为x,其余为y 且x=y+1或者x=1
        //注意考虑一个为x一个为y的情况
        if(fre.size()==2)
        {
            pair<int,int> x,y;
            x= make_pair(0,-1);
            y= make_pair(0,-1);
            for(auto i:fre)
            {
                if(x.second!=-1) y=i;
                else x=i;
                if(i.first==1&&i.second==1) return 1;
            }

            if(x.second==1&&y.second==1)
                if(abs(x.first-y.first)==1) return 1;

            if(x.second==1&&(x.first-y.first==1)) return 1;
            if(y.second==1&&(y.first-x.first==1)) return 1;
        }
        return 0;
    }

    int maxEqualFreq(vector<int>& nums) {

        int ans=0;
        for(int i=0;i<nums.size();i++)
        {
            if(fre[cnt[nums[i]]]>0)fre[cnt[nums[i]]]--;
            if(fre[cnt[nums[i]]]==0) fre.erase(cnt[nums[i]]);
            cnt[nums[i]]++;
            fre[cnt[nums[i]]]++;
            if(ch1()||ch2()) ans=i+1;
        }
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    Solution s;
    vector<int> x={1,2,2,2,2};
    cout<<s.maxEqualFreq(x);
    return 0;
}

day04

层数最深叶子节点的和

搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
    层数最深叶子节点的和
    2022-09-04 15:51:33
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

 //* 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) {}
};

//leetcode submit region begin(Prohibit modification and deletion)

class Solution {
public:
    int ans=0,num=0;
    void dfs(TreeNode* r,int x)
    {
        if(r== nullptr) return;
        if(x>num)
        {
            ans=r->val;
            num=x;
        }
        else if(x==num) ans+=r->val;

        dfs(r->left,x+1);
        dfs(r->right,x+1);
    }
    int deepestLeavesSum(TreeNode* root) {
        dfs(root,1);
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    Solution s;
    return 0;
}

day05

设计有序流

模拟,读懂题就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
    设计有序流
    2022-09-04 15:59:30
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class OrderedStream {
public:
    vector<string> s;
    int ptr=1;
    OrderedStream(int n) {
        s.resize(n+1);
    }
    
    vector<string> insert(int idKey, string value) {
        s[idKey]=value;
        vector<string> ans;
        if(idKey==ptr)
        {
            while(ptr<s.size()&&s[ptr].size()!=0)
            {
                ans.push_back(s[ptr]);
                ptr++;
            }
        }
        return ans;
    }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */
//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    //Solution s;
    OrderedStream p(10);
    return 0;
}

day06

设计循环双端队列

如果不想模拟循环队列的话,直接开2倍空间快乐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
    设计循环双端队列
    2022-09-04 22:03:40
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class MyCircularDeque {
public:
    vector<int> data;
    int l,r,s;
    MyCircularDeque(int k) {
        s=k;
        data.resize(k*2);
        l=k;
        r=k-1;
    }
    
    bool insertFront(int value) {
        if(r-l+1==s) return false;
        data[--l]=value;
        return true;
    }
    
    bool insertLast(int value) {
        if(r-l+1==s) return false;
        data[++r]=value;
        return true;
    }
    
    bool deleteFront() {
        if(r<l) return false;
        l++;
        return true;
    }
    
    bool deleteLast() {
        if(r<l) return false;
        r--;
        return true;

    }
    
    int getFront() {
        if(r<l) return -1;
        return data[l];
    }
    
    int getRear() {
        if(r<l) return -1;
        return data[r];
    }
    
    bool isEmpty() {
        return r<l;
    }
    
    bool isFull() {
        return r-l+1==s;
    }
};


//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
 //* Your MyCircularDeque object will be instantiated and called as such:
  MyCircularDeque* obj = new MyCircularDeque(3);
  bool param;
    param = obj->insertLast(1);
    param = obj->insertLast(2);
    param = obj->insertFront(3);
    param = obj->insertFront(4);

  bool param_3 = obj->deleteFront();
  bool param_4 = obj->deleteLast();
  int param_5 = obj->getFront();
  int param_6 = obj->getRear();
  bool param_7 = obj->isEmpty();
  bool param_8 = obj->isFull();

    return 0;
}

模拟循环队列

为了方便多开一个空间

r的位置为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
    设计循环双端队列
    2022-09-04 22:03:40
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class MyCircularDeque {
public:
    vector<int> data;
    int l,r,s;
    MyCircularDeque(int k) {
        data.resize(k+1);
        l=r=0;
        s=k;
    }

    bool insertFront(int value) {
        if(r-l==s||r+1==l) return false;
        l=(l+s)%(s+1);
        data[l]=value;
        return true;
    }

    bool insertLast(int value) {
        if(r-l==s||r+1==l) return false;
        data[r]=value;
        r=(r+1)%(s+1);
        return true;
    }

    bool deleteFront() {
        if(l==r) return false;
        l=(l+1)%(s+1);
        return true;
    }

    bool deleteLast() {
        if(l==r) return false;
        r=(r+s)%(s+1);
        return true;
    }

    int getFront() {
        if(l==r) return -1;
        return data[l];
    }

    int getRear() {
        if(l==r) return -1;
        return data[(r+s)%(s+1)];
    }

    bool isEmpty() {
        return l==r;
    }

    bool isFull() {
        return r-l==s||r+1==l;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */


//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    return 0;
}