建筑公司网站石家庄,网站建设 朝阳区,在线小程序,怎么做免费的企业网站第 118 场双周赛 文章目录 第 118 场双周赛查找包含给定字符的单词最大化网格图中正方形空洞的面积购买水果需要的最少金币数找到最大非递减数组的长度 查找包含给定字符的单词
模拟
class Solution {
public:vectorint findWordsContaining(vectorstringint findWordsContaining(vectorstring words, char x) {vectorintres;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, vectorint hBars, vectorint 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(vectorint 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]);}
};找到最大非递减数组的长度
后面补题 –
