专栏首页Michael阿明学习之路程序员面试金典 - 面试题 05.08. 绘制直线(位运算)

程序员面试金典 - 面试题 05.08. 绘制直线(位运算)

1. 题目

绘制直线。有个单色屏幕存储在一个一维数组中,使得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]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/draw-line-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 一行有几个int,n = w/32 个
  • 从 y 行开始,那么起始下标 idx = y * n
class Solution {
public:
    vector<int> drawLine(int length, int w, int x1, int x2, int y) {
        int n = w>>5, idx = y*n;
        vector<int> ans(length,0);
        while(x1 > 31)//不在当前int内
        {
        	idx++;//下一个int
        	x1 -= 32;//区间挪动
        	x2 -= 32;
        }
        int l = x1, r;//找到了x1所在int
        for( ; x2>=0; l=0,x2-=32)
        {
        	r = min(x2,31);//右端点
        	for(int i = l; i <= r; i++)
        	{
        		ans[idx] |= 1<<(31-i);//把1挪到各个位置上
        	}
        	idx++;
        }
        return ans;
    }
};

4 ms 7.4 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • LeetCode 347. 前 K 个高频元素(哈希/优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/top-k-frequent-elements 著作...

    Michael阿明
  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)

    我们可以把图行列拆开,同时对于行/列拆成很多个联通块,然后考虑每个点所在的行联通块/列联通块的贡献。

    attack
  • 13:大整数的因子

    13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9,现给出长度最大为30位...

    attack
  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长

扫码关注云+社区

领取腾讯云代金券