B站在?？途W(wǎng)（https://www.nowcoder.com/test/16519291/summary）上發(fā)了一套自己秋招的編程題，恰好今年被老師忽悠著去再參加一次藍(lán)橋杯（我參加C++組，所以下面的題都是用C++做的，沒用我熟悉的python），雖然那個(gè)比賽很水，但是還是要提高我的編程能力才是。于是準(zhǔn)備做點(diǎn)題練習(xí)下，B站這個(gè)題挺好，題目很新穎（僅限題目描述），不過內(nèi)容和那個(gè)比賽一樣水，所以給大家解析下。

1.扭蛋機(jī)?

時(shí)間限制：1秒
空間限制：32768K

22娘和33娘接到了小電視君的扭蛋任務(wù)：
一共有兩臺扭蛋機(jī)，編號分別為扭蛋機(jī)2號和扭蛋機(jī)3號，22娘使用扭蛋機(jī)2號，33娘使用扭蛋機(jī)3號。
扭蛋機(jī)都不需要投幣，但有一項(xiàng)特殊能力：
扭蛋機(jī)2號：如果塞x（x范圍為>=0正整數(shù)）個(gè)扭蛋進(jìn)去，然后就可以扭到2x+1個(gè)
扭蛋機(jī)3號：如果塞x（x范圍為>=0正整數(shù)）個(gè)扭蛋進(jìn)去，然后就可以扭到2x+2個(gè)
22娘和33娘手中沒有扭蛋，需要你幫她們設(shè)計(jì)一個(gè)方案，兩人“輪流扭”（誰先開始不限，扭到的蛋可以交給對方使用），用“最少”的次數(shù)，使她們能夠最后恰好扭到N個(gè)交給小電視君。

輸入描述:

輸入一個(gè)正整數(shù)，表示小電視君需要的N個(gè)扭蛋。

輸出描述:

輸出一個(gè)字符串，每個(gè)字符表示扭蛋機(jī)，字符只能包含”2”和”3”。

輸入例子1:

10

輸出例子1:

233

思路有兩種，一種是BFS，一種是通過二叉樹（其實(shí)你看到2x+1和2x+2就差不多知道了），因?yàn)檫@個(gè)題是這樣的：

可以看到，n是奇數(shù)都是最后22扭的，n是偶數(shù)都是最后33扭的，那么我們就可以倒著找出最終的順序。找到下一層之后返回上一層，如果是奇數(shù)就是(n-1)/2,偶數(shù)就是(n-2)/2，具體可自行驗(yàn)證。給出C++的示例代碼：

2.臉滾鍵盤

時(shí)間限制：1秒
空間限制：32768K

av394281?中，充滿威嚴(yán)的蕾米莉亞大小姐因?yàn)橛|犯某條禁忌，被隙間妖怪八云紫（紫m……èi）按住頭在鍵盤上滾動。

同樣在彈幕里亂刷梗被紫姐姐做成罪袋的你被指派找到大小姐臉滾鍵盤打出的一行字中的第?k?個(gè)僅出現(xiàn)一次的字。
(為簡化問題，大小姐沒有滾出 ascii 字符集以外的字)

輸入描述:

每個(gè)輸入都有若干行，每行的第一個(gè)數(shù)字為k，表示求第k個(gè)僅出現(xiàn)一次的字。然后間隔一個(gè)半角空格，之后直到行尾的所有字符表示大小姐滾出的字符串S。

輸出描述:

輸出的每一行對應(yīng)輸入的每一行的答案，如果無解，輸出字符串Myon~

