Divay9Sharma
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| long countInversions(vector<int> arr) { | |
| map<int,pair<int,int>> mp; | |
| int count; | |
| for(int i=0;i<arr.size();i++){ | |
| mp[arr[i]].first++; | |
| } | |
| count = mp.size(); | |
| mp.insert({0,{0,0}}); | |
| for(auto i=mp.begin();i!=mp.end();i++){ | |
| if(count>0){ |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| void dfs(vector<vector<int>> &adj,int arr[],int len,int curr,int curr_len,string temp){ | |
| temp+=to_string(curr); | |
| if(curr_len == len){ | |
| //cout<<temp<<" "; | |
| arr[stoi(temp)]=1; | |
| return; | |
| } |
Divay9Sharma
/ disjoint_paths_graph.cpp
Created
July 25, 2020 14:33
Maximum product of two non-intersecting paths in a tree - dfs graph
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| void dfs1(vector<int> g[],int visit[],int curr,int len,int *max,int* node){ | |
| if(len > *max){ | |
| *max = len; | |
| *node = curr; | |
| } | |
| visit[curr] = 1; | |
| for(auto i= g[curr].begin();i!=g[curr].end();i++){ |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { | |
| map<int,unordered_set<int>> mp; | |
| for(int i=0;i<edges.size();i++){ | |
| mp[edges[i][0]].insert(edges[i][1]); | |
| mp[edges[i][1]].insert(edges[i][0]); | |
| } | |
| vector<int> curr; | |
| if(n==1){ |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void dfs(map<string,vector<pair<string,double>>> &mp,map<string,bool> &visit,double *result,string end,string curr,double temp){ | |
| if(curr == end){ | |
| *result = temp; | |
| return; | |
| } | |
| visit[curr] = true; | |
| for(auto i = 0;i<mp[curr].size();i++){ | |
| if(visit[mp[curr][i].first] == false){ | |
| temp *= mp[curr][i].second; | |
| dfs(mp,visit,result,end,mp[curr][i].first,temp); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using namespace std; | |
| struct Location{ | |
| int i; | |
| int j; | |
| }; | |
| bool distinct(int a, int b, int c, int d){ | |
| if(a!=b&&a!=c&&a!=d) | |
| if(b!=c&&b!=d) |
Divay9Sharma
/ subsets.cpp
Created
July 21, 2020 12:16
Subsets - recursion backtracking bit manipluation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Firsrt appraoch | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| void another(int I,vector<int> &temp,set<vector<int>> &ans,int A[],int n){ | |
| vector<int> x = temp; | |
| sort(x.begin(),x.end()); | |
| ans.insert(x); | |
| for(int i=I;i<n;i++){ | |
| temp.push_back(A[i]); |
Divay9Sharma
/ serialize_deserialize_tree.cpp
Created
July 21, 2020 11:51
Serialize and Deserialize Binary Tree - queue level order
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Encodes a tree to a single string. | |
| string serialize(TreeNode* root) { | |
| queue<TreeNode*> q; | |
| q.push(root); | |
| string s; | |
| while(!q.empty()){ | |
| TreeNode* temp = q.front(); | |
| q.pop(); | |
| if(temp==NULL){ | |
| s+="N,"; |
Divay9Sharma
/ serialize_deserialize_bst.cpp
Last active
July 21, 2020 11:49
Serialize and Deserialize BST - bst preorder queue
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Encodes a tree to a single string. | |
| void another(TreeNode* root,string &ans){ | |
| if(root==NULL){ | |
| return; | |
| } | |
| ans+=to_string(root->val)+","; | |
| another(root->left,ans); | |
| another(root->right,ans); | |
| } | |
Divay9Sharma
/ interleaved_strings.cpp
Created
July 21, 2020 10:23
Interleaved Strings - dp recursion
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| bool isInterleave(string A, string B, string C) | |
| { | |
| if(A.length()==0 && B.length()==0 && C.length()==0){ | |
| return true; | |
| } | |
| if(C.length() < A.length()+B.length()){ | |
| return false; | |
| } | |
| bool ans = false; | |
| if(A.length()!=0 && A[0]==C[0]){ |
NewerOlder