Skip to content

Commit 48f55df

Browse files
RajSDERajSDE
committed
up26/02
1 parent c4e54a8 commit 48f55df

6 files changed

Lines changed: 456 additions & 0 deletions

File tree

‎JavaPractice/CountInversion/Readme.md‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
## Count Inversion
2+
Given an array of integers. Find the Inversion Count in the array.
3+
4+
**Inversion Count:** For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum.
5+
Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. [🔗Goto](https://practice.geeksforgeeks.org/problems/inversion-of-array-1587115620/1/?page=1&difficulty[]=1&status[]=unsolved&company[]=Amazon&sortBy=submissions#)
6+
7+
<details>
8+
<summary>Full Code</summary>
9+
10+
```java
11+
import java.util.*;
12+
import java.io.*;
13+
import java.lang.*;
14+
15+
class Sorting
16+
{
17+
public static void main (String[] args)
18+
{
19+
Scanner sc = new Scanner(System.in);
20+
long t = sc.nextLong();
21+
22+
while(t-- > 0)
23+
{
24+
long n = sc.nextLong();
25+
long arr[] = new long[(int)n];
26+
27+
for(long i = 0; i < n; i++)
28+
arr[(int)i] = sc.nextLong();
29+
30+
System.out.println(new Solution().inversionCount(arr, n));
31+
32+
}
33+
}
34+
}
35+
```
36+
</details>
37+
38+
```java
39+
class Solution
40+
{
41+
static long inversionCount(long arr[], long N)
42+
{
43+
return sort(arr,0,(int)N-1);
44+
}
45+
static long sort(long[] arr, int l, int r){
46+
long count =0;
47+
if(l<r){
48+
int m=l+(r-l)/2;
49+
count +=sort(arr,l,m);
50+
count +=sort(arr,m+1,r);
51+
count +=merge(arr,l,m,r);
52+
}
53+
return count;
54+
}
55+
static long merge(long[] arr, int l, int m, int r){
56+
int n1 =m-l+1;
57+
int n2 =r-m;
58+
59+
long left[] = new long[n1];
60+
long right[] = new long[n2];
61+
62+
for(int i=0; i<n1; ++i){
63+
left[i]=arr[l+i];
64+
}
65+
for(int j=0; j<n2; ++j){
66+
right[j] = arr[m+1+j];
67+
}
68+
int i=0, j=0,k=l;
69+
long count=0;
70+
while( i < n1 && j < n2 ){
71+
if(left[i]<=right[j])
72+
arr[k++]=left[i++];
73+
else{
74+
arr[k++]=right[j++];
75+
count+=n1-i;
76+
}
77+
}
78+
while(i<n1){
79+
arr[k++]=left[i++];
80+
}
81+
while(j<n2){
82+
arr[k++] = right[j++];
83+
}
84+
return count;
85+
}
86+
}
87+
88+
```

‎JavaPractice/LongestCommonSubsequence/Readme.md‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
## Longest Common Subsequence
2+
3+
Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase. [🔗Goto](https://practice.geeksforgeeks.org/problems/longest-common-subsequence-1587115620/1/?page=2&difficulty[]=1&status[]=unsolved&sortBy=submissions#)
4+
5+
<details>
6+
<summary>Full Code</summary>
7+
8+
```java
9+
import java.util.*;
10+
import java.lang.*;
11+
import java.io.*;
12+
13+
class GFG {
14+
public static void main (String[] args) {
15+
16+
Scanner sc=new Scanner(System.in);
17+
int test=sc.nextInt();
18+
while(test-- > 0){
19+
int p=sc.nextInt(); // Take size of both the strings as input
20+
int q=sc.nextInt();
21+
22+
String s1=sc.next(); // Take both the string as input
23+
String s2=sc.next();
24+
25+
Solution obj = new Solution();
26+
27+
System.out.println(obj.lcs(p, q, s1, s2));
28+
}
29+
}
30+
}
31+
```
32+
</details>
33+
34+
```java
35+
class Solution
36+
{
37+
static int lcs(int x, int y, String s1, String s2)
38+
{
39+
int[][]dp = new int[x+1][y+1];
40+
41+
for(int i=1;i<dp.length;i++){
42+
for(int j=1;j<dp[0].length;j++){
43+
44+
if(s1.charAt(i-1) == s2.charAt(j-1)){
45+
dp[i][j] = dp[i-1][j-1]+1;
46+
}
47+
else{
48+
dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]);
49+
}
50+
51+
}
52+
}
53+
54+
return dp[x][y];
55+
}
56+
57+
}
58+
```

‎JavaPractice/MaximumRectangularAreainaHistogram/Readme.md‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
## Maximum Rectangular Area in a Histogram
2+
Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit, there will be N bars height of each bar will be given by the array arr. [🔗Goto](https://practice.geeksforgeeks.org/problems/maximum-rectangular-area-in-a-histogram-1587115620/1/?page=3&difficulty[]=1&status[]=unsolved&sortBy=submissions)
3+
4+
<details>
5+
<summary>Full Code</summary>
6+
7+
```java
8+
import java.util.*;
9+
import java.lang.*;
10+
import java.io.*;
11+
12+
class GFG {
13+
14+
15+
public static void main (String[] args) throws IOException {
16+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
17+
int t = Integer.parseInt(br.readLine().trim());
18+
while(t-->0){
19+
long n = Long.parseLong(br.readLine().trim());
20+
String inputLine[] = br.readLine().trim().split(" ");
21+
long[] arr = new long[(int)n];
22+
for(int i=0; i<n; i++)arr[i]=Long.parseLong(inputLine[i]);
23+
System.out.println(new Solution().getMaxArea(arr, n));
24+
}
25+
}
26+
}
27+
```
28+
</details>
29+
30+
```java
31+
class Solution
32+
{
33+
//Function to find largest rectangular area possible in a given histogram.
34+
public static long getMaxArea(long hist[], long n)
35+
{
36+
long maxAns = 0;
37+
int ps[] = previousSmaller(hist);
38+
int ns[] = nextSmaller(hist);
39+
for(int i=0; i<hist.length; i++){
40+
long cur = ((ns[i]-ps[i])-1)*hist[i];
41+
maxAns = Math.max(cur,maxAns);
42+
}
43+
return maxAns;
44+
}
45+
public static int[] previousSmaller(long hist[]){
46+
int[] ps = new int[hist.length];
47+
Stack<Integer> s = new Stack<>();
48+
for(int i=0; i<hist.length; i++){
49+
while(!s.isEmpty() && hist[s.peek()] >= hist[i]){
50+
s.pop();
51+
}
52+
if(s.isEmpty()){
53+
ps[i] = -1;
54+
}else{
55+
ps[i] = s.peek();
56+
}
57+
s.push(i);
58+
}
59+
return ps;
60+
}
61+
public static int[] nextSmaller(long hist[]){
62+
int[] ns = new int[hist.length];
63+
Stack<Integer> s = new Stack<>();
64+
for(int i=hist.length-1; i>=0; i--){
65+
while(!s.isEmpty() && hist[s.peek()] >= hist[i]){
66+
s.pop();
67+
}
68+
if(s.isEmpty()){
69+
ns[i] = hist.length;
70+
}else{
71+
ns[i] = s.peek();
72+
}
73+
s.push(i);
74+
}
75+
return ns;
76+
}
77+
}
78+
```

‎JavaPractice/RearrangeALinkedList/Readme.md‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
## Rearrange a linked list
2+
Given a singly linked list, the task is to rearrange it in a way that all odd position nodes are together and all even positions node are together.
3+
Assume the first element to be at position 1 followed by second element at position 2 and so on.
4+
**Note:** You should place all odd positioned nodes first and then the even positioned ones. (considering 1 based indexing). Also, the relative order of odd positioned nodes and even positioned nodes should be maintained. [🔗Goto](https://practice.geeksforgeeks.org/problems/rearrange-a-linked-list/1/?page=8&difficulty[]=1&status[]=unsolved&sortBy=submissions#)
5+
6+
<details>
7+
<summary>Full Code</summary>
8+
9+
```java
10+
import java.util.*;
11+
import java.io.*;
12+
13+
class Node{
14+
int data;
15+
Node next;
16+
17+
Node(int x){
18+
data = x;
19+
next = null;
20+
}
21+
22+
}
23+
class GFG{
24+
static void printList(Node node)
25+
{
26+
while (node != null)
27+
{
28+
System.out.print(node.data + " ");
29+
node = node.next;
30+
}
31+
System.out.println();
32+
}
33+
public static void main(String args[]) throws IOException {
34+
Scanner sc = new Scanner(System.in);
35+
int t = sc.nextInt();
36+
while(t > 0){
37+
int n = sc.nextInt();
38+
Node head = new Node(sc.nextInt());
39+
Node tail = head;
40+
for(int i=0; i<n-1; i++)
41+
{
42+
tail.next = new Node(sc.nextInt());
43+
tail = tail.next;
44+
}
45+
new Solution().rearrangeEvenOdd(head);
46+
printList(head);
47+
t--;
48+
}
49+
}
50+
}
51+
```
52+
</details>
53+
54+
```java
55+
class Solution
56+
{
57+
void rearrangeEvenOdd(Node head)
58+
{
59+
Node odd = head;
60+
Node even = head.next;
61+
Node evenHead = head.next;
62+
while(even!=null && even.next!=null){
63+
odd.next = even.next;
64+
even.next=even.next.next;
65+
odd = odd.next;
66+
even = even.next;
67+
}
68+
odd.next = evenHead;
69+
70+
}
71+
}
72+
```

0 commit comments

Comments
 (0)