腾讯面试题安置路灯深度解析_解题思路_算法实现_求职指南

一、题目背景与核心逻辑解析

在腾讯的算法面试中，「安置路灯」是一道极具代表性的模拟题与贪心/动态规划结合的题目。它不仅仅考察代码能力，更考察对边界条件的处理以及数学模型的抽象能力。

📝 题目描述

假设有一条长度为 N 米的街道，街道上有 K 个需要照明的特定位置。每个路灯的照射范围为 R 米（即路灯安装在位置 X，可以照亮 [X-R, X+R] 的区间）。现在要求计算出最少需要安装多少个路灯，才能覆盖所有需要照明的位置。

⚙️ 输入输出示例

输入： N=10, K=3, R=2
需要照明位置：[2, 5, 8]
输出： 2
解释： 在位置4安装一盏灯，可覆盖[2,6]，照亮2和5；在位置8安装一盏灯，覆盖[6,10]，照亮8。共需2盏。

⚠️ 常见陷阱

1. 边界重叠：路灯范围是闭区间还是开区间？
2. 未排序：输入的位置通常是无序的，必须先排序。
3. 极端情况：K=0 或 R=0 时的处理。

二、解题思路演进：从暴力到最优

面对「腾讯面试题安置路灯」，不同阶段的候选人往往给出不同复杂度的解法。面试官通常希望看到思维的迭代过程。

阶段一：暴力枚举法 O(NR)

思路：遍历街道上的每一个整数点，如果该点未被覆盖且属于需要照明点，则在此处或其右侧最远端放置路灯。
缺点： 当N非常大（如10^9）时，遍历效率极低，直接超时。

阶段二：贪心算法 O(K log K)

思路：这是解决此类区间覆盖问题的标准最优解。 1. 将所有需要照明的位置按从小到大排序。 2. 找到第一个未被覆盖的最左边的点 P。 3. 为了尽可能覆盖右边的点，路灯应该安装在 P + R 的位置（前提是P+R不超过街道长度限制，若有上限需取min）。 4. 标记所有被 [P, P+2R] 覆盖的点。 5. 重复步骤2直到所有点被覆盖。
优势： 只需遍历需要照明的点，时间复杂度主要取决于排序。

阶段三：动态规划 (进阶变种)

如果题目增加限制，例如每个路灯有安装成本，或者路灯之间不能太近，贪心可能失效，此时需转化为DP问题。定义 dp[i] 为覆盖前 i 个点所需的最小路灯数。
状态转移： dp[i] = min(dp[j]) + 1，其中 j 是上一个路灯能覆盖到的最左边的点的索引。

三、多语言代码实现示例

以下提供「腾讯面试题安置路灯」最核心的贪心算法实现。这是面试中最被推荐的高分代码。

Java 核心代码

