第一题 AC100 做法有点笨😂
public int numberofprize (int a, int b, int c) {
// write code here
int res = Math.min(a,Math.min(b,c));
//手动模拟
while(Math.min(a,Math.min(b,c)) >= res){
//第一次减，从最大的数减1
if (a >= b && a >= c){
a--;
}else if(b >= a && b >= c){
b--;
}else if(c >= a && c >= b){
c--;
}
//第二次减
if (a >= b && a >= c){
if (b > c){//从最大的数减1，最小的数加1
a--;
c++;
}else{
a--;
b++;
}
}else if(b >= a && b >= c){
if (a > c){
b--;
c++;
}else{
b--;
a++;
}
}else if(c >= a && c >= b){
if (b > a){
c--;
a++;
}else{
c--;
b++;
}
}
res = Math.max(res,Math.min(a,Math.min(b,c)));
}
return res;
}
第二题 AC100
public int getHouses (int t, int[] xa) {
// write code here
int res = 2;
double[] right = new double[xa.length/2];//每个房子右边界
double[] left = new double[xa.length/2];//每个房子左边界
int index = 0;
for (int i = 0; i < xa.length; i++) {
if(i % 2 == 0){
left[index] =xa[i] - (double)xa[i+1]/2;
right[index] = xa[i] + (double)xa[i+1]/2;
index++;
}
}
for (int i = 0; i < xa.length / 2 - 1; i++) {
if(left[i] + t < right[i+1]){//放下房子后还有空，可以靠左和靠右
res+=2;
}else if(left[i] + t == right[i+1]){//放下房子没空了，只有一种情况
res++;
}
}
return res;
} 第三题 AC70 复杂度太高了
//回溯，结果存在set中去重
Set<String> set = new HashSet<>();
public long getPasswordCount (String password) {
// write code here
int n = password.length();
set.add(password);
for (int i = 0; i <= 9; i++) {
StringBuilder sb = new StringBuilder();
sb.append(i);
backtrack(password,1,sb,i);
}
return set.size()-1;
}
public void backtrack(String password,int i,StringBuilder sb,double pre){
if(i == password.length()){
set.add(sb.toString());
return;
}
int cur = Integer.valueOf(password.charAt(i)-'0');
double newNum = (pre + cur) / 2;
int num =(int) newNum;
sb.append(num);
backtrack(password,i+1,sb,num);
sb.deleteCharAt(sb.length()-1);
if(newNum > num){
sb.append(num+1);
backtrack(password,i+1,sb,num+1);
sb.deleteCharAt(sb.length()-1);
}
}
全部评论
(6) 回帖