Untitled

adityass

Apr 29th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 4.98 KB | None | 0 0

raw download clone embed print report

// N queens
class Solution {
public:
bool isSafe(int row , int col ,vector<string> board , int n )
{
int checkr = row ;
int checkc = col ;
while( checkr >=0 && checkc>=0)
{
if(board[checkr][checkc]=='Q')
{
return false ;
}
checkr --; checkc --;
}
int tc = col ;
while(tc>=0)
{
if(board[row][tc]=='Q')
{
return false ;
}
tc--;
}
checkr = row ;
checkc = col ;
while( checkr <n && checkc>=0)
{
if(board[checkr][checkc]=='Q')
{
return false ;
}
checkr ++; checkc --;
}
return true ;
}
void solve(int col ,vector<string> &board , vector<vector<string>> &answer , int n )
{
if (col == n )
{
answer.push_back(board) ;
return ;
}
for(int row =0 ; row<n ; row++)
{
if(isSafe(row , col , board , n))
{
board[row][col]= 'Q';
solve(col+1 , board , answer , n );
board[row][col]= '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> answer ;
vector<string> board(n) ;
string s(n , '.') ;
for(int i = 0 ; i <n ;i++)
{
board[i] = s ;
}
solve(0, board , answer , n);
return answer;
}
};
// activity seq
class Solution {
public:
static bool compare(vector<int> v1 , vector<int> v2 )
{
if (v1[1] == v2[1]) return v1[0]<v2[0];
return v1[1]<v2[1] ;
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), compare);
int i = 0 ;
int j = 1 ;
int c = 1 ;
int n = intervals.size();
while(j<n)
{
if(intervals[i][1] <= intervals[j][0])
{
c++;
i = j ;
j++ ;
}
else
{
j++ ;
}
}
return n - c ;
}
};
// LCS
#include<vector>
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s1, string s2, int i, int j, vector<vector<int>>& vec) {
if (i == s1.length() || j == s2.length()) {
return 0;
}
if (vec[i][j] != -1) {
return vec[i][j];
}
int ans = 0;
if (s1[i] == s2[j]) {
ans = 1 + solve(s1, s2, i + 1, j + 1, vec);
}
else {
ans = max(solve(s1, s2, i + 1, j, vec), solve(s1, s2, i, j + 1, vec));
}
return vec[i][j] = ans;
}
int longestCommonSubsequence(string text1, string text2) {
int rows = text1.length();
int cols = text2.length();
vector<vector<int>> vec(rows, vector<int>(cols, -1));
return solve(text1, text2, 0, 0, vec);
}
};
//eulers
#include <unordered_map>
#include<queue>
#include<list>
bool iscyclicBFS(int src, unordered_map<int,bool> &visited, unordered_map<int,list<int>> adj){
unordered_map<int,int> parent;
parent[src]=-1;
visited[src]=1;
queue<int> q;
q.push(src);
while(!q.empty()){
int front = q.front();
q.pop();
for(auto neighbour: adj[front]){
if(visited[neighbour]==true && neighbour!=parent[front]){
return true;
}
else if(!visited[neighbour]){
q.push(neighbour);
visited[neighbour]=1;
parent[neighbour]=front;
}
}
}
return false;
}
bool iscyclicDFS(int node,int parent, unordered_map<int,bool> &visited, unordered_map<int,list<int>> &adj){
visited[node]=true;
for(auto neighbour: adj[node]){
if(!visited[neighbour]){
bool cycledetected=iscyclicDFS(neighbour, node,visited,adj);
if(cycledetected)
return true;
}
else if(neighbour != parent){
//cycle present
return true;
}
}
return false;
}
string cycleDetection (vector<vector<int>>& edges, int n, int m)
{
// create adjacency list
unordered_map<int,list<int>> adj;
for(int i=0;i<m;i++){
int u = edges[i][0];
int v = edges[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
//to handle disconnected components
unordered_map<int,bool> visited;
for(int i=0;i<n;i++){
if(!visited[i]){
// bool ans = iscyclicBFS(i,visited,adj);
bool ans = iscyclicDFS(i,-1,visited,adj);
if(ans == 1){
return "Yes";
}
}
}
return "No";
}

Add Comment

Please, Sign In to add comment