f*****o
发帖数: 1151 | 1 请问一下JAVA考题最佳算法是啥？
Problem 1:
Write a method which given two integers, returns the integer that is closest
to 1000.
Problem 2:
Write a method which given a string, returns a string where every character
in the original is doubled. For example, given the string "xyz";, return the
string "xxyyzz";
Problem 3:
Write a method which takes an array of integers. The method should return
true if there is a way to split the array in two so that the sum of the
numbers on one side of the split equals the sum of the numbers on the other
side.
Problem 4
Write a method which given a string, returns a string with an asterisk
inserted between every character in the original. Use recursion in your
solution. | L**********1
发帖数: 797 | 2 1.
int getClosestTo1K (int num1, int num2) {
if(Math.abs(1000-num1) < Math.abs(1000-num2)) {
return num1;
} else {
return num2;
}
} | L**********1
发帖数: 797 | 3 2.
String doubleStr (String ipt) {
String ret = "";
for(int i=0; i
ret += String.valueOf(ipt.charAt(i)) + String.valueOf(ipt.charAt(i));
}
return ret;
} | L**********1
发帖数: 797 | 4 4.
String insertAsterisk (String prefix, String ipt) {
// initially, the prefix == ""
if(null == ipt || "".equals(ipt)) {
return prefix;
} else if (1 == ipt.length()) {
return prefix + "*" + ipt;
} else {
return insertAsterisk(prefix + "*" + ipt.substring(0,1), ipt.substring(1
);
}
} | L**********1
发帖数: 797 | | z*****u
发帖数: 3010 | | f*****o
发帖数: 1151 | | g****s
发帖数: 1755 | 8 3 draft:
private static boolean partitionPro(int[] array) {
int sum = 0;
HashSet sumSet = new HashSet();
for(int i=0; i
sum += array[i];
sumSet.add(sum);
}
if(sum%2==1) return false;
return sumSet.contains(sum/2);
} | f*****o
发帖数: 1151 | 9 能解释一下：
sumSet.contains(sum/2)
谢谢
【在 g****s 的大作中提到】
: 3 draft:
: private static boolean partitionPro(int[] array) {
: int sum = 0;
: HashSet sumSet = new HashSet();
: for(int i=0; i:
: sum += array[i];
: sumSet.add(sum);
: }
: if(sum%2==1) return false;
| L**********1
发帖数: 797 | 10 这个意思是如果sum是奇数，就返回false
【在 f*****o 的大作中提到】
: 能解释一下：
: sumSet.contains(sum/2)
: 谢谢
| | | L**********1
发帖数: 797 | 11 这个意思是如果sum是奇数，就返回false
【在 f*****o 的大作中提到】
: 能解释一下：
: sumSet.contains(sum/2)
: 谢谢
| f*****o
发帖数: 1151 | 12 sumSet包含逐个相加的和，但sum/2并不一定在其中
比如数列：1,2,2,3,5,7
sumset:1,3,5,8,13,20
sum/2=10
10 不在sumset里， 但partition 存在：1，2，2，5，和3，7 | g****s
发帖数: 1755 | 13 抱歉，是我理解错了；
如果整个数列可以随意arrange的话，需要O(n^2)；
即需要要计算任意组合的sum值。需要用到Combination的算法。
import java.util.HashSet;
import java.util.Scanner;
public class PartitionProblem {
public static void main(String[] args){
//int[] array = creatArray();
int[] array = {1,2,2,3,5,7};
boolean PN = partitionPro(array);
if(PN) System.out.println("yes!");
else System.out.println("Nope.");
}//end main()
private static boolean partitionPro(int[] array) {
// TODO Auto-generated method stub
int totalSum = 0;
HashSet sumSet = new HashSet();
//add each single element to the hashSet, and count the totalSum
for(int i=0; i
totalSum += array[i];
sumSet.add(array[i]);
}
if(totalSum%2==1) return false;
//for a combination of n-elements: n
for(int combination = 2; combination
int currSum = 0;
int elements = 0;
int start =0;
sumCombinationofNElements(currSum, elements, combination, array, start,
sumSet);
}
return sumSet.contains(totalSum/2);
}//end of partitionPro() method;
private static void sumCombinationofNElements(int currSum, int elements,
int combination,
int[] array, int start, HashSet sumSet) {
// TODO Auto-generated method stub
if(elements == combination){
int tempSum = currSum;
sumSet.add(tempSum);
} else {
for(int i=start; i
currSum += array[i];
sumCombinationofNElements(currSum, elements+1, combination, array, i+1,
sumSet);
//recover currSum
currSum = currSum-array[i];
}
}//end if-else elements==combination condition;
}//end of sumCombinationofNElements() method;
private static int[] creatArray() {
// TODO Auto-generated method stub
System.out.println("Please input the num of elements in the array:");
Scanner input = new Scanner(System.in);
int num = input.nextInt();
input.close();
int[] array = new int[num];
for(int i=0; i
array[i] = (int)(Math.random()*5);
System.out.print(" " + array[i]);
}
System.out.println();
return array;
}//end creatArray() method;
}//end of everything in PartitionProblem class;
【在 f*****o 的大作中提到】
: sumSet包含逐个相加的和，但sum/2并不一定在其中
: 比如数列：1,2,2,3,5,7
: sumset:1,3,5,8,13,20
: sum/2=10
: 10 不在sumset里， 但partition 存在：1，2，2，5，和3，7
| g****s
发帖数: 1755 | 14 抱歉抱歉，最初把这个Q3想得太简单了，==！
如果数列可以随意Arrange，则需要考虑任何一个Combination的sum.
上面的Code看着太乱，想看的兄弟可以去看一下刚传到GitHub的上code；
https://github.com/breezedu/LeetCode2011/blob/master/PartitionProblem.java | f*****o
发帖数: 1151 | 15 题目应该是split，不是partition.所以你之前的算法是对的，谢谢 | f*****o
发帖数: 1151 | 16 is this better for #4?
String insertAsterisk (String s) {
if (s.length()==1) return s;
else
return s.substring(0,1)+ "*"+ insertAsterisk(s.substring(1));
} |
|
