Your task is to create a navigation program for an autonomous car. The car is currently in development and has its drawbacks. The car can make no more than two turns on its way from the starting point to the finish point.
The testing center is a grid of b rows and p columns. Find a way from the starting point to the finish point that has no more than two turns and does not contain cells with blockages, or determine that it is impossible to reach the end. The car can only move upwards, downwards, to the left, and the right.
Input:
- First line: integer
b - Second line: integer
p - Next
blines:pspace-separated characters whereo= empty cell,x= blockage,Q= start,W= end.QandWappear only once.
Output: "DRIVE!" if reachable, else "DON'T DRIVE!".
Example: a 4x4 grid where Q and W are diagonally opposite and the row/col path is clear should return "DRIVE!" if it can be done in at most two turns.
解法
在状态 (row, col, direction, turns_used) 上 BFS。每个状态可以沿当前方向继续走，或在 turns_used < 2 时原地切换到任意其他方向。复杂度 O(rows * cols * 4 * 3)。
from collections import deque
def solve(grid):
n, m = len(grid), len(grid[0])
sr = sc = er = ec = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 'Q': sr, sc = i, j
elif grid[i][j] == 'W': er, ec = i, j
DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
dq = deque()
seen = set()
for d in range(4):
dq.append((sr, sc, d, 0)); seen.add((sr, sc, d, 0))
while dq:
r, c, d, t = dq.popleft()
if (r, c) == (er, ec): return "DRIVE!"
dr, dc = DIRS[d]
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != 'x' and (nr, nc, d, t) not in seen:
seen.add((nr, nc, d, t)); dq.append((nr, nc, d, t))
if t < 2:
for nd in range(4):
if nd != d and (r, c, nd, t + 1) not in seen:
seen.add((r, c, nd, t + 1)); dq.append((r, c, nd, t + 1))
return "DON'T DRIVE!"class Solution {
public String solve(char[][] g) {
int n = g.length, m = g[0].length, sr = 0, sc = 0, er = 0, ec = 0;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
if (g[i][j] == 'Q') { sr = i; sc = j; }
else if (g[i][j] == 'W') { er = i; ec = j; }
}
int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
boolean[][][][] seen = new boolean[n][m][4][3];
Deque<int[]> q = new ArrayDeque<>();
for (int d = 0; d < 4; d++) { q.add(new int[]{sr, sc, d, 0}); seen[sr][sc][d][0] = true; }
while (!q.isEmpty()) {
int[] s = q.poll();
int r = s[0], c = s[1], d = s[2], t = s[3];
if (r == er && c == ec) return "DRIVE!";
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && g[nr][nc] != 'x' && !seen[nr][nc][d][t]) {
seen[nr][nc][d][t] = true; q.add(new int[]{nr, nc, d, t});
}
if (t < 2) for (int nd = 0; nd < 4; nd++) if (nd != d && !seen[r][c][nd][t+1]) {
seen[r][c][nd][t+1] = true; q.add(new int[]{r, c, nd, t+1});
}
}
return "DON'T DRIVE!";
}
}string solve(vector<vector<char>>& g) {
int n = g.size(), m = g[0].size();
int sr=0, sc=0, er=0, ec=0;
for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
if (g[i][j] == 'Q') { sr = i; sc = j; }
else if (g[i][j] == 'W') { er = i; ec = j; }
}
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
vector seen(n, vector(m, vector(4, vector<int>(3, 0))));
queue<tuple<int,int,int,int>> q;
for (int d = 0; d < 4; ++d) { q.push({sr, sc, d, 0}); seen[sr][sc][d][0] = 1; }
while (!q.empty()) {
auto [r, c, d, t] = q.front(); q.pop();
if (r == er && c == ec) return "DRIVE!";
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && g[nr][nc] != 'x' && !seen[nr][nc][d][t]) {
seen[nr][nc][d][t] = 1; q.push({nr, nc, d, t});
}
if (t < 2) for (int nd = 0; nd < 4; ++nd) if (nd != d && !seen[r][c][nd][t+1]) {
seen[r][c][nd][t+1] = 1; q.push({r, c, nd, t+1});
}
}
return "DON'T DRIVE!";
}You are given a queue of n integers, from which x integers will be selected as explained below:
- You will perform
xiterations on the queue. - In each iteration,
xintegers will be dequeued.
- If the queue has fewer than
xnumbers, all of them will be dequeued.
- The maximum integer out of the ones dequeued will be selected.
- If there is more than one occurrence of the maximum number, then the first in the queue will be selected.
- The remaining ones when decremented by 1 and enqueued back in the same order in which they were dequeued.
- Once the value becomes 0, the integer cannot be decremented any further, and it will continue to remain 0.
Print the original indexes in the queue of the x integers that are chosen (indexing starts from 1).
Example: x=5, queue=[1,2,2,3,4,5,5] returns the 1-based original indices selected across x rounds.
解法
用承载 (original_index, value) 的双端队列模拟。每轮取前 x 项，挑首个最大值，把其下标追加到答案，剩余项减 1(不低于 0)后重新入队。最坏复杂度 O(x² · n)。
from collections import deque
def solve(x, queue):
dq = deque((i + 1, v) for i, v in enumerate(queue))
chosen = []
for _ in range(x):
if not dq: break
batch = [dq.popleft() for _ in range(min(x, len(dq)))]
mv = max(v for _, v in batch)
for i, (idx, v) in enumerate(batch):
if v == mv:
chosen.append(idx)
for ridx, rv in batch[:i] + batch[i+1:]:
dq.append((ridx, max(0, rv - 1)))
break
return chosenclass Solution {
public List<Integer> solve(int x, int[] queue) {
Deque<int[]> dq = new ArrayDeque<>();
for (int i = 0; i < queue.length; i++) dq.add(new int[]{i + 1, queue[i]});
List<Integer> chosen = new ArrayList<>();
for (int it = 0; it < x && !dq.isEmpty(); it++) {
List<int[]> batch = new ArrayList<>();
for (int j = 0; j < x && !dq.isEmpty(); j++) batch.add(dq.poll());
int maxV = Integer.MIN_VALUE, pos = -1;
for (int i = 0; i < batch.size(); i++) if (batch.get(i)[1] > maxV) { maxV = batch.get(i)[1]; pos = i; }
chosen.add(batch.get(pos)[0]);
for (int i = 0; i < batch.size(); i++) if (i != pos)
dq.add(new int[]{batch.get(i)[0], Math.max(0, batch.get(i)[1] - 1)});
}
return chosen;
}
}vector<int> solve(int x, vector<int>& queue) {
deque<pair<int,int>> dq;
for (int i = 0; i < (int)queue.size(); ++i) dq.push_back({i + 1, queue[i]});
vector<int> chosen;
for (int it = 0; it < x && !dq.empty(); ++it) {
vector<pair<int,int>> batch;
for (int j = 0; j < x && !dq.empty(); ++j) {
batch.push_back(dq.front()); dq.pop_front();
}
int maxV = INT_MIN, pos = -1;
for (int i = 0; i < (int)batch.size(); ++i) if (batch[i].second > maxV) { maxV = batch[i].second; pos = i; }
chosen.push_back(batch[pos].first);
for (int i = 0; i < (int)batch.size(); ++i) if (i != pos)
dq.push_back({batch[i].first, max(0, batch[i].second - 1)});
}
return chosen;
}Find employees whose complete records appear more than once in the EMPLOYEE table (NAME, PHONE, AGE must all match for duplicate).
解法
按构成「完整记录」的所有列分组，筛选 COUNT(*) > 1 的组。SQL 题，不需要 <Tabs>。
SELECT NAME
FROM EMPLOYEE
GROUP BY NAME, PHONE, AGE
HAVING COUNT(*) > 1
ORDER BY NAME;