每日一题 week05

完结撒花

image-20220915161056238

day01

二叉搜索子树的最大键值和

用结构体维护子树的min,max,sum值并返回

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
/*
    二叉搜索子树的最大键值和
    2022-09-14 14:11:10
    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.
 * 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 {
    int ans=0;
    struct no{
        int maxx=INT_MIN,minn=INT_MAX,sum=0;
    };
    no dfs(TreeNode* r)
    {
        if(!(r->left||r->right))
        {
            ans=max(ans,r->val);
            return {r->val,r->val,r->val};
        }

        no ls,rs;
        if(r->left) ls=dfs(r->left);
        if(r->right) rs=dfs(r->right);

        if(r->right&&r->left)
        {
            if(ls.maxx<r->val&&r->val<rs.minn)
            {
                ans=max(ans,rs.sum+r->val+ls.sum);
                return {rs.maxx,ls.minn,rs.sum+r->val+ls.sum};
            }
        }
        else if(r->right)
        {
            if(r->val<rs.minn)
            {
                ans=max(ans,r->val+rs.sum);
                return {rs.maxx,r->val,r->val+rs.sum};
            }
        }
        else if(r->left)
        {
            if(ls.maxx<r->val)
            {
                ans=max(ans,ls.sum+r->val);
                return {r->val,ls.minn,ls.sum+r->val};
            }
        }
        return {INT_MAX,INT_MIN,INT_MIN};
    }
public:
    int maxSumBST(TreeNode* root) {
        dfs(root);
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    Solution s;
    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
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-14 14:14:43
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
    TreeNode* ans= nullptr;
    void dfs(TreeNode* a,TreeNode* b,TreeNode* t)
    {
        if(ans) return ;
        if(a==t)
        {
            ans=b;
            return;
        }
        if(a->left)dfs(a->left,b->left,t);
        if(a->right) dfs(a->right,b->right,t);
    }
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        dfs(original,cloned,target);
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


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

day03

两个数组间的距离值

快乐暴力

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
/*
    两个数组间的距离值
    2022-09-14 23:24:51
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int cnt=0;
        for(auto i:arr1)
        {
            bool f=1;
            for(auto j:arr2)
                if(abs(i-j)<=d)
                {
                    f=0;
                    break;
                }
            if(f) cnt++;
        }
        return cnt;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


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

day04

安排电影院座位

由于位置1和位置10对结果没有影响,所以去掉后变为8位数,int可以装下

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-14 14:54:08
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    unordered_map<int,int> mp;
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        for(auto i:reservedSeats)
        {
            if(!mp.count(i[0]))
                mp[i[0]]=0xff;
            if(i[1]>1&&i[1]<10)
                mp[i[0]]-=(1<<(9-i[1]));

            //cout<<mp[i[0]];
        }

        int ans=(n-mp.size())*2;
        for(auto i:mp)
        {
            //cout<<i.second&0xf0<<" "
            bool f1=(i.second&0xf0)==0xf0;
            bool f2=(i.second&0x3c)==0x3c;
            bool f3=(i.second&0x0f)==0x0f;

            if(f1) ans++,f2=0;
            if(f2||f3) ans++;

        }
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    Solution s;
    vector<vector<int> > a={{1,2},{1,3},{1,8},
                            {2,6},{3,1},{3,10}};
    s.maxNumberOfFamilies(3,a);
    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
47
48
49
50
/*
    将整数按权重排序
    2022-09-14 14:26:25
    by ergou
*/
#include<bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    struct no{
        int num,w;
        bool operator<(const no& p)
        {
            if(w==p.w) return num<p.num;
            return w<p.w;
        }

    };
    int W(int x)
    {
        int cnt=0;
        while(x!=1)
        {
            if(x&1) x=x*3+1;
            else x/=2;
            cnt++;
        }
        return cnt;
    }
public:
    int getKth(int lo, int hi, int k) {
        vector<no> ans;
        for(int i=lo;i<=hi;i++)
            ans.push_back({i,W(i)});
        sort(ans.begin(),ans.end());
        for(auto i:ans) cout<<i.num<<" ";
        cout<<"\n";
        return ans[k-1].num;
    }
};
//leetcode submit region end(Prohibit modification and deletion)


signed  main()
{
    Solution s;
    s.getKth(12,15,2);
    return 0;
}