Algo
// Mergesort
void merge(ll arr[], ll lft, ll mid, ll rgt){
ll n1 = mid-lft+1;
ll n2 = rgt-mid;
ll a[n1+1];
ll b[n2+1];
for(ll i=0 ; i<n1 ; i++){
a[i] = arr[lft+i];
}
for(ll i=0 ; i<n2 ; i++){
b[i] = arr[mid+1+i];
}
a[n1] = b[n2] = INT_MAX;
ll i1=0;
ll i2=0;
for(ll i=lft ; i<=rgt ; i++){
if(a[i1]<=b[i2]){
arr[i] = a[i1];
i1++;
}
else{
arr[i] = b[i2];
i2++;
}
}
}
void mergesort(ll arr[], ll lft, ll rgt) {
if(lft<rgt){
ll mid = (lft+rgt)/2;
mergesort(arr,lft,mid);
mergesort(arr,mid+1,rgt);
merge(arr,lft, mid, rgt);
}
}
//----------------------------------------------------------------------------------------------------
//quickSort
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int Partition(int arr[], int l, int r) {
/*
যদি pivot point টা array এর প্রথম position হয়
তাহলে array টা যদি sorted থাকে তাহলে এর t.c
O(n^2) হবে।
এর থেকে বাঁচার জন্যে ২ টা উপায় আছে,
১. mid pivot point
২. random pivot point
১. যদি pivot point টা array এর mid position
টা নিই তাহলে এর average t.c O(nlog(n))হবে।
তবে মাঝে মধ্যে t.c O(n^2) হতে পারে।
২.যদি pivot point টা random pivot point
নিই তাহলে এর average t.c O(nlog(n))হবে।
তবে random function টা যদি array এর প্রথম
position টা দিলে তখন t.c O(n^2) হবে।
*/
int pivot = arr[l];
int i = l, j = r;
while (i < j) {
while (arr[i] <= pivot) i++;
while (arr[j] > pivot) j--;
if (i < j)
swap(arr[i], arr[j]);
}
swap(arr[l], arr[j]);
return j;
}
void quickSort(int arr[], int l, int r) {
if (l < r) {
int pivotPos = Partition(arr, l, r);
quickSort(arr, l, pivotPos - 1);
quickSort(arr, pivotPos + 1, r);
}
}
int main() {
int arr[8] = {3, 1, 8, 5, 3, 1, 9, 2};
quickSort(arr, 0, 7);
for (int i = 0; i < 8; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
//--------------------------------------------------------------
//LCS
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
using namespace std;
int lcs(int x, int y, string s1, string s2) {
int dp[102][102];
for (int i = 0; i < (x + 1); i++) {
for (int j = 0; j < (y + 1); j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i < (y + 1); i++) {
for (int j = 1; j < (x + 1); j++) {
if (s2[i - 1] == s1[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[y][x];
}
int main() {
int t, n, k, x, y;
cin >> t;
while (t--) {
cin >> x >> y;
string s1, s2;
cin >> s1 >> s2;
cout << lcs(x, y, s1, s2) << endl;
}
return 0;
}
//-------------------------------------------------
//Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver program
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}
Comments
Post a Comment