05.08. Draw Line
Description
A monochrome screen is stored as a single array of int, allowing 32 consecutive pixels to be stored in one int. The screen has width w
, where w
is divisible by 32 (that is, no byte will be split across rows). The height of the screen, of course, can be derived from the length of the array and the width. Implement a function that draws a horizontal line from (x1, y)
to (x2, y)
.
Given the length of the array, the width of the array (in bit), start position x1
(in bit) of the line, end position x2
(in bit) of the line and the row number y
of the line, return the array after drawing.
Example1:
Input: length = 1, w = 32, x1 = 30, x2 = 31, y = 0 Output: [3] Explanation: After drawing a line from (30, 0) to (31, 0), the screen becomes [0b000000000000000000000000000000011].
Example2:
Input: length = 3, w = 96, x1 = 0, x2 = 95, y = 0 Output: [-1, -1, -1]
Solutions
Solution 1: Bit Manipulation
First, we calculate the positions of $x_1$ and $x_2$ in the result array, denoted as $i$ and $j$. Then, we set the elements between $i$ and $j$ to $-1$.
If $x_1 \bmod 32 \neq 0$, we need to set the first $x_1 \bmod 32$ bits of the element at position $i$ to $0$.
If $x_2 \bmod 32 \neq 31$, we need to set the last $31 - x_2 \bmod 32$ bits of the element at position $j$ to $0$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 |
|