前言+說明

??旺仔兄弟們！這個是位元組跳動2022屆校招生筆試，總共四道編程題！
如果覺得博主分享的不錯，希望能留下您的一鍵??三連??（點贊+評論+收藏） ，您的支持就是我前進的動力??，您的三連對我特別重要，
注明：下述題目只用于學習交流所用，禁止用于商業銷售，同時在題解方面也希望大家能提出寶貴建議，共同進步??！
??此次博文受益于大神“英雄哪里出來”的啟發和指點，加了下面文章中的動圖，
??大神“英雄哪里出來”的演算法題圖解很漂亮，特別推薦！??

一、演算法編程題（種樹）

時間限制： 3000MS
記憶體限制： 1048576KB
題目描述：
每年的3月12日是我國的植樹節，為了保證樹苗的存活率，栽種每顆樹苗都需要有一定的間隔，即不能種植在相鄰的土地上，否則會發生爭奪養分而導致樹苗枯萎，你作為一名愛護壞境的Bytedancer分到了一塊長度為n乘1的土地，即由n塊地組成的一個陣列，其中如果種了樹的地塊用“B”表示，沒有種樹的地塊用“Y”表示，每個地塊最多只能種一顆樹苗，并且沒有相鄰地塊種了樹苗，請你計算出最多還能種多少棵樹？

輸入描述

第一行輸入一個正整數N代表陣列大小 1 ≤ N ≤ 10000，
第二行輸入陣列 bytetreed，其中bytetreed[i] 為 B 或 Y

輸出描述

非負整數

示例1

輸入：

5
B Y Y Y B

輸出

1

示例2

輸入：

4
Y Y Y B

輸出

1

規則

請盡量在全場考試結束10分鐘前除錯程式，否則由于密集排隊提交，可能查詢不到編譯結果，點擊“除錯”亦可保持代碼
本編程題不可以使用本地編譯器

解題思路：

一、能種樹的空缺位置為奇數個時：
如下圖：索引i = 0~14，可種樹的索引范圍為0 ~ 2、6 ~ 8、12 ~ 14，每段都有3個位置可選，



1、首段：temp的初始值為-1，i從0指向4，在此程序中能種樹的索引范圍為：0~2（3個位置），此段最多可種的樹num = i/2，

參考代碼：

import java.util.Scanner;

public class TikTok_Test01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String[] arrs = sc.nextLine().split(" ");
        int ans = plant(arrs);
        System.out.println(ans);
    }
    public static int plant(String[] arrs){
        int ans = 0;
        int n = arrs.length;
        int temp = -1;
        for (int i=0; i<n; i++){
            if (arrs[i].equals("B")){
                if (temp < 0){
                    //最左邊的空位置
                    ans += i/2;
                }else {
                    //temp與i之間最多能種的樹位置范圍為：i-temp-3；
                    //當i-temp-3為奇數時，能種樹的數目為：(i-temp-2)/2;
                    //當i-temp-3為偶數時，能種樹的數目為：(i-temp-3)/2;
                    //在整數運算中，i-temp-3為偶數時，(i-temp-3)/2=(i-temp-2)/2
                    ans += (i-temp-2)/2;
                }
                //存下種了樹的位置索引
                temp = i;
            }
        }
        if (temp < 0){//所有位置都未栽樹，當n為偶數時ans=n/2，當n為奇數時ans=（n+1）/2，
            ans += (n+1)/2;
        }else {//在temp之后都是空位，最右邊的空位置
            ans += (n-temp-1)/2;
        }
        return ans;
    }
}

二、演算法編程題（小A的吃雞之旅）

時間限制： 2000MS
記憶體限制： 524288KB
題目描述：
眾所周知，小A不管玩什么游戲都很菜，總是拖隊伍的后腿，在小A和朋友組隊開黑一款跳傘大逃殺游戲的時候，他總是到處亂闖，胡亂開槍，帶領隊伍反向吃雞，為了帶領小A贏下游戲，體會到吃雞的快感，小A的隊友們不得己卸下了小A的武器，讓小A在房間里好好地“茍著”，其他人出去搜索物資，可小A一點也不老實，總在窗戶晃悠，不僅被轟炸得只剩了一絲血，還因此引來窗外狙擊手的注意，
狙擊手以一定角度向窗內進行射擊，小A聽到槍聲后嚇得直接以“人”字形趴了下去，假設子彈在屋內最多反彈三次（鏡面反射，第4次撞擊時不會再反彈），而且只要子彈擊中或者擦到小A，小A就會陣亡，需要注意的是小A身上帶了一個隊友留給他的平底鍋，如果子彈中了平底鍋（包括擦到平底鍋）就會陷入平底鍋不再反彈，而且也不會對小A造成傷害，房間是一個6×6的格子，可以簡單抽象為下圖：

