第 22 场双周赛

Posted on | In , | |
Words count in article: 531 | Reading time ≈ 3

5348. 两个数组间的距离值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int count = 0;
        for(int i=0; i<arr1.size(); i++) {
            int f = 0;
            for(int j=0; j<arr2.size(); j++) {
                if(abs(arr1[i]-arr2[j]) <= d) {
                    f = 1;
                    break;
                }
            }
            if(f == 0) count++;
        }
        return count;
    }
};

5349. 安排电影院座位

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
class Solution {
public:
    int cnt=0;
    map<int,int> id;
    vector<int> r[10010];
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        for(int i=0;i<reservedSeats.size();++i)
        {
            vector<int> a=reservedSeats[i];
            if(id[a[0]]==0)id[a[0]]=++cnt;
            r[id[a[0]]].push_back(a[1]);
        }
        int ans=0;
        for(int i=1;i<=cnt;++i)
        {
            bool c1=1,c2=1,c3=1;
            for(int j=0;j<r[i].size();++j)
            {
                if(r[i][j]==2)c1=0;
                if(r[i][j]==3)c1=0;
                if(r[i][j]==4)c1=c2=0;
                if(r[i][j]==5)c1=c2=0;
                if(r[i][j]==6)c3=c2=0;
                if(r[i][j]==7)c3=c2=0;
                if(r[i][j]==8)c3=0;
                if(r[i][j]==9)c3=0;
            }
            if(c1&&c3){ans+=2;continue;}
            if(c1 || c2 || c3)ans++;
        }
        return (long long)(n-cnt)*2+ans;
    }
};

5350. 将整数按权重排序

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
unordered_map<int, int> mp;
int get(int x) {
    if(mp.find(x) != mp.end()) return mp[x];
    int ret = 0;
    while(x != 1) {
        if(x % 2==0) x = x/2;
        else x = 3*x+1;
        ret++;
    }
    mp[x] = ret;
    return ret;
}

class Solution {
public:
    static bool cmp(int a, int b) {
        int cura = get(a);
        int curb = get(b);
        if(cura == curb) return a < b;
        return cura < curb;
    }
    int getKth(int lo, int hi, int k) {
        vector<int> tmp;
        for(int i=lo; i<=hi; i++) {
            tmp.push_back(i);
        }
        sort(tmp.begin(), tmp.end(), cmp);
        return tmp[k-1];
    }
};

5351. 3n 块披萨

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int f[500][500][2];
    int maxSizeSlices(vector<int>& slices) {
        memset(f,0,sizeof(f));
        f[1][1][1]=slices[0];
        for(int i=2;i<=slices.size();++i)
        {
            for(int j=1;j<=max(i,(int)slices.size()/3);++j)
            {
                f[i][j][0]=f[i-1][j][0];
                f[i][j][1]=f[i-1][j][1];
                f[i][j][0]=max(f[i][j][0],f[i-2][j-1][0]+slices[i-1]);
                f[i][j][1]=max(f[i][j][1],f[i-2][j-1][1]+slices[i-1]);
            }
        }
        return max(f[slices.size()][slices.size()/3][0],f[slices.size()-1][slices.size()/3][1]);
    }
};
Donate? comment?