LeetCode 面试题 05.08. 绘制直线
目录
题目描述
题意分析
屏幕按行存进一维
int数组，每个整数连续表示 32 个像素。给定屏幕宽度w、行号y和横坐标闭区间[x1, x2]，要把这条线上的像素设为 1，其余位置保持 0。坐标到存储位置有两层映射：一行占
w / 32个整数，所以第y行从数组下标y * w / 32开始；行内像素x落在第x / 32个整数中。题目规定每个整数的最高位代表更靠左的像素。因此
x % 32 = 0对应 bit 31，而不是 bit 0；真正的位号是31 - x % 32。Java 返回数组里出现负数并不表示错误——若某个整数的最高位为 1，它按有符号十进制打印自然是负数，但 32 位图案完全正确。
解法：逐像素定位并置位
核心思路
最直接且不易错的方案是遍历
[x1, x2]中的每个横坐标，分别算出它所在的整数下标与位号，再用或运算置 1。每个像素只处理一次，坐标换算与题目存储定义逐字对应。令
rowStart = y * w / 32。对当前x，数组下标是rowStart + x / 32，掩码是1 << (31 - x % 32)。执行screen[idx] |= mask只会把目标位设为 1，不会影响同一整数里的其它像素。面试官若追问优化，可以按整数块处理：首尾两个不完整块用掩码，中间完整块直接赋为
-1，时间降为经过的 32 位块数。但本实现的逐像素版更短，复杂度上界也受线段实际长度控制，是解释坐标映射的可靠基线。
解题步骤
- 创建长度为
length的零数组，代表全黑屏幕。- 计算第
y行的首个整数下标rowStart = y * w / 32。- 从
x1到x2含两端逐像素遍历。- 用
rowStart + x / 32找到目标整数，用31 - x % 32找到其中的目标位，并用或运算置位。- 返回屏幕数组。
以
length = 3、w = 96、x1 = 30、x2 = 34、y = 0为例。x = 30、31落在第 0 个整数的 bit 1、0，得到十进制3；x = 32、33、34落在第 1 个整数的 bit 31、30、29，位图为0xE0000000，Java 十进制表示是-536870912；第 2 个整数保持 0。结果为[3, -536870912, 0]。
代码实现
// 屏幕每行按 32 位整数分块，块内最左像素对应最高位。
class Solution {
public int[] drawLine(int length, int w, int x1, int x2, int y) {
int[] screen = new int[length];
int rowStart = y * w / 32;
for (int x = x1; x <= x2; x++) {
int idx = rowStart + x / 32;
int bit = 31 - x % 32;
screen[idx] |= 1 << bit;
}
return screen;
}
}
// 屏幕每行按 32 位整数分块，块内最左像素对应最高位。
func drawLine(length int, w int, x1 int, x2 int, y int) []int {
screen := make([]int, length)
rowStart := y * w / 32
for x := x1; x <= x2; x++ {
idx := rowStart + x/32
bit := 31 - x%32
screen[idx] |= 1 << bit
}
return screen
}
复杂度分析
- 时间复杂度：$O(x2 - x1 + 1)$，线段上的每个像素置位一次。按整块优化后可降为 $O(\lceil(x2-x1+1)/32\rceil)$。
- 空间复杂度：返回数组占 $O(length)$；不计返回值，辅助空间为 $O(1)$。
关键点总结
- 先算“第几个 32 位块”，再算“块内第几位”，是所有位图坐标映射题的通用拆法。
- 本题的块内方向与普通最低位编号相反：左侧像素映射到高位，所以位号必须是
31 - x % 32。- 面试表达应主动解释负数输出：数组元素是有符号
int，但题目关心的是它的 32 位图案。- 追问优化时再给“首尾掩码 + 中间块全 1”，不要一开始就用难验证的复杂掩码掩盖坐标关系。
易错点总结
- 把块内位号写成
x % 32：x = 0会点亮最低位，线段被整块水平镜像；正确位置是 bit 31。- 漏掉行偏移：
y = 1时仍写进数组开头，把第二行画到第一行。- 循环条件写成
x < x2：最右端像素不亮；题目给的是闭区间，必须包含x2。- 看到负数就认为溢出：设置 bit 31 后有符号
int本来就为负，不应清除符号位。- 用赋值代替或运算：同一个整数里先前已经画好的像素会被后一位掩码覆盖，只剩最后一个点。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 190. 颠倒二进制位 | 简单 | 理解固定 32 位中的位置映射 |
| 191. 位1的个数 | 简单 | 基础掩码与逐位操作 |
| 201. 数字范围按位与 | 中等 | 用公共高位处理整段二进制区间 |
| 面试题 05.07. 配对交换 | 简单 | 用交替掩码批量搬移位 |