LeetCode, GeeksForGeeks Problem of the day solution
Открыть в Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Больше1 250
Подписчики
+224 часа
+147 дней
+2930 день
Архив постов
class Solution {
public:
unordered_map> gp;
TreeNode* headroot;
void addedge(TreeNode* u, TreeNode* v){
gp[u].push_back(v);
gp[v].push_back(u);
}
void dfs(TreeNode* root){
if(root == NULL){
return;
}
if(root -> left != NULL) addedge(root, root -> left);
if(root -> right != NULL) addedge(root, root -> right);
dfs(root -> left);
dfs(root -> right);
}
void check(TreeNode* a, int d,unordered_map& degree,int& ans, unordered_map& visited){
visited[a] = true;
if(degree[a] == 1 && a != headroot){
ans++;
}
if(d == 0){
return;
}
for(auto i:gp[a]){
if(visited[i] == false){
check(i, d-1, degree, ans, visited);
}
}
}
int countPairs(TreeNode* root, int distance) {
headroot = root;
dfs(root);
unordered_map degree;
for(auto i:gp){
degree[i.first] = i.second.size();
}
int ans = 0;
unordered_map visited;
for(auto i:degree){
if(i.second == 1){
ans--;
check(i.first,distance,degree,ans,visited);
visited.clear();
}
}
if(ans == 1){
return 0;
}
return ans/2;
}
};
class Solution {
public:
int alternatingMaxLength(vector& arr) {
int n = arr.size();
if (n <= 1) return n;
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i-1]) {
up = down + 1;
} else if (arr[i] < arr[i-1]) {
down = up + 1;
}
}
return max(up, down);
}
};
class Solution {
public:
vector<TreeNode*> result;
stack<TreeNode*> noParent;
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
unordered_set<int> s(to_delete.begin(),to_delete.end());
noParent.push(root);
while(!noParent.empty())
{
TreeNode* topEl=noParent.top();
noParent.pop();
if(s.find(topEl->val)==s.end())
{
result.push_back(topEl);
}
traverse(topEl,s);}
return result;
}
TreeNode* traverse(TreeNode* root, unordered_set<int>& s)
{
if(root==NULL)
{
return NULL;
}
if(s.find(root->val)!=s.end())
{
if(root->left){
noParent.push(root->left);}
if(root->right){noParent.push(root->right);}
root->left=NULL, root->right=NULL;
return NULL;
}
root->left=traverse(root->left,s);
root->right=traverse(root->right,s);
return root;
}
};
class Solution {
public:
// Function to construct binary tree from parent array.
Node* createTree(vector parent) {
// Your code here
int n=parent.size();
vector> v(n+1);
int r_d;
for(int i=0;i q;
q.push(root);
while(!q.empty()){
auto z=q.front();
q.pop();
if(v[z->data].size()>=1){
z->left=new Node(v[z->data][0]);
q.push(z->left);
if(v[z->data].size()>1){
z->right=new Node(v[z->data][1]);
q.push(z->right);
}
}
}
return(root);
}
};
class Solution {
public:
TreeNode * LCA(TreeNode* root, int startValue, int destValue){
if(root==NULL or root->val==startValue or root->val==destValue){
return root;
}
TreeNode * left=LCA(root->left,startValue,destValue);
TreeNode * right=LCA(root->right,startValue,destValue);
if(left==NULL){
return right;
}
else if(right==NULL){
return left;
}
else{
return root;
}
}
bool findPath(TreeNode* root, int value, string& path) {
if (root == nullptr) {
return false;
}
if (root->val == value) {
return true;
}
path.push_back('L');
if (findPath(root->left, value, path)) {
return true;
}
path.pop_back();
path.push_back('R');
if (findPath(root->right, value, path)) {
return true;
}
path.pop_back();
return false;
}
string getDirections(TreeNode* root, int startValue, int destValue) {
TreeNode * lca=LCA(root,startValue,destValue);
string start="";
findPath(lca,startValue,start);
string end="";
findPath(lca,destValue,end);
string result(start.size(), 'U');
result += end;
return result;
}
};
class Solution {
public:
string printString(string s, char ch, int count) {
int n=s.size();
int index=0;
string ss="";
for(int i=0;i
class Solution {
private:
TreeNode* createNode(int val, unordered_map &nodeList){
TreeNode* node = new TreeNode(val);
nodeList[val] = node;
return node;
}
void connectNode(TreeNode* &parent, TreeNode* &child, int left){
left == 1 ? parent->left = child : parent->right = child;
}
TreeNode* findNode(int val, unordered_map &nodeList){
return nodeList.count(val) ? nodeList[val] : nullptr;
}
public:
TreeNode* createBinaryTree(vector>& descriptions) {
unordered_map nodeList;
unordered_set childList;
for(auto &desc: descriptions){
int parent = desc[0], child = desc[1], left = desc[2];
TreeNode *parentNode, *childNode;
parentNode = (findNode(parent, nodeList) ? findNode(parent, nodeList) : createNode(parent, nodeList));
childNode = (findNode(child, nodeList) ? findNode(child, nodeList) : createNode(child, nodeList));
connectNode(parentNode, childNode, left);
childList.insert(child);
}
int root;
for(auto &desc: descriptions){
if(childList.find(desc[0]) == childList.end()){
root = desc[0];
break;
}
}
TreeNode* rootNode = findNode(root, nodeList);
return rootNode;
}
};
class Solution {
public:
string smallestNumber(int s, int d) {
if(s > d*9){
return "-1";
}
vector vec(d);
vec[0] = 1;
int sum = 1,i = d-1;
while(sum < s && i>=0){
if(sum + 9 <= s){
sum += 9;
vec[i]+=9;
}else{
while(sum < s){
sum++;
vec[i]++;
}
}
i--;
}
if(sum < s) return "-1";
string str = "";
for(int digit : vec){
str += (char)digit + '0';
}
return str;
}
};
class Solution {
public:
string countOfAtoms(string formula) {
map<string,int> mp;
stack<pair<string,int>> st;
int count =1;
string ele = "";
int n= formula.size();
int i=0;
while(i<n){
char ch = formula[i];
if(ch=='('){
if(ele!=""){
st.push({ele,count});
st.push({"(",0});
ele = "";
}else{
st.push({"(",0});
ele = "";
}
i++;
}
else if(isupper(ch)){
if(ele!=""){
st.push({ele,count});
ele = "";
ele+=ch;
count =1;
}else{
ele+=ch;
count =1;
}
i++;
} else if(islower(ch)){
ele+=ch;
i++;
}else if(isdigit(ch)){
string digits = "";
int j =i;
while(j<n && isdigit( formula[j])){
digits+=formula[j];
j++;
}
i=j;
if(digits!=""){
count = stoi(digits);
}
} else if(ch==')'){
if(ele!=""){
st.push({ele,count});
ele = "";
count =1;
}
int j=i+1;
string digits = "";
while(j<n && isdigit(formula[j])){
digits+=formula[j];
j++;
}
i=j;
if(digits!=""){
count = stoi(digits);
}
vector<pair<string,int>> v;
while(!st.empty() && st.top().first!="("){
v.push_back({st.top().first, st.top().second*count});
st.pop();
}
st.pop();
for(auto k:v){
st.push(k);
}
}
}
if(ele!=""){
st.push({ele,count});
}
while(!st.empty()){
mp[st.top().first]+=st.top().second;
st.pop();
}
string ans = "";
for(auto i: mp){
ans+=i.first;
if(i.second!=1){
ans+=to_string(i.second);
}
}
return ans;
}
};
class Solution {
public:
void segregate0and1(vector &arr) {
int cnt0=0;
int cnt1=0;
for(int i=0; i
