salvo4u
BAN USERuses DP and more can be read on en.wikipedia.org/wiki/Partition_problem :
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int arr[] = new int[n];
int K = 0;//sum of array
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
K = K + arr[i];
}
//algorithm starts here
int M[] = new int[K + 1];
M[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = K - arr[i]; j >= 0; j--) {
if (M[j] == 1)
M[j + arr[i]] = 1;
}
}
int mindiff = Integer.MAX_VALUE;
for (int i = 1; i <= K; i++) {
if (M[i] == 1) {
int s1 = i;
int s2 = K - s1;
if (Math.abs(s2 - s1) < mindiff)
mindiff = Math.abs(s2 - s1);
}
}
System.out.println(mindiff);
}
// to add two numbers using strings a,b are two numbers
public static String stringAddition(String a, String b) {
String sum = "";
int carry = 0;
if (a.length() > b.length()) {
String temp = a;
a = b;
b = temp;
}
for (int i = 0; i < a.length(); i++) {
int s = a.charAt(a.length() - 1 - i) + b.charAt(b.length() - 1 - i)
- 96 + carry;
if (s > 9) {
carry = (s - s % 10) / 10;
s = s % 10;
} else {
carry = 0;
}
sum = s + sum;
}
for (int i = 0; i < b.length() - a.length(); i++) {
int s = b.charAt(b.length() - a.length() - 1 - i) + carry - 48;
if (s > 9) {
carry = (s - s % 10) / 10;
s = s % 10;
} else {
carry = 0;
}
sum = s + sum;
}
if (carry != 0)
return carry + sum;
else
return sum;
}
Visit the link: anshulsalvo.blogspot.in/2012/02/problem-20.html
- salvo4u June 23, 2012HashMap<Integer, Long> hmap=new HashMap<Integer, Long>();
long power(int a, int b) {
if (b == 0)
return 1;
if (b == 1)
return a;
if(hmap.containsKey(b))
return hmap.get(b);
long p = power(a, b / 2) * power(a, b / 2);
if (b % 2 == 1)
p=p*a;
hmap.put(b, p);
return p;
}
uses DP also
- salvo4u June 16, 2012use a heap
* build a min heap of 4 elements
* iterate over the remaining elements
* if the remaining element is greater than the minimum element of the heap
----- delete the minimum element
----- insert the new element
at the end u will be left with the 4 greatest element in the heap
public class problem {
static HashMap<Integer, ArrayList<String>> hmap = new HashMap<Integer, ArrayList<String>>();
static ArrayList<String> mergeList(ArrayList<String> l1,
ArrayList<String> l2, int n) {
ArrayList<String> list = new ArrayList<String>();
for (int i = 0; i < l1.size(); i++) {
String first = l1.get(i);
for (int j = 0; j < l2.size(); j++) {
String second = l2.get(j);
String s = first + " " + second;
if (hmap.get(n) == null) {
list.add(s);
hmap.put(n, list);
continue;
} else {
if (hmap.get(n).contains(s) == false)
hmap.get(n).add(s);
}
}
}
return list;
}
static ArrayList<String> getList(int n) {
ArrayList<String> mainlist = new ArrayList<String>();
if (n == 1) {
mainlist.add("1");
hmap.put(n, mainlist);
return mainlist;
}
if (n == 2) {
mainlist.add("1 1");
hmap.put(n, mainlist);
return mainlist;
}
if (n == 3) {
mainlist.add("1 1 1");
mainlist.add("1 2");
hmap.put(n, mainlist);
return mainlist;
}
ArrayList<String> l1, l2, list;
for (int i = 1; i <= n / 2; i++) {
if (hmap.get(i) == null)
l1 = getList(i);
else
l1 = hmap.get(i);
if (hmap.get(n - i) == null)
l2 = getList(n - i);
else
l2 = hmap.get(n - i);
list = mergeList(l1, l2, n);
list.add(i + " " + (n - i));
mainlist.addAll(list);
}
hmap.put(n, mainlist);
System.out.println(n + "----->" + mainlist.size());
return mainlist;
}
public static void main(String args[]) {
ArrayList<String> list = getList(6);
System.out.println(list);
}
}
Assume A[0]=m then
A[1]=m-1 or m+1
A[2]=m-2 , m, m+2
A[3]=m-3,m-1,m+1,m+3
So A[n] can be any one of these
A[n] = m-n, m-(n-2) , .......... , m+(n-2) , m+n
So A[i] belongs to m-i to m+i for i=1 to n
Hence we can perform a binary search at every level
Time:O(lg1)+O(lg2)+O(lg3)+....+O(lgn) = O(n) similar to construction of binary heap
if A[0]=m then the codemight look like this:
public static boolean bsearch(int start, int end, int ele) {
int mid = start + (end - start) / 2;
if (start > end)
return false;
if (ele == mid)
return true;
if (ele < mid)
return bsearch(start, mid - 1, ele);
else
return bsearch(mid + 1, end, ele);
}
public static void main(String[] args) {
int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13};
int m = arr[0];
int k=12;
for (int i = 1; i < arr.length; i++) {
boolean found=bsearch(m-i,m+i,k);
if(found)
{
System.out.println("index "+i+" = +k);
System.exit(1);
}
}
System.out.println("Not Found");
}
uses DP :
static HashMap<Integer, Integer> hmap=new HashMap<Integer,Integer>();
public static int catalanNumber(int n) {
if (n == 1||n==0)
return 1;
if (n == 2)
return 2;
if(hmap.containsKey(n))
return hmap.get(n);
int sum = 0;
for (int i = 0; i < n; i++)
sum = sum + catalanNumber(i) * catalanNumber(n - i - 1);
hmap.put(n,sum);
return sum;
}
@Ram :
* Assume u have n nodes
* the left subtree has i nodes
* the right subtree will have n-i-1 nodes
Let
T(i) the number of trees for the left subtree then
T(n-i-1) will the number of subtrees for the right
Total number of trees will be T(i)*T(n-i-1) for all i belongin to 0 to n-1
The recurssion is what i have coded above wothout DP
U r rite but the remove thing might not be true
* The solution are identical apart from the fact that u have to explicitly maintain 2 stacks i dont do that and travesre the arraylist in opposite direction.
* Secondly i manage things using 1 object only in ur case an extra object has to be maintained
import java.io.IOException;
import java.util.ArrayList;
class TreeNode {
public TreeNode levelnext,next,left, right;
public int data;
TreeNode(int data) {
this.data = data;
}
}
public class ZIGZAGTRAVERSAL {
public static TreeNode getRandomBST() {
TreeNode mainroot = new TreeNode(7);
TreeNode root = mainroot;
root.left = new TreeNode(5);
root.right = new TreeNode(12);
root.left.left = new TreeNode(3);
root.left.left.left = new TreeNode(2);
root.left.right = new TreeNode(6);
root.left.left.right = new TreeNode(4);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(14);
return mainroot;
}
public static void zigZag(TreeNode node) {
int direction = 1;
ArrayList<TreeNode> alist = new ArrayList<TreeNode>();
alist.add(node);
int count1 = 1;
int count2 = 0;
while (alist.size() > 0) {
if (direction == 1) {
for (int i = 0; i < count1; i++) {
TreeNode n = alist.get(i);
if (n.left != null) {
count2++;
alist.add(n.left);
}
if (n.right != null) {
count2++;
alist.add(n.right);
}
}
for (int i = 0; i < count1; i++) {
System.out.print(alist.get(0).data + " ");
alist.remove(0);
}
count1 = 0;
} else {
int pos2 = alist.size() - 1;
int pos1 = alist.size() - count2;
for (int i = pos1; i <= pos2; i++) {
TreeNode n = alist.get(i);
if (n.left != null) {
count1++;
alist.add(n.left);
}
if (n.right != null) {
count1++;
alist.add(n.right);
}
}
for (int i = pos2; i >= pos1; i--) {
System.out.print(alist.get(i).data + " ");
alist.remove(i);
}
count2 = 0;
}
direction = direction ^ 1;
}
}
public static void main(String args[]) throws IOException {
TreeNode bst = getRandomBST();
zigZag(bst);
}
}
public static Node kReverseList(int k, Node head) {
int i = 0;
Node x = head;
if (x == null) {
}
Node y = x.next;
if (y == null)
return x;
Node z = x.next.next;
while (i < k - 1) {
y.next = x;
if (z == null) {
head.next = null;
return y;
}
x = y;
y = z;
z = z.next;
i++;
}
head.next = kReverseList(k, y);
return x;
}
this 1 from wiki:
public class Quine
{
public static void main( String[] args )
{
char q = 34; // Quotation mark character
String[] l = { // Array of source code
"public class Quine",
"{",
" public static void main( String[] args )",
" {",
" char q = 34; // Quotation mark character",
" String[] l = { // Array of source code",
" ",
" };",
" for( int i = 0; i < 6; i++ ) // Print opening code",
" System.out.println( l[i] );",
" for( int i = 0; i < l.length; i++ ) // Print string array",
" System.out.println( l[6] + q + l[i] + q + ',' );",
" for( int i = 7; i < l.length; i++ ) // Print this code",
" System.out.println( l[i] );",
" }",
"}",
};
for( int i = 0; i < 6; i++ ) // Print opening code
System.out.println( l[i] );
for( int i = 0; i < l.length; i++ ) // Print string array
System.out.println( l[6] + q + l[i] + q + ',' );
for( int i = 7; i < l.length; i++ ) // Print this code
System.out.println( l[i] );
}
}
u will any how have to keep a hashset or a treeset as they are concrete classes.
Set is just an interface.
Secondly i used a set so that words are not repeated.
Syso(hashmap) will not give an error it will otpur the whole hashmap with keys and corresponding sets.
The sets are ur answer
public static void main(String[] args) {
String arr[] = { "plates", "stop", "staple", "pots", "meat", "not",
"pot", "team" };//read from file
HashMap<String, TreeSet<String>> hashMap = new HashMap<String, TreeSet<String>>();
for (int i = 0; i < arr.length; i++) {
String s = arr[i];
char charr[] = s.toCharArray();
Arrays.sort(charr);
String sorted = new String(charr);
if (hashMap.containsKey(sorted))
hashMap.get(sorted).add(s);
else {
TreeSet<String> ts = new TreeSet<String>();
ts.add(s);
hashMap.put(sorted, ts);
}
}
System.out.println(hashMap);
}
* sort each word for the anagram test
* make the sorted word the key
* keep adding to the list of the sorted word
/*
public class TreeNode {
public TreeNode levelnext,next,left, right;
public int data;
TreeNode(int data) {
this.data = data;
}
}
*/
static TreeNode next;
public static void inorderSuccersor(TreeNode root) {
if (root != null) {
inorderSuccersor(root.right);
root.next = next;
next = root;
inorderSuccersor(root.left);
}
}
Use Kadane's algorithm
public static int kadanes(int arr[]) {
int currsum = 0, maxsum = 0;
for (int i = 0; i < arr.length; i++) {
currsum = currsum + arr[i];
if (currsum > maxsum)
maxsum = currsum;
if (currsum < 0)
currsum = 0;
}
return maxsum;
}
* This wont work for negative numbers
- salvo4u May 15, 2012public static void printPaths(int mat[][], int s, int t, int n,ArrayList<Integer> list) {
if (list.contains(new Integer(t + ""))) {
System.out.println(list);
return;
}
for (int i = 0; i < n; i++) {
if (mat[s][i] == 1) {
list.add(new Integer(i));
mat[s][i] = 0;
mat[i][s]=0;
printPaths(mat, i, t, n, list);
list.remove((Object) i);
mat[s][i] = 1;
mat[i][s]=1;
}
}
}
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int n = new Integer(s);
int mat[][] = new int[n][n];
for (int i = 0; i < n; i++) {
s = br.readLine();
String arr[] = s.split(" ");
for (int j = 0; j < n; j++)
mat[i][j] = new Integer(arr[j]);
}
Integer s1=1,t1=0;
ArrayList list=new ArrayList<Integer>();
list.add(s1);
printPaths(mat, s1, t1, n, list);
}
* code performs DFS and checks for all possible paths between s and t .
* mat is the sqaure matrix of size n*n.
* list in recursion maintains all the paths
USE kadanes algorithm for maximum subarray :
en.wikipedia.org/wiki/Maximum_subarray_problem
For extending this problem in 2d for squares the following DP solution can work:
M[ i ][ j ] = min( M[ i -1 ][ j ], M[ i ][ j-1 ],M[ i-1 ][ j-1 ] )+1
where M[ i ][ j ] contains the maximum 2d subarray in size which the original matrix element C[ i ][ j ] is a part of.
USE kadanes algorithm for maximum subarray :
en.wikipedia.org/wiki/Maximum_subarray_problem
For extending this problem in 2d for squares the following DP solution can work:
M[ i ][ j ] = min( M[ i -1 ][ j ], M[ i ][ j-1 ],M[ i-1 ][ j-1 ] )+1
where M[ i ][ j ] contains the maximum 2d subarray in size which the original matrix element C[ i ][ j ] is a part of.
Travel thru the list once count the number of 0s(m) and 1s.(n)
- salvo4u August 13, 2012In the next traversal set the first m nodes to 0 and the next n to 1 ....