輸入描述

輸入第一行包含一個正整數n（1 ≤ n ≤ 1000），代表有n行輸入，
接下來n行每行給出子彈射入的角度θ（0 ≤ θ ≤ π 且 θ ≠ π / 2）的tan值，請你判斷每次射擊小A能否存活下來，

輸出描述

如果一顆子彈未擊中小A或者擊中平底鍋，請在一行內輸出“YES”，否則，輸出“NO”，

示例1

輸入：

3
0
0.8
999.9999

輸出

YES
YES
NO

備注

浮點數精度控制在1e-6即可，

規則

請盡量在全場考試結束10分鐘前除錯程式，否則由于密集排隊提交，可能查詢不到編譯結果，點擊“除錯”亦可保持代碼
本編程題不可以使用本地編譯器

解題思路：
采用分類并遞回的方式：（大神說這是會讓面試官暈倒的方法），
【引數解釋：】
順時針方向為正
@param x 子彈與墻面相交的橫坐標
@param y 子彈與墻面相交的縱坐標
@param tanh 子彈與墻面的夾角
@param n 子彈的反彈次數，初始為0
@return 是否擊中小A
1、當x=0時，表示在左側墻面，
(1.1)當tanh > 0時有以下情形
(1.1.1)打中底側墻面：
①重置x,y,n和tanh的值：x=y×tanh、y=0、tanh=1/tanh和n=n+1，
②遞回呼叫此方法
(1.1.2)打中小A，直接回傳值true，
(1.1.3)打中平底鍋，直接回傳值false，
(1.1.4)打中右側墻面：
①重置x,y,n和tanh的值：x=6、y=y-6/tanh、tanh=-tanh和n=n+1，
②遞回呼叫判斷方法
(1.2)當tanh < 0時有以下情形
(1.2.1)打中頂側墻面：
①重置x,y,n和tanh的值：x=-(6-y)×tanh、y=6、tanh=1/tanh和n=n+1，
②遞回呼叫此方法
(1.2.2)打中小A，直接回傳值true，
(1.2.3)打中平底鍋，直接回傳值false，
(1.2.4)打中右側墻面：
①重置x,y,n和tanh的值：x=6、y=y-6/tanh、tanh=-tanh和n=n+1，
②遞回呼叫判斷方法
(1.3)當tanh = 0時,回傳false，
2、當y=0時，表示在底側墻面，
與1同理，
3、當x=6時，表示在右側墻面，
與1同理，
4、當y=6時，表示在頂側墻面，
與1同理，

三、演算法編程題（有序最大K位數）

時間限制： 2000MS
記憶體限制： 254288KB
題目描述：
給定N個陣列成的序列，其中每個元素都是0~9之間的個數，要求從這個序列中找出K個元素，組成一個K位數，并且這K個元素在原N個數中的相對順序不變，為這個K位數最大是多少？

輸入描述

第一行 輸入為N和K（1 ≤ N ≤ 1e⁶,1 ≤ K ≤ N），用空格分隔，其中N為無序序列的長度，K為需要得到的有序數長度，
第二行 依次輸入N個個位數，用空格分隔，表示這個序列

輸出描述

能夠得到的最大K位數的數值（前綴0不輸出）

示例1

輸入：

2 2
1 2

輸出

12

示例2

輸入：

8 4
4 6 2 5 4 1 9 8

輸出

6598

示例3

輸入：

6 2
0 0 0 0 0 0

輸出

0

規則

請盡量在全場考試結束10分鐘前除錯程式，否則由于密集排隊提交，可能查詢不到編譯結果，點擊“除錯”亦可保持代碼
本編程題不可以使用本地編譯器

解題思路：

1、將陣列中索引為0 ~ n-k的數存入集合curList，如下圖pre與i之間的數值（黃色區域）存入curList集合，并求出curList集合中的最大值6及索引，

2、將pre指標移到最大值索引后一位，將i向后移動一位，重新將pre與i之間數值（綠色區域）存入curList集合，并求集合里的最大值及索引，與上次求出的最大值6作拼接，得到65，

3、重新將pre指標移到最大值5索引后一位，將i向后移動一位，重新將pre與i之間的黃色區域存入curList集合，并求集合里的最大值及索引，與上次求出的最大值65作拼接得到659，

4、依次回圈k次，

