代码都有优化的空间，不喜勿喷～
1.二分法：
public int numberofprize (int a, int b, int c) {
// write code here
int left=min(a,b,c);
int right=max(a,b,c);
while (left<=right){
int mid=left+(right-left)/2;
if (check(mid,a,b,c)){
left=mid+1;
}else{
right=mid-1;
}
}
return right;
}
private boolean check(int mid, int a, int b, int c) {
long left=0;
if (a>=mid){
left+=(a-mid);
}else {
left-=(2*(mid-a));
}
if (b>=mid){
left+=(b-mid);
}else {
left-=(2*(mid-b));
}
if (c>mid){
left+=(c-mid);
}else {
left-=(2*(mid-c));
}
return left>=0;
}
private int min(int a, int b, int c) {
return Math.min(Math.min(a,b),c);
}
private int max(int a, int b, int c) {
return Math.max(Math.max(a,b),c);
} 2. 数组模拟，注意转换成浮点数计算
public int getHouses (int t, int[] xa) {
// write code here
if (xa==null||xa.length==0)
return 0;
double[][] xAndA=new double[xa.length/2][2];
int idx=0;
for (int i = 0; i < xa.length; i+=2) {
xAndA[idx][0]=(double)xa[i]-(double) xa[i+1]/2;
xAndA[idx][1]=(double)xa[i]+(double) xa[i+1]/2;
idx++;
}
int count=2;
for (int i = 0; i < xAndA.length-1; i++) {
if ((xAndA[i+1][0]-xAndA[i][1])==t){
count++;
}else if ((xAndA[i+1][0]-xAndA[i][1])>t){
count+=2;
}
}
return count;
} 3. 回溯（80%）
public long getPasswordCount (String password) {
// write code here
if (password.length()==1)
return 9;
int i[]=new int[1];
Deque<Character> stack=new ArrayDeque<>();
backTrack(password.toCharArray(),0,i,stack);
return i[0];
}
private void backTrack(char[] chars, int start, int[] i, Deque<Character> stack) {
if (stack.size()==chars.length){
if (!checkEquals(stack,chars)){
i[0]++;
}
return;
}
if (start==0){
for (int j = 0; j <=9; j++) {
stack.addLast((char)('0'+(j-0)));
backTrack(chars,start+1,i,stack);
stack.pollLast();
}
}else{
int cur=((chars[start]-'0')+(stack.peekLast()-'0'));
if (cur%2==0){
stack.addLast((char)('0'+(cur/2-0)));
backTrack(chars,start+1,i,stack);
stack.pollLast();
}else{
for (int j = 0; j < 2; j++) {
stack.addLast((char)('0'+(cur/2+j-0)));
backTrack(chars,start+1,i,stack);
stack.pollLast();
}
}
}
}
private boolean checkEquals(Deque<Character> stack, char[] chars) {
int idx=0;
for (Character c:stack){
if (c!=chars[idx++])
return false;
}
return true;
} 
全部评论
(7) 回帖