0918字节跳动后端笔试情况及代码（AK）
等12点笔试结束后更新代码
第一题
堆金字塔，每块石头长1m，宽1m，按cm计算，给你金字塔的高度n层，然后从1-n给你n个列表，每个列表代表第i层的石头放的位置，如果一个石头左右两边都有石头垫着，或者中心点下面有别的石头，就能稳定，否则就会掉落，上方依赖他的石头也会跟着掉落，问最终只剩下几个石头。
思路：
模拟，因为本身有序，每层的石头掉落情况是依赖于他底下一层石头的剩余情况，按层判断每个石头是否会掉落，用一个新列表存，而不是用老列表删除（有坑，会超时）。
代码：
import java.util.*;
/*
输入：
3
2 100 280
2 190 360
2 150 360
输出：
4
输入：
5
5 0 1000 2000 3010 3200
4 40 1050 2049 3100
1 80
1 120
1 160
输出：
10
*/
public class Q1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<List<Integer>> blocks = new ArrayList<>();
for (int i = 0; i < n; i++) {
int cnt = sc.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for (int j = 0; j < cnt; j++) {
list.add(sc.nextInt());
}
blocks.add(list);
}
int ans = blocks.isEmpty()?0:blocks.get(0).size();
for (int i = 1; i < blocks.size(); i++) {
//顺序查找
List<Integer> newList = new ArrayList<>();
List<Integer> down = blocks.get(i-1);
int downIdx = 0;
Iterator<Integer> it = blocks.get(i).iterator();
while (it.hasNext() && downIdx < down.size()) {
Integer left = it.next();
//找到第一块有接触的石块
while(downIdx < down.size() && down.get(downIdx)+100 <= left) {
downIdx++;
}
if(downIdx >= down.size()) {
break;
}
//保持中心
else if((down.get(downIdx)<left+50 && down.get(downIdx)+100 > left+50)) {
newList.add(left);
ans++;
}
//保持两边
else if(down.get(downIdx)+100 <= left+100 && downIdx+1 < down.size() && down.get(downIdx+1)<left+100 ) {
newList.add(left);
ans++;
}
}
blocks.set(i,newList);
}
System.out.println(ans);
}
}
第二题
字符串中只有01，判断一个“好串”的最大长度（我忘了叫什么名字了）
好串定义：长度大于3，相邻字符不等
思路：
贪心，类似滑动窗口，On。
代码：
import java.util.Scanner;
/*
输入：0101011101
输出：6
*/
public class Q2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int left = 0;
int ans = 0;
int n = str.length();
while (left < n) {
int right = left+1;
while(right < n && str.charAt(right) != str.charAt(right-1)){
right++;
}
if(right-left>=3)
ans = Math.max(right-left,ans);
left = right;
}
System.out.println(ans);
}
}
第三题
给你一个字符串，里面只有ASDF四个字母，且长度为4的倍数，你可以将一个子串修改为任意一个子串，在所有修改后可以使得四个字母的个数相等的子串中，求最小子串的长度。
思路：
滑动窗口，记录比len/4多余的字母的个数，如果窗口内的字母个数>=这个个数，则这个窗口满足条件，找最小满足条件的窗口
代码：
import java.util.Scanner;
/*
输入：
ADDF
输出：
1
输入：
ASAFASAFADDD
输出：
3
*/
public class Q3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int n = str.length();
int cnt = n/4;
int Acnt = 0, Scnt = 0, Dcnt = 0, Fcnt = 0;
for (int i = 0; i < n; i++) {
switch (str.charAt(i)) {
case 'A':
Acnt++;
break;
case 'S':
Scnt++;
break;
case 'D':
Dcnt++;
break;
default:
Fcnt++;
break;
}
}
if(Acnt == Scnt && Scnt == Dcnt && Dcnt == Fcnt) {
System.out.println(0);
return;
}
// System.out.println("A:"+Acnt+"\tS:"+Scnt+"\tD:"+Dcnt+"\tF:"+Fcnt);
Acnt = Acnt>=cnt?Acnt-cnt:0;
Scnt = Scnt>=cnt?Scnt-cnt:0;
Dcnt = Dcnt>=cnt?Dcnt-cnt:0;
Fcnt = Fcnt>=cnt?Fcnt-cnt:0;
// System.out.println("A:"+Acnt+"\tS:"+Scnt+"\tD:"+Dcnt+"\tF:"+Fcnt);
int ans = n;
int Acnt1 = 0, Scnt1 = 0, Dcnt1 = 0, Fcnt1 = 0;
int left = 0,right = 0;
while (left < n) {
while (right < n && (Acnt1<Acnt || Scnt1<Scnt || Dcnt1<Dcnt || Fcnt1<Fcnt)) {
char ch = str.charAt(right++);
switch (ch) {
case 'A':
Acnt1++;
break;
case 'S':
Scnt1++;
break;
case 'D':
Dcnt1++;
break;
default:
Fcnt1++;
break;
}
}
// System.out.println("left:"+left+"\tright:"+right+"\tstr:"+str.substring(left,right));
if((Acnt1>=Acnt && Scnt1>=Scnt && Dcnt1>=Dcnt && Fcnt1>=Fcnt))
ans = Math.min(ans,right-left);
char ch = str.charAt(left++);
switch (ch) {
case 'A':
Acnt1--;
break;
case 'S':
Scnt1--;
break;
case 'D':
Dcnt1--;
break;
default:
Fcnt1--;
break;
}
}
System.out.println(ans);
}
}
第四题
小明做书架，题目太长了，很难复述，欢迎大佬们补充，我看题目看了十几分钟才明白。
思路：
线段树+二分查找
先通过二分查找找出长度
然后通过线段树查找这个长度区间内的最大值和最小值，判断是否满足条件
代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/*
输入：
3 3
14 12 10
输出：
2 2
1 2
2 3
输入：
2 0
10 10
输出：
2 1
1 2
输入：
4 5
8 19 10 13
输出：
2 1
3 4
*/
public class Q4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int bookCnt = sc.nextInt();
int k = sc.nextInt();//高度差不能超过k
int h[] = new int[bookCnt+1];//第i本书的高度
NumTree tree = new NumTree(1, bookCnt);
for (int i = 1; i <= bookCnt; i++) {
h[i] = sc.nextInt();
tree.update(i, h[i]);
}
List<Integer> idx = new ArrayList();
int a = 1;
int low = 1, high = bookCnt;
while (low <= high) {
int mid = (low+high) >> 1;
//判断长度为mid是否能满足条件
List<Integer> list = new ArrayList<>();
for (int i = 1; i + mid -1 <= bookCnt; i++) {
int res[] = tree.query(i,i+mid-1);
if(res[1]-res[0] <= k) {
list.add(i);
}
}
//找不到
if(list.size()==0) {
high = mid-1;
}
else {
low = mid+1;
a = mid;
idx = list;
}
}
System.out.println(a+" "+idx.size());
for (int i = 0; i < idx.size(); i++) {
System.out.println(idx.get(i)+" "+(idx.get(i)+a-1));
}
}
}
class NumTree{
int left;
int right;
int min;
int max;
NumTree lchild;
NumTree rchild;
public NumTree(int left, int right){
this.left = left;
this.right = right;
this.min = Integer.MAX_VALUE;
this.max = Integer.MIN_VALUE;
if(left < right) {
int mid = (left+right)>>1;
lchild = new NumTree(left, mid);
rchild = new NumTree(mid+1, right);
}
else {
lchild = rchild = null;
}
}
public void update(int idx, int val) {
if(idx < left || idx > right) return;
this.max = Math.max(this.max, val);
this.min = Math.min(this.min, val);
if(left != right) {
int mid = (left + right) >> 1;
if (idx <= mid) {
lchild.update(idx, val);
} else {
rchild.update(idx, val);
}
}
}
public int[] query(int L, int R) {
if(R < left || L > right) {
return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
}
else if(L <= left && R >= right) {
return new int[]{min,max};
}
else {
int res1[] = lchild.query(L,R);
int res2[] = rchild.query(L,R);
return new int[]{Math.min(res1[0],res2[0]),Math.max(res1[1],res2[1])};
}
}
}
类似资料：