LeetCode, GeeksForGeeks Problem of the day solution

class Solution{ public: int dp[1001][1001]; int solve(string A,int i,int j){ if(i>j)return 0; if(i==j)return 1; if(dp[i][j]!=-1)return dp[i][j]; if(A[i]==A[j]){ return dp[i][j] =2+solve(A,i+1,j-1); } else{ return dp[i][j] = max(solve(A,i+1,j), solve(A,i,j-1)); } } int longestPalinSubseq(string A) { //code here int n=A.size(); memset(dp, -1, sizeof(dp)); // dp.resize(n, vector(n, -1)); return solve(A,0,n-1); } };

class LRUCache { public: class node{ public: int key,val; node* next; node* prev; node(int newkey,int newval){ key=newkey,val=newval; } }; node* head=new node(-1,-1); node* tail=new node(-1,-1); int storecap; //to store the capacity which is allowed unordered_map mp; LRUCache(int capacity) { storecap=capacity; head->next=tail; tail->prev=head; // initialised everything first } void addnode(node* newnode){ node* temp=head->next; newnode->next=temp; newnode->prev=head; head->next=newnode; temp->prev=newnode; } void deletenode(node* delnode){ node* delprev=delnode->prev; node* delnext=delnode->next; delprev->next=delnext; delnext->prev=delprev; } int get(int keyfind) { if(mp.find(keyfind)!=mp.end()){ node* resnode=mp[keyfind]; int result=resnode->val; mp.erase(keyfind); deletenode(resnode); addnode(resnode); mp[keyfind]=head->next; //new address return result; } return -1; } void put(int keytoput, int value) { if(mp.find(keytoput)!=mp.end()){ //if found in map node* existnode=mp[keytoput]; //then delete this from mp and list mp.erase(keytoput); deletenode(existnode); // and we will add it the right position } if(mp.size()==storecap){ //if the capacity is full mp.erase(tail->prev->key); //then delete the least recently used deletenode(tail->prev); //from map as well as list } node* nodetoput=new node(keytoput,value); addnode(nodetoput); //insert the node right after head as it is recently used mp[keytoput]=head->next;//add it to the map also } };

class Solution { public: int LongestRepeatingSubsequence(string str){ int n = str.length(); int dp[n+1][n+1]; for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) dp[i][j] = 0; for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { if (str[i-1] == str[j-1] && i != j) dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } } return dp[n][n]; } };

class Solution { public: ListNode* reverse(ListNode* head){ ListNode* prev= NULL; ListNode* curr= head; while (curr){ ListNode* forward= curr->next; curr->next= prev; prev= curr; curr= forward; } return prev; } ListNode* add(ListNode* l1, ListNode* l2){ ListNode* head= new ListNode(-1); ListNode* curr= head; int carry=0; while (l1!=NULL l2!=NULL carry>0){ int v1=0, v2=0; if (l1)v1= l1->val; if (l2)v2= l2->val; int sum= v1+v2+carry; carry= sum/10; sum= sum%10; curr->next= new ListNode(sum); curr= curr->next; if (l1)l1= l1->next; if (l2)l2= l2->next; } head= head->next; return head; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { l1= reverse(l1); l2= reverse(l2); ListNode* ans= add(l1,l2); ans= reverse(ans); return ans; } };

class Solution { public: string FirstNonRepeating(string A){ unordered_map charCount; vector order; string res = ""; for (char c : A) { charCount[c]++; if (charCount[c] == 1) { order.push_back(c); } else { auto it = find(order.begin(), order.end(), c); if (it != order.end()) { order.erase(it); } } if (!order.empty()) { res += order.front(); } else { res += "#"; } } return res; } };

Join in for every week's post Leetcode Contest solutions: https://t.me/leetcodeContestSol

class Solution { public: vector smallestSufficientTeam(vector& req_skills, vector>& people) { unordered_map skills; int n = req_skills.size(); for (int i = 0; i < req_skills.size(); ++i) skills[req_skills[i]] = i; int m = people.size(); vector people_skill(m); for (int i = 0; i < m; ++i) for (int j = 0; j < people[i].size(); ++j){ int temp = skills[people[i][j]]; people_skill[i]|=(1< dp(s, INT_MAX); vector parent(s,-1); vector parent_state(s); dp[0] = 0; for (int i=0; i <(1<dp[i]+1) {parent[temp]=j; parent_state[temp]=i; dp[temp]=dp[i]+1;} } int temp = (1< ret; while (parent[temp]!=-1){ ret.push_back(parent[temp]); temp = parent_state[temp]; } return ret; } };

class Solution { public: queue rev(queue q) { int n= q.size(); queue q2; vector v(n); for(int i=0;i=0;i--){ q2.push(v[i]); } return q2; } };

class Solution { public: int binary(vector<vector<int>> &events,int i,int lastday){ int low=i+1; int high=events.size()-1; int ans=events.size(); while(low<=high){ int mid=(low+high)/2; if(events[mid][0]>lastday){ ans=mid; high=mid-1; } else{ low=mid+1; } } return ans; } int help(vector<vector<int>>& events,int i,int k,vector<vector<int>> &dp){ if(i==events.size() || k==0){ return 0; } if(dp[i][k]!=-1){ return dp[i][k]; } int nextindex=binary(events,i,events[i][1]); int take=events[i][2] + help(events,nextindex,k-1,dp); int notTake=help(events,i+1,k,dp); return dp[i][k]=max(take,notTake); } int maxValue(vector<vector<int>>& events, int k) { vector<vector<int>> dp(events.size()+1,vector<int> (k+1,-1)); sort(events.begin(), events.end()); return help(events,0,k,dp); } };

class Solution { public: //Function to delete middle element of a stack. void deleteMid(stack<int>&s, int sizeOfStack) { int mid = ceil((sizeOfStack+1)/2); stack<int> st; for(int i=0;i<sizeOfStack;i++){ if(i != sizeOfStack-mid){ st.push(s.top()); } s.pop(); } for(int i=0;i<sizeOfStack-1;i++){ int temp = st.top(); st.pop(); s.push(temp); } } };

class Solution { public: int longestSubsequence(vector& arr, int difference) { int ans=0; unordered_map dp; for(int i=0;i