0%

字节跳动校招

关于字节跳动校招的一些题目

皮卡丘

传送门(字节跳动)

题目描述

存在n+1个房间,每个房间依次为房间1 2 3…i,每个房间都存在一个传送门,i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问),每次移动他有两种移动策略:
A. 如果访问过当前房间 i 偶数次,那么下一次移动到房间i+1;
B. 如果访问过当前房间 i 奇数次,那么移动到房间pi;
现在路人甲想知道移动到房间n+1一共需要多少次移动;

输入描述:

1
第一行包括一个数字n(30%数据1<=n<=100,100%数据 1<=n<=1000),表示房间的数量,接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。

输出描述:

1
输出一行数字,表示最终移动的次数,最终结果需要对1000000007 (10e9 + 7) 取模。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;
public class ChuanSongMen {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] p = new int[n+1];
int[] dp = new int[n+1];
dp[0] = 0;
int mod = 1000000007;
for(int i = 1; i <= n; i++){

p[i] = sc.nextInt();
/**
* 记dp[i]为第二次到达房间i所需的步数,则dp[i-1]+1是第一次到达房间i的步数
* 再+1,跳到p[i],而第一次到达p[i]的步数为dp[p[i]-1]+1,
* 然后要二次跳到i-1房间,总步数为dp[i-1],这两个步数相减就是p[i]二次到达i-1到步数
* 再+1,第二次到达房间i
* dp[i] = (2*dp[i-1] - dp[p[i] - 1] + 2)
*/
dp[i] = (2*dp[i-1] - dp[p[i] - 1] + 2) % mod;
}
dp[n] = dp[n] > 0 ? dp[n] : dp[n]+mod;
System.out.println(dp[n]);
sc.close();
}
}

房间分配(字节跳动)

题目描述

有n个房间,现在i号房间里的人需要被重新分配,分配的规则是这样的:先让i号房间里的人全都出来,接下来按照 i+1, i+2, i+3, … 的顺序依此往这些房间里放一个人,n号房间的的下一个房间是1号房间,直到所有的人都被重新分配。

现在告诉你分配完后每个房间的人数以及最后一个人被分配的房间号x,你需要求出分配前每个房间的人数。数据保证一定有解,若有多解输出任意一个解。

输入描述:

1
2
第一行两个整数n, x (2<=n<=10^5, 1<=x<=n),代表房间房间数量以及最后一个人被分配的房间号;
第二行n个整数 a_i(0<=a_i<=10^9) ,代表每个房间分配后的人数。

输出描述:

1
输出n个整数,代表每个房间分配前的人数。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Scanner;

public class RoomDistribution{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int x = sc.nextInt();
long[] person_now = new long[n];
long min_value = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
person_now[i] = sc.nextInt();
min_value = Math.min(min_value, person_now[i]);
}
//从最后一个放入到房间向右开始找,第一个最小值就是起始房间
int index = x - 1;
int count = 0;

while(person_now[(index + n) % n] != min_value){
person_now[(index + n) % n] -= min_value + 1;
index--;
count++;
}

person_now[(index + n) % n] = n * min_value + count;
index--;

while((index + n) % n != x - 1){
person_now[(index + n) % n] -= min_value;
index --;
}

for (int i = 0; i < n; i++) {
System.out.print(person_now[i] + " ");
}
sc.close();
}
}
-------------本文结束感谢您的阅读-------------