Anirudh
BAN USERThis is based on Kadane's algo. Please correct me if I am wrong anywhere.
public class LengthOfMaxSumArray {
public static int[] getMaxSumArray(int array[]) {
int max_ending_here = 0;
int max_so_far = 0;
int max_start_index = 0;
int max_end_index = 0;
for(int i=0; i<array.length; i++) {
max_ending_here = max_ending_here + array[i];
if(max_ending_here < 0) {
max_ending_here = 0;
max_start_index = i+1;
}
if(max_so_far < max_ending_here) {
max_so_far = max_ending_here;
max_end_index = i;
}
}
int res[] = new int[max_end_index - max_start_index+1];
int j=0;
for(int i=max_start_index; i<= max_end_index; i++) {
res[j] = array[i];
j++;
}
return res;
}
public static void main(String args[]) {
int array[] = {7,4,-2,5,3,-6,8,-8};
int res[] =getMaxSumArray(array);
for(int i=0; i<res.length; i++) {
System.out.println(res[i]);
}
}
}
I have written a code which produces all ordered strings. All it takes is the total number of input characters. You can also specify the start of the string if you wish to. If you don't specify, it gives you all ordered strings of that length starting from 'a'.
public class OrderedString {
//private static int stringCount=0;
public static void getAllOrderedStrings(String currentString, int charsLeft) {
if(charsLeft==0)
{
System.out.println(currentString);
//stringCount++;
}
char i;
if(currentString.isEmpty())
i='a';
else
i=(char) (currentString.charAt(currentString.length()-1)+1);
for (;i<='z';i++)
{
getAllOrderedStrings(currentString+i, charsLeft-1);
}
}
public static void main(String args[]) {
getAllOrderedStrings("", 4);
}
}
This is a simple java code.
import java.util.ArrayList;
import java.util.HashMap;
public class BullsAndCows {
public static int[] getBullsAndCows(String A, String B) {
int bulls = 0;
int cows = 0;
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer, ArrayList<Integer>>();
A = A.toLowerCase();
B = B.toLowerCase();
for(int i=0; i<A.length(); i++) {
int a = A.charAt(i);
if(!hm.containsKey(a)) {
ArrayList<Integer> array = new ArrayList<Integer>();
array.add(i);
hm.put(a, array);
}
else {
ArrayList<Integer> array = hm.get(a);
array.add(i);
hm.put(a, array);
}
}
for(int i=0; i<B.length(); i++) {
int b = B.charAt(i);
if(hm.containsKey(b)) {
ArrayList<Integer> array = hm.get(b);
if(array.contains(i)) {
bulls++;
}
else {
cows++;
}
}
}
int res[] = new int[2];
res[0] = bulls;
res[1] = cows;
return res;
}
public static void main(String args[]) {
int array[] = getBullsAndCows("forum", "four");
System.out.println("Bulls = " + array[0] + "," + "Cows =" + array[1]);
}
}
This is a simple java solution. I try to find all subsets greater than size 1 and then calculate the product and if it is unique, return true; else false.
import java.util.ArrayList;
public class ColorfulNumber {
public static boolean checkColorful(int num) {
String str = String.valueOf(num);
ArrayList<Integer> array = new ArrayList<Integer>();
for(int i=0; i<str.length(); i++) {
int a = str.charAt(i);
a = a - 48;
array.add(a);
}
ArrayList<Integer> products = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> subsets = getSubsets(array);
for(ArrayList<Integer> set : subsets) {
if(set.size() >= 2) {
int val = 1;
for(int i=0; i<set.size(); i++) {
val = val * set.get(i);
}
if(!products.contains(val)) {
products.add(val);
}
else {
return false;
}
}
}
return true;
}
public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> array) {
ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
if(array.size() == 0) {
subsets.add(new ArrayList<Integer>());
}
else {
ArrayList<Integer> array_copy = new ArrayList<Integer>();
array_copy.addAll(array);
int first = array_copy.remove(0);
ArrayList<ArrayList<Integer>> reduced_set = getSubsets(array_copy);
subsets.addAll(reduced_set);
reduced_set = getSubsets(array_copy);
for(ArrayList<Integer> set : reduced_set) {
set.add(0, first);
}
subsets.addAll(reduced_set);
}
return subsets;
}
public static void main(String args[]) {
System.out.println(checkColorful(235));
}
}
import java.util.ArrayList;
public class Criteria {
public static ArrayList<Integer> produceSeries(int start, int end) {
ArrayList<Integer> array = new ArrayList<Integer>();
for(int i=start; i<end; i++) {
if(checkCriteria(i)) {
array.add(i);
}
}
return array;
}
public static boolean checkCriteria(int num) {
String str = String.valueOf(num);
if(str == null || str.length() == 1 || str.length() == 2) {
return false;
}
for(int i=0; i<str.length(); i++) {
if(i == 0) {
if(str.charAt(i) != str.charAt(i+1)) {
return false;
}
}
else if(i >= 2) {
int a = str.charAt(i);
a = a -48;
int b = str.charAt(i-1);
b = b - 48;
int c = str.charAt(i-2);
c = c - 48;
if(a != b+c) {
return false;
}
}
}
return true;
}
public static void main(String args[]) {
ArrayList<Integer> array = produceSeries(1000, 9999);
System.out.println(array);
}
}
This is just traversing each level and if you encounter the last element in the level, add that corresponding linkedlist to an arrayList. To know if the end of each level has been reached, we can simply add a null in the queue in beginning and if you enounter null while pop, add another.
- Anirudh February 28, 2015