注册一亩三分地论坛，查看更多干货！
您需要 登录 才可以下载或查看附件。没有帐号？注册账号 
x
Given a 2-D grid with cells marked C (charging station), V (electric vehicle), and (empty), return the shortest distance from each vehicle to its nearest charging station under 4-directional movement. Variants use a 1-D array to find the nearest target value or character; follow-ups extend to global assignment and streaming input.
Requirements
- 2-D grid input where each cell is one of C, V, .
- For every V cell, output the Manhattan / step distance to the nearest C cell (4-directional movement, no obstacles in the base case).
- 1-D variant: array of {0, 1, 2} where 0 = empty, 1 = vehicle, 2 = charger. Return the minimum distance between any vehicle and any charger.
- Character-array variant: given an array containing values such as x, y, and z, find the nearest z for each relevant position. Start with a precomputed representation, then discuss how the contract changes when values arrive as a stream.
- Follow-up (Global Assignment): pair every vehicle with a unique charger so the total driving distance is minimized. If there are more vehicles than chargers, the assignment is impossible. Given a target vehicle index, return which charger that vehicle receives in the globally optimal assignment.
- The interviewer typically does not provide a function signature or example I/ array contains no charger and reject an out-of-range start.
- The global assignment follow-up minimizes total vehicle-to-charger distance, not each vehicle's nearest individual charger. If there are more vehicles than chargers, the assignment is impossible.
- The safe solution is dynamic programming over sorted vehicle and charger indices: dp[i][j] = minimum cost to match the first i vehicles using the first j chargers, with transitions that either skip charger j or match it to vehicle i. Backtrack through the table to answer which charger a queried vehicle receives.
- Minority variant: Some reports phrase the follow-up as a greedy nearest-pair matching. Clarify whether the objective is one-to-one nearest assignment or globally minimum total distance before coding.
|
狗仔卡
收藏
淘帖
好苗
杂草
匿名用户-6PKRE
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
楼主