(請不要輸出多余的空行）

為了方便評測，如果答案存在且為c，請輸出[c]

輸入例子1:

2 misakamikotodaisuki
3 !bakabaka~ bakabaka~ 1~2~9!
3 3.1415926535897932384626433832795028841971693993751o582097494459211451488946419191919l91919hmmhmmahhhhhhhhhh
7?www.bilibili.com/av170001
1 111

輸出例子1:

[d]
[9]
[l]
[7]
Myon~

這個(gè)題有幾種思路，最簡單的還是使用映射(map)，讓出現(xiàn)的每個(gè)字符對應(yīng)到0上。掃描整個(gè)字符串，如果碰到一個(gè)字符，就讓他對應(yīng)的數(shù)+1，同時(shí)記錄每個(gè)字符出現(xiàn)的順序。然后掃描記錄的順序，找到第k個(gè)對應(yīng)數(shù)是1的字符。但是我們看到題目說的是不超過ASCII，所以直接用ASCII來映射就好了，給出示例C++代碼：

3.簡單表達(dá)式計(jì)算?

時(shí)間限制：1秒
空間限制：32768K

給定一個(gè)合法的表達(dá)式字符串，其中只包含非負(fù)整數(shù)、加法、減法以及乘法符號（不會有括號），例如7+3*4*5+2+4-3-1，請寫程序計(jì)算該表達(dá)式的結(jié)果并輸出；

輸入描述:

輸入有多行，每行是一個(gè)表達(dá)式，輸入以END作為結(jié)束

輸出描述:

每行表達(dá)式的計(jì)算結(jié)果

輸入例子1:

7+3*4*5+2+4-3-1
2-3*1
END

輸出例子1:

69
-1

這個(gè)題就是水題了，有幾種思路，可以用逆波蘭，但是這就是高射炮打蚊子——大材小用了，這個(gè)題一沒有括號，二沒有除法，這還不是隨便做(棧還是要用的)。只要先算乘法再算加法就好了，給出示例C++代碼：

4.小A最多會新認(rèn)識的多少人

時(shí)間限制：1秒
空間限制：32768K

小A參加了一個(gè)n人的活動，每個(gè)人都有一個(gè)唯一編號i(i>=0 & i<n< code="" style="box-sizing: inherit;">)，其中m對相互認(rèn)識，在活動中兩個(gè)人可以通過互相都認(rèn)識的一個(gè)人介紹認(rèn)識?，F(xiàn)在問活動結(jié)束后，小A最多會認(rèn)識多少人？

輸入描述:

第一行聚會的人數(shù)：n（n>=3 & n<10000）；
第二行小A的編號: ai（ai >= 0 & ai < n)；
第三互相認(rèn)識的數(shù)目: m（m>=1 & m< n(n-1)/2）；
第4到m+3行為互相認(rèn)識的對，以’,’分割的編號。

輸出描述:

輸出小A最多會新認(rèn)識的多少人？

輸入例子1:

7
5
6
1,0
3,1
4,1
5,3
6,1
6,5

輸出例子1:

3

這個(gè)題很明顯的并查集，但是據(jù)其他人說用鄰接表+BFS也能做，但是這里我就不嘗試了，給出并查集（最后要記得減去小A本來就認(rèn)識的人）的C++示例代碼：

5.山寨金閃閃?

時(shí)間限制：3秒
空間限制：262144K

金閃閃死后，紅A拿到了王之財(cái)寶，里面有n個(gè)武器，長度各不相同。紅A發(fā)現(xiàn)，拿其中三件武器首尾相接，組成一個(gè)三角形，進(jìn)行召喚儀式，就可以召喚出一個(gè)山寨金閃閃。（例如，三件武器長度為10、15、20，可以召喚成功。若長度為10、11、30，首尾相接無法組成三角形，召喚失敗。）紅A于是開了一個(gè)金閃閃專賣店。他把王之財(cái)寶排成一排，每個(gè)客人會隨機(jī)抽取到一個(gè)區(qū)間[l,r],客人可以選取區(qū)間里的三件武器進(jìn)行召喚（客人都很聰慧，如果能找出來合適的武器，一定不會放過）。召喚結(jié)束后，客人要把武器原樣放回去。m個(gè)客人光顧以后，紅A害怕過多的金閃閃愉悅太多男人，于是找到了你，希望你幫他統(tǒng)計(jì)出有多少山寨金閃閃被召喚出來。

輸入描述:

第一行武器數(shù)量:n <= 1*10^7
第二行空格分隔的n個(gè)int，表示每件武器的長度。
第三行顧客數(shù)量：m <= 1*10^6
后面m行，每行兩個(gè)int l，r，表示每個(gè)客人被分配到的區(qū)間。

輸出描述:

山寨金閃閃數(shù)量。

輸入例子1:

5
1 10 100 95 101
4
1 3
2 4
2 5
3 5

輸出例子1:

3

我知道這是《Fate》系列作品的衍生題目，我不玩游戲，但是咱也知道金閃閃是男的，為什么偷♂稅男人啦。不過這個(gè)題很有說頭，思路可以分為這幾步：

1，首先，判斷三個(gè)正整數(shù)a,b,c是否能組成三角形，判斷方法是：將abc升序排列，然后如果a+b>c,則可以構(gòu)成三角形。其次，判斷一個(gè)區(qū)間[L,R]內(nèi)是否能找到三個(gè)數(shù)使其構(gòu)成三角形，可以將這R-L+1個(gè)元素取出并排序，然后從前往后三個(gè)三個(gè)判斷。查詢每次區(qū)間長度都在1~1e7之間，當(dāng)然不能每次都暴力找，不然有1e6次查詢，時(shí)間復(fù)雜度肯定爆炸，那么怎么處理呢？實(shí)際上，如果數(shù)一多，是非常容易構(gòu)成三角形的，如果要剛好卡到邊界，剛好不能構(gòu)造成三角形（a+b==c），則要構(gòu)造這樣的數(shù)據(jù)：1，1，2，3，5，8......。
巧了，其實(shí)就是斐波那契數(shù)列，題目的數(shù)據(jù)給出的數(shù)據(jù)在int范圍內(nèi)，然后我們發(fā)現(xiàn)大概在40多項(xiàng)的時(shí)候就不能構(gòu)造出全都不滿足構(gòu)成三角形的數(shù)據(jù)了，下面是打表的出的結(jié)果。

所以，只要在給出的區(qū)間長度較大的，一定能構(gòu)成三角形，區(qū)間長度較小的，則可以存下來排序后判斷，下面給出C++示例代碼：

不過我覺得這就是B站程序員出的題目的巔峰了，下面的題水的成分還是蠻多的。

6.比較兩個(gè)版本字符串version1和version2

時(shí)間限制：1秒
空間限制：32768K

如果version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

輸入的version字符串非空，只包含數(shù)字和字符.。.字符不代表通常意義上的小數(shù)點(diǎn)，只是用來區(qū)分?jǐn)?shù)字序列。例如字符串2.5并不代表二點(diǎn)五，只是代表版本是第一級版本號是2，第二級版本號是5.

輸入描述:

兩個(gè)字符串，用空格分割。
每個(gè)字符串為一個(gè)version字符串，非空，只包含數(shù)字和字符.

輸出描述:

只能輸出1, -1，或0

輸入例子1:

0.1 1.1

輸出例子1:

-1

開始水了。。。果然B站大佬都喜歡水，這個(gè)只要根據(jù)'.'分割輸入的字符串，然后逐一對比大小就行了，根本沒啥講頭，真是屑呢。下面給出C++示例代碼：

7.精靈鼠從入口到出口的最少減少速度

時(shí)間限制：2秒
空間限制：131072K

