dp
1.longest common sub sequence
import java.io.*;
class longest
{
public static int lcs(char[] x,char[] y,int m,int n)
{
int[][] a=new int[m+1][n+1];
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0 || j==0)
{
a[i][j]=0;
}
else if(x[i-1]==y[j-1])
a[i][j]=a[i-1][j-1] +1;
else
a[i][j]=Math.max(a[i-1][j],a[i][j-1]);
}
}
return a[m][n];
}
public static void main(String[] args)
{
String s1="AGGTAB";
String s2="GXTXAYB";
char[] x=s1.toCharArray();
char[] y=s2.toCharArray();
int m=x.length;
int n=y.length;
System.out.print(lcs(x,y,m,n));
}
}
Output:
4
2.longest increasing subsequence
class Solution
{
public int lengthOfLIS(int[] nums)
{
int[] lis=new int[nums.length];
for(int i=0;i<nums.length;i++)
{
lis[i]=1;
}
for(int i=1;i<lis.length;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j] && lis[i]<lis[j]+1)
{
lis[i]=lis[j]+1;
}
}
}
int max=0;
for(int i=0;i<lis.length;i++)
{
if(lis[i]>max)
{
max=lis[i];
}
}
return max;
}
}
3.Edit distance
Given two words word1 and word2, find the minimum number of operations required
to convert word1 to word2.
to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
class Solution
{
public int minDistance(String s1, String s2)
{
int[][] a=new int[s1.length() + 1][s2.length() +1];
for(int i=0;i<=s1.length();i++)
{
for(int j=0;j<=s2.length();j++)
{
if(i==0 && j==0)
{
a[i][j]=0;
}
else if(i==0)
{
a[i][j]=j;
}
else if(j==0)
{
a[i][j]=i;
}
else if(s1.charAt(i-1)==s2.charAt(j-1))
{
a[i][j]=a[i-1][j-1];
}
else
{
a[i][j]=1+Math.min(Math.min(a[i-1][j-1],a[i-1][j]),a[i][j-1]);
}
}
}
return a[s1.length()][s2.length()];
}
}
Example 4:
cutting the rod
Given a rod of length n inches and an array of prices that contains prices of all pieces
of size smaller than n. Determine the maximum value obtainable by cutting up the
rod and selling the pieces.
of size smaller than n. Determine the maximum value obtainable by cutting up the
rod and selling the pieces.
Input:
First line consists of T test cases. First line of every test case consists of N, denoting
the size of array. Second line of every test case consists of price of ith length piece.
the size of array. Second line of every test case consists of price of ith length piece.
Output:
Single line output consists of maximum price obtained.
Input:
1
8
1 5 8 9 10 17 17 20
Output:
22
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static int print(int[] a)
{
int[] table=new int[a.length +1];
table[0]=0;
for(int i=1;i<=a.length;i++)
{
int max=Integer.MIN_VALUE;
for(int j=0;j<i;j++)
{
max=Math.max(max,a[j] + table[i-j-1]);
}
table[i]=max;
}
return table[a.length];
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int s=sc.nextInt();
int[] a=new int[s];
for(int j=0;j<s;j++)
{
a[j]=sc.nextInt();
}
System.out.println(print(a));
}
}
}
5.longest palindronic substring
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer. //leetcode
class Solution
{
private int lo,maxlen;
public String longestPalindrome(String s)
{
int len=s.length();
if(len<=2)
{
return s;
}
for(int i=0;i<len-1;i++)
{
extrapalindrome(s,i,i);
extrapalindrome(s,i,i+1);
}
return s.substring(lo, lo + maxlen);
}
private void extrapalindrome(String s,int j,int k)
{
while(j>=0 && k<s.length() && s.charAt(j)==s.charAt(k))
{
j--;
k++;
}
if(maxlen<k-j-1)
{
lo=j+1;
maxlen=k-j-1;
}
}
}
6.longest palindromic subsequence
Given a string s, find the longest palindromic subsequence's length in s.
You may assume that the maximum length of s is 1000.
You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
class Solution
{
public int longestPalindromeSubseq(String s)
{
int[][] dp=new int[s.length()][s.length()];
for(int k=0;k<s.length();k++)
{
for(int i=0,j=k;i<s.length() && j<s.length() ;i++,j++)
{
dp[i][j]=(i==j)?1:s.charAt(i)==s.charAt(j)?dp[i+1][j-1] + 2:Math.max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][s.length()-1];
}
}
7.0/1 knapsack
Input:
The first line of input contains an integer T denoting the number of test cases.
Then T test cases follow. Each test case consists of four lines.
The first line consists of N the number of items.
The second line consists of W, the maximum capacity of the knapsack.
In the next line are N space separated positive integers denoting the values of
the N items and in the fourth line are N space separated positive integers denoting
the weights of the corresponding items.
Then T test cases follow. Each test case consists of four lines.
The first line consists of N the number of items.
The second line consists of W, the maximum capacity of the knapsack.
In the next line are N space separated positive integers denoting the values of
the N items and in the fourth line are N space separated positive integers denoting
the weights of the corresponding items.
Output:
Print the maximum possible value you can get with the given conditions that you
can obtain for each test case in a new line.
can obtain for each test case in a new line.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void calculate(int[] wt,int[] va,int w)
{
int[][] a=new int[va.length+1][w+1];
for(int i=0;i<=va.length;i++)
{
for(int j=0;j<=w;j++)
{
if(i==0 || j==0)
{
a[i][j]=0;
continue;
}
if(j-wt[i-1]>=0)
{
a[i][j]=Math.max(a[i-1][j],a[i-1][j-wt[i-1]] + va[i-1]);
}
else
{
a[i][j]=a[i-1][j];
}
}
}
System.out.println(a[va.length][w]);
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int n1=sc.nextInt();
int w=sc.nextInt();
int[] wt=new int[n1];
int[] va=new int[n1];
for(int j=0;j<n1;j++)
{
va[j]=sc.nextInt();
}
for(int j=0;j<n1;j++)
{
wt[j]=sc.nextInt();
}
calculate(wt,va,w);
}
}
}
8.minimum no of jump to cover
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static int calculate(int[] ar)
{
int[] jumps=new int[ar.length];
jumps[0]=0;
if(ar.length==0 || ar[0]==0)
{
return -1;
}
for(int i=1;i<ar.length;i++)
{
jumps[i]=Integer.MAX_VALUE;
for(int j=0;j<i;j++)
{
if(i<=j+ar[j] && jumps[j]!=Integer.MAX_VALUE)
{
jumps[i]=Math.min(jumps[i],jumps[j] + 1);
break;
}
}
}
if(jumps[ar.length-1]==Integer.MAX_VALUE)
return -1;
else
return jumps[ar.length-1];
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int a=sc.nextInt();
int[] ar=new int[a];
for(int j=0;j<a;j++)
{
ar[j]=sc.nextInt();
}
System.out.println(calculate(ar));
}
}
}
9.egg problem
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void calculate(int egg,int number)
{
int[][] a=new int[egg+1][number+1];
int c=0;
for(int i=0;i<=number;i++)
{
a[1][i]=i;
}
for(int i=2;i<=egg;i++)
{
for(int j=1;j<=number;j++)
{
a[i][j]=Integer.MAX_VALUE;
for(int k=1;k<=j;k++)
{
c=1+Math.max(a[i-1][k-1],a[i][j-k]);
if(c<a[i][j])
{
a[i][j]=c;
}
}
}
}
System.out.println(a[egg][number]);
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int egg=sc.nextInt();
int number=sc.nextInt();
calculate(egg,number);
}
}
}
10.matrix chain multilication
import java.io.*;
class matrix_chain_multiplication
{
public static void calculate(int[] a)
{
int[][] temp=new int[a.length][a.length];
int q=0;
for(int l=2;l<a.length;l++)
{
for(int i=0;i<a.length-l;i++)
{
int j=i+l;
temp[i][j]=1000;
for(int k=i+1;k<j;k++)
{
q=temp[i][k] + temp[k][j] + a[i]*a[k]*a[j];
if(q<temp[i][j])
{
temp[i][j]=q;
}
}
}
}
System.out.print(temp[0][a.length-1]);
}
public static void main(String[] args)
{
int[] a={1,2,3,4};
calculate(a);
}
}
11.word break problem
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
class Solution
{
public boolean wordBreak(String s, List<String> wordDict)
{
if(s==null ||wordDict==null) return false;
boolean[] dp=new boolean[s.length() +1];
dp[0]=true;
for(int i=1;i<s.length() +1;i++)
{
for(int j=0;j<i;j++)
{
if(dp[j] && wordDict.contains(s.substring(j,i)))
{
dp[i]=true;
continue;
}
}
}
return dp[s.length()];
}
}
12.partition sum problem
Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.
public class SubsetSum
{
public boolean subsetSum(int input[], int total)
{
boolean T[][] = new boolean[input.length + 1][total + 1];
for (int i = 0; i <= input.length; i++)
{
T[i][0] = true;
}
for (int i = 1; i <= input.length; i++)
{
for (int j = 1; j <= total; j++)
{
if (j - input[i - 1] >= 0)
{
T[i][j] = T[i - 1][j] || T[i - 1][j - input[i - 1]];
}
else
{
T[i][j] = T[i-1][j];
}
}
}
return T[input.length][total];
}
public boolean partition(int arr[])
{
int sum = 0;
for (int i = 0; i < arr.length; i++)
{
sum += arr[i];
}
if (sum % 2 != 0)
{
return false;
}
sum = sum / 2;
boolean[][] T = new boolean[arr.length + 1][sum + 1];
for (int i = 0; i <= arr.length; i++)
{
T[i][0] = true;
}
for (int i = 1; i <= arr.length; i++)
{
for (int j = 1; j <= sum; j++)
{
if (j - arr[i - 1] >= 0)
{
T[i][j] = T[i - 1][j - arr[i - 1]] || T[i - 1][j];
}
else
{
T[i][j] = T[i-1][j];
}
}
}
return T[arr.length][sum];
}
public static void main(String args[])
{
SubsetSum ss = new SubsetSum();
int arr[] = {1, 3, 5, 5, 2, 1, 1, 6};
System.out.println(ss.partition(arr));
int arr1[] = {2, 3, 7, 8};
System.out.print(ss.subsetSum(arr1, 11));
}
}
13.check subset sum is available or not
import java.util.*;
import java.io.*;
class GFG
{
static boolean modularSum(int arr[],int n, int m)
{
boolean[][] a=new boolean[n+1][m+1];
int i=0;
int j=0;
for(i=0;i<n;i++)
{
a[i][0]=true;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(j<arr[i-1])
{
a[i][j]=a[i-1][j];
}
else
{
a[i][j]=a[i-1][j] || a[i-1][j-arr[i-1]];
}
}
}
return a[n][m];
}
public static void main(String arg[])
{
int arr[] = {1,3,7};
int n = arr.length;
int m = 10;
if(modularSum(arr, n, m))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}
14.Consider a game where a player can score 3 or 5 or 10 points in a move.
Given a total score n, find number of distinct combinations to reach the given score.
Given a total score n, find number of distinct combinations to reach the given score.
input
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N.
Output:
Print number of ways/combinations to reach the given score.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static int count(int ar)
{
int[] table=new int[ar+1];
table[0]=1;
for(int i=3;i<=ar;i++)
{
table[i]=table[i] + table[i-3];
}
for(int i=5;i<=ar;i++)
{
table[i]=table[i] + table[i-5];
}
for(int i=10;i<=ar;i++)
{
table[i]=table[i] + table[i-10];
}
return table[ar];
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] ar=new int[n];
for(int i=0;i<n;i++)
{
ar[i]=sc.nextInt();
}
for(int i=0;i<n;i++)
{
System.out.println(count(ar[i]));
}
}
}
Comments
Post a Comment