參考代碼：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class TikTok_Test03 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        int ans = maxNum(arr,k);
        System.out.println(ans);
    }
    public static int maxNum(int[] arr, int k){
        List<Integer> list = new ArrayList<Integer>();
        List<Integer> curList = new ArrayList<Integer>();
        int n = arr.length;
        int pre = -1;
        int max = 0;
        for (int i=0;i<n; i++){
            list.add(arr[i]);
        }

        StringBuilder sb  =  new StringBuilder();
        for (int i=k-1; i>=0; i--){
            for (int j=pre+1;j<n-i; j++){
                curList.add(arr[j]);
            }
            max = Collections.max(curList);
            pre = list.indexOf(max);
            sb.append(max);
            curList.clear();
        }

        int ans = Integer.parseInt(sb.toString());
        return ans;
    }
}

四、演算法編程題（測驗計劃的最大成功率）

時間限制： 2000MS
記憶體限制： 524288KB
題目描述：
某測驗計劃有N個測驗用例串行執行，現已知條件如下：
1、每個測驗用例都是可重復執行的獨立事件；
2、用例的執行成功率分別為A1，A2…An （0.9 ≤ An ≤ 1）；
3、每個用例的執行時間均為1秒；
4、每個用例需要事先設定重復執行次數；
5、測驗用例需要至少通過一次，則認為該測驗用例通過；
6.、如果全部測驗用例執行通過，則認為該測驗計劃執行通過；
請問在M秒內(2N＞M≥N)，該測驗計劃通過的成功率最大為多少？

輸入描述

第一行是一個正整數N（2 ≤ N ≤ 10000）
第二行是N個成功率A1,A2…An，其中0.9 ≤ An ≤ 1
第三行是一個正整數M （2N ＞ M ≥ N）

輸出描述

輸出一個數字x（保留4位小數），表示最大成功率，

示例1

輸入：

5
0.9 0.92 0.94 0.92 0.95
10

輸出

0.9714

規則

請盡量在全場考試結束10分鐘前除錯程式，否則由于密集排隊提交，可能查詢不到編譯結果，點擊“除錯”亦可保持代碼
本編程題不可以使用本地編譯器

解題思路：
【分析】
想要測驗通過的成功率最大，則需要排除掉因某個事件失敗而導致的整體測驗失敗；
事件Ai不影響整個測驗集測驗成功的單個事件最大發生率為：1-（1 - Ai）^m-n （其中：1 ≤ i≤n），可得出最大成功率：

R_max = ∏ i = 1 m ? n ( 1 ? （ 1 ? A i ） K i ) \prod_{i=1}^{m-n} (1-（1 - Ai）^{Ki}) ∏i=1m?n?(1?（1?Ai）Ki) ∏ j = m ? n + 1 m ( A j ) \prod_{j=m-n+1}^{m} (Aj) ∏j=m?n+1m?(Aj)，

∑ i = 1 N K i = m ? n \sum_{i=1}^N K_i=m-n ∑i=1N?Ki?=m?n ，

【代碼思路】
1、將各事件發生的概率k按升序排序，
2、當rep = m-n＞0時：
2.1、當 1-（1 - A_i）^k ≤ A_i+1，則k++(2 ≤ k ≤ m-n)，rep = rep-1，
2.2、當 1-（1 - A_i）^k > A_i+1，則i++(1 ≤ i ≤ n-1)，
2.3、當i=n時，A_n= 1-（1 - A_n）^rep ，
3、當rep=0且i<n時，
事件的概率不發生改變
4、將所有的事件相乘并保留4位小數輸出，

參考代碼

import java.util.*;
public class TikTok_Test04 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Double> list = new ArrayList<Double>();
        for (int i=0; i<n; i++){
            list.add(sc.nextDouble());
        }
        int m = sc.nextInt();
        System.out.println(list.toString());
        double ans = maxRate(list,m,n);
        System.out.printf("%.4f",ans);
    }
    public static double maxRate(List<Double> list, int m,int n){
        double ans = 1.0;
        int rep = m-n;
        List<Double> temp = new ArrayList<Double>();
        Collections.sort(list);
        temp.addAll(list);

        for (int i=0; i<n; i++){
            while (rep>0){
                if (i!=n-1){
                    if (temp.get(i)<=temp.get(i+1)){
                        temp.set(i,1-(1-temp.get(i))*(1-list.get(i)));
                    }else {
                        break;
                    }
                }else{
                    temp.set(i,1-(1-temp.get(i))*(1-list.get(i)));
                }
                rep--;
            }
            ans *= temp.get(i);
        }

        return ans;
    }
}