题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

绘制直线。有个单色屏幕存储在一个一维数组中，使得 32 个连续像素可以存放在一个 int 里。屏幕宽度为 w，且 w 可被 32 整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。

给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数  y。返回绘制过后的数组。

示例 1:

• 输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0
• 输出：[3]
• 说明：在第 0 行的第 30 位到第 31 为画一条直线，屏幕表示为[0b000000000000000000000000000000011]

示例 2:

• 输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0
• 输出：[-1, -1, -1]

题目思考

1. 可以使用什么位运算来尽可能减少操作次数?

解决方案

思路

• 根据题目描述, 最终结果是一个整数数组, 每个整数代表 32 位
• 所以我们可以通过适当的转换, 将开始和结束位置以及行数转换成数组的下标, 然后将其之间的位全部填充为 1 即可
• 具体做法如下:
  1. 首先初始化长度为 length 的数组, 将其值全部设为 0, 代表空白屏幕
  2. 然后得到直线所在行的起点对应的数组下标 startIndex, 以及开始和结束位置对应的下标 s 和 e, 具体转换过程可以参考下面的代码和注释
  3. 对于该行的数字, 再分为以下三部分 (下面的[]表示闭区间, ()表示开区间):
     1. [startIndex,s)和(e, endIndex]区间的数字: 仍然全部用 0 填充, 不需要做改变 (endIndex 代表该行终点下标, 因为这部分无需改变, 所以不用求出 endIndex)
     2. 数字 s 和 e (s 可能等于 e): 对应的 x1~x2 之间的位用 1 填充
     3. (s,e)区间的数字: 全部用 1 填充, 即赋值为-1 (对应的 32 位全部为 1)
• 注意 python 需要额外处理 32 位整数最高位是 1 的问题:
  • 当最终结果大于 32 位正数最大值 (即0x7FFFFFFF)时, python 会继续显示更大的正数, 而不像其他语言(例如 Java)那样显示负数
  • 所以我们需要将其额外转成正常的负数表示方式, 这个可以利用~(a ^ 0xFFFFFFFF)实现, 即先对低 32 位的逐位取反, 更高位不变, 然后整体再取反, 从而将大于等于 32 位的位变成 1, 此时结果就是正常的 32 位负数了

复杂度

• 时间复杂度 O((x2-x1)/32): 只需要遍历(s,e)区间的数字将其全部位赋值为 1, 其他都是常数操作
• 空间复杂度 O(1): 只使用了几个变量 (结果数组不计算在内)

代码

Python 3

class Solution:
    def drawLine(self, length: int, w: int, x1: int, x2: int,
                 y: int) -> List[int]:
        # 初始化长度为 length 的数组, 将其值全部设为 0, 代表空白屏幕
        res = [0] * length
        # w//32代表每一行有多少个数字, 乘以直线所在行数y, 即得到直线所在行的起点对应的数组下标
        startIndex = y * (w // 32)
        # 通过x1和x2除以32得到偏移量, 再与直线所在行起点下标相加, 从而得到s和e
        s = startIndex + x1 // 32
        e = startIndex + x2 // 32
        for i in range(s + 1, e):
            # 将(s,e)区间的数字的全部位赋值为1
            res[i] = -1
        # posMx代表正数最大值, 如果超过这个值的话需要手动转成负数
        posMx = 0x7FFFFFFF
        mx = 0xFFFFFFFF
        if s == e:
            # 如果s和e相等, 则变更的位数是当前这个数字[x1 % 32, x2 % 32]区间的位
            # 注意右边是低位, 所以mask是1 << (31 - b), 也即第31位对应的是数字1, 下同
            for b in range(x1 % 32, x2 % 32 + 1):
                mask = 1 << (31 - b)
                res[s] |= mask
            if res[s] > posMx:
                # 超出32位正数表示范围时, 需要额外转成32位负数表示, 下同
                res[s] = ~(mx ^ res[s])
        else:
            # 如果s和e相等, 则变更的位数是s的[x1 % 32, 31]区间以及e的[0, x2 % 32]的位
            for b in range(x1 % 32, 32):
                mask = 1 << (31 - b)
                res[s] |= mask
            for b in range(x2 % 32 + 1):
                mask = 1 << (31 - b)
                res[e] |= mask
            if res[s] > posMx:
                res[s] = ~(mx ^ res[s])
            if res[e] > posMx:
                res[e] = ~(mx ^ res[e])
        return res

大家可以在下面这些地方找到我~