字节跳动9.22笔试
第一题 AC：
店铺离厕所最近距离
保存left厕所和right厕所的点，遍历一遍就可以了
代码没存
第二题：
动态规划 64.29%
做题
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int total = in.nextInt();
for(int ll=0; ll<total; ll++){
int n = in.nextInt();
int m = in.nextInt();
int[] a = new int[n];
for(int i=0; i<n; i++){
a[i] = in.nextInt();
}
int[][] result = new int[n][m+1];
for(int j=0; j<=m; j++){
result[0][j] = 0;
}
for(int i=1; i<n; i++){
for(int j=0; j<=m; j++){
if( j - a[i-1] >= 0){
result[i][j] = max(result[i-1][j-a[i-1]] + 1, result[i-1][j]);
}else{
result[i][j] = result[i-1][j];
}
}
}
for(int i=0; i<n; i++){
System.out.print(i - result[i][m-a[i]]);
System.out.print(" ");
}
System.out.println();
}
}
public static int max(int a, int b){
return a>b ? a : b;
}
} 第三题 90%： 有向无环图
import java.util.*;
class Node{
int val;
LinkedList<Node> pre;
LinkedList<Node> next;
public Node(int _val){
this.val = _val;
pre = new LinkedList<>();
next = new LinkedList<>();
}
}
public class Main6 {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
HashMap<Integer,Node> temp = new HashMap<>();
ArrayList<Integer> result = new ArrayList<>();
while(in.hasNextLine()){
String line = in.nextLine();
if(line.equals("")){
break;
}
String[] ls = line.split(" ");
int first = Integer.parseInt(ls[0]);
Node la, prn;
if(!temp.containsKey(first)){
la = new Node(first);
temp.put(first, la);
}else{
la = temp.get(first);
}
for(int i=1; i<ls.length; i++){
int pr = Integer.parseInt(ls[i]);
if(!temp.containsKey(pr)){
prn = new Node(pr);
temp.put(pr, prn);
}else{
prn = temp.get(pr);
}
la.pre.add(prn);
prn.next.add(la);
}
}
Set<Integer> s = temp.keySet();
int length = s.size();
while(result.size() < length){
int cur = -1;
Iterator<Integer> it = s.iterator();
while (it.hasNext()){
int i = it.next();
if(temp.get(i).pre.size() == 0 && (cur == -1 || i < cur)){
cur = i;
}
}
if(cur == -1){
System.out.println(-1);
return;
}else{
result.add(cur);
Node node = temp.get(cur);
Iterator<Node> l = node.next.iterator();
while (l.hasNext()){
Node next = l.next();
next.pre.remove(node);
}
temp.remove(node);
s.remove(cur);
}
}
Iterator<Integer> i = result.iterator();
while (i.hasNext()){
System.out.print(i.next() + " ");
}
}
}
第四题： 暴力解法 8%， 实在想不出
个人感觉可以用质数加因数分解优化一下
import java.util.Scanner;
public class Main7 {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int an = in.nextInt();
int bn = in.nextInt();
if(an==0){
System.out.println(bn);
}
if(bn==0){
System.out.println(an);
}
int result = 0;
for(int k=1; k<=an+bn; k++){
for(int ak=1; ak<k; ak++){
int bk = k - ak;
int as = an/ak;
int bs = bn/bk;
if(as == bs || (as == bs + 1 && an%ak == 0) || (bs == as + 1 && bs%bk == 0)){
result++;
break;
}
}
}
System.out.println(result);
}
}
查看5道真题和解析
