
題目解析:給定一個迷宮矩陣,找出從起點走到最近出口(邊界的空地)最少需要走幾步,起點本身不能算作出口
解題思路:找最短路徑直接用 BFS,因為它一層層往外找,最先遇到的出口保證是最佳解。先設 dy 跟 dx 陣列輔助上下左右移動,再設一個佇列裝目前的位子,並把起點標記成牆壁 '+' 防止回頭。丟進迴圈跑,每次把同一層的位子拿出來往四方拓展。如果超出界線或撞牆就跳過,走到邊界就回傳累積步數,不然就把新位子標成牆並塞進佇列。全跑完沒找到就回傳 -1
class Solution {
public:
int nearestExit(vector>& maze, vector& entrance) {
int m = maze.size(), n = maze[0].size();
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
queue> q;
q.push({entrance[0], entrance[1]});
maze[entrance[0]][entrance[1]] = '+';
int steps = 0;
while (!q.empty()) {
int sz = q.size();
steps++;
while (sz--) {
auto [y, x] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int ny = y + dy[d], nx = x + dx[d];
if (ny < 0 || ny >= m || nx < 0 || nx >= n) continue;
if (maze[ny][nx] == '+') continue;
if (ny == 0 || ny == m - 1 || nx == 0 || nx == n - 1)
return steps;
maze[ny][nx] = '+';
q.push({ny, nx});
}
}
}
return -1;
}
};

題目解析:經典猜數字遊戲,在 1 到 n 之間猜出系統設定的數字,可呼叫 API 知道猜的數字是太大、太小還是剛好猜中
解題思路:為了快速鎖定答案,直接使用二分搜尋法。設變數 ans 裝答案,並寫一個遞迴函數。為了避免相加時超過整數上限導致溢位,中間值刻意寫成 l + (r - l) / 2。每次取中間數字呼叫 API:回傳 0 代表猜中,把答案給 ans 並結束;回傳 -1 代表猜太大,把範圍縮到左半邊繼續找;回傳 1 就往右半邊找。最後回傳 ans