AbdallahCh89
BAN USERimport java.util.*;
public class mergeStr {
public static void main(String[] args) {
double startTime = System.currentTimeMillis();
String A = "Abdallah";
String B = "1234";
System.out.println(shuffleStr(A,B));
double stopTime = System.currentTimeMillis();
double elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);
}
public static ArrayList <String> shuffleStr(String A, String B) {
ArrayList <String> strCombo = new ArrayList<String>();
int [] start = new int [B.length()+2]; //Inner indices are the locations of the B string chars
start[0] = -1; //Starting Index is predefined
start[start.length-1] = A.length() + B.length(); // Ending index is predefined.
strCombo = shuffleStr(strCombo, start, 1, 0, A.length(), A, B);
return strCombo;
}
public static ArrayList<String> shuffleStr(ArrayList<String> res, int [] start, int pos, int min, int max, String A, String B) {
//base case (add current shuffledStr)
if (pos == start.length-1) {
char [] addedStr = new char [A.length()+B.length()]; //
int locA = 0;
for (int i = 1; i < start.length; i++) { //Start directly from the inner
if (i != start.length-1) { addedStr[start[i]] = B.charAt(i-1); } //If still did not hit the outer index
//Fill in the String A (could be done using Strings). But, it is expensive to do substring
for (int j = start[i-1]+1; j < start[i]; j++) {
addedStr[j] = A.charAt(locA);
locA = locA + 1;
}
}
res.add(new String(addedStr)); //Add it .. Also could be done by appending a string: res = res + ....
return res;
}
//Recursion case
else {
for (int i = min; i <= max; i++) { //update char position of B, minimum location, max location
start[pos] = i;
res = shuffleStr(res, start, pos+1, i+1, max+1, A, B);
}
return res;
}
}
}
import java.util.ArrayList;
public class hotels {
public static void main(String[] args) {
int [] [] scores = {{1001, 501, 7}, {1001, 502, 7}, {1001, 503, 7}, {2001, 504, 10}, {3001, 505, 5}, {2001, 506, 5}};
ArrayList<Integer> hotel_ids = get_hotels(scores,7);
System.out.println(hotel_ids);
}
public static ArrayList<Integer> get_hotels(int [] [] scores, int min_avg_score) {
//Step 1: Check the averages of all the unique hotels
ArrayList<Integer> subList = new ArrayList<Integer>();
ArrayList<double[]> compareTo = new ArrayList<double[]>();
for (int i = 0; i < scores.length; i++) {
//If the hotel already exist, Update the average and counter (how many items it appeared)
int indx = subList.indexOf(scores[i][0]);
if (indx != -1) {
double [] E = compareTo.get(indx);
E[1] = E[1] + 1; //How many times this hotel appeared (helps in calculating the average)
E[0] = (E[0]*(E[1]-1)+scores[i][2])/E[1]; //The new average
compareTo.set(indx, E); //update the average and counter of the existing hotel
}
//if it is new to the list, initiate the average to be the score and the counter to be 1
else {
subList.add(scores[i][0]);
double [] E2 = {scores[i][2], 1}; //average and counter
compareTo.add(E2); //add the new hotel to the list of available hotels
}
}
//Step 2: Check which hotels pass the test and add it to the list
ArrayList <Integer> result = new ArrayList<Integer>();
for (int i = 0; i < subList.size(); i++) {
if (compareTo.get(i)[0] >= min_avg_score) {
result.add(subList.get(i));
}
}
return result;
}
}
public static void main(String[] args) {
String nums = "1234";
for (int count = 0; count < nums.length(); count++) { //loop over th degrees of freedom (inner parantheses)
int [] start = new int [count+2];
start[0] = -1; //this is loc the outer parentheses always fixed (...
start[start.length-1] = nums.length()-1; //this is the loc outer parentheses always fixed ...)
printOrder(nums, start, 1, count, 0, nums.length()-2); //count = number of inner parantheses
}
}
public static void printOrder (String orig, int [] start, int pos, int count, int min, int max) {
if (count == 0) { //base case (print)
for (int j = 1; j < start.length; j++) { //insert the parentheses at the right location
System.out.print("(" + orig.substring(start[j-1]+1,start[j]+1) + ")");
}
System.out.println("");
}
else { //Recursion step for the current inner parentheses (goes between position min to max)
for (int k = min; k <= max-count+1; k++) {
start[pos] = k; //update the location of the parentheses
printOrder(orig, start, pos+1, count-1, start[pos]+1, max); //move to the next parentheses
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] nums = {1,2,3,4,5,6,7,8,9,10};
ArrayList<int[]> res = new ArrayList<int[]>();
//The way to think about this is the degrees of freedom
//Here you can imagine the inner parentheses as the degrees of freedom
//We might have "0", "1", ... , "n-1" number of parentheses.
//So we loop over them. As a matter of fact there exist summation(nCk) for k = 0 --> n possible outcomes (= 2^(n-1) )
for (int count = 0; count < nums.length; count++) {
int [] start = new int [count+2];
//Count = number of parentheses, start = location of the parantheses, nums = list of numbers given by user
//res = output, 0 goes for the minimum possible location and nums.length-2 the maximum possible location
res = printOrder(nums, res, start, 1, count, 0, nums.length-2);
}
}
public static ArrayList<int[]> printOrder (int [] orig, ArrayList<int[]> locs, int [] start, int pos, int count, int min, int max) {
//base case only printing out in a nice way using parentheses
if (count == 0) {
start[0] = -1;
start[start.length-1] = orig.length-1;
locs.add(start); //Here is the important thing if you want to keep track and memory
//Printing the substring could be done differently (depends on the data type)
for (int j = 1; j < start.length; j++) {
System.out.print("(");
for (int r = start[j-1]+1; r <= start[j]; r++) {
System.out.print(orig[r]);
}
System.out.print(")");
}
System.out.println("");
return locs;
}
//Recursion step
else {
for (int k = min; k <= max; k++) {
start[pos] = k;
locs = printOrder(orig, locs, start, pos+1, count-1, start[pos]+1, max);
}
}
return locs;
}
Simplified version of the code for strings
public static void main(String[] args) {
String nums = "1234";
for (int count = 0; count < nums.length(); count++) { //loop over th degrees of freedom (inner parantheses)
int [] start = new int [count+2];
start[0] = -1; //this is loc the outer parentheses always fixed (...
start[start.length-1] = nums.length()-1; //this is the loc outer parentheses always fixed ...)
printOrder(nums, start, 1, count, 0, nums.length()-2); //count = number of inner parantheses
}
}
public static void printOrder (String orig, int [] start, int pos, int count, int min, int max) {
if (count == 0) { //base case (print)
for (int j = 1; j < start.length; j++) { //insert the parentheses at the right location
System.out.print("(" + orig.substring(start[j-1]+1,start[j]+1) + ")");
}
System.out.println("");
}
else { //Recursion step for the current inner parentheses (goes between position min to max)
for (int k = min; k <= max-count+1; k++) {
start[pos] = k; //update the location of the parentheses
printOrder(orig, start, pos+1, count-1, start[pos]+1, max); //move to the next parentheses
}
}
}
- AbdallahCh89 July 14, 2016