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:
int minimumEffortPath(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> visi(n,vector<int>(m,1e7));
priority_queue<pair<int,pair<int,int>>> q;
vector<pair<int,int>> dirs = {{1,0},{0,1},{-1,0},{0,-1}};
q.push({0,{0,0}});
visi[0][0]=0;
while(!q.empty()){
auto t = q.top();
if(t.second.first==n-1&&t.second.second==m-1)return -1*t.first;
q.pop();
for(auto& dir:dirs){
int nx = t.second.first+dir.first;
int ny = t.second.second + dir.second;
if(nx<0 or ny<0 or nx>=n or ny>=m)continue;
int val = -1*max(-1*t.first,abs(grid[nx][ny]-grid[t.second.first][t.second.second]));
if(-1*val<visi[nx][ny]){
q.push({val,{nx,ny}});
visi[nx][ny]=-val;
}
}
}
return -1;
}
};
class Solution
{
public:
//Function to count the number of ways in which frog can reach the top.
long long countWays(int n)
{
long long mod = 1000000007;
vector dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(long long i=3;i<=n;i++){
dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%mod;
}
return dp[n]%mod;
}
};
class Solution {
int dist(int x1, int y1, int x2, int y2){
return abs (x1-x2) + abs(y1-y2);
}
public:
int minCostConnectPoints(vector>& points) {
if (points.size() < 1) return 0;
int V = points.size();
int result = 0;
vector minDists(V, INT_MAX);
vector mst(V, 0);
minDists[0] = 0;
mst[0] = 1;
for (auto i = 0 ; i < V; i++) {
minDists[i] = dist(points[0][0],points[0][1],points[i][0],points[i][1]);
}
for(int i = 0;i
class Solution{
public:
int solve(int i, int sum, int N,int a[], vector>&dp){
if( i >= N){
if(sum == 0) return 1;
return 0;
}
if(sum == 0) return 1;
if(sum < 0) return 0;
if(dp[i][sum] != -1) return dp[i][sum];
int include = solve(i+1,sum-a[i],N,a,dp);
int exclude = solve(i+1,sum,N,a,dp);
return dp[i][sum] = include || exclude;
}
int equalPartition(int N, int arr[])
{
// code here
int sum = 0;
for(int i = 0 ;i>dp(N+1,vector(sum/2+1,-1));
if(sum%2 != 0) return 0;
return solve(0,sum/2,N,arr,dp);
}
};
class Solution {
public:
vector findItinerary(vector>& tickets) {
unordered_map> adjlist;
vector res{"JFK"};
int n = tickets.size();
sort(tickets.begin(), tickets.end());
for (auto ticket: tickets)
{
string src = ticket[0];
string dst = ticket[1];
adjlist[src].push_back(dst);
}
dfs(res, adjlist, "JFK", n);
return res;
}
bool dfs(vector& res, unordered_map>& adjlist, string cur, int n)
{
if (res.size() == n + 1)
return true;
if (adjlist.find(cur) == adjlist.end())
return false;
deque tmp = adjlist[cur];
while (!tmp.empty())
{
string dst = tmp.front();
tmp.pop_front();
res.push_back(dst);
adjlist[cur].pop_front();
if (dfs(res, adjlist, dst, n))
return true;
res.pop_back();
adjlist[cur].push_back(dst);
}
return false;
}
};
class Solution{
public:
int perfectSum(int arr[], int n, int sum)
{
vector dp(sum + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = sum; j >= arr[i]; j--) {
dp[j] += dp[j - arr[i]];
dp[j] %= 1000000007; // Modulo to avoid integer overflow
}
}
return dp[sum];
}
};
class Solution {
public:
int candy(vector& ratings)
{
int n=ratings.size();
vector candies(n,1);
if(n==1)
{
return 1;
}
for(int i=1;iratings[i-1] && candies[i]<=candies[i-1])
{
candies[i]=candies[i-1]+1;
}
}
for(int i=n-2;i>=0;i--)
{
if(ratings[i]>ratings[i+1] && candies[i]<=candies[i+1])
{
candies[i]=candies[i+1]+1;
}
}
int total=0;
for(int i=0;i
class Solution{
public:
string findLargest(int N, int S){
if(N>1 && S==0){
return "-1";
}
string ans="";
while(N>0){
if(S>=9){
ans += "9";
S -= 9;
}
else{
ans += char(S+'0');
S -= S;
}
N--;
}
if(S==0)
return ans;
return "-1";
}
};
class Solution {
public:
int minDeletions(string s) {
int arr[26] = {0};
for(int i=0;iv;
for(int i=0;i<26;i++)
if(arr[i] > 0)
v.push_back(arr[i]);
sort(v.begin(),v.end());
int ans = 0;
for(int i=v.size()-2;i>=0;i--){
if(v[i+1] == 0){
ans += v[i];
v[i] = 0;
}
else if(v[i] >= v[i+1]){
ans += v[i]-v[i+1]+1;
v[i] = v[i+1]-1;
}
}
return ans;
}
};
class Solution {
public:
int isPerfectNumber(long long N) {
if(N==1) return 0;
long long sum=1;
for(long long i=2;i*i<=N;i++){
if(N%i==0){
sum += i;
if(N/i != i){
sum += N/i;
}
}
}
return sum==N;
}
};
