Leetcode Weekly Contest 442

[oin1104 (是oin的說)]

感覺開學之後
最近比較少刷題
分數就卡在1900左右了
感覺沒有特別來練習的話有點難進步
不過每天都有寫的話
至少不太會退步
0.0




Q1 能放多少箱子

思路
暴力
沒什麼特別的

```cpp
class Solution {
public:
    int maxContainers(int n, int w, int maxWeight)
    {

        int res = 0;
        int now = 0;

        while(now+w <= maxWeight  && res < n*n)
        {
            res ++;
            now += w;
        }

        return res;

    }
};
```


Q2
有k個相同的數字的話就可以連在一起
請問有幾團連在一起的

思路
union find + 一個用水桶來判斷相同數字的函式
最後看有幾團就好


```cpp

class UnionFind {
    vector<int> par, cnt;
public:
    UnionFind(int n): par(n, -1), cnt(n, 1) { }
    int find(int a) {
        if(par[a] == -1) return a;
        return par[a] = find(par[a]);
    }
    bool un(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if(pa == pb) return 0;
        if(cnt[pa] < cnt[pb]) swap(pa, pb);
        cnt[pa] += cnt[pb];
        par[pb] = pa;
        return 1;
    }
};


class Solution {
public:

    int intersect(vector<int>& a,vector<int>& b)
    {
        int re = 0;
        for(int i = 0 ; i < 101 ; i ++)
        {
            if(a[i] >0 && b[i] > 0)re++;
        }

        return re;

    }

    int numberOfComponents(vector<vector<int>>& properties, int k)
    {

        int n = properties.size();
        UnionFind uf(n);

        vector<vector<int>> paper(n, vector<int>(101, 0));

        for(int i = 0 ; i < n ; i ++)
        {
            for(int j : properties[i])
            {
                paper[i][j]++;
            }
        }

        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = i+1 ; j < n ; j ++)
            {
                if(intersect(paper[i] , paper[j]) >= k)
                {
                    // cout << intersect(properties[i] , properties[j]) << endl;
                    uf.un(i,j);
                }
            }
        }

        unordered_set<int> fgo;
        for(int i = 0 ; i < n ; i ++)
        {
            fgo.insert({uf.find(i)});
        }

        return fgo.size();
    }
};
```



Q3
一群巫師輪流釀藥水
時間是mana*skill
然後藥水一定要連著釀

思路
因為要每種藥水都看開始釀造的最好時機
所以用dp來慢慢推或比較方便
看每次釀藥水最快能開始釀的時候
要看的時間就是上一種藥水釀好後
下一個人能開始釀的時間

0.0


```cpp
class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana)
    {

        int n = skill.size();
        int m = mana.size();

        vector<vector<long long>> paper( m , vector<long long>(n,0) ) ;

        paper[0][0] = skill[0]*mana[0];
        for(int i = 1 ; i < n ; i ++)
        {
            paper[0][i] = skill[i]*mana[0] + paper[0][i-1];
        }

        for(int i = 1 ; i < m ; i ++)
        {
            vector<long long> now(n);
            now[0] = skill[0]*mana[i] + paper[i-1][0];
            for(int p = 1 ; p < n ; p ++)
            {
                now[p] = skill[p]*mana[i] + now[p-1];
            }
            long long shift = 0;

            for(int s = 0 ; s < n-1 ; s ++)
            {
                shift = max(shift , paper[i-1][s+1] - now[s]);
            }

            for(int x = 0 ; x < n ; x ++)
            {
                paper[i][x] = now[x] + shift;
            }


        }

        // for(int i = 0 ; i < m  ; i ++)
        // {
        //     for(int j = 0 ; j < n ; j ++)
        //     {
        //         cout << paper[i][j] << " " ;
        //     }
        //     cout << endl;
        // }


        return paper[m-1][n-1];
    }
};

//   1  5  2  4
// 5 5  30 40 60
// 1 1  5  7  4
//   29 35 53
// 4
// 2
```


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.40.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1742714314.A.6A4.html
推 DJYOMIYAHINA: 我想s
推 sustainer123: 大師