字节跳动-后台Java笔试20190316,记录
1.换钱币,最少给几个硬币
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int minx=getCoin(1024-n);
System.out.println(minx);
}
private static int getCoin(int i) {
int i64=i/64;
int i16=(i%64)/16;
int i4=(i%16)/4;
int i1=(i%4)/1;
return i64+i16+i4+i1;
}
}
2.字符串问题
对输入字符串处理,使之满足:
1)AAA 处理成AA
2)AABB 处理成 AAB
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String[] words=new String[n+1];
int i=0;
while(sc.hasNextLine()) {
words[i++]=sc.nextLine();
if(i==(n+1))
break;
}
sc.close();
for(int j=1;j<words.length;j++) {
checkedWord(words[j]);
}
}
@Test
public void testName() throws Exception {
checkedWord("hellooo");
checkedWord("w00000w");
}
private static void checkedWord(String word) {
if(word.isEmpty())
System.out.println("");
char[] wc=word.toCharArray();
int cur_count=0;
int pre_count=0;
for(int i=0;i<wc.length;i++) {
if(i==0) {
cur_count=1;
continue;
}
if(wc[i]==wc[i-1]) {
cur_count++;
if(cur_count==3) {
wc[i-2]=',';
cur_count=2;
}
if(cur_count==2 && pre_count==2) {
wc[i-1]=',';
cur_count=1;
}
}else {
pre_count=cur_count;
cur_count=1;
}
}
String result=new String(wc);
System.out.println(result.replaceAll(",", ""));
}
}
3.发奖品
输入:n个数字表示得分(第一个和第n个相邻),如果得分大于相邻的人,奖励也要大.
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] scores=new int[n];
for(int i=0;i<scores.length;i++)
scores[i]=sc.nextInt();
int[] gifts=new int[n];
for(int i=0;i<n;i++) {
if(gifts[i]==0)
cal(scores,gifts,i);
}
sumGifts(gifts);
}
private static void sumGifts(int[] gifts) {
int sum=0;
for(int i=0;i<gifts.length;i++)
sum+=gifts[i];
System.out.println(sum);
}
private static int cal(int[] scores, int[] gifts, int i) {
int n=scores.length;
if(gifts[i] !=0)
return gifts[i];
if(scores[i]<=scores[(i+1)%n] && scores[i]<=scores[(n+i-1)%n]) {
gifts[i]=1;
}
if(scores[i]>scores[(i+1)%n] && scores[i]<=scores[(n+i-1)%n]) {
gifts[i]=cal(scores,gifts,(i+1)%n)+1;
}
if(scores[i]<=scores[(i+1)%n] && scores[i]>scores[(n+i-1)%n]) {
gifts[i]=cal(scores,gifts,(n+i-1)%n)+1;
}
if(scores[i]>scores[(i+1)%n] && scores[i]>scores[(n+i-1)%n]) {
gifts[i]=(cal(scores,gifts,(i+1)%n)+1)>(cal(scores,gifts,(n+i-1)%n)+1)?(cal(scores,gifts,(i+1)%n)+1):(cal(scores,gifts,(n+i-1)%n)+1);
}
return gifts[i];
}
4,割绳子
N条长度为L1,L2...的绳子,割出长度相等的K条绳子,N<K
这道题当时没时间做,下面是后来的思路:看别人分享的,我这里没有过多考虑精度.
import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Test;
public class Main {
final double eps=1e-8;
double[] arr= {4,12,10};
@Test
public void test() throws Exception {
solve(arr, 10);
}
/**
* 思路:二分法
* 1.最大平均长度K在[0,max](或者[0,avg])之间,初始的区间没有太大影响,只要保证左区间是0
* 网上有的解法,左区间是min,这里会出现错误(比如当avg<min,肯定就找不到合适的切割长度)
* 2.然后,判断所有绳子按照ki的切割,是否可以切割出N份.每次ki取(left+right)/2
* 3.
* @param arr
* @param k
*/
void solve(double[]arr,int k) {
Arrays.sort(arr);
int n=arr.length;
//注意:ki的长度在区间(0,max]上
double mid=0,l=0,r=arr[n-1];
while(l+eps<r) {
mid=(l+r)/2.0;
//判断mid是否可以切割出k条绳子
if(check(mid,k))
l=mid;
else
r=mid;
}
//这里输出l r mid 都行,因为精度不止小数点后两位
System.out.printf("最大长度%.2f",mid,r);
}
boolean check(double mid,int k) {
int count=0;
for(int i=0;i<arr.length;i++) {
//记录下当前绳子可以切割出来几条
count+=arr[i]/mid;
}
System.out.println("mid:"+mid+",count:"+count);
//如果可以切割出K,就说明找到了,返回
return count>=k;
}
}
