程序员面试金典 - 面试题 05.08. 绘制直线
2021/6/5 12:23:58
本文主要是介绍程序员面试金典 - 面试题 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]
题目思考
- 可以使用什么位运算来尽可能减少操作次数?
解决方案
思路
- 根据题目描述, 最终结果是一个整数数组, 每个整数代表 32 位
- 所以我们可以通过适当的转换, 将开始和结束位置以及行数转换成数组的下标, 然后将其之间的位全部填充为 1 即可
- 具体做法如下:
- 首先初始化长度为 length 的数组, 将其值全部设为 0, 代表空白屏幕
- 然后得到直线所在行的起点对应的数组下标 startIndex, 以及开始和结束位置对应的下标 s 和 e, 具体转换过程可以参考下面的代码和注释
- 对于该行的数字, 再分为以下三部分 (下面的[]表示闭区间, ()表示开区间):
[startIndex,s)
和(e, endIndex]
区间的数字: 仍然全部用 0 填充, 不需要做改变 (endIndex 代表该行终点下标, 因为这部分无需改变, 所以不用求出 endIndex)- 数字 s 和 e (s 可能等于 e): 对应的 x1~x2 之间的位用 1 填充
(s,e)
区间的数字: 全部用 1 填充, 即赋值为-1 (对应的 32 位全部为 1)
- 注意 python 需要额外处理 32 位整数最高位是 1 的问题:
- 当最终结果大于 32 位正数最大值 (即
0x7FFFFFFF
)时, python 会继续显示更大的正数, 而不像其他语言(例如 Java)那样显示负数 - 所以我们需要将其额外转成正常的负数表示方式, 这个可以利用
~(a ^ 0xFFFFFFFF)
实现, 即先对低 32 位的逐位取反, 更高位不变, 然后整体再取反, 从而将大于等于 32 位的位变成 1, 此时结果就是正常的 32 位负数了
- 当最终结果大于 32 位正数最大值 (即
复杂度
- 时间复杂度 O((x2-x1)/32): 只需要遍历(s,e)区间的数字将其全部位赋值为 1, 其他都是常数操作
- 空间复杂度 O(1): 只使用了几个变量 (结果数组不计算在内)
代码
Python 3
class Solution: def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]: # 初始化长度为 length 的数组, 将其值全部设为 0, 代表空白屏幕 res = [0] * length # w//32代表每一行有多少个数字, 乘以直线所在行数y, 即得到直线所在行的起点对应的数组下标 startIndex = y * (w // 32) # 通过x1和x2除以32得到偏移量, 再与直线所在行起点下标相加, 从而得到s和e s = startIndex + x1 // 32 e = startIndex + x2 // 32 for i in range(s + 1, e): # 将(s,e)区间的数字的全部位赋值为1 res[i] = -1 # posMx代表正数最大值, 如果超过这个值的话需要手动转成负数 posMx = 0x7FFFFFFF mx = 0xFFFFFFFF if s == e: # 如果s和e相等, 则变更的位数是当前这个数字[x1 % 32, x2 % 32]区间的位 # 注意右边是低位, 所以mask是1 << (31 - b), 也即第31位对应的是数字1, 下同 for b in range(x1 % 32, x2 % 32 + 1): mask = 1 << (31 - b) res[s] |= mask if res[s] > posMx: # 超出32位正数表示范围时, 需要额外转成32位负数表示, 下同 res[s] = ~(mx ^ res[s]) else: # 如果s和e相等, 则变更的位数是s的[x1 % 32, 31]区间以及e的[0, x2 % 32]的位 for b in range(x1 % 32, 32): mask = 1 << (31 - b) res[s] |= mask for b in range(x2 % 32 + 1): mask = 1 << (31 - b) res[e] |= mask if res[s] > posMx: res[s] = ~(mx ^ res[s]) if res[e] > posMx: res[e] = ~(mx ^ res[e]) return res
大家可以在下面这些地方找到我~
这篇关于程序员面试金典 - 面试题 05.08. 绘制直线的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么修改Kafka的JVM参数?-icode9专业技术文章分享
- 2024-12-23线下车企门店如何实现线上线下融合?
- 2024-12-23鸿蒙Next ArkTS编程规范总结
- 2024-12-23物流团队冬至高效运转,哪款办公软件可助力风险评估?
- 2024-12-23优化库存,提升效率:医药企业如何借助看板软件实现仓库智能化
- 2024-12-23项目管理零负担!轻量化看板工具如何助力团队协作
- 2024-12-23电商活动复盘,为何是团队成长的核心环节?
- 2024-12-23鸿蒙Next ArkTS高性能编程实战
- 2024-12-23数据驱动:电商复盘从基础到进阶!
- 2024-12-23从数据到客户:跨境电商如何通过销售跟踪工具提升营销精准度?