havefun
BAN USERpublic class MaxSubArrayProduct {
static class Data{
int product;
int startIndex;
int endIndex;
Data(){
super();
this.product = Integer.MIN_VALUE;
this.startIndex = -1;
this.endIndex = -1;
}
public Data(int product, int startIndex, int endIndex) {
super();
this.product = product;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
@Override
public String toString() {
return "Data [product=" + product + ", startIndex=" + startIndex + ", endIndex=" + endIndex + "]";
}
}
static Data ProcessSubArray(int[] arr, int startIndex, int endIndex){
if (startIndex == endIndex){
return new Data(arr[startIndex], startIndex, endIndex);
}else{
int val = 1;
int firstNegativeIndex = -1;
int lastNegativeIndex = -1;
for (int i=startIndex; i<=endIndex; i++){
val *= arr[i];
if (arr[i] <0){
if (firstNegativeIndex == -1){
firstNegativeIndex = i;
}
lastNegativeIndex = i;
}
}
if (val < 0){
int multiplierFirst = 1;
for (int j=startIndex; j<=firstNegativeIndex; j++){
multiplierFirst*=arr[j];
}
int multiplierLast = 1;
for (int j=lastNegativeIndex; j<=endIndex; j++){
multiplierLast*=arr[j];
}
if (val/multiplierFirst > val/multiplierLast){
startIndex = firstNegativeIndex+1;
val = val/multiplierFirst;
}else{
endIndex = lastNegativeIndex -1;
val = val/multiplierLast;
}
}
Data data = new Data(val, startIndex, endIndex);
return data;
}
}
private static void ProcessArr(int[] arr) {
if (arr == null || arr.length <=0){
System.out.println(new Data(Integer.MIN_VALUE, -1, -1));
return;
}
Data maxData = new Data();
int startIndex = -1;
for (int i=0; i<arr.length; i++){
if (arr[i] == 0){
if (startIndex != -1){
Data data = ProcessSubArray(arr, startIndex, i-1);
if (data.product>maxData.product){
maxData = data;
}
startIndex =-1;
}
if (0>maxData.product){
maxData = new Data(0, i, i);
}
} else {
if (startIndex == -1){
startIndex = i;
}
}
}
if (startIndex!=-1){
Data data = ProcessSubArray(arr, startIndex, arr.length-1);
if (data.product>maxData.product){
maxData = data;
}
}
System.out.println(maxData.toString());
}
public static void main(String[] args){
int arr[] = {0, 1, 2, -6, 8, 10, -9, -5, 1, 0, 8, 6, 5, 0};
ProcessArr(arr);
arr = new int[]{};
ProcessArr(arr);
arr = new int[]{0};
ProcessArr(arr);
arr = new int[]{-1};
ProcessArr(arr);
arr = new int[]{2};
ProcessArr(arr);
arr = new int[]{-3, 2};
ProcessArr(arr);
arr = new int[]{3, -2};
ProcessArr(arr);
arr = new int[]{-3, 2, 0, 0 , 3, -2};
ProcessArr(arr);
arr = new int[]{0, 0, -3, 2, 0, 0 , 3, -2, 0, 0};
ProcessArr(arr);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
public class MinIntervalCountToCoverInterval {
static class Interval implements Comparable<Interval>{
Integer sT;
Integer eT;
Interval(int sT, int eT){
this.sT = sT;
this.eT = eT;
}
@Override
public int compareTo(Interval o) {
return eT.compareTo(o.eT);
}
@Override
public String toString() {
return "[" + sT + ", " + eT + "]";
}
}
static ArrayList<Interval> FindMinInterval(ArrayList<Interval> list, Interval reqInterval){
Set<Integer> set = new HashSet<Integer>();
for (int i=0; i< list.size(); i++){
set.add(list.get(i).sT);
set.add(list.get(i).eT);
}
set.add(reqInterval.sT);
set.add(reqInterval.eT);
Integer arr[] = set.toArray(new Integer[set.size()]);
Arrays.sort(arr);
HashMap<Integer, Interval> bestIntervalMap = new HashMap<Integer, Interval>();
for (int i=0; i< list.size(); i++){
Interval interval = list.get(i);
int startIndex = Arrays.binarySearch(arr, interval.sT);
if (startIndex < 0){
startIndex = -startIndex -1;
}
int endIndex = Arrays.binarySearch(arr, interval.eT);
if (endIndex < 0){
endIndex = -endIndex -1;
}
endIndex--;
for (int j=startIndex; j<=endIndex; j++){
if (!bestIntervalMap.containsKey(arr[j])){
bestIntervalMap.put(arr[j], interval);
} else {
if (bestIntervalMap.get(arr[j]).eT < interval.eT){
bestIntervalMap.put(arr[j], interval);
}
}
}
}
int startTime = reqInterval.sT;
ArrayList<Interval> intervalList = new ArrayList<Interval>();
while (startTime < reqInterval.eT){
Interval interval = bestIntervalMap.get(startTime);
if (interval == null){
return null;
}
intervalList.add(interval);
startTime = interval.eT;
}
return intervalList;
}
static void PrintList(ArrayList<Interval> list){
if (list!=null){
for (int i=0; i<list.size(); i++){
System.out.print(list.get(i).toString() + ((i == list.size()-1) ? "" : ", "));
}
System.out.println();
}else{
System.out.println("Not possible");
}
}
public static void main(String[] args){
ArrayList<Interval> list = new ArrayList<Interval>();
list.add(new Interval(-1, 9));
list.add(new Interval(1, 10));
list.add(new Interval(0, 3));
list.add(new Interval(9, 10));
list.add(new Interval(3, 14));
list.add(new Interval(2, 9));
list.add(new Interval(10, 16));
PrintList(FindMinInterval(list, new Interval(2, 15)));
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class PrintTreePathWithHyphen2 {
static class Node{
Character c;
Node l,r;
Node(Character c){
this.c = c;
this.l=null;
this.r = null;
}
}
static String GetStringForHyphen(int count){
String hyphenString = "";
for (int i=0; i<count; i++){
hyphenString+="-";
}
return hyphenString;
}
static void PrintTree(Node head, int hyphenCnt, int minHyphenCnt, ArrayList<Node> q, HashMap<Node, Integer> map){
map.put(head, hyphenCnt);
q.add(head);
if (head.r == null && head.l == null){
for (int i=0; i<q.size(); i++){
Node n = q.get(i);
String hyphenStr = GetStringForHyphen(map.get(n) - minHyphenCnt);
System.out.println(hyphenStr + n.c);
}
System.out.println("");
q.remove(q.size()-1);
return;
}
if (head.l != null) {
PrintTree(head.l, hyphenCnt-1, Integer.min(minHyphenCnt, hyphenCnt-1), q, map);
}
if (head.r != null) {
PrintTree(head.r, hyphenCnt+1, Integer.min(minHyphenCnt, hyphenCnt+1), q, map);
}
q.remove(q.size()-1);
}
static public void main(String[] val){
Node head = new Node('A');
head.l = new Node('B');
head.r = new Node('C');
head.l.l = new Node('D');
head.l.r = new Node('E');
head.r.l = new Node('F');
head.r.r = new Node('G');
head.l.l.l = new Node('H');
head.l.l.r = new Node('I');
head.l.r.l = new Node('J');
head.l.r.r = new Node('K');
head.l.r.r.l = new Node('P');
head.l.r.r.l.l = new Node('Q');
head.l.r.r.l.l.l = new Node('R');
head.l.r.r.l.l.l.l = new Node('S');
head.r.l.l = new Node('L');
head.r.l.r = new Node('M');
head.r.r.l = new Node('N');
head.r.r.r = new Node('O');
ArrayList<Node> stack = new ArrayList<Node>();
PrintTree(head, 0, 0, stack, new HashMap<Node, Integer>());
/*
A
B C
D E F G
H I J K L M N O
*/
}
}
import java.util.ArrayList;
public class PrintTreePathWithHyphen {
static class Node{
Character c;
Node l,r;
Node(Character c){
this.c = c;
this.l=null;
this.r = null;
}
}
static void PrintList(ArrayList<String> list){
System.out.println("Output:");
for (String s: list){
System.out.println(s);
}
System.out.println();
}
static void AddHyphenPrefix(ArrayList<String> list){
for (int j=list.size()-1; j>=0; j--){
String s = list.get(j);
s ="-" + s;
list.set(j, s);
}
}
static String GetStringForHyphen(int count){
String hyphenString = "";
for (int i=0; i<count; i++){
hyphenString+="-";
}
return hyphenString;
}
static void PrintTree(Node node, ArrayList<String> list, int hyphenCount){
if (node.l == null && node.r == null){
PrintList(list);
return;
}else{
if (node.r != null){
list.add(GetStringForHyphen(hyphenCount+1) + node.r.c);
PrintTree(node.r, list, hyphenCount+1);
list.remove(list.size()-1);
}
int hyphenCountL = hyphenCount;
if (node.l != null){
if (hyphenCountL > 0) {
hyphenCountL--;
list.add(GetStringForHyphen(hyphenCountL) + node.l.c);
PrintTree(node.l, list, hyphenCountL);
list.remove(list.size()-1);
} else {
ArrayList<String> listL = (ArrayList<String>)list.clone();
AddHyphenPrefix(listL);
listL.add("" + node.l.c);
PrintTree(node.l, listL, hyphenCountL);
}
}
}
}
static public void main(String[] val){
Node node = new Node('A');
node.l = new Node('B');
node.r = new Node('C');
node.l.l = new Node('D');
node.l.r = new Node('E');
node.r.l = new Node('F');
node.r.r = new Node('G');
node.l.l.l = new Node('H');
node.l.l.r = new Node('I');
node.l.r.l = new Node('J');
node.l.r.r = new Node('K');
node.r.l.l = new Node('L');
node.r.l.r = new Node('M');
node.r.r.l = new Node('N');
node.r.r.r = new Node('O');
ArrayList<String> list = new ArrayList<String>();
list.add("" + node.c);
PrintTree(node, list, 0);
/*
A
B C
D E F G
H I J K L M N O
*/
}
}
- havefun March 13, 2017