ToanVu
BAN USERMy solution is written by Java. My idea is translate this problem to new problem: presenting all cases how to separate an integer number to sum of all smaller integers.
Ex: input 4, output: 4; 1+3; 1+1+2; 1+2+1; 2+2; 2+1+1; 3+1; 1+1+1+1
After that we can easy come back our problem.
INPUT: {1,2,3,4}
OUTPUT :
(1,2,3,4)
(1,2,3)(4)
(1,2)(3,4)
(1,2)(3)(4)
(1)(2,3,4)
(1)(2,3)(4)
(1)(2)(3,4)
(1)(2)(3)(4)
public class NonOverLappingPair {
public static void main(String[] args) {
int[] input = new int[] { 1, 2, 3, 4 };
print(input);
}
private static void print(int[] input) {
int n = input.length;
int[] arr = new int[n + 1];
arr[0] = 0;
printPair(input, arr, n, 1, n);
}
private static void printPair(int[] input, int[] arr, int length, int n, int remain) {
if (n > length + 1) {
return;
}
if (remain == 0) {
int sum = 0;
StringBuilder builder = new StringBuilder();
int run = 0;
for (int i = 1; i <= length; i++) {
if (sum == length) {
arr[i] = 0;
} else
sum = sum + arr[i];
// builder string
int temp = arr[i];
if (temp > 0) {
builder.append("(");
}
while (temp > 0) {
builder.append(input[run++]);
if (temp > 1)
builder.append(",");
temp--;
}
if (arr[i] > 0) {
builder.append(")");
}
}
System.out.println(builder.toString());
return;
}
for (int i = remain; i > 0; i--) {
arr[n] = i;
printPair(input, arr, length, n + 1, remain - i);
}
}
}
Try my idea, using Java:
Ex: INPUT: 100
OUTPUT:
50*2
25*4
25*2*2
20*5
10*10
10*5*2
5*5*4
5*5*2*2
CODE:
public class PrintFactors {
public static void main(String[] args) {
printFactor(100);
}
private static void printFactor(int n) {
if (n <= 0) {
System.out.print("Wrong input!");
return;
}
if (n == 1) {
System.out.print("1");
return;
}
long[] a = new long[n/2];
findFactor(n/2, n, a, 0);
}
private static void findFactor(long i, long n, long[] arr, int index) {
if (i == 1) {
if (n == 1) {
for (int k = 0; k < index - 1; k++) {
System.out.print(arr[k]);
if (k < index - 2) {
System.out.print("*");
}
}
System.out.println();
}
return;
}
for (long k = i; k >= 1; k--) {
if (n % k == 0) {
arr[index] = k;
findFactor(k, n / k, arr, index + 1);
}
}
}
}
import java.util.ArrayList;
public class MatchDictionary {
public static void main(String[] args){
ArrayList<String> dictionary = new ArrayList<>();
dictionary.add("cat");
dictionary.add("dog");
dictionary.add("frog");
System.out.println(formatOutput(getMatch("catkddogfhat", dictionary)));
}
private static float getMatch(String text, ArrayList<String> dictionary){
if (dictionary.contains(text)){
return 1f;
}
if (text.length() ==0){
return 0;
}
float max = 0f;
float length = text.length() * 1f;
for (int i = 1; i< length; i++){
float temp = i/length * getMatch(text.substring(0, i), dictionary) + (length-i)/length *getMatch(text.substring(i, text.length()), dictionary);
if (max < temp){
max = temp;
}
}
return max;
}
private static String formatOutput(float rate){
return String.format("%.2f %%", rate*100);
}
}
My idea is we use an ArrayList to store all Palindromes. And
F(2i) = "1" + F(2i-2) + "1";
F(2i +1) = "1" + F(2i-2) + "1";
With F(j) is all values in this ArrayList. Note that before we add new value to ArrayList, we ensure that F(2i-2) and F(2i-1) have exact length by adding "0" at 2 sizes of F. (I use method format(String s, int length) to do this)
import java.util.ArrayList;
public class FirstNPalindromes {
public static void main(String[] args) {
print(10);
}
private static void print(int n) {
ArrayList<String> list = new ArrayList<>();
list.add("0");
list.add("1");
list.add("11");
if (n == 0) {
return;
}
if (n >= 1) {
System.out.println("1");
}
if (n >= 2) {
System.out.println("11");
}
int length = 3;// length of current palindromes
int current = 3; // count size
int i = 3;
int j = 0;
while (i < n) {
j = 0;
current = list.size();
while (j < current && i <= n) {
String obj = list.get(j);
if ((length - obj.length()) % 2 != 0) {
if (j == 0) {
obj = "1" + format("", length - 2) + "1";
list.add(obj);
System.out.println(obj);
}
j++;
continue;
}
obj = "1" + format(obj, length - 2) + "1";
list.add(obj);
System.out.println(obj);
j++;
i++;
}
length++;
}
}
private static String format(String s, int length) {
StringBuilder builder = new StringBuilder();
int need = (length - s.length()) / 2;
for (int i = 0; i < need; i++) {
builder.append("0");
}
StringBuilder builderTotal = new StringBuilder();
builderTotal.append(builder).append(s).append(builder);
return builderTotal.toString();
}
}
My solution in Java:
F(first, last) = min{ (F(first, i) + F(i, last)) } (i : first+ 1 -> last). After that we need compare with min F(first, last) if (first, last) existed inside a range in input.
- ToanVu June 11, 2016