绘制直线

难度: Medium

已知一个由像素点组成的单色屏幕，每行均有 w 个像素点，所有像素点初始为 0，左上角位置为 (0,0)。

现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中，再依次存入长度为 length 的一维数组中。

我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线（即像素点修改为 1），请返回绘制过后的数组。

注意：

用例保证屏幕宽度 w 可被 32 整除（即一个 int 不会分布在两行上）

示例1:

 输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0
 输出：[3]
 解释：在第 0 行的第 30 位到第 31 位画一条直线，屏幕二进制形式表示为 [00000000000000000000000000000011]，因此返回 [3]

示例2:

 输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0
 输出：[-1, -1, -1]
 解释：由于二进制 11111111111111111111111111111111 的 int 类型代表 -1，因此返回 [-1,-1,-1]

提示：

1 <= length <= 10^5
1 <= w <= 3 * 10^5
0 <= x1 <= x2 < w
0 <= y <= 10

Submission

运行时间: 27 ms

内存: 16.3 MB

class Solution:
    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:
        bit321 = 0xffffffff  # 32bit1
        width = w // 32
        # height = length // width

        res = [0] * length
        start = width * y + x1 // 32  # res影响index start
        end = width * y + x2 // 32

        def _to32bit(num):
            # print(333, num)
            # num = num & bit321
            if (num >> 31) & 1:
                return - ((num ^ bit321) + 1)
            return num

        for i in range(start+1, end):
            res[i] = -1  # 32位1 表示-1

        res[start] = bit321 >> (x1 % 32)
        tmp = (bit321 << (31-x2%32)) & bit321
        if start == end:
            res[end] = tmp & res[start]
        else:
            res[end] = tmp
        res[start] = _to32bit(res[start])
        res[end] = _to32bit(res[end])
        return res

Explain

这个题解通过分段绘制直线来处理问题。首先计算出每行32个像素对应一个整数值，再根据输入的x1和x2计算出要修改的整数范围。题解的主要步骤包括：1. 计算影响到的起始和结束索引。2. 对于起始和结束索引内的所有整数，设置为全1（即-1，因为整数中的32个1表示的二进制数转换为整数是-1）。3. 对于起始和结束索引，根据x1和x2的位置设置相应的位。4. 如果x1和x2在同一个整数内，需要特别处理这一整数的位。5. 使用_to32bit函数处理整数的表示，确保返回的整数值是正确的（处理了整数的符号位）。

时间复杂度: O(length)

空间复杂度: O(length)

class Solution:
    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:
        bit321 = 0xffffffff  # 定义一个整数，其32位均为1
        width = w // 32  # 计算每行的整数数量
        # height = length // width # 可以用于计算屏幕高度，此处未使用

        res = [0] * length  # 初始化结果数组
        start = width * y + x1 // 32  # 计算影响的起始整数索引
        end = width * y + x2 // 32  # 计算影响的结束整数索引

        def _to32bit(num):
            # 处理32位整数的表示，特别是负数的情况
            if (num >> 31) & 1:
                return - ((num ^ bit321) + 1)
            return num

        for i in range(start+1, end):
            res[i] = -1  # 直接将整数设置为全1

        res[start] = bit321 >> (x1 % 32)  # 设置起始整数的特定位
        tmp = (bit321 << (31-x2%32)) & bit321  # 设置结束整数的特定位
        if start == end:
            res[end] = tmp & res[start]  # 特殊处理x1和x2在同一整数内的情况
        else:
            res[end] = tmp
        res[start] = _to32bit(res[start])  # 应用_to32bit确保整数表示正确
        res[end] = _to32bit(res[end])
        return res

Explore

这里的`length`实际上代表整个屏幕所需的整数数量，而不是像素数量。由于每个整数包含32个像素（即一个整数可以表示一行中的32个像素），因此整个屏幕的像素通过一系列整数来表示。`length`已经是按照整数计算的总量，可能由调用者根据屏幕的宽度`w`和高度计算得到，并传入函数中。这样直接使用`length`可以简化计算过程，避免在函数内部重复计算屏幕所需的整数数量。

`width * y`是计算从屏幕顶部开始到指定行`y`为止所需跳过的整数总数。因为每一行占据`width`个整数，所以`y`行之前的所有像素占据的整数总数就是`width * y`。这样，当我们在第`y`行绘制从`x1`到`x2`的直线时，可以通过这个计算直接定位到这一行的起始和结束整数索引，从而正确设置这些整数的对应位。

在这个题解中，负数的情况确实可能发生，特别是当整数全部位被设置为1时。在二进制表示中，如果一个整数的所有32位都被设置为1，它将被解释为`-1`，因为这在补码表示中代表-1。这种情况发生在我们将整数中的所有位直接设置为1（如使用`-1`或`0xffffffff`）以表示连续的32个像素被标记。因此，`_to32bit`函数确保转换后的整数值正确处理了符号位，避免错误地解释这些整数值。