class Solution {
public:
vector<int> drawLine(int length, int w, int x1, int x2, int y) {
}
};
面试题 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]
示例2:
输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0 输出：[-1, -1, -1] 解释：由于二进制 11111111111111111111111111111111 的 int 类型代表 -1，因此返回 [-1,-1,-1]
提示：
1 <= length <= 10^51 <= w <= 3 * 10^50 <= x1 <= x2 < w0 <= y <= 10原站题解
python3 解法, 执行用时: 76 ms, 内存消耗: 16 MB, 提交时间: 2022-11-30 21:10:59
class Solution:
def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:
"""
解题思路：1.先根据length初始化结果数组，元素全为0
2. 计算结果数组中第几个元素开始，值会发生改变，start
3. 将发生变化的元素用数组b_nums保存下来，这里需要将x1对应的像素向左扩展，x2向右扩展，使其能成为一个完整的32位像素
4. 遍历b_nums数组，每32个元素划分一次，利用基本的十进制和二进制转换的方法，将其转换为一个十进制数
:param length:
:param w:
:param x1:
:param x2:
:param y:
:return:
"""
# 先初始化结果数组，全为0
out = [0 for i in range(length)]
width = w // 32
height = length * 32 // width
# 计算从第几个元素开始需要更改结果数组
start = y * width + x1 // 32
b_nums = [] # 发生变化的二进制数组
for i in range(x1//32*32, x2//32*32+32):
if x1 <= i <= x2:
b_nums.append(1)
else:
b_nums.append(0)
# 一共几个元素发生了改变
count = len(b_nums) // 32
for i in range(count):
a = b_nums[i*32 : i*32+32]
positive_flag = True
# 判断是否为负数
if a[0] == 1:
positive_flag = False
# 减1操作
for j in range(31, -1, -1):
if a[j] == 0:
a[j] = 1
else:
a[j] = 0
break
#按位取反操作
for j in range(32):
if a[j] == 0:
a[j] = 1
else:
a[j] = 0
ten = 0
for k in range(32):
ten = ten + a[k] * pow(2, 31-k)
if not positive_flag:
ten = ten * (-1) # 负数需要乘以-1
out[start] = ten
start += 1
return out
python3 解法, 执行用时: 52 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-30 21:07:51
class Solution:
def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:
res = [0] * length
for i in range(x1, x2+1):
width = w // 32
res[width * y + (i // 32)] |= (1 << (31 - (i % 32)))
for i in range(length):
if res[i] & (2 ** 31):
res[i] ^= (2**32 - 1)
res[i] = -res[i] - 1
return res
java 解法, 执行用时: 0 ms, 内存消耗: 41.9 MB, 提交时间: 2022-11-30 21:04:32
class Solution {
public int[] drawLine(int length, int w, int x1, int x2, int y) {
int[] ans=new int[length];
int low=(y*w+x1)/32;
int high=(y*w+x2)/32;
for(int i=low;i<=high;i++){
ans[i]=-1;
}
ans[low]=ans[low]>>>x1%32;
ans[high]=ans[high]&Integer.MIN_VALUE>> x2 % 32;
return ans;
}
}