logoChat01.ai

class Solution { public: int findMaximizedCapi...

Erstellt am: 30. Mai 2026

Beantwortet mit GPT-5.5 Thinking von Chat01

Frage

class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
int n=profits.size();
vector<pair<int,int>> proj;
for(int i=0;i<n;i++){
proj.push_back({capital[i],profits[i]});
}
priority_queue<int> pq;
int idx=0;
int res=0;
while(k--){
while(idx<n){
if(proj[idx].first>w) break;
pq.push(proj[idx].second);
}
if(pq.empty()) return w;
w=w+pq.top();
pq.pop();
// k--;
}
return w;
}
}; fix this

Gedanke

Thought for a couple of seconds

Antwort

You need to sort projects by required capital and increment idx inside the inner loop. Otherwise, idx never changes and the loop can become infinite.

cpp
class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();

        vector<pair<int, int>> proj;
        for (int i = 0; i < n; i++) {
            proj.push_back({capital[i], profits[i]});
        }

        sort(proj.begin(), proj.end());

        priority_queue<int> pq;
        int idx = 0;

        while (k--) {
            while (idx < n && proj[idx].first <= w) {
                pq.push(proj[idx].second);
                idx++;
            }

            if (pq.empty()) return w;

            w += pq.top();
            pq.pop();
        }

        return w;
    }
};

Main fixes:

cpp
sort(proj.begin(), proj.end());

and inside the inner loop:

cpp
idx++;

Without idx++, the same project keeps getting pushed forever.

Frage

class Solution {
public:
struct cmp {
bool operator()(pair<int,int>& a, pair<int,int>& b) {
if(a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
};

text
int lastStoneWeight(vector<int>& stones) {
    unordered_map<int,int> f;
    int n=stones.size();
    priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
    for(int i=0;i<n;i++){
        f[stones[i]]++;
    }
    for(auto i:f){
        int key =i.first;
        int freq=i.second;
        pair<int,int> curr={key,freq};
        pq.push(curr);
    }
        while(pq.size()>1) {
        if(pq.top().second==1){
            int x=pq.top().first;
            pq.pop();
            if(pq.top().second==1){
                int y=pq.top().first;
                pq.pop();
                pq.push({x-y,1});
            }
            else{
                int z=pq.top().first;
              int c= pq.top().second-1;
              pq.pop();
              pq.push({z,c});
                pq.push({x-z,1});
            }
        }
        else{
            int m=pq.top().first;
           int l= pq.top().second;
           l--;
            if(l==1) pq.pop();
        }
    }
    if(pq.empty()) return 0;
    if(pq.top().second==0)  return 0;
    return pq.top().first;
}

}; fix this

Gedanke

Thought for a couple of seconds

Antwort

Use a simple max-heap of stone weights. You do not need frequency pairs here.

cpp
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;

        for (int stone : stones) {
            pq.push(stone);
        }

        while (pq.size() > 1) {
            int x = pq.top();
            pq.pop();

            int y = pq.top();
            pq.pop();

            if (x != y) {
                pq.push(x - y);
            }
        }

        return pq.empty() ? 0 : pq.top();
    }
};

Why your code was breaking:

cpp
pq.push({x - y, 1});

can push 0, which should not be added.

Also here:

cpp
else {
    int m = pq.top().first;
    int l = pq.top().second;
    l--;
    if(l==1) pq.pop();
}

you reduce l, but you never update the heap with the new frequency. Also, when two equal stones are smashed, the frequency should decrease by 2, not 1.

The heap-only solution is the cleanest and accepted approach.

Diesen Q&A teilen