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:
void solve(int index, vector& vec, vector> &ans){
if(index==vec.size()){
ans.push_back(vec);
return;
}
for(int i=index;i> permute(vector& nums) {
vector vec = nums;
vector> ans;
solve(0, vec, ans);
return ans;
}
};
class Solution {
public:
int shortestDistance(int N, int M, vector<vector<int>> A, int X, int Y) {
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
pq.push({0, {0, 0}});
vector<vector<int>> vis(N, vector<int>(M, 0));
vis[0][0]=1;
int di[]={0, -1, 0, 1};
int dj[]={-1, 0, 1, 0};
while(!pq.empty()){
int steps = pq.top().first;
int x = pq.top().second.first;
int y = pq.top().second.second;
pq.pop();
if(x==X && y==Y){
return steps;
}
for(int i=0;i<4;i++){
int dx = x + di[i];
int dy = y + dj[i];
if(dx>=0 && dx<N && dy>=0 && dy<M && A[dx][dy]==1 && vis[dx][dy]==0){
vis[dx][dy]=1;
pq.push({steps+1,{dx, dy}});
}
}
}
return -1;
}
};
class Solution {
public:
vector> ans;
void solve(int id , int n, int k, vector &temp){
if(temp.size()==k){
ans.push_back(temp);
return;
}
for(int i=id;i<=n;i++){
temp.push_back(i);
solve(i+1, n, k, temp);
temp.pop_back();
}
}
vector> combine(int n, int k) {
vector temp;
solve(1, n, k, temp);
return ans;
}
};
class Solution {
public:
// Function to return a list containing the DFS traversal of the graph.
void dfs(int node, vector adj[], vector &res, vector&vis){
vis[node]=1;
res.push_back(node);
for(auto it:adj[node]){
if(!vis[it]){
dfs(it, adj, res, vis);
}
}
}
vector dfsOfGraph(int V, vector adj[]) {
vector res;
vector vis(V, 0);
dfs(0, adj, res, vis);
return res;
}
};
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int n1 = s1.size();
int n2 = s2.size();
vector> dp(n1 + 1, vector(n2 + 1));
dp[0][0] = 0;
for(int i = 0; i < n1; ++i){
dp[i + 1][0] = dp[i][0] + s1[i];
}
for(int j = 0; j < n2; ++j){
dp[0][j + 1] = dp[0][j] + s2[j];
}
for(int i = 0; i < n1; ++i){
for(int j = 0; j < n2; ++j){
if(s1[i] == s2[j]){
dp[i + 1][j + 1] = dp[i][j];
}else{
dp[i + 1][j + 1] = min(dp[i][j + 1] + s1[i], dp[i + 1][j] + s2[j]);
}
}
}
return dp[n1][n2];
}
};
class Solution {
public:
// Function to return Breadth First Traversal of given graph.
vector bfsOfGraph(int V, vector adj[]) {
vector vis(V, 0);
vector ans;
queue q;
q.push(0);
vis[0] = 1;
while(!q.empty()){
int node = q.front();
q.pop();
ans.push_back(node);
for(auto it:adj[node]){
if(vis[it]==0){
vis[it]=1;
q.push(it);
}
}
}
return ans;
}
};
class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
vector> dp(n, vector(n));
for (int i = n - 1; i >= 0; --i) {
dp[i][i] = 1;
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
dp[i][j] = dp[i][j - 1];
} else {
dp[i][j] = INT_MAX;
for (int k = i; k < j; ++k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
}
return dp[0][n - 1];
}
};
class Solution{
public:
// returns the inorder successor of the Node x in BST (rooted at 'root')
Node * inOrderSuccessor(Node *root, Node *x)
{
Node* ans;
while(root){
if(root->data<=x->data){
root=root->right;
}
else if(root->data>x->data){
ans = root;
root=root->left;
}
}
return ans;
}
};
class Solution {
public:
vector> ops = {{100, 0}, {75, 25}, {50, 50}, {25, 75}};
unordered_map> memo;
double solve(int A, int B) {
if (A <= 0 && B <= 0) {
return 0.5; // Both A and B are empty at the same time with probability 0.5
}
if (A <= 0) {
return 1.0; // A is empty first with probability 1.0
}
if (B <= 0) {
return 0.0; // B is empty first with probability 0.0
}
if (memo.count(A) && memo[A].count(B)) {
return memo[A][B];
}
double probability = 0.0;
for (const auto& op : ops) {
int a = op.first;
int b = op.second;
probability += 0.25 * solve(max(0, A - a), max(0, B - b));
}
memo[A][B] = probability;
return probability;
}
double soupServings(int n) {
if (n >= 4800) return 1.0;
return solve(n, n);
}
};
void inorder(vector<int> &ans, Node* root){
if(root==NULL){
return;
}
inorder(ans, root->left);
ans.push_back(root->data);
inorder(ans, root->right);
}
float findMedian(struct Node *root)
{
vector<int> ans;
inorder(ans, root);
if(ans.size()&1){
int ind = ans.size()/2;
return ans[ind];
}
int ind1 = ans.size()/2;
int ind2 = ind1-1;
return (float)((float)(ans[ind1]+ans[ind2])/2.0);
}
