hissar
BAN USERDivision is costly.
/**
* @author hissar
*/
public class NextGreatest {
public String nextGreatestLinear (String str) {
if (str == null) return null;
char[] arr = str.toCharArray();
int k = -1;
for (int i = arr.length - 2; i >= 0; i--) {
if (arr[i] < arr[i+1]) {
k = i;
break;
}
}
if (k == -1) return null;
int l = -1;
for (int i = arr.length - 1; i > k; i--) {
if (arr[i] > arr[k]) {
l = i;
break;
}
}
if (l == -1) return null;
// Swap the required characters.
char tmp = arr[k];
arr[k] = arr[l];
arr[l] = tmp;
// reverse the remaining string.
int limit = (l-k) >> 1;
for (int i = 0; i < limit; i++) {
tmp = arr[k+i+1];
arr[k+i+1] = arr[l-i];
arr[l-i] = tmp;
}
return new String(arr);
}
public static void main(String[] args) {
String result = new NextGreatest ().nextGreatestLinear ("144765");
System.out.println(result == null ? "Not Possible" : result);
}
}
/**
* @author hissar
*/
import java.security.InvalidParameterException;
public class KthNodeSwap {
public static <T> void swapKthNodes (LinkedNode<T> head, int k) {
if (head == null)
throw new NullPointerException ("Empty list");
if (k == 0)
throw new InvalidParameterException ("Invalid value of k");
LinkedNode<T> kth = null;
LinkedNode<T> front = null;
LinkedNode<T> track = head;
while (track != null) {
k--;
if (k == 0) {
kth = head;
front = track;
break;
}
track = track.next;
}
if (k != 0 || track == null)
throw new NullPointerException ("In-sufficient no. of Nodes");
while (track.next != null) {
track = track.next;
kth = kth.next;
}
// Perform the swap
T data = front.data;
front.data = kth.data;
kth.data = data;
}
public static void main(String[] args) {
LinkedNode<Integer> head = new LinkedNode<Integer>(1);
LinkedNode<Integer> track = head;
for (int i = 2; i < 8; i++) {
track.next = new LinkedNode<Integer>(i);
track = track.next;
}
swapKthNodes (head, 3);
while (head != null) {
System.out.println(head.data.intValue());
head = head.next;
}
}
}
/**
* @author hissar
*/
public class MinWeightedNode {
static Pair minWeightedNode (BinaryNode<Integer> root,
Pair cand) {
if (root == null) return cand;
Pair c_left = minWeightedNode (root.left, cand);
Pair c_right = minWeightedNode (root.right, c_left);
if (cand == null || cand.value < c_right.value)
cand = c_right;
int sum = root.data +
(root.left != null ? root.left.data : 0) +
(root.right != null ? root.right.data : 0);
if (cand == null || sum > cand.value) {
MinWeightedNode obj = new MinWeightedNode();
return (obj.new Pair(root, sum));
}
return cand;
}
class Pair {
BinaryNode<Integer> node;
int value;
Pair () {
node = null;
value = -1;
}
Pair (BinaryNode<Integer> node, int value) {
this.node = node;
this.value = value;
}
}
public static void main(String[] args) {
BinaryNode<Integer> root = new BinaryNode<Integer>(5);
root.left = new BinaryNode<Integer>(2);
root.right = new BinaryNode<Integer>(6);
root.left.left = new BinaryNode<Integer>(12);
Pair result = minWeightedNode(root, null);
System.out.println (result == null ? "No result" : result.value);
}
}
/**
* @author hissar
*/
import java.io.IOException;
import java.util.Scanner;
public class Deque {
private int arr[];
private final int INIT_SIZE = 1;
private int front;
private int back;
private int currentLength;
private boolean isFull;
Deque () {
this.arr = new int[INIT_SIZE];
this.currentLength = this.INIT_SIZE;
this.front = 0;
this.back = 0;
this.isFull = false;
}
int next (int i) {
i++;
if (i == this.currentLength) i = 0;
return i;
}
int prev (int i) {
i--;
if (i == -1) i = this.currentLength - 1;
return i;
}
void pushBack (int n) {
if (isFull) grow();
arr[back] = n;
back = next(back);
if (front == back) isFull = true;
}
void pushFront (int n) {
if (isFull) grow();
front = prev (front);
arr[front] = n;
if (front == back) isFull = true;
}
int popBack () {
if (!isFull && front == back)
throw new NullPointerException("Empty Deque.");
back = prev(back);
isFull = false;
return arr[back];
}
int popFront () {
if (!isFull && front == back)
throw new NullPointerException("Empty Deque.");
int val = arr[front];
front = next(front);
isFull = false;
return val;
}
private void grow() {
int len = this.currentLength;
this.currentLength <<= 1;
int[] newarr = new int[this.currentLength];
int index = 0;
for (int i = front; i < len; i++)
newarr[index++] = arr[i];
for (int i = 0; i < back; i++)
newarr[index++] = arr[i];
isFull = false;
front = 0;
back = index;
arr = newarr;
}
void print () {
System.out.println("Front = " + front + "\nBack = " + back +
"\nisFull = " + isFull);
System.out.println("DQ => ");
for (int i = 0; i < this.currentLength; i++)
System.out.print(arr[i] + " ");
System.out.println("");
}
public static void main(String[] args) throws IOException {
Scanner ob = new Scanner (System.in);
Deque dq = new Deque();
do {
System.out.println("1. Push Front\n2. Push Back\n3. Pop Front\n4. Pop Back"
+ "\n5. Print\n6. Exit");
int choice = ob.nextInt();
switch (choice) {
case 1: System.out.println("Enter"); dq.pushFront(ob.nextInt()); break;
case 2: System.out.println("Enter"); dq.pushBack(ob.nextInt()); break;
case 3: System.out.println("Popped = " + dq.popFront()); break;
case 4: System.out.println("Popped = " + dq.popBack()); break;
case 5: dq.print(); break;
default : ob.close(); System.exit(0);
}
} while (true);
}
}
Time = O(n); Space = O(n)
- hissar March 26, 2013