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