字节跳动-后台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;
	}
}