绘制直线

绘制直线。有个单色屏幕存储在一个一维数组中，使得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,970提交次数3,652

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/draw-line-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目的意思

用一维数组来存储所有像素值：

• length是结果数组的长度是length；
• w是当前屏幕宽度，单位是像素。除以32就是一行用多少个int表示；
• 高度就是length*32 / w，实际计算没啥用。y+1别超过这个值就可以；
• 题目要求在第y行画一条直线（0开始计数）。像素位置是从x1到x2；
• 图像的坐标是左上角为原点，水平向右x递增，水平向下是y递增；
  所以，题目中的示例改一改就是这样的：

length = 3, w = 32, x1 = 18, x2 = 28, y = 2

只用1个int，表示一个高度为3，宽度为32的屏幕，绘制的位置第2行（0开始计数）是从18到28

0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0011 1111 1111 1000
                      ^            ^   
                     x1           x2
结果中第一个数字在数组中的位置是 gIndex=y * (w / 32) + (w / 32 - 1);
新添加数字时gIndex--;

class Solution {
    public int[] drawLine(int length, int w, int x1, int x2, int y) {
        if (w == 0) return new int[]{0};
        int[] screen = new int[w];
        for (int i = x1; i <= x2; i++) {
            screen[i] = 1;
        }
        int index = 0;
        int[] res = new int[length];


        int val = 0;
        int bitPow = 1;
        int gIndex = y * (w / 32) + (w / 32 - 1);


        while (index < w) {
            val += screen[w - index - 1] * bitPow;
            bitPow *= 2;
            index++;
            if (index % 32 == 0) {
                res[gIndex--] = val;
                val = 0;
                bitPow = 1;
            }
        }
        return res;
    }
}

位运算

class Solution {
    public int[] drawLine(int length, int w, int x1, int x2, int y) {
        int[] ret = new int[length];
        // 注意根据所在行数计算偏移量
        int offset = y * w / 32;
        // 首位数字下标
        int head = x1 / 32 + offset;
        // 末位数字下标
        int rear = x2 / 32 + offset;
        // 把涉及到的数全部置 -1 也就是 0b11111111111111111111111111111111
        for (int i = head; i <= rear; i++)
            ret[i] = -1;
        // 调整首位数字
        ret[head] = ret[head] & -1 >>> x1 % 32;
        // 调整末位数字
        ret[rear] = ret[rear] & Integer.MIN_VALUE >> x2 % 32;
        return ret;
    }
}

作者：1ujin
链接：https://leetcode-cn.com/problems/draw-line-lcci/solution/java-wei-yun-suan-shuang-bai-by-1ujin/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：1ujin 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信