Leetcode Weekly Contest 415

[oin1104 (是oin的說)]

我徽章沒了

下次再復仇

這次是題目太搞

faker也有版本不合的時候

你們給我等著


第一題
這兩個重複的數字

思路
建表遍歷後查詢

```cpp
class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums)
    {
        vector<int> res;
        int n = nums.size();

        int paper[101] = {};

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

        for(int i = 0 ; i < 101 ; i ++)
        {
            if(paper[i] == 2)res.push_back(i);
        }

        return res;

    }
};
```

第二題
給你a陣列有四個數字
要跟b陣列的很多數字
依照“順序”相乘之後 加起來
能得到的最大數字是多少


思路
用dp
紀錄上一層最大的同時更新新的可能

```cpp
class Solution {
public:
    long long maxScore(vector<int>& a, vector<int>& b)
    {
        int an = a.size();
        int bn = b.size();

        vector<vector<long long>> paper(an,vector<long long> (bn , 0));

        for(int j = 0 ; j < bn-3 ; j ++)
        {
            paper[0][j] = (long long)a[0] * (long long)b[j];
        }

        for(int i = 1 ; i < 4 ; i ++)
        {
            long long mv = paper[i-1][i-1];
            for(int j = i ; j < bn-3+i ; j ++)
            {
                long long now = (long long)a[i] * (long long)b[j];
                paper[i][j] = now + mv;
                mv = max(paper[i-1][j],mv);
            }
        }

        long long res = paper[3][3];

        for(int i = 3 ; i < bn ; i ++)
        {
            res = max(res,paper[3][i]);
        }

        return res;
    }
};
```

第三題
可以用words裡面的字的前綴
要用多少次才可以組合出target

思路
用set記錄
但是我超記憶體了
因為字太多
我吐了


```cpp
class Solution {
public:
    int minValidStrings(vector<string>& words, string target)
    {

        unordered_set<string> save;
        int n = target.size();

        for(string k : words)
        {
            int len = k.size();
            for(int i = 1 ; i <= len ; i ++)
            {
                save.insert(k.substr(0,i));
            }
        }

        vector<int> paper(n+1,99999999);
        paper[0] = 0;

        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = i ; j >= 0 ;j --)
            {
                string now = target.substr(j,i-j+1);

                if(save.find(now) != save.end())
                {
                    paper[i+1] = min(paper[i+1] , paper[j]+1);
                }
            }
        }



        if(paper[n] == 99999999)return -1;
        return paper[n];
    }
};
```








--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.18.55 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726373304.A.5E6.html
推 sustainer123: 還好我沒打
推 mrsonic: 你好沒用
推 DJYOMIYAHINA: 我去死
推 enmeitiryous: 我好爛
→ wu10200512: 你好強
→ SydLrio: 你有什麼用
→ dont: 還好我沒打