LeetCode, GeeksForGeeks Problem of the day solution
Ir al canal en Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Mostrar más1 250
Suscriptores
+224 horas
+147 días
+2930 días
Archivo de publicaciones
class Solution {
public:
vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
int n=positions.size();
map<int, int> mp;
stack<int> st;
for(int i=0;i<n;i++) {
mp[positions[i]] = i;
}
for(auto i:mp) {
int pos = i.first;
int ind = i.second;
if(directions[ind] == 'L' && st.empty()) {
continue;
} else if(directions[ind] == 'L') {
while(!st.empty() && healths[ind] != 0) {
int pInd = st.top();
st.pop();
if(healths[ind] > healths[pInd]) {
healths[ind]--;
healths[pInd] = 0;
} else if(healths[ind] < healths[pInd]) {
healths[pInd]--;
healths[ind] = 0;
st.push(pInd);
} else {
healths[ind] = 0;
healths[pInd] = 0;
}
}
} else {
st.push(ind);
}
}
vector<int> res;
for(auto i:healths) {
if(i != 0)
res.push_back(i);
}
return res;
}
};
class Solution {
public:
vector<int> shortestPath(int n, int m, vector<vector<int>>& edges) {
// Code here
vector<vector<pair<int,int>>> adj(n+1);
for(auto &it:edges){
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> dist(n+1,1e9), parent(n+1);
for(int i=1;i<=n;i++) parent[i] = i;
dist[1] = 0;
pq.push({0,1});
while(!pq.empty()){
auto it = pq.top();
int dis = it.first;
int node = it.second;
pq.pop();
for(auto &it:adj[node]){
int adjNode = it.first;
int edW = it.second;
if(dis + edW < dist[adjNode]){
dist[adjNode] = dis + edW;
pq.push({dist[adjNode],adjNode});
parent[adjNode] = node;
}
}
}
// if destination is not reachable
if(dist[n]==1e9) return {-1};
vector<int> path;
int node = n;
while(parent[node] != node){
path.push_back(node);
node = parent[node];
}
path.push_back(1);
path.push_back(dist[n]);
reverse(path.begin(),path.end());
return path;
}
};
class Solution {
public:
int maximumGain(string s, int x, int y) {
int n = s.length();
stack<char> st;
bool flag = (x > y) ? 1:0;
int res = 0;
for(int i=0; i<n; i++){
if(s[i] != ((flag)? 'b':'a'))
st.push(s[i]);
else{
if(!st.empty() && st.top() == ((flag)? 'a':'b')){
res+= (flag)? x:y;
st.pop();
}
else
st.push(s[i]);
}
}
string t = "";
while(!st.empty()){
t.push_back(st.top());
st.pop();
}
reverse(t.begin(), t.end());
for(int i=0; i<t.length(); i++){
if(t[i] != ((flag)? 'a':'b'))
st.push(t[i]);
else{
if(!st.empty() && st.top() == ((flag)? 'b':'a')){
res+= (flag)? y:x;
st.pop();
}
else
st.push(t[i]);
}
}
return res;
}
};
class Solution {
public:
// Function to find a continuous sub-array which adds up to a given number.
vector subarraySum(vector arr, int n, long long s) {
// Your code here
int right = 0;
int left = 0;
long long sum = arr[left];
while(right < n){
if(sum == s){
return {left+1,right+1};
}
else if(sum < s){
right++;
sum += arr[right];
}
else if(sum > s && left == right){
left++;
right++;
sum = arr[left];
}
else{
sum -= arr[left];
left++;
}
}
return {-1};
}
};
class Solution {
public:
bool check(vector<int>&v, int m, int mid){
int n=v.size();
int num=v[0];
int c=1;
for(int i=1; i<n; i++){
if(v[i]-num>=mid){
c++;
num=v[i];
}
}
return c>=m;
}
int maxDistance(vector<int>& v, int m) {
int n=v.size();
sort(v.begin(),v.end());
int s=1;
int ans=s;
int e=v[n-1]-v[0];
while(s<=e){
int mid=(s+e)/2;
if(check(v,m,mid)){
ans=mid;
s=mid+1;
}
else e=mid-1;
}
return ans;
}
};
class Solution {
public:
long long int InternalCount(long long int p[], long long int q[],
long long int r[]) {
long long int A=abs((p[0]*(q[1]-r[1]) + q[0]*(r[1]-p[1]) + r[0]*(p[1]-q[1]))/2);
long long int B1 =__gcd(abs(p[0]-q[0]),abs(p[1]-q[1]))+1;
long long int B2 =__gcd(abs(q[0]-r[0]),abs(q[1]-r[1]))+1;
long long int B3 =__gcd(abs(r[0]-p[0]),abs(r[1]-p[1]))+1;
long long int B=(B1+B2+B3-3)/2;
return (A-B+1);
}
};
class Solution {
public:
// Whether it is possible required bouquets with given max time
bool bouquetPossible(vector& bloom_days, int bloom_day, int m, int k) {
int bouquets = 0, flowers = 0;
for(const int& day: bloom_days) {
if(day <= bloom_day)
++flowers;
else
flowers = 0;
if(flowers == k)
++bouquets, flowers = 0;
}
return bouquets >= m;
}
int minDays(vector& bloomDay, int m, int k) {
// No. of flowers req more than available
if(m * k > bloomDay.size())
return -1;
int low = 0, high = INT_MAX;
while(low < high) {
// Candidate bloom date for making req bouquets
int bloom_day = low + (high - low) / 2;
if(bouquetPossible(bloomDay, bloom_day, m, k))
high = bloom_day;
else
low = bloom_day + 1;
}
return high;
}
};
class Solution {
public:
double maxVolume(double perimeter, double area) {
double P = perimeter;
double A = area;
double sqrtTerm = sqrt(P * P - 24 * A);
double dimension1 = (P - sqrtTerm) / 12.0;
double dimension2 = (P / 4.0) - 2 * dimension1;
double volume = pow(dimension1, 2) * dimension2;
return round(volume * 100.0) / 100.0;
}
};
class Solution {
public:
vector getPrimes(int n) {
vector isP(n+1,true);
isP[0]=isP[1]=false;
for(int i=2;i*i<=n;i++){
if(isP[i]){
for(int j=i*i;j<=n;j+=i) isP[j]=false;
}
}
vector p;
for(int i=2;i<=n;i++) if(isP[i]) p.push_back(i);
int i=0,j=p.size()-1;
if(n&1){
if(isP[n-2]) return {2,n-2};
else return {-1,-1};
}
while(i<=j){
if(p[i]+p[j]==n) return {p[i],p[j]};
if(p[i]+p[j]
class Solution {
public:
int findMaximizedCapital(int k, int w,
vector<int>& profits, vector<int>& capital) {
int n = profits.size();
vector<pair<int, int>> projects;
for (int i = 0; i < n; ++i) {
projects.push_back({ capital[i], profits[i] });
}
sort(projects.begin(), projects.end());
int pind = 0;
priority_queue<int> q;
for (int i = 0; i < k; ++i) {
while (pind < n && projects[pind].first <= w) {
q.push(projects[pind++].second);
}
if (q.empty()) break;
w += q.top();
q.pop();
}
return w;
}
};
