LeetCode, GeeksForGeeks Problem of the day solution

class Solution { public: vector helper(int n){ if(n==1) return {new TreeNode(0)}; vector ans; for(int i=1;i left = helper(i); vector right = helper(n-i-1); for(auto l:left){ for(auto r:right){ TreeNode* root = new TreeNode(); root->left = l; root->right = r; ans.push_back(root); } } } return ans; } vector allPossibleFBT(int n) { return helper(n); } };

class Solution { public: //Function to sort a linked list of 0s, 1s and 2s. Node* segregate(Node *head) { maphmap; Node*curr=head; while(curr){ hmap[curr->data]++; curr=curr->next; } Node*dummy=new Node(-1); Node*temp=dummy; for(auto &it:hmap){ int k=it.second; while(k--){ temp->next=new Node(it.first); temp=temp->next; } } return dummy->next; } };

Join in for Biweekly Contest 109 solutions: https://t.me/leetcodeContestSol

class Solution { double dp[26][26][101]; double f(int n,int k,int i,int j){ if(k==0) return 1; if(dp[i][j][k]>=0) return dp[i][j][k]; int dx[8] = {2,2,1,1,-1,-1,-2,-2}; int dy[8] = {1,-1,2,-2,2,-2,-1,+1}; double cnt = 0; for(int p=0;p<8;p++){ int ni = dx[p] + i; int nj = dy[p] + j; if(ni>=0 && ni<n && nj<n && nj>=0){ cnt+=f(n,k-1,ni,nj); } } return dp[i][j][k] = cnt; } public: double knightProbability(int n, int k, int row, int column) { memset(dp,-1,sizeof(dp)); return f(n,k,row,column)/pow(8,k); } };

class Solution { public: //Function to remove duplicates from unsorted linked list. Node * removeDuplicates( Node *head) { if(head==NULL){ return NULL; } Node* temp = head; Node* prev = head; set st; st.insert(temp->data); temp = temp->next; while(temp){ if(st.find(temp->data) != st.end()){ prev->next = temp->next; } else{ st.insert(temp->data); prev = temp; } temp=temp->next; } return head; } };

class Solution { public: int findNumberOfLIS(vector& nums) { int n = nums.size(), maxlen = 1, ans = 0; vector cnt(n, 1), len(n, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { if (len[j]+1 > len[i]) { len[i] = len[j]+1; cnt[i] = cnt[j]; } else if (len[j]+1 == len[i]) cnt[i] += cnt[j]; } } maxlen = max(maxlen, len[i]); } // find the longest increasing subsequence of the whole sequence // sum valid counts for (int i = 0; i < n; i++) if (len[i] == maxlen) ans += cnt[i]; return ans; } };

class Solution { public: struct node *reverse (struct node *head, int k) { if(head==NULL) return NULL; node* p = NULL; node* c = head; node* n = head->next; int count = 0; while(c!=NULL && countnext; c->next=p; p=c; c=n; count++; } if(n!=NULL){ head->next = reverse(n,k); } return p; } };

class Solution { public: vector asteroidCollision(vector& asteroids) { vector v; for(int i=0;i0){ v.push_back(asteroids[i]); } else{ while(v.size()!=0 && v.back()>0 && v.back()<(-asteroids[i])){ v.pop_back(); } if(v.size()==0 || v.back()<0){ v.push_back(asteroids[i]); } else if(v.back()==(-asteroids[i])){ v.pop_back(); } } } return v; } };

class Solution { public: //Function to find the first non-repeating character in a string. char nonrepeatingCharacter(string S) { map mp; for(auto i:S){ mp[i]++; } for(auto i:S){ if(mp[i]==1){ return i; } } return '$'; } };

class Solution { public: struct A { int s, e; bool operator <(const A&o)const{ return e == o.e ? s < o.s : e < o.e; } }; int eraseOverlapIntervals(vector>& intervals) { int n = intervals.size(), cnt = 0, last = -1e9; vector v; for(auto x : intervals) { v.push_back({x[0], x[1]}); } sort(v.begin(), v.end()); for(auto [s, e] : v) { if(s >= last) cnt++, last = e; } return n - cnt; } };