力扣118双周赛

第 118 场双周赛

查找包含给定字符的单词

模拟

class Solution {
public:vector<int> findWordsContaining(vector<string>& words, char x) {vector<int>res;for(int j = 0 ; j < words.size() ; j ++){bool f = false;string t = words[j];for(int i = 0 ; i < t.size() ; i ++){if(t[i] == x)f = true;}if(f)res.push_back(j);}return res;}
};

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

长和宽分别找最长的连续部分，取最小相乘

class Solution {
public:int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {ranges::sort(hBars);ranges::sort(vBars);int res = 0 , a = 0 , b = 0 , c = 0;int last = -1;for(int i = 0 ; i < hBars.size() ; i ++){if(last == -1){last = hBars[i] ; a = max(a , 1); c = 1;continue;}if(hBars[i] - last == 1){c ++;}else{a = max(a , c);c = 1;}last = hBars[i];}a = max(a , c);last = -1;for(int i = 0 ; i < vBars.size() ; i ++){if(last == -1){last = vBars[i] ; b = max(b , 1); c = 1;continue;}if(vBars[i] - last == 1){c ++;}else{b = max(b , c);c = 1;}last = vBars[i];          }b = max(b , c);res = (min(a,b) + 1) * (min(a,b) + 1);return res;}
};

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

用dp[i][0]表示买前i个水果且不买第i个水果的最少金币数
用dp[i][1]表示买前i个水果且买第i个水果的最少金币数

class Solution {
public:int minimumCoins(vector<int>& prices) {int n = prices.size();int dp[1005][2];//初始化for(int i = 0 ; i <= n ; i ++){dp[i][0] = dp[i][1] = 999999;}dp[1][1] = prices[0];//dpfor(int i = 1 ; i < n ; i ++){//买第i个dp[i + 1][1] = min(dp[i][0] ,dp[i][1]) + prices[i];//不买第i个for(int j = i; j + j >= i  + 1; j --){dp[i + 1][0] = min(dp[i + 1][0] , dp[j][1]);}}return min(dp[n][0],dp[n][1]);}
};

找到最大非递减数组的长度

后面补题

–