Leetcode Biweekly Contest 145

[oin1104 (是oin的說)]

幹 我第三題差一點寫出來
我就錯在用string紀錄的數字
4位數變成的3位數不能變回4位數
幹你娘
我快哭了
差點進1000名
不過這次2500
大概是+0分
ㄏ

第一題
題目看超久 超難看懂
反正就暴力

```cpp
class Solution {
public:
    int minOperations(vector<int>& nums, int k)
    {

        int n = nums.size();

        for(int i : nums)if(i < k)return -1;

        vector<int> paper(101,0);

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

        int res = 0;
        for(int i = k+1 ; i <= 100 ; i ++)
        {
            if(paper[i] > 0)res ++;
        }

        return res;

    }
};
```

第二題
用n!的方法檢查每種組合

```cpp
class Solution {
public:

    vector<int> lock ;
    int n ;
    int mintime;
    int k ;


    void find( vector<int> &save , int now , int time  , int x )
    {
        if(now == n)
        {
            mintime = min(mintime , time);
        }

        for(int i = 0 ; i < n ; i ++)
        {
            if(save[i] == 0)
            {
                save[i] = 1;
                int cost = lock[i]/x;
                if(lock[i]%x > 0)cost ++;
                find(save , now + 1 , time + cost , x+k  );

                save[i] = 0;
            }
        }

    }


    int findMinimumTime(vector<int>& strength, int K)
    {
        n = strength.size();

        lock = strength;
        mintime = INT_MAX;
        k = K;

        vector<int> saa(n,0);
        find(saa , 0 , 0 , 1);

        return mintime;
    }
};
```


第三題
用bfs+pq
其實可以把他當成在數字做成的n維空間中
用每次的cost來Dijkstra
然後記得不做質數就好

class Solution {
public:

    bool isprime(int num)
    {
        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;

        for (int i = 3 ; i * i <= num ; i += 2)
        {
            if (num % i == 0) return false;
        }
        return true;
    }



    int minOperations(int n, int m)
    {

        if(isprime(m))return -1;
        int ten = to_string(n).size();


        priority_queue<pair<int,string> , vector<pair<int,string>> , greater<pai
r<int,string>> > q;
        q.push({n,to_string(n)});

        int res = INT_MAX;

        vector<int> paper(100001 , INT_MAX);


        while(!q.empty())
        {
            string nowstr = q.top().second;
            int nowint = stoi(nowstr);
            int nowt = q.top().first;


            // cout << nowstr << " " << nowt << " " << endl ;
            q.pop();

            if(nowint == m)return nowt;
            if( isprime(nowint) ) continue;


            int first = 0;
            for(int i = 0 ; i <  ten  ; i ++)
            {
                if(nowstr[i] == '0' && first == 0)
                {
                    continue;
                }
                first = 1;
                if(nowstr[i] == '9')
                {
                    string hi = nowstr;
                    hi[i] --;
                    int hint = stoi(hi);
                    if(isprime(hint))continue;
                    int nxtt = nowt + hint;
                    if(paper[hint] > nxtt)
                    {
                        paper[hint] = nxtt;
                        q.push({nxtt,hi});
                    }
                }
                else if(nowstr[i] == '0')
                {
                    string hi = nowstr;
                    hi[i] ++;
                    int hint = stoi(hi);
                    if(isprime(hint))continue;
                    int nxtt = nowt + hint;
                    if(paper[hint] > nxtt)
                    {
                        paper[hint] = nxtt;
                        q.push({nxtt,hi});
                    }
                }
                else
                {
                    string hi = nowstr;
                    hi[i] ++;
                    int hint = stoi(hi);
                    if(!isprime(hint))
                    {
                        int nxtt = nowt + hint;
                        if(paper[hint] > nxtt)
                        {
                            paper[hint] = nxtt;
                            q.push({nxtt,hi});
                        }
                    }
                    hi[i] -=2;
                    int hint2 = stoi(hi);
                    if(!isprime(hint2))
                    {
                        int nxtt2 = nowt + hint2;
                        if(paper[hint2] > nxtt2)
                        {
                            paper[hint2] = nxtt2;
                            q.push({nxtt2,hi});
                        }
                    }
                }
            }
        }

        if(paper[m] == INT_MAX)return -1;
        return paper[m];

    }
};


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.41.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733590549.A.2A8.html
推 altecaux: 不可以動不動就哭 尼是小件貨 哭ㄌ會心疼
→ oin1104: 嗚嗚嗚哇哇哇
推 mrsonic: 你是啞巴嗎