LeetCodeWeeklyContest-174

タイトル転送:第174週試合
Rank:789/1659 Grade:7/18がんばれ!力ボタンが改版されたようで、前の週の試合が終わってから、まだ入ることができて、今終わってから直接問題庫に入って、悪くないようですね~
1.方陣の中で最も戦闘力の弱いK行
レコードを1つの構造体で保存し、ソートの比較関数をカスタマイズし、問題に署名します.

struct node{
	int index;
	int armynum;
};
bool cmp(node a,node b){
	if(a.armynum!=b.armynum)
		return a.armynum < b.armynum;
	else  return a.index < b.index; 
}
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
	    int m = mat.size(),n = mat[0].size();
	    node arr[m];
        memset(arr,0,sizeof(arr));
	    for(int i=0;i<m;i++){
	 	    arr[i].index = i;
	 	    for(int j=0;j<n;j++){
	 		    if(mat[i][j]==1) arr[i].armynum ++;
		    }
	    } 
        
	    sort(arr,arr+m,cmp);
	    vector<int> res;
	    for(int i=0;i<k;i++){
		    res.push_back(arr[i].index);
	    }  
	    return res;    
    }
};

2.配列サイズ半減
最小要素の個数を見つけると、集合内の要素の個数を半減させることができます.各要素に現れる個数を統計し、個数を減算して並べ替え、半減するまで個数配列を巡回します...

class Solution {
public:
    int minSetSize(vector<int>& arr) {
 	sort(arr.begin(),arr.end());
    int n = arr.size(),cnt = 1;
 	vector<int> res;
 	
    for(int i=1;i<n;i++){
		if(arr[i-1]!=arr[i]){
			res.push_back(cnt);
			cnt = 1;
		}
		else cnt ++;
	}
    res.push_back(cnt);
    // for(int i=0;i
    //     cout << res[i] << " ";
	sort(res.begin(),res.end(),greater<int>());
	int ans = 0,r=0;
	for(int i=0;i<res.size();i++){
		ans += res[i],r++;
		if(ans>=n/2){
			return r;
		}
	}
    return n;
 }
};

3.分岐ツリーの最大積
やはり検索するか、dfstotal関数は木の和を求めるために使われているので、2番目のdfs関数は考えにくいと思います.

typedef  long long ll;
class Solution {
    ll total = 0,ans=0,mod=1e9+7;
    void  dfstotal(TreeNode *root){
        if(root==NULL) return ;
        total += root->val;
        dfstotal(root->left);
        dfstotal(root->right);
    }
    ll dfs(TreeNode* root){
        if(root==NULL) return 0;
        ll suml = dfs(root->left),sumr = dfs(root->right);
        ans = max(ans,suml*(total-suml));
        ans = max(ans,sumr*(total-sumr));
        return root->val+suml+sumr;
    }
public:
    int maxProduct(TreeNode* root) {
        dfstotal(root);
        dfs(root);
        return ans%mod;
        
    }
};

4.ジャンプゲームV
参考:dp記憶化検索f[i]は、下付きiからアクセスできる最大要素数を示しており、タイトル要求は高いところから低いところへしかジャンプできないが、中にはもっと高いものはない.中には多くの繰り返し計算が含まれており、f[i]配列で記録することができ、つまり記憶化することができ、f[i]に値があれば、検索する必要はありません.

#define N 100050
int f[N],a[N];
int dfs(int i,int d,int n){
    if(f[i]!=-1) return f[i];
    f[i] = 1;
    for(int u=i+1;u-i<=d&&u<n;u++){
        if(a[u]>=a[i]) break;
        f[i] = max(f[i],1+dfs(u,d,n));
    }
    for(int u=i-1;u>=0&&i-u<=d;u--){
        if(a[u]>=a[i]) break;
        f[i] = max(f[i],1+dfs(u,d,n));
    }
    return f[i];   
}
class Solution {
public:
int maxJumps(vector<int>& arr, int d) {
   	int n = arr.size(),ans = 0;
    for(int i=0;i<n;i++) a[i] = arr[i];
    memset(f,-1,sizeof(f));
    for(int i=0;i<n;i++){
        ans = max(ans,dfs(i,d,n));
    }
	 return ans;
}
};