面试题 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]

1
2
3
4

示例2:

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

解题

方法一：bitset模拟

输入length=9, w=96, x1=61 , x2=63,y=2

遍历每个像素组(32个为一组),如果row==y，说明直线在这一行通过$x1<=col\ast 32+k<=x2$来判断当前像素是否为直线所在像素。

class Solution {
public:
    vector<int> drawLine(int length, int w, int x1, int x2, int y) {
        vector<int> res;
        int cols=w/32;//屏幕的列组数(32(int)个像素一组)
        int rows=length/cols;//屏幕的行数

        for(int row=0;row<rows;row++){//遍历行数
            for(int col=0;col<cols;col++){//遍历列组数
                if(row==y){//确定直线所在行
                    bitset<32> num;
                    for(int k=0;k<32;k++){//遍历每个组(32个像素)
                        if(x1<=col*32+k&&col*32+k<=x2){//像素的列坐标在直线范围中，就置1
                            num[31-k]=1;
                        }
                    }
                    res.push_back((int)num.to_ulong());
                }
                else res.push_back(0);
            }
        }
        return res;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二：位运算

参考链接

class Solution {
public:
    vector<int> drawLine(int length, int w, int x1, int x2, int y) {
        vector<int> res(length,0);
        for(int i=x1;i<=x2;i++){
            res[(w*y+i)>>5]|=(1<<(31-i%32));
        }
        return res;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12