猛獸俠中精靈鼠在利劍飛船的追逐下逃到一個(gè)n*n的建筑群中，精靈鼠從（0,0）的位置進(jìn)入建筑群，建筑群的出口位置為（n-1,n-1），建筑群的每個(gè)位置都有阻礙，每個(gè)位置上都會相當(dāng)于給了精靈鼠一個(gè)固定值減速，因?yàn)榫`鼠正在逃命所以不能回頭只能向前或者向下逃跑，現(xiàn)在問精靈鼠最少在減速多少的情況下逃出迷宮？

輸入描述:

第一行迷宮的大小: n >=2 & n <= 10000；
第2到n+1行，每行輸入為以’,’分割的該位置的減速,減速f >=1 & f < 10。

輸出描述:

精靈鼠從入口到出口的最少減少速度？

輸入例子1:

3
5,5,7
6,7,8
2,2,4

輸出例子1:

19

這個(gè)題很明顯的動態(tài)規(guī)劃，建立一個(gè)n × n項(xiàng)的矩陣X(里面所有元素為0)，先讓X的第一行等于建筑群減速信息中的第一行。然后從第二行開始，判斷X的上面和左邊哪個(gè)數(shù)比較小(忽略左邊沒有的情況，此時(shí)默認(rèn)為上面)，選擇最小的那個(gè)，再加上自身對應(yīng)位置的建筑群減速信息的數(shù)。循環(huán)對每行進(jìn)行操作，最后X的第(n,n)項(xiàng)就是答案。就相當(dāng)于把走過的存下來，就不用重復(fù)走了。當(dāng)然這個(gè)題可以壓縮空間，因?yàn)榫仃嚩际怯玫趎-1排，前面的用完了就沒用了。所以用個(gè)n+1項(xiàng)的數(shù)組就行了，下面給出C++示例代碼：

8.順時(shí)針打印數(shù)字矩陣?

時(shí)間限制：1秒
空間限制：32768K

給定一個(gè)數(shù)字矩陣，請?jiān)O(shè)計(jì)一個(gè)算法從左上角開始順時(shí)針打印矩陣元素

輸入描述:

輸入第一行是兩個(gè)數(shù)字，分別代表行數(shù)M和列數(shù)N；接下來是M行，每行N個(gè)數(shù)字，表示這個(gè)矩陣的所有元素；當(dāng)讀到M=-1，N=-1時(shí)，輸入終止。

輸出描述:

請按逗號分割順時(shí)針打印矩陣元素（注意最后一個(gè)元素末尾不要有逗號！例如輸出“1，2，3”，而不是“1，2，3，”），每個(gè)矩陣輸出完成后記得換行

輸入例子1:

3 3
1 2 3
4 5 6
7 8 9
-1 -1

輸出例子1:

1,2,3,6,9,8,7,4,5

水題+1，而且這道題是《劍指offer》第二版面試題第29題，連動都沒用就拿上來了，偷? ? ? 懶? ? ?了。這個(gè)題有兩種思路，一種是從外圈到里圈，一圈一圈的打印，向內(nèi)再走一圈接著繼續(xù)循環(huán)。當(dāng)要返回的數(shù)組的下標(biāo)達(dá)到 n*m 時(shí)，說明所有的值都遍歷完了，就結(jié)束循環(huán)。第二種思路是將第一行輸出，同時(shí)刪除第一行 ，使用魔方旋轉(zhuǎn)的思路，將剩余矩陣整體逆時(shí)針旋轉(zhuǎn)，繼續(xù)取第一行輸出……直到所有矩陣被刪空為止，這個(gè)思路比較適合Python用，C++還是用第一種，下面給出C++示例代碼：

9.寫一段程序判斷IP字符串是否屬于內(nèi)網(wǎng)IP

時(shí)間限制：1秒
空間限制：32768K

從業(yè) 666 年的 BILIBILI 網(wǎng)絡(luò)安全工程師 KindMo 最近很困惑，公司有一個(gè)業(yè)務(wù)總是受到 SSRF 攻擊。請幫他寫一個(gè)程序，判斷輸入的字符串是否屬于內(nèi)網(wǎng)IP，用于防御該漏洞。
我們知道常見的內(nèi)網(wǎng)IP有，127.0.0.1，192.168.0.1 等。

輸入描述:

每次輸入僅包含一個(gè)IP字符串，即一個(gè)測試樣例

輸出描述:

對于每個(gè)測試實(shí)例輸出整數(shù)1或0，1代表True，即輸入屬于內(nèi)網(wǎng)IP，0代表False，即輸入不屬于內(nèi)網(wǎng)IP或不是IP字符串。

輸入例子1:

42.96.146.169

輸出例子1:

0

水題+2，這個(gè)題只要是10.xxx.xxx.xxx,127.yy.xxx.xxx,192.168.xxx.xxx的都是內(nèi)網(wǎng)，沒啥好說的，整上C++示例代碼：

10.給定一個(gè)整數(shù)數(shù)組,判斷其中是否有3個(gè)數(shù)和為N

時(shí)間限制：1秒
空間限制：131072K

給定一個(gè)整數(shù)數(shù)組,判斷其中是否有3個(gè)數(shù)和為N

輸入描述:

輸入為一行
逗號前為一個(gè)整數(shù)數(shù)組，每個(gè)元素間用空格隔開；逗號后為N

輸出描述:

輸出bool值
True表示存在3個(gè)和為N的數(shù)
False表示不存在3個(gè)和為N的數(shù)

輸入例子1:

1 2 3 4 5,10

輸出例子1:

True

這個(gè)題可以用超·二分查找的方式（其實(shí)就是二分查找，只不過是三個(gè)數(shù)），可以對這一排數(shù)先升序排列，先算第一個(gè)和第二個(gè)還有最后一個(gè)的和是不是等于N，如果大于N，說明最后一個(gè)數(shù)大了，就求第一個(gè)和第二個(gè)還有倒數(shù)第二個(gè)的值是不是N；如果小于N，說明第二個(gè)小了，求第一個(gè)和第三個(gè)還有最后一個(gè)的值是不是N。算到中間數(shù)還不行，說明第一個(gè)數(shù)不行，再從第二個(gè)數(shù)開始，算第二個(gè)和第三個(gè)還有最后一個(gè)的值是不是N……，大概思路就是這樣，給出C++示例代碼：

11.實(shí)現(xiàn)一個(gè)HTML語法檢查器

時(shí)間限制：1秒
空間限制：32768K

實(shí)現(xiàn)一個(gè)HTML語法檢查器。HTML語法規(guī)則簡化如下：標(biāo)簽必須閉合，可以由開始和結(jié)束兩個(gè)標(biāo)簽閉合，如<div></div>，也可以自閉合， 如<div />?標(biāo)簽可以嵌套如<div><a></a></div>或者?<div><a/></div>，但是標(biāo)簽不能交叉：<div><a></div></a>是不允許的。標(biāo)簽里可以有屬性 如<div id="a<1"></div>?屬性的規(guī)則是name="任意非引號字符"，多屬性聲明之間必須有空格，屬性聲明不符合規(guī)則時(shí)，整段HTML都算語法錯誤 輸入文本只會出現(xiàn)字母a-z和<>"= 請用任意語言實(shí)現(xiàn)一個(gè)HTML語法檢查器函數(shù)，有語法錯誤返回1，沒有語法錯誤返回0

輸入描述:

一行，一個(gè)HTML字符串

輸出描述:

有語法錯誤返回1，沒有語法錯誤返回0

這個(gè)題沒有輸入案例，看來是因?yàn)楸粸g覽器識別成HTML代碼了，有人看到?jīng)]有測試用例，于是自暴自棄，使用了隨緣法，居然過了85%：

由于C++處理字符實(shí)在蛋疼，于是我便不想寫了，主要就是用棧來存儲，還是比較簡單的，至于題目說的有<div id="a<1"></div>的問題，其實(shí)把引號里的東西屏蔽下就行了，給出其他大佬的C++代碼，它的注釋還是寫的比較全的：

12.孫悟空的徒弟

時(shí)間限制：3秒
空間限制：131072K

打敗魔人布?xì)W以后，孫悟空收了n個(gè)徒弟，每個(gè)徒弟戰(zhàn)斗力各不相同。他教導(dǎo)所有的徒弟和體術(shù)，合體后戰(zhàn)斗力為原戰(zhàn)斗力相乘。任何兩個(gè)徒弟都可以合體，所以一共有n*(n-1)/2種合體徒弟。有一天，他想考驗(yàn)一下孫悟天戰(zhàn)斗力如何，希望在所有n*(n-1)/2種合體徒弟中選擇戰(zhàn)斗力第k高的，與孫悟天對戰(zhàn)。可是孫悟空徒弟太多了，他已然懵逼，于是找到了你，請你幫他找到對的人。

輸入描述:

第一行兩個(gè)int。徒弟數(shù)量：n <= 1*10^6；

戰(zhàn)斗力排名:k <= n*(n-1)/2

第二行空格分隔n個(gè)int，表示每個(gè)徒弟的戰(zhàn)斗力。

輸出描述:

戰(zhàn)斗力排名k的合體徒弟戰(zhàn)斗力。

輸入例子1:

5 2
1 3 4 5 9

輸出例子1:

36

這個(gè)題也是用二分查找，畢竟題目暗示很清楚了，但是不能用簡單的二分查找，主要還是沒有k代表的值是多少，所以就只能進(jìn)行兩層二分查找。也就是說想要找出排名第K的數(shù)，需要我們在內(nèi)部使用二分查找，若有至少k個(gè)數(shù)大于mid，那么我們便可以更新left為mid值；當(dāng)區(qū)間右邊的部分少于k個(gè)數(shù)大于mid，也就是說，第k個(gè)值在left與mid中間了，更新r為mid-1；更新r值直到1中的二分查找退出，left的位置便是從最后數(shù)的第k個(gè)位置。給出示例C++代碼：

13.翻轉(zhuǎn)鏈表

時(shí)間限制：1秒
空間限制：32768K

對于一個(gè)鏈表 L: L0→L1→…→Ln-1→Ln,
將其翻轉(zhuǎn)成 L0→Ln→L1→Ln-1→L2→Ln-2→…

輸入是一串?dāng)?shù)字，請將其轉(zhuǎn)換成單鏈表格式之后，再進(jìn)行操作

輸入描述:

一串?dāng)?shù)字，用逗號分隔

輸出描述:

一串?dāng)?shù)字，用逗號分隔

輸入例子1:

1,2,3,4,5

輸出例子1:

1,5,2,4,3

這個(gè)題是LeetCode第143題重排鏈表，改了改題目就用起來了，又? 偷? 懶? 了

可以用鏈表做，但沒必要，反復(fù)橫跳即可，即先輸出第一個(gè)、再輸出最后一個(gè)、再輸出第二個(gè)、再輸出倒數(shù)第二個(gè)……，給出C++示例代碼：

當(dāng)然按照題意用鏈表做的話就是用快慢指針（設(shè)置兩個(gè)指針，慢指針每次走一步，快指針每次走兩步，快指針走完慢指針就剛好走了一半）拆分鏈表，翻轉(zhuǎn)后半部分，再和前半部分拼接即可，給出C++示例代碼：

現(xiàn)在年頭按照規(guī)則辦事的人可不多了！不過有簡單方法為什么不用呢？

14.ん…紅茶？

時(shí)間限制：1秒
空間限制：131072K

高貴的蕾米莉亞大小姐每天需要飲用定量 B 型血的紅茶以保持威嚴(yán)，并且要分兩杯在不同時(shí)段飲用。
女仆長十六夜咲夜每天可以制作很多杯不同劑量 B 型血的紅茶供蕾米莉亞大小姐飲用。
某日，你和天才妖精琪露諾偷偷潛入紅魔館被咲夜抓住，要求在今日份的紅茶中挑出所有滿足大小姐要求的茶杯，否則……

輸入描述:

每個(gè)樣例有三行輸入，第一行輸入表示茶杯個(gè)數(shù)，第二行輸入表示每份茶杯里的 B 型血劑量，第三行表示大小姐今天的定量

輸出描述:

對每一個(gè)樣例，輸出所有可能的搭配方案，如果有多種方案，請按每個(gè)方案的第一杯 B 型血劑量的大小升序排列。
如果無法找到任何一種滿足大小姐的方案，輸出”NO”(不包括引號)并換行。

輸入例子1:

7
2 4 6 1 3 5 7
7

輸出例子1:

1 6
2 5
3 4

這個(gè)題按照大佬的說法確認(rèn)是真·內(nèi)部人員出的，畢竟不少車車人都不知道蕾咪喜歡喝B型血的。而且題目唐 突 惡 臭。作為最后一道題，完全沒有對得起這個(gè)名號，也是二分查找即可，碰到一種就輸出一種。給出C++示例代碼：

后記

這套題難度偏低，很多題水的成分偏多。其實(shí)我本來想出個(gè)互動視頻，但是因?yàn)閷?shí)在沒啥思路可以用在視頻里。而且做了個(gè)demo，群友反應(yīng)平平，表示十分枯燥，就放棄這個(gè)想法，直接弄了個(gè)專欄解析。題目很多解析并不好，還請大佬們海涵，如果你覺得有什么紕漏之處，煩請?jiān)谠u論區(qū)向我提出意見。

所以我能入職B站了嘛？？？