jiex.cs
BAN USERpublic class Digits {
private int MAX;
private int[] digits;
private void print() {
for (int i = 0; i < digits.length; i++)
System.out.print(digits[i]);
System.out.println();
}
private void generate(int index) {
if (index == MAX)
print();
else {
if (digits[0] == 4 && index == MAX - 1) {
digits[index] = 4;
generate(index + 1);
} else {
for (int i = 0; i < 10; i++) {
if (index == 0 || digits[index - 1] != i) {
digits[index] = i;
generate(index + 1);
}
}
}
}
}
public void printDigits(int max) {
this.MAX = max;
this.digits = new int[MAX];
generate(0);
}
public static void main(String[] args) {
new Digits().printDigits(4);
}
}
it is as simple as continuously applying a procedure of merging two adjacent sorted lists.
For example,
1,2,3,12,11,2,10,6
Round 1. Merge 1,2,3,12 and 11,2, merge 10 and 6, the result is 1,2,2,3,11,12, 6,10
Round 2. Merge 1,2,2,3,11,12 and 6,10' the result is 1,2,2,3,6,10,11,12
It's O(log m) where m is the number of sorted sublists, note m <=n ( number of elements in the lists)
Using two pointers,pointing two positions in the two sorted sublist, the merge can be done in place, so space is O(1)
Repcamillerharry, Data Engineer at Student
Hi, I am Camille from Easton USA. Currently, I am working as Staff assistant at Northern Star company. A managed ...
1. First sort the array A
- jiex.cs January 23, 20122. Then solve this problem using DP as follows:
Let f(i, j) denote, maximum difference if you select i numbers from the array, starting from index j and element at index j must be selected.
f(i, j) = max { min( f(i-1, m), A[m]-A[j] ) }, m=j+1 to n-1, if i<=n-j
f(i, j) = -Infinity, if i >n-j
the goal is to solve f(1, k), (note: it is always safe to include 1st element in the k numbers), complexity is O(n^2)