LeetCode 面试题 05.08. 绘制直线
题目描述
题意分析
屏幕初始全为零，每行有
w个像素，按从上到下、从左到右的顺序，每32个像素装进一个有符号整数。块内最左像素对应第31位，最右像素对应第0位。要把第
y行中横坐标落在闭区间[x1,x2]的像素设为一，返回完整的整数数组，其余像素保持为零。题目保证w能被32整除，所以每行恰好占w/32个完整整数块。
解法：按行偏移与块内位号逐像素置位
核心思路
[!blue]
第
y行之前有y行，每行占w/32个整数，因此这一行的起点下标为rowStart=y*w/32。同一行内，横坐标x所在的块号是x/32，对应数组下标就是rowStart+x/32。
x%32表示像素在块内从左起的偏移，整数位号却从右侧最低位开始编号，所以目标位是31-x%32。用1 << bit得到只有该位为一的掩码，再与当前整数按位或，就能点亮这个像素，同时保留同一块里之前已经画好的像素。从
x1扫描到x2。每一步只改变当前像素对应的唯一位，处理完横坐标x后，区间[x1,x]已经全部画好，其他位置仍未被改变。当循环越过x2，整条闭区间直线恰好完成；跨越整数块时，商决定进入下一个块，余数让位号重新从31开始。返回的是有符号 32 位整数，第
31位为一时出现负数是正确的位模式，不代表计算出错。Java 的int已经具有这个宽度；Go 在每次合并时转成int32运算，再转回int保存，保证同一个 32 位模式得到相同的有符号值，全一块因此是-1。
解题步骤
- 分配全零返回数组。
- 计算
rowStart=y*w/32。- 对
x1..x2的每个像素，找到数组下标与块内位号并按位或。- 返回完整数组，未经过的行和位保持初始零值。
x1==x2时只设置一个像素；两个端点位于同一整数块或不同块，都沿用相同映射，不需要另外拆分左右边界。
代码实现
// 屏幕每行按 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] = int(int32(screen[idx]) | int32(1)<<bit)
}
return screen
}
复杂度分析
- 时间复杂度：$O(length+x2-x1+1)$，包括完整返回数组的零初始化和逐像素绘制。
- 空间复杂度：辅助空间为 $O(1)$；输出数组占 $O(length)$，不计入辅助空间。
关键点总结
[!green]
- 行偏移确定数组中的行起点，横坐标的商确定整数块，余数确定块内位置。
- 块内从左起的像素偏移与从右起的位号相反，需要用
31-x%32转换。- 按位或累积已绘制像素，32 位有符号解释决定最终返回的整数值。
易错点总结
[!yellow]
x2也属于线段，循环条件必须包含等号。- 数组下标按整数块计数，不能直接把像素数量
y*w当成行起点。- 不能直接用
x%32作为位号，否则块内左右方向会颠倒。- Go 的机器整数可能宽于 32 位，不能把正的全一低 32 位数值当作题目要求的有符号结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 05.01. 插入 | 简单 | 一行像素可视为整数中的连续位段；本题把坐标换成块内位号，该题展示清除目标位段后再合并新位值的掩码操作。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！