shiqing881215
BAN USERHi this is good solution, but the time complexity should not be O(n), it should be O(nlogn), coz you cannot guarantee you can eliminate n-1 in the first round, the worst situation you can only delete n/2.
- shiqing881215 September 30, 2012I use recursive, and I think it's not good, I'm looking forward to seeing better solution
private static double equalGreater = 0;
public static void findProbability(int n, int m, int x, ArrayList<Integer> list, int index) {
if (index == n) {
if (sum(list) >= x) {
equalGreater++;
}
} else {
for (int i = 1; i <= m; i++) {
if (index == list.size()) { // first time
list.add(i);
} else { // the remaining steps just change it
list.set(index, i);
}
ArrayList<Integer> newList = (ArrayList<Integer>) list.clone();
findProbability(n,m,x,newList,index+1);
}
}
}
public static int sum(ArrayList<Integer> list) {
int r = 0;
for (int i = 0; i < list.size(); i++) {
r += list.get(i);
}
return r;
}
public static double getProbility(int n, int m, int x) {
int min = n;
int max = m*n;
if (x <= min) return 1;
if (x > max) return 0;
double doublen = n;
double doublem = m;
double total = Math.pow(doublem, doublen);
findProbability(n,m,x,new ArrayList<Integer>(), 0);
return equalGreater/total;
}
In my opinion, not sure whether the number out of the bounds of integer is correct, I mean, in java, int is 4 bytes. Also not sure whether number like 4+6j, which is a virtual number, is right
- shiqing881215 August 25, 2012Can we store the last node reference in an additional node variable, and after each operation on the linked list, we update this variable.
- shiqing881215 August 24, 2012I think we can use recursive to solve this problem.
private static ArrayList<Integer> allSizes = new ArrayList<Integer>();
public void getAllSize(int[] array, int sum, ArrayList<Integer> list, int index) {
if (getSum(list) == sum) {
allSizes.add(list.size());
return;
}
if (getSum(list) > sum) {
return;
}
for (int i = index; i < array.length; i++) {
list.add(array[i]);
getAllSize(array, sum, list, i+1);
list.remove(list.size()-1);
}
}
public int getMinNumberCoin(int[] array, int sum) {
getAllSize(array,sum,new ArrayList<Integer>(),0);
int min = Integer.MAX_VALUE;
for (int i = 0; i < allSizes.size(); i++) {
if (min > allSizes.get(i)) {
min = allSizes.get(i);
}
}
return min;
}
public int getSum(ArrayList<Integer> list) {
int result = 0;
for (int i = 0; i < list.size(); i++) {
result += list.get(i);
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
Amazon16_MinNumberCoins a = new Amazon16_MinNumberCoins();
int[] array = {25,5,50,25,25,25,1};
System.out.print(a.getMinNumberCoin(array, 100));
}
what if the number of needed move is larger than the move left. What should we do when we have no enough move to move the largest number to the first position?
- shiqing881215 August 21, 2012Just have 2 queues to implement this question
- shiqing881215 August 20, 2012public class Google13_FindMinDiffSets {
/*
* In my opinion,
* First, we find the first two numbers which have the min diff.
* Then recursive on the following set, find another two, compare which set should add these two new value,
* Then continue until all elements have been assigned
*/
private static ArrayList<Integer> zero = new ArrayList<Integer>();
private static ArrayList<Integer> one = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> getMinSumDiffSets(int[] array) {
if (array.length % 2 != 0) {
return null;
}
ArrayList<ArrayList<Integer>> result ;
if (array.length == 2) {
if (Math.abs((sum(zero)+array[0])-(sum(one)+array[1])) < Math.abs((sum(zero)+array[1])-(sum(one)+array[0]))) {
zero.add(array[0]);
one.add(array[1]);
} else {
zero.add(array[1]);
one.add(array[0]);
}
result= new ArrayList<ArrayList<Integer>>();
result.add(zero);
result.add(one);
return result;
} else {
int[] min = findMinDiff(array);
if (Math.abs((sum(zero)+array[min[0]])-(sum(one)+array[min[1]])) < Math.abs((sum(zero)+array[min[1]])-(sum(one)+array[min[0]]))) {
zero.add(array[min[0]]);
one.add(array[min[1]]);
} else {
zero.add(array[min[1]]);
one.add(array[min[0]]);
}
result = getMinSumDiffSets(deleteElements(array, min[0], min[1]));
return result;
}
}
public int[] findMinDiff(int[] a) {
int min = Integer.MAX_VALUE;
int[] result = new int[2];
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[j]-a[i] < min) {
min = a[j]-a[i];
result[0] = i;
result[i] = j;
}
}
}
return result;
}
public int sum (ArrayList<Integer> a) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
sum += a.get(i);
}
return sum;
}
public int[] deleteElements(int[] a, int i, int j) {
int[] result = new int[a.length-2];
int index = 0;
for (int k = 0; k < a.length; k++) {
if (k == i || k == j) {
continue;
} else {
result[index++] = a[k];
}
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,2,3,100};
Google13_FindMinDiffSets g = new Google13_FindMinDiffSets();
ArrayList<ArrayList<Integer>> result = g.getMinSumDiffSets(a);
System.out.println(g.sum(result.get(0)));
System.out.println(g.sum(result.get(1)));
}
}
@ shondik hi, it's very nice to discuss with you, if you don't mind, can we make a friend? my email is username @gmail
- shiqing881215 July 23, 2012@shondik Thx for you correction. I have change the tree to following:
.............................10
..................2......................11
......................3
...........................9
......................8
.................4
......................5
...........................6
However, I run your code, as i expected, it doesn't output 11, instead, it outputs the 9.
Coz in your second for loop, when you go to the node 3, now p is the node 4, node 3 has a right child 9 which is not equal to p, so you will return the 9. And i think that's not right. thx
i'm not sure but i think there maybe some problem for this solution, think the following situation:
.............................10
..................2......................11
......................3
...........................9
......................8
.................1
......................4
...........................5
if i wanna find the successor of 5, it should be 11, however, using the above method, the return should be 3. I don't know whether I'm right, if any mistake, please point out.
I agree, and I think we can just use a modified BFS to do
- shiqing881215 July 20, 2012
no need to push so many 2 in stack2, if it less than 2, push it, otherwise, do nothing to stack2
- shiqing881215 October 01, 2012