Leetcode Weekly Contest 419

[oin1104 (是oin的說)]

幹
我1700名
我有徽章了

抽插Knight
抽插左手

爽


Q1
有一串陣列
對於每個長度k的子陣列
留下前x多的元素
如果一樣多的話數字大的優先留下
請問每個子陣列的和是多少

思路:
暴力找出每個子陣列之後
再直接暴力拿出最小的直到剩下x種元素

```cpp


class Solution {
public:
    vector<int> findXSum(vector<int>& nums, int k, int x)
    {

        int n = nums.size();

        vector<int> res(n-k+1);

        int l = 0;
        int r = 0;
        for(int i = 0 ; i < n-k+1 ; i ++)
        {
            vector<int> tmp(51,0);
            int cnt = 0;
            for(int j = i ; j < i+k ; j ++)
            {
                if(tmp[nums[j]] == 0)cnt ++;
                tmp[nums[j]]++;
            }
            // cout << "??" << cnt << endl;

            while(cnt > x)
            {
                //cout << " ?????? " << endl;
                int mi = 0;
                int micnt = 100;

                for(int k = 0 ; k < 51 ; k ++)
                {
                    if(tmp[k] == 0)continue;
                    if(tmp[k] < micnt)
                    {
                        // cout << " ?????? " << endl;
                        micnt = tmp[k];
                        mi = k;
                    }
                }
                tmp[mi] = 0;
                cnt --;
            }

            for(int k = 0 ; k < 51 ; k ++)
            {
                // cout << tmp[k] << endl;
                res[i] += tmp[k] * k;
            }
        }


        return res;
    }
};
```

Q2
一個完美平衡二元樹
就是他的左邊跟右邊節點一樣多 層數也一樣
找出所有的完美平衡二元樹
跟他們的節點數量
請問第x多的樹有幾個節點

思路:
遞迴 而且要用pii記節點數量跟層數
每次的判斷都可以用左邊右邊的遞迴做
條件就是看數量跟層數有沒有一樣
一樣的話要去全域變數紀錄
不一樣就-1,-1
遇到空節點回傳0,0

弄完之後sort看有沒有x個
然後回傳答案

```cpp
/**
 * 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), ri
ght(right) {}
 * };
 */
class Solution {
public:

    vector<int> save;

    //  cnt  layer
    pair<int,int> find(TreeNode* root)
    {
        if(root == NULL)return {0,0};

        pair<int,int> l = find(root->left);
        pair<int,int> r = find(root->right);

        if(l.first == -1)return {-1,-1};
        if(r.first == -1)return {-1,-1};
        if(l.second != r.second)return {-1,-1};


        save.push_back(l.first+r.first+1);


        return {l.first+r.first+1,r.second+1};


        return {-1,-1};
    }


    int kthLargestPerfectSubtree(TreeNode* root, int k)
    {

        save.clear();

        find(root);

        sort(save.begin(),save.end(),greater<int>());
        if(k > save.size())return -1;

        return save[k-1];

    }
};
```

Q3
Alice 跟 Bob 玩剪刀石頭布
Bob不能連續出兩種一樣的
Alice每個小場會出的都記錄在陣列裡
你只要小場總共贏得次數比他多
就算是你大場贏了
請問Bob有幾種大場贏得方式

思路:
DP
而且用map記錄 {勝場 , 數量}
記錄Bob最後一個出的種類
每次更新都看另外兩種拳的勝場跟數量
這種種類會不會贏 = k
這種種類的map[勝場+k] += 別種的數量
加到最後
再全部看>1的有多少

我寫超醜

```cpp
class Solution {
public:

    int win(char A , char B)
    {
        if(A == B)return 0;
        if(A == 'F' )
        {
            if(B == 'E') return -1;
            return 1;
        }
        if(A == 'W' )
        {
            if(B == 'F') return -1;
            return 1;
        }
        if(A == 'E' )
        {
            if(B == 'W') return -1;
            return 1;
        }
        return 0;
    }

    int countWinningSequences(string s)
    {

        int n = s.size();

        unordered_map<long long,long long> F;
        unordered_map<long long,long long> W;
        unordered_map<long long,long long> E;

        F.insert({win(s[0],'F') , 1});
        W.insert({win(s[0],'W') , 1});
        E.insert({win(s[0],'E') , 1});

        for(int i = 1 ; i < n ; i ++)
        {
            int fwin = win(s[i],'F');
            unordered_map<long long,long long> Ftmp;
            for(auto k : W)
            {
                Ftmp[k.first+fwin] += k.second;
                Ftmp[k.first+fwin] %= 1000000007;
            }
            for(auto k : E)
            {
                Ftmp[k.first+fwin]+= k.second;
                Ftmp[k.first+fwin] %= 1000000007;
            }

            int Wwin = win(s[i],'W');
            unordered_map<long long,long long> Wtmp;
            for(auto k : F)
            {
                Wtmp[k.first+Wwin]+= k.second;
                Wtmp[k.first+Wwin] %= 1000000007;
            }
            for(auto k : E)
            {
                Wtmp[k.first+Wwin]+= k.second;
                Wtmp[k.first+Wwin] %= 1000000007;
            }

            int Ewin = win(s[i],'E');
            unordered_map<long long,long long> Etmp;
            for(auto k : W)
            {
                Etmp[k.first+Ewin]+= k.second;
                Etmp[k.first+Ewin] %= 1000000007;
            }
            for(auto k : F)
            {
                Etmp[k.first+Ewin]+= k.second;
                Etmp[k.first+Ewin] %= 1000000007;
            }

            F = Ftmp;
            W = Wtmp;
            E = Etmp;
        }

        int res = 0;
        for(auto k : F)
        {
            if( k.first > 0)
            {
                res += k.second % 1000000007;
                res %= 1000000007;
            }
        }
        for(auto k : W)
        {
            if( k.first > 0)
            {
                res += k.second % 1000000007;
                res %= 1000000007;
            }
        }
        for(auto k : E)
        {
            if( k.first > 0)
            {
                res += k.second % 1000000007;
                res %= 1000000007;
            }
        }

        return res%1000000007;
    }
};
```

Q4

我沒時間了 連題目都沒看

姆咪




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.19.26 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728797268.A.74E.html
推 Furina: 我好崇拜你
→ Sougou: 東大資工就屬芋圓最強大
→ oin1104: 亂講 我室友2500 我才1800
推 sixB: 我真的很崇拜你
→ Sougou: 東大資工現在這麼卷喔
→ oin1104: 六比哥哥 你是大師
→ Sougou: 東大資工當時學測不高啊
→ oin1104: 我認識另一個2300 的學長 很扯
→ Sougou: 靠，這麼卷了嗎？我當時念的時候沒這麼優秀啊
→ oin1104: 我感覺東華落差很大 有人利扣2500 有人作業寫不出來 本
→ oin1104: 科程式設計被當
推 sustainer123: 好扯= = 東大那麼卷 幹 我真的還很廢
→ oin1104: 我只認識這兩個很捲的 其他都普通
推 Sougou: 這兩個台清交資工碩有沒有望
→ oin1104: 保底吧
→ Sougou: 大神了
→ devilkool: 我屬於廢物的那邊
→ devilkool: Q4就是Q1的long版，我Q1寫法調一點去跑就TLE
→ oin1104: 我看別人是做一個容器 開兩個set 跟一個map 然後紀錄紀
→ oin1104: 錄轉換轉換
→ rainkaras: 大師
推 Che31128: 大師
推 DJYOSHITAKA: 大師...