今天把百度2016/2017秋招剩余的4星題目，以及少部分有難度或者比較有趣味的3星題目來一起分析下，所以這次就來個合集了(共包含了4個題目)，總體來看題目比較簡單，所以分析也會寫得相對簡略一些。盡管題目比較簡單，但是實際編寫的時候還是會遇到一些問題，建議自己動手嘗試解答。

---

格子距離

<題目來源: 百度2017秋招 原題鏈接-可在線提交(賽碼網)>

問題描述

有一個nm的格子圖，每個格子最多與其周圍的四個相鄰，不相鄰的格子之間互相不可達。設一個46的格子圖坐標如下：
_ 123456
1 ######
2 ######
3 ######
4 ######
則(2,3)的格子與(1,3),(3,3),(2,2),(2,4)相鄰。
格子與格子之間存在特殊的墻，阻止兩個相鄰的格子的移動。若(2,3)存在一堵左側的墻，則（2,3）將無法直接到達(2,2)，但(2,2)仍能到達(2,3)。
現給出每個格子周圍墻的情況，求從給定的點(S,T)出發(fā)，到達每一個格子最少經過多少個格子。

這個題目需要求到地鐵每一個格子的最短距離，顯然我們需要從起點不斷地向外擴展，不斷的嘗試移動一步可以到哪些距離，移動兩步可以到哪些距距離...如此移動下去直到所有的格子都被到達，我們可以確保我們到達每一個格子都是最短的距離。

其實這個正是我們BFS(廣度優(yōu)先搜索的思想)，而且這個題目十分適合作為BFS的入門題目。我們首先為按廣度優(yōu)先的方式，遍歷這個地圖設置一個方向增量，以便我們去每次向4個方向擴展(如果沒有圍墻的情況)

dirs = [[-1, 0, 0], [1, 0, 1], [0, -1, 2], [0, 1, 3]]

外層列表表示其有4個方向，其中內層列表的含義：
第1位表示要移動到的這個方向，當前x坐標需要增加(減少)的單位
第2位寶石要移動到的這個方向，當前y坐標需要增加(減少)的單位
第3位表示判斷這個方向是否存在圍墻的二進制位在從低位開始計數的第幾位

從起點開始擴展，設置一個隊列來存儲到達的那些位置以及距離，每次擴展后的x,y坐標和距離都放入這個隊列，然后再從隊列中取出，不斷進行擴展，要主要判斷邊界和圍墻的情況。

讓然，這個題目也可以按最短路徑的方式，上下左右相鄰的兩個點只要沒有圍墻，就建一條邊，然后從起點求一次單源點最短路徑即可。

const_x = 0 const_y = 1 const_wall_bit = 2 dirs = [[-1, 0, 0], [1, 0, 1], [0, -1, 2], [0, 1, 3]]def bfs(map_info, dist, n, m, s, t):que = [(s, t)]dist[s][t] = 0while len(que):cur_x, cur_y = que.pop(0)for d in dirs:if 1 <= cur_x + d[const_x] <= n and 1 <= cur_y + d[const_y] <= m and \not map_info[cur_x][cur_y] & (1 << d[const_wall_bit]) and \dist[cur_x + d[const_x]][cur_y + d[const_y]] == -1:dist[cur_x + d[const_x]][cur_y + d[const_y]] = dist[cur_x][cur_y] + 1que.append((cur_x + d[const_x], cur_y + d[const_y]))def main():t_cases = int(raw_input())for t_case in range(1, t_cases + 1):temp = raw_input().split(' ')n, m, s, t = int(temp[0]), int(temp[1]), int(temp[2]), int(temp[3])map_info = [[0 for i in range(m + 2)] for i in range(n + 2)]for i in range(1, n + 1):line = raw_input().split(' ')for j in range(1, m + 1):map_info[i][j] = int(line[j - 1])dist = [[-1 for i in range(m + 2)] for i in range(n + 2)]bfs(map_info, dist, n, m, s, t)print 'Case {}:'.format(t_case)for i in range(1, n + 1):for j in range(1, m + 1):print dist[i][j],printif __name__ == '__main__':main()

---

Search in XML

<題目來源：百度2017秋招 原題鏈接-可在線提交(賽碼網)>

問題描述

可擴展標記語言（英語：Extensible Markup Language，簡稱：XML），是一種標記語言。
XML 設計用來傳送及攜帶數據信息，不用來表現或展示數據，HTML語言則用來表現數據，所以 XML 用途的焦點是它說明數據是什么，以及攜帶數據信息。
例如，下面是一段 XML 標簽。

＜recipe＞＜recipename＞Ice Cream Sundae＜/recipename＞＜ingredlist＞＜listitem＞＜quantity＞3＜/quantity＞＜itemdescription＞chocolate syrup or chocolate fudge＜/itemdescription＞＜/listitem＞＜listitem＞＜quantity＞1＜/quantity＞＜itemdescription＞nuts＜/itemdescription＞＜/listitem＞＜listitem＞＜quantity＞1＜/quantity＞＜itemdescription＞cherry＜/itemdescription＞＜/listitem＞＜/ingredlist＞＜preptime＞5 minutes＜/preptime＞ ＜/recipe＞

在這個問題中，你需要在給定的文本 XML 中，查找出給定模式 XML 的所有出現的位置。文本 XML 中的每個標簽按照出現的順序編號，根節(jié)點的編號為 1，例如上面的第一個 ＜listitem＞ 標簽的編號為 4，文本和模式標簽有且僅有一個根節(jié)點，輸出每組匹配中，模式 XML 的根節(jié)點標簽在文本 XML 中的編號。

模式是類似這樣的字符串：＜listitem＞＜quantity＞＜/quantity＞＜/listitem＞

這題目是要處理xml并匹配模式。這類題目首先我們需要能方便的訪問它的每一個節(jié)點，XML本深就是一種樹形結構，顯然我們應該先建樹，采用tree-list的形式，并且按照層次的順序為其標號。為了建樹和描述這個xml，我們數據結構設計如下：

class TreeType:def __init__(self, lab='', father=None, num=0):self.num = numself.lab = labself.father = fatherself.son_list = []

其中num表示編號，lab是xml的標簽，father是父親節(jié)點，方便我們建樹時，遇到</>返回到其父節(jié)點。son_list是當前節(jié)點的所有的子節(jié)點。

為了方便處理，先建個虛擬的根節(jié)點(盡管本題說明了xml只有一個根節(jié)點，這樣做的好處是，你每個節(jié)點都可以調用統(tǒng)一的插入或者返回上層節(jié)點的操作，不需要特別處理一開始的根節(jié)點)，建樹按行掃描xml，遇到<>就為當創(chuàng)建一個新的節(jié)點，并且添加描述信息，然后將當前節(jié)點指向這個新建的節(jié)點。如果遇到</>就退回到其父節(jié)點即可。當退回到虛擬的根節(jié)點的時候，表明xml讀取完成(這也是簡歷虛擬根節(jié)點的好處)。

建樹完成后，我們對這棵樹進行dfs，按深度去查找是否存在題目給定的模式。需要注意到下面的這種特殊的情況：

<a><b><c></c><c></c><c></c></b> </a>

如果模式為

<b><c></c></c>，

我們DFS的時候要注意重復識別的問題，這樣的模式題目只算出現一次。此外，不要從本題的頁面直接復制輸入樣例。

import sysconst_self = 1class TreeType:def __init__(self, lab='', father=None, num=0):self.num = numself.lab = labself.father = fatherself.son_list = []def parse_line(line):labs = []t_lab = []lab_f = Falsefor ch in line:if ch == '<':lab_f = Trueif lab_f:t_lab.append(ch)if ch == '>':lab_f = Falselabs.append(list(t_lab))t_lab[:] = []return labsdef new_lab_to_tree(cn, r, cnt):node = TreeType(r, cn, cnt)cn.son_list.append(node)return nodedef finish_lab(cn, r):return cn.fatherdef dfs(cn, mode, state, first_p, matched_p, fi):lab = ''.join(cn.lab)next_s = stateif lab == ''.join(mode[state]):next_s += 1else:next_s = 0if next_s == 1:first_p = cn.numif next_s >= len(mode) / 2 and not fi:if not len(matched_p) or first_p != matched_p[-1]:matched_p.append(first_p)fi = Truefor son in cn.son_list:dfs(son, mode, next_s, first_p, matched_p, fi)def main():node_cnt = 0current_node = TreeType('', None, node_cnt)xml = []while True:line = map(str, sys.stdin.readline().strip().split('\n'))[0]labs = parse_line(line)xml.append(labs)for lab in labs:if ''.join(lab).startswith('</'):current_node = finish_lab(current_node, lab) # r is used for verifyelse:node_cnt += 1current_node = new_lab_to_tree(current_node, lab, node_cnt)if current_node.num == 0:breakmode = parse_line(map(str, sys.stdin.readline().strip().split('\n'))[0])matched_p = []dfs(current_node, mode, 0, 0, matched_p, False)print len(matched_p)for p in matched_p:print p,if __name__ == '__main__':main()

---

內存檢查

<題目來源：百度2017秋招 原題鏈接-可在線提交(賽碼網)>

問題描述

有一個含n字節(jié)的連續(xù)內存區(qū)域可能存在問題，工程師手中有一種檢查軟件，軟件每次運行可以檢查一段連續(xù)內存區(qū)間。由于檢查的區(qū)間長度越長，要花費的時間就越多，因此工程師希望能夠在運行最多m次程序的情況下，每次檢查的區(qū)間長度最大值最小，且檢查的區(qū)間的并集包含了所有出現的"1"。現給出內存的情況（0代表該字節(jié)不需要檢查，1代表該字節(jié)需要檢查），求最小的區(qū)間最大長度。

需要注意到這類題目的重要信息：最小的區(qū)間最大長度，仔細閱讀這個題目之后我們會發(fā)現，如果我們從正面入手考慮，會考慮比較多的情況，尤其是既要考慮到這個最小的區(qū)間，又要考慮到使得其長度盡可能的大，難度比較大。另外觀察到，這個題目的答案是一個已知的區(qū)間，答案的范圍不外乎就是整個內存區(qū)域的長度，或者在m足夠大的情況，我們可以為每個“1”單獨檢查一次，這時的答案是1。

由于答案是連續(xù)且單調遞增的，那么我們可以考慮二分枚舉所有的答案，剩下的問題就是如何驗證這個答案是否正確了。顯然我們從內存區(qū)域的一個方向開始后，碰到1就需要檢查，這個時候，按長度檢查即可。當前長度的區(qū)間檢查完后掃描內存，碰到1就繼續(xù)及檢查，如果超過m次，且還沒完成檢查，那么證明這個答案不可行，我們就縮小了答案的范圍。

import sysdef test_scan(l_segment, i_segment_len, i_len, i_lim):i_cur_lf = 0i_use = 0b_allzero = Truefor i in range(i_segment_len):if '1' == l_segment[i]:b_allzero = Falseif not i_cur_lf:i_use += 1i_cur_lf = i_lenif i_cur_lf:i_cur_lf -= 1if i_use <= i_lim:if i_len > 0 or (0 == i_len and b_allzero):return Truereturn Falseif __name__ == '__main__':i_test_case = int(raw_input())for scr in range(i_test_case):l_line = raw_input().split()i_segment_len = int(l_line[0])i_exe_lim = int(l_line[1])l_segment = list(raw_input())i_top = i_segment_leni_bot = 0while i_top >= i_bot:i_mid = (i_top + i_bot) / 2if test_scan(l_segment, i_segment_len, i_mid, i_exe_lim):i_res = i_midi_top = i_mid - 1else:i_bot = i_mid + 1print 'Case ' + str(scr + 1) + ': ' + str(i_res)

時鐘

<題目來源: 百度2017秋招 原題鏈接-可在線提交(賽碼網)>

問題描述

小A、小B、小C三人正組隊參加現場賽。小A剛過了一道大模擬，伸出手想看看幾點了，卻發(fā)現自己沒有帶表，隊友也沒有帶，因為大家平時是用手機看的。小A發(fā)現現場有一個電子顯示屏上面有時間。
電子顯示屏是一個7100的點陣,當前時間為一個729的矩陣,在顯示屏上左右滾動,詳見樣例
數字0~9分別用7*6的矩陣表示如下

遺憾的是，小A眼睛高度近視，需要你念出時間給他聽...
所以現在給你一個這樣的點陣，輸出當前時間。

輸入
多組輸入數據，第一行是數據組數T(T≤1440)。
接下來是T組數據，每組數據是一個7100的點陣。輸入數據保證其中存在合法的729的點陣，詳見樣例。

輸出
對每組數據輸出一行答案，該行中輸出“Case #k: result”(對應第k組數據，冒號后有空格),result為當前時間h:m。

這類題目主要難點在于字符串的處理，如何設計數據結構去存儲這個樣的一個點陣，然后是要利于我們對這個點陣進行處理。
首先，我們考慮如何識別點陣數字，其實這個里面有一些特征，我們可以耐心的去找出來，我們可以從需要數目多的開始入手:例如"8"，我們確保3個點的有無""就可以識別。但是，總體我覺得還是比較麻煩。容易出錯，還不太好排除問題。
我的方法就比較暴力，但是很有效：把每個數字的76的點陣存在代碼里，取出7100點陣中的每個數字，然后逐行按字符串比較即可。

剩下最后一個需要解決的問題是如何定位的問題，因為這個數碼從哪一列開始，并不是固定的。觀察后，我們發(fā)現通過定位“:”然后計算小時的開始，和分鐘的開始很方便，每個數碼相對于":"的位置[-14, -7, 2, 9]，至此這個問題也就徹底解決了。

import sysconst_board_row = 7 const_board_col = 100template = [['******','* *','* *','* *','* *','* *','******'],[' *',' *',' *',' *',' *',' *',' *'],['******',' *',' *','******','* ','* ','******'],['******',' *',' *','******',' *',' *','******'],['* *','* *','* *','******',' *',' *',' *'],['******','* ','* ','******',' *',' *','******'],['******','* ','* ','******','* *','* *','******'],['******',' *',' *',' *',' *',' *',' *'],['******','* *','* *','******','* *','* *','******'],['******','* *','* *','******',' *',' *','******']]def compare_dig(board, col_begin, col_end):for i in range(10):match_f = Truefor row in range(7):# print ''.join(board[row][col_begin:col_end + 1])if ''.join(board[row][col_begin:col_end + 1]) != ''.join(template[i][row]):match_f = Falsebreakif match_f:return ireturn -1def main():test_cases = map(int, sys.stdin.readline().strip().split())[0]for test_case in range(1, test_cases + 1):board = [['' for i in range(const_board_col)] for j in range(const_board_row)]for i in range(const_board_row):board[i] = map(str, sys.stdin.readline().split('\n'))[0]# local divide tagfor i in range(const_board_col):cnt = 0for j in range(const_board_row):if board[j][i] == '*':cnt += 1if cnt == 2 and board[2][i] == '*' and board[4][i] == '*':dv_tag_col = ibreakdg_local = [-14, -7, 2, 9]rs = []for i in range(4):rs.append(compare_dig(board, dv_tag_col + dg_local[i], dv_tag_col + dg_local[i] + 5))hh = rs[0] * 10 + rs[1]mm = rs[2] * 10 + rs[3]print ('Case #{}: {}:{}').format(test_case, hh, mm)if __name__ == '__main__':main()

總結

以上是生活随笔為你收集整理的百度2016/2017秋招部分题目解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。