力扣第118场双周赛

b.最大化网格图中正方形空洞的面积

2943. 最大化网格图中正方形空洞的面积

为什么没写出来啊, 布吉岛啊好奇怪, 补题一发过啊 QAQ

就 排序后统计连续数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int so(vector<int>& v){
        int n=v.size();
        int i=1;
        int ans=1;
        while(i<n){
            int c=1;
            while(i<n && v[i-1]+1==v[i]){i++;c++;}
            ans=max(c,ans);
            i++;
        }
        return ans;
    }
    int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {
        sort(hBars.begin(),hBars.end());
        sort(vBars.begin(),vBars.end());
        int x=so(hBars),y=so(vBars);
        int ans=min(x,y)+1;
        return ans*ans;
    }
};

c.购买水果需要的最少金币数

2944. 购买水果需要的最少金币数

简单dp, 为什么不会啊, 不知道啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int dp[1005]={0};
    int minimumCoins(vector<int>& prices) {
        int n=prices.size();
        for(int i=1;i<=prices.size();i++){
            for(int j=i;j<=min(i+i,n);j++){
                if(dp[j]) dp[j]=min(dp[j],dp[i-1]+prices[i-1]);
                else dp[j]=dp[i-1]+prices[i-1];
            }
        }
        return dp[n];
    }
};

一个错误的思路:

​ 贪心:遍历数组,加起来如果比前面的值大就ans++, 否则继续加直到大于前面的树

被这个样例给挂了

1
[272,482,115,925,983]

d .看不太懂题解