import java.util.Arrays;
public class StreetLight {
    public static int minLights(int n, int[] needs, int r) {
        if (needs == null || needs.length == 0) return 0;
        // 1. 排序
        Arrays.sort(needs);
        int count = 0;
        int i = 0;
        int len = needs.length;
        while (i < len) {
            // 2. 找到第一个未覆盖的点
            int currentPos = needs[i];
            count++;
            // 3. 放置路灯的位置：currentPos + r
            // 注意：如果题目有街道长度限制 L，这里需要 Math.min(currentPos + r, L)
            int lightPos = currentPos + r;
            // 4. 跳过所有被覆盖的点
            // 覆盖范围是 [lightPos - r, lightPos + r]
            // 即 [currentPos, currentPos + 2r]
            while (i < len && needs[i] <= lightPos + r) {
                i++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[] needs = {2, 5, 8};
        System.out.println(minLights(10, needs, 2)); // 输出 2
    }
}

代码解析： 关键在于 needs[i] <= lightPos + r 这个判断条件，它确保了只要点在路灯右侧射程内，就被视为已覆盖。

Python 核心代码

def min_lights(needs, r):
    if not needs:
        return 0
    # 1. 排序
    needs.sort()
    count = 0
    i = 0
    n = len(needs)
    while i < n:
        # 2. 当前未被覆盖的最左点
        current_pos = needs[i]
        count += 1
        # 3. 路灯安装位置
        light_pos = current_pos + r
        # 4. 跳过所有覆盖范围内的点
        # 覆盖区间: [current_pos, light_pos + r]
        while i < n and needs[i] <= light_pos + r:
            i += 1
    return count
测试
print(min_lights([2, 5, 8], 2)) # 输出 2

Pythonic 风格： Python 的列表排序和索引操作非常简洁，适合快速原型开发，但在超大规模数据下需注意性能开销。

C++ 核心代码

#include 
#include 
#include 
using namespace std;
int minLights(vector& needs, int r) {
    if (needs.empty()) return 0;
    // 1. 排序
    sort(needs.begin(), needs.end());
    int count = 0;
    int i = 0;
    int n = needs.size();
    while (i < n) {
        int currentPos = needs[i];
        count++;
        // 3. 路灯位置
        int lightPos = currentPos + r;
        // 4. 跳过覆盖点
        while (i < n && needs[i] <= lightPos + r) {
            i++;
        }
    }
    return count;
}
int main() {
    vector needs = {2, 5, 8};
    cout << minLights(needs, 2) << endl; // 输出 2
    return 0;
}

C++ 性能： 使用 std::sort 和 vector 是标准做法，对于内存敏感型面试，需注意指针操作和内存释放。

四、面试官考察点与进阶追问

在回答「腾讯面试题安置路灯」时，仅仅给出代码是不够的。面试官通常会根据你的回答进行深度追问，以考察你的工程思维和边界意识。

考察维度	常见问题	高分回答策略
边界条件	如果路灯必须安装在整数位置怎么办？	讨论浮点数与整数的转换，以及向下取整的影响。
扩展性	如果路灯有不同的功率（覆盖范围不同）？	转化为加权区间覆盖问题，可能需要动态规划或优先队列。
数据规模	如果N=10^9，K=10^5怎么办？	强调坐标离散化或只关注关键点，避免遍历街道长度N。
工程落地	实际工程中如何优化电费？	引入成本函数，从“最少数量”转向“最小成本”，讨论多目标优化。

💡 进阶：坐标离散化技巧

当街道长度 N 极大（如 10^9）但需要照明的点 K 较少时，直接开数组会内存溢出。此时应使用坐标离散化或只记录关键点的方法。在「腾讯面试题安置路灯」的变种中，我们只关心需要照明的点 needs[i] 和它们之间的相对距离，因此 N 的具体数值不影响算法逻辑，只影响边界判断。

五、网友们还关心

除了「腾讯面试题安置路灯」本身，求职者在准备腾讯及其他大厂面试时，通常还会关注以下相关热点话题。这些内容构成了完整的算法知识体系。

六、常见问题解答 (FAQ)

Q1: 如果路灯可以安装在非整数位置，解法有变化吗？

如果允许非整数位置，贪心策略依然有效，但放置点可以是浮点数。例如，第一个点 P=2, R=2，路灯可装在 4.0。如果要求整数，则装在 4。核心逻辑 lightPos = currentPos + R 不变，只是数据类型从 int 变为 float。

Q2: 为什么贪心算法在这里是最优的？

贪心选择性质在于：为了覆盖最左边的未覆盖点 P，我们必须放置一个路灯。为了使这个路灯能覆盖到尽可能多的右侧点，它应该尽可能靠右，但不能超过 P+R（否则 P 就无法被覆盖了）。因此，P+R 是局部最优解，也是全局最优解的一部分。

Q3: 这道题属于什么难度？

在 LeetCode 和各大题库中，基础版属于Easy或Medium难度。但如果加上动态更新、多光源异构、成本优化等限制，难度会升至Hard。

一、 题目背景与核心逻辑解析

二、 解题思路演进：从暴力到最优

三、 多语言代码实现示例