Re: [閒聊] 每周leetcode

[oin1104 (是oin的說)]

https://i.imgur.com/HxG7TRf.png

我要衝擊徽章了 家人們



第一題:
每一次都(max+min)/2
求最小的

思路:
sort 然後姆咪


```cpp
class Solution {
public:
    double minimumAverage(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        vector<double> paper;

        for(int i = 0 ; i < len/2 ; i ++)
        {
            paper.push_back( ((double)nums[i] + (double)nums[len-i-1])/2.0 );
        }

        double p = paper[0];
        for(int i = 0 ; i < len/2 ; i ++)
        {
            p = min(paper[i],p);
        }

        return p;
    }
};
```

第二題:
找一個矩形把所有1都覆蓋

思路:
上下左右往中間找
我好像寫超醜

```cpp
class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) 
    {

        int n = grid.size();
        int m = grid[0].size();

        int u = 0;
        int d = n-1;
        int l = 0;
        int r = m-1;

        for( ; u < n ; u ++ )
        {
            int ok = 0;
            for(int i = 0 ; i < m ; i ++)
            {
                if(grid[u][i] == 1)ok = 1;
            }
            if(ok)break;
        }

        for( ; d >= 0 ; d -- )
        {
            int ok = 0;
            for(int i = 0 ; i < m ; i ++)
            {
                if(grid[d][i] == 1)ok = 1;
            }
            if(ok)break;
        }

        for( ; l < m ; l ++ )
        {
            int ok = 0;
            for(int i = 0 ; i < n ; i ++)
            {
                if(grid[i][l] == 1)ok = 1;
            }
            if(ok)break;
        }

        for( ; r >= 0 ; r -- )
        {
            int ok = 0;
            for(int i = 0 ; i < n ; i ++)
            {
                if(grid[i][r] == 1)ok = 1;
            }
            if(ok)break;
        }

        return (d-u+1) * (r-l+1);

    }
};
```



第三題:
可以把陣列分成好多子陣列
每個子陣列都是1-2+3-4+5的順序加起來
問全部加起來最大多少

思路:
跟股票啥的有點像
分成兩排 
因為其實 [1,2][3,4]根本就跟[1,2,3,4]一樣
所以
一排就是當子陣列開頭
一排當子陣列結尾

每次的開頭都可以從上次的開頭拿 或是上次的結尾拿
每次結尾只能去開頭接

然後我把long long 寫成int
操機掰
多五分鐘
我吐了


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

        int len = nums.size();
        
        vector<vector<long long>> paper(len , vector<long long>(2,0) );

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

        return max(paper[len-1][0],paper[len-1][1]);
    }
};```




第四題:
給你一個2d陣列
叫你把全部的1塞進三個矩形裡面
不能塞到0

思路:
沒有
我去死




這題好像是前綴和 + 分治

一個半小時誰寫的玩

我哭了




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.142.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719116028.A.098.html
推 rainkaras: 7
推 sustainer123: 你怎麼那麼猛
推 DJYOMIYAHINA: 別捲了
推 SecondRun: 大師 995
→ oin1104: 二跑葛格 教我unity