Leetcode Weekly Contest 426

[oin1104 (是oin的說)]

幹你娘咧
我寫的真的太慢
然後第三四題題目看的又慢
中間還分心去找jiwp調情

我就差一點點時間寫出第四題
我只差三分鐘就能AK了
操
我快哭了

不過還是有2000名
大概+個10分

0.0

sixb哥哥真的好厲害...


第一題
超水
直接做

```cpp
class Solution {
public:
    int smallestNumber(int n)
    {

        int res =1;

        while(res < n)
        {
            res <<= 1;
            res += 1;
        }

        return res;

    }
};
```

第二題
要找一個特別的數字 拿出來之後
讓其他數字能夠全部加起來剛好有一個數字是他的一半

思路
排序加起來之後用hash紀錄就很好寫了
其實不用排序

```cpp
class Solution {
public:
    int getLargestOutlier(vector<int>& nums)
    {
        int n = nums.size();
        unordered_map<int,int> save;

        sort(nums.begin() , nums.end());

        vector<int> paper(n , 0);
        paper[0] = nums[0];

        save[nums[0]] ++;
        for(int i = 1 ; i < n ; i ++)
        {
            paper[i] = paper[i-1] + nums[i];
            save[nums[i]] ++;
        }


        for(int i = n-1 ; i >= 0 ; i --)
        {
            if((paper[n-1] - nums[i]) % 2 != 0 )continue;
            save[nums[i]] --;
            if( save[(paper[n-1] - nums[i])/2] > 0  )return nums[i];
            save[nums[i]] ++;
        }

        return 0;
    }
};
```


第三題
有兩顆樹
可以把一個點連到另一顆樹的隨便一個點
問你距離小於k的最多的節點是多少

```cpp
class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>&
 edges2, int k)
    {
        int n1 = edges1.size()+1;
        int n2 = edges2.size()+1;

        vector<int> cnt1(n1 , 0);
        unordered_map<int,vector<int>> path1;
        for(vector<int> k1 : edges1)
        {
            path1[k1[0]].push_back(k1[1]);
            path1[k1[1]].push_back(k1[0]);
        }

        vector<int> cnt2(n2 , 0);
        unordered_map<int,vector<int>> path2;
        for(vector<int> k2 : edges2)
        {
            path2[k2[0]].push_back(k2[1]);
            path2[k2[1]].push_back(k2[0]);
        }

        vector<int> passed1(n1,0);
        queue<pair<int,int>> q1;
        q1.push({0,i});

        while(!q1.empty())
        {
            int dist = q1.front().first;
            int idx = q1.front().second;
            q1.pop();
            if(dist > k || passed[idx] == 0) continue;
            cnt ++;
            passed[idx] = 1;
            if(dist+1 > k) continue;
            for(auto k1 : path1[idx])
            {
                if(save[k1] == 0)q1.push({dist+1,k1});
            }
        }
        for(int i = 0 ; i < n2 ; i ++)
        {
            int cnt = 0;
            vector<int> save(n2,0);
            queue<pair<int,int>> q;
            q.push({0,i});

            while(!q.empty())
            {
                int dist = q.front().first;
                int idx = q.front().second;
                q.pop();
                if(dist > k-1 || save[idx] == 1) continue;
                cnt ++;
                save[idx] = 1;
                if(dist+1 > k-1) continue;
                for(auto k2 : path2[idx])if(save[k2] == 0)q.push({dist+1,k2});
            }

            cnt2[i] = cnt;
        }
        int maxcnt = 0;
        for(int i = 0 ; i < n2 ; i ++) maxcnt = max(maxcnt , cnt2[i]);
        vector<int> res(n1,0);
        for(int i = 0 ; i < n1 ; i ++)res[i] = cnt1[i] + maxcnt;
        return res;
    }
};
```

第四題
跟第三題一樣
但是要改成距離剛好是偶數

```cpp
class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>&
 edges2)
{
        int n1 = edges1.size()+1;
        int n2 = edges2.size()+1;

        vector<int> cnt1(n1 , 0);
        unordered_map<int,vector<int>> path1;
        for(vector<int> k1 : edges1){
            path1[k1[0]].push_back(k1[1]);
            path1[k1[1]].push_back(k1[0]);
        }

        vector<int> cnt2(n2 , 0);
        unordered_map<int,vector<int>> path2;
        for(vector<int> k2 : edges2){
            path2[k2[0]].push_back(k2[1]);
            path2[k2[1]].push_back(k2[0]);
        }


        vector<int> save1(n1,0);
        queue<pair<int,int>> q1;
        q1.push({0,0});

        while(!q1.empty()){
            int dist = q1.front().first;
            int idx = q1.front().second;
            q1.pop();
            if(save1[idx] == 1) continue;

            cnt1[idx] = dist;
            save1[idx] = 1;

            for(auto k1 : path1[idx])if(save1[k1] == 0)q1.push({dist+1,k1});
        }

        vector<int> save2(n2,0);
        queue<pair<int,int>> q2;
        q2.push({1,0});

        while(!q2.empty()){
            int dist = q2.front().first;
            int idx = q2.front().second;
            q2.pop();
            if( save2[idx] == 1) continue;
            cnt2[idx] = dist;
            save2[idx] = 1;
            for(auto k2 : path2[idx])if(save2[k2] == 0)q2.push({dist+1,k2});
        }


        int maxcnt = 0;
        for(int i = 0 ; i < n2 ; i ++)if(cnt2[i]&1) maxcnt++;


        maxcnt = max(maxcnt , n2 - maxcnt);
        vector<int> res(n1,0);

        int maxcnt1_1 = 0;
        int maxcnt1_2 = 0;
        for(int i = 0 ; i < n1 ; i ++){
            if(cnt1[i]&1) maxcnt1_1++;
            else  maxcnt1_2++;
        }

        for(int i = 0 ; i < n1 ; i ++){
            if(cnt1[i]&1) res[i] = maxcnt1_1 + maxcnt;
            else  res[i] = maxcnt1_2 + maxcnt;
        }

        return res;

    }
};
```




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.163.187 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733027857.A.0EE.html
推 DJYOMIYAHINA: 我有什麼用
→ sixB: 你是準ak 大地球指日可待 我算什麼咖==