Java版LeetCode

Appearance

面试题 05.08. 绘制直线 ​

题目 ​

已知一个由像素点组成的单色屏幕，每行均有 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]
 输入：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]
 输入：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

题解 ​

java
public int[] drawLine(int length, int w, int x1, int x2, int y) {
    int[] result = new int[length];
    // 数字像素长度 屏幕宽度几个数字
    int len = 32, width = w / len;

    // 保证x1小于x2
    if (x1 > x2) {
        x1 ^= x2;
        x2 ^= x1;
        x1 ^= x2;
    }

    // 根据直线起止位置找到横跨的数字位置
    for (int j = x1 / len; j < (x2 / len + (x2 % len == 0 ? 0 : 1)); j++) {
        // 数字开始像素索引
        int begin = j * len;
        // 数字结束像素索引
        int end = (j + 1) * len - 1;
        // 若包含一个数字的开始符号位像素 则是负数 否则为正数
        if (x1 <= begin) {
            // 区分是正数还是负数
            result[y * width + j] = -1;
            // 由低位到高位去0的位数
            int bit = end - Math.min(x2, end);
            // 去掉低位的0
            for (int i = 0; i < bit; i++) {
                result[y * width + j] &= (result[y * width + j] - 1);
            }
        } else {
            // 需要左移动位数 确定最低位1
            // 若终点像素大于当前数字最大像素则从1开始 否则左移
            result[y * width + j] = 1 << (x2 >= end ? 0 : end - x2);
            int bit = Math.min(x2, end) - Math.max(x1, begin);
            for (int i = 0; i < bit; i++) {
                // 高位加1
                result[y * width + j] |= (result[y * width + j] << 1);
            }
        }
    }

    return result;
}
public int[] drawLine(int length, int w, int x1, int x2, int y) {
    int[] result = new int[length];
    // 数字像素长度 屏幕宽度几个数字
    int len = 32, width = w / len;

    // 保证x1小于x2
    if (x1 > x2) {
        x1 ^= x2;
        x2 ^= x1;
        x1 ^= x2;
    }

    // 根据直线起止位置找到横跨的数字位置
    for (int j = x1 / len; j < (x2 / len + (x2 % len == 0 ? 0 : 1)); j++) {
        // 数字开始像素索引
        int begin = j * len;
        // 数字结束像素索引
        int end = (j + 1) * len - 1;
        // 若包含一个数字的开始符号位像素 则是负数 否则为正数
        if (x1 <= begin) {
            // 区分是正数还是负数
            result[y * width + j] = -1;
            // 由低位到高位去0的位数
            int bit = end - Math.min(x2, end);
            // 去掉低位的0
            for (int i = 0; i < bit; i++) {
                result[y * width + j] &= (result[y * width + j] - 1);
            }
        } else {
            // 需要左移动位数 确定最低位1
            // 若终点像素大于当前数字最大像素则从1开始 否则左移
            result[y * width + j] = 1 << (x2 >= end ? 0 : end - x2);
            int bit = Math.min(x2, end) - Math.max(x1, begin);
            for (int i = 0; i < bit; i++) {
                // 高位加1
                result[y * width + j] |= (result[y * width + j] << 1);
            }
        }
    }

    return result;
}