跳转至

面试题 05.08. 绘制直线

题目描述

绘制直线。有个单色屏幕存储在一个一维数组中，使得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]

解法

方法一：位运算

思考

在位图第 \(y\) 行把 \([x_1,x_2]\) 涂成 \(1\)，存储是按 \(32\) 位打包的整数数组。逐像素置位正确但与字边界交互繁琐。

整段覆盖的字可一次写成全 \(1\)（即 \(-1\)），只需修补首尾两个不完全字。

由 \(y\cdot w+x\) 算出首尾字下标 \(i\)、\(j\)，先把 \([i,j]\) 置 \(-1\)，再按 \(x_1\bmod 32\)、\(x_2\bmod 32\) 清掉首字高位与尾字低位以外的位。

我们先算出 \(x_1\) 和 \(x_2\) 在结果数组中的位置，记为 \(i\) 和 \(j\)。然后将 \(i\) 到 \(j\) 之间的元素置为 \(-1\)。

如果 \(x_1 \bmod 32 \neq 0\)，我们需要将 \(i\) 位置的元素的前 \(x_1 \bmod 32\) 位置为 \(0\)。

如果 \(x_2 \bmod 32 \neq 31\)，我们需要将 \(j\) 位置的元素的后 \(31 - x_2 \bmod 32\) 位置为 \(0\)。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:
        ans = [0] * length
        i = (y * w + x1) // 32
        j = (y * w + x2) // 32
        for k in range(i, j + 1):
            ans[k] = -1
        ans[i] = (ans[i] & 0xFFFFFFFF) >> (x1 % 32) if x1 % 32 else -1
        ans[j] &= -0x80000000 >> (x2 % 32)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int[] drawLine(int length, int w, int x1, int x2, int y) {
        int[] ans = new int[length];
        int i = (y * w + x1) / 32;
        int j = (y * w + x2) / 32;
        for (int k = i; k <= j; ++k) {
            ans[k] = -1;
        }
        ans[i] = ans[i] >>> (x1 % 32);
        ans[j] &= 0x80000000 >> (x2 % 32);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> drawLine(int length, int w, int x1, int x2, int y) {
        vector<int> ans(length);
        int i = (y * w + x1) / 32;
        int j = (y * w + x2) / 32;
        for (int k = i; k <= j; ++k) {
            ans[k] = -1;
        }
        ans[i] = ans[i] & unsigned(-1) >> (x1 % 32);
        ans[j] = ans[j] & unsigned(-1) << (31 - x2 % 32);
        return ans;
    }
};

评论