Leetcode Weekly Contest 423

[oin1104 (是oin的說)]

昨天耍白痴
2000名變7000名
因為我寫錯一個地方
幹你娘

今天還不錯
不過一直出錯
有夠靠北
直接錯8次+40分鐘
不過還是2500名

爽


第一題
找兩個相鄰的子陣列
他們都是遞增的

思路
暴力找


```cpp
class Solution {
public:
    bool hasIncreasingSubarrays(vector<int>& nums, int k)
    {
        int n = nums.size();
        if(k == 1 && n > 1)return 1;

        int a = 0;
        int b = 0;
        for(int i = 0 ; i+2*k-1 < n ; i ++)
        {
            int ok = 1;
            a = i;
            b = a+k;
            // cout << nums[a] << " " << nums[b] << endl;

            for(int j = 0 ; j < k-1 ; j ++)
            {
                if(nums[a+j] >= nums[a+j+1])ok = 0;
                if(nums[b+j] >= nums[b+j+1])ok = 0;
                // cout << nums[a+j] << " " << nums[b+j] << endl;
            }
            if(ok)return 1;
        }

        return 0;

    }
};
```

第二題
這次要在陣列裡面找最長的
兩個相鄰遞增陣列
的k值

思路
直到怎麼找之後
直接用二分搜找k值
結果超時
把找的方法改一下
改成用prefix紀錄遞增的方式
就過了

```cpp
class Solution {
public:

    vector<int> paper;

    bool hi( int k)
    {
        int n = paper.size();
        if(k == 1 && n > 1)return 1;

        for(int i = 0 ; i+2*k-1 < n ; i ++)
        {
            int a = i + k-1;
            int b = a + k;

            if(paper[a] >= k && paper[b] >= k)return 1;
        }

        return 0;
    }

    int maxIncreasingSubarrays(vector<int>& nums)
    {
        int len = nums.size();
        int l = 1 ;
        int r = len/2;
        paper.resize(len,1);

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

        // for(int i = 0 ; i < len ; i ++)cout << paper[i] << " ";


        while(l<=r)
        {
            int m = (l+r)/2;
            if(hi(m))
            {
                l = m+1;
            }
            else
            {
                r = m-1;
            }
        }

        return r;
    }
};
```


第三題
要找所有subsequence
就是可以刪子陣列的元素但不改變順序
要讓他們相鄰元素相差小於1
然後把全部subsequence裡的元素加起來
問你是多少

思路
因為要一直看之前出現的數字
只要看+1-1
所以很適合用map dp
然後是dp的思路
而且要用map記錄這數字當結尾的值跟數量
每次更新都要去+1-1的地方拿值跟數量
全部加起來就好了
0.0

```cpp
class Solution {
public:
    int sumOfGoodSubsequences(vector<int>& nums)
    {

        unordered_map<long long,pair<long long,long long>> paper;
        int res = 0;

        int n = nums.size();

        for(int i = 0 ; i < n ; i ++)
        {
            res += nums[i];
            res%=1000000007;
            long long cur = 0 ;
            if(paper.find(nums[i]-1)!=paper.end())
            {
                long long tmp = (long long)paper[nums[i]-1].first + (long long)n
ums[i]*(long long)paper[nums[i]-1].second;
                paper[nums[i]].first += tmp;
                cur += tmp;
                cur %= 1000000007;
                paper[nums[i]].second += paper[nums[i]-1].second;
                paper[nums[i]].first%= 1000000007;
                paper[nums[i]].second%= 1000000007;
                // cout << "!";
            }
            if(paper.find(nums[i]+1)!=paper.end())
            {
                long long tmp = (long long)paper[nums[i]+1].first + (long long)n
ums[i]*(long long)paper[nums[i]+1].second;
                paper[nums[i]].first += tmp;
                cur += tmp;
                cur %= 1000000007;
                paper[nums[i]].second += paper[nums[i]+1].second;
                paper[nums[i]].first%= 1000000007;
                paper[nums[i]].second%= 1000000007;
                // cout << "?";
            }

            res += cur;
            res%= 1000000007;

            paper[nums[i]].first += nums[i];
            paper[nums[i]].first%= 1000000007;
            paper[nums[i]].second += 1;


            // for(auto k : paper)
            // {
            //     cout << k.first << " " << k.second.first << " " << k.second.s
econd  ;
            //     cout << endl;
            // }
            // cout <<  res << endl;
        }

        // for(auto k : paper)
        // {
        //     cout << k.first << " " << k.second ;
        //     cout << endl;
        // }

        return res;
    }
};
```





--

我是小黃瓜
https://i.imgur.com/1YMQtyf.jpeg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.167.248 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731219659.A.8CB.html
→ DJYOMIYAHINA: 我好崇拜你
推 dont: 大師