本文主要是介绍程序员面试金典---5.8 绘制直线（leetcode），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

• 题目：绘制直线
• 一、思路
• 二、解法
• • 1.单独处理头尾法

题目：绘制直线

绘制直线。有个单色屏幕存储在一个一维数组中，使得32个连续像素可以存放在一个 int 里。屏幕宽度为w，且w可被32整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点( x 1 x_1 x1​, y)到点( x 2 x_2 x2​, y)的水平线。
给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x 1 x_1 x1​（比特为单位）、直线结束位置 x 2 x_2 x2​（比特为单位）、直线所在行数 y。返回绘制过后的数组。（书上为8比特的字节数组，leetcode本题为32比特的int数组,但是解法是一样的）。

一、思路

1.蛮力法：用for循环迭代，从 x 1 x_1 x1​到 x 2 x_2 x2​，一路设定每个像素。但是这么做是在太没劲，效率也不高
2.单独处理头尾法：假如 x 1 x_1 x1​和 x 2 x_2 x2​距离非常远，可以把中间包含的完整元素都直接设置为0xFFFFFFFF，然后单独处理起点和终点部分的位。

二、解法

1.单独处理头尾法

vector<int> drawLine(int length, int w, int x1, int x2, int y){
	vector<int> screen(length, 0);
	int start_offset = x1 % 32;
	int first_full_byte = x1 / 32;
	if(start_offset != 0){
		first_full_byte++;
	}
	int end_offset = x2 % 32;
	int last_full_byte = x2 / 32;
	if(end_offset != 31){
		last_full_byte--;
	}
	// 把中间的像素置位1
	for(int b = first_full_byte; b<=last_full_byte; b++){
		screen[(w/32)*y + b] = 0xFFFFFFFF;
	}
	int start_mask = 0xFFFFFFFF >> start_offset;
	int end_mask = 0;
	// 算数右移32位 -1右移，符号位会补1 还为-1
	if(end_offset + 1 == 32){
		end_mask = 0xFFFFFFFF;
	}else{
		end_mask = ~(0xFFFFFFFF >> (end_offset+1));
	}
	if((x1 / 32) == (x2/32)){
		int mask = start_mask & end_mask;
		screen[(w/32)*y + (x1/32)] |= mask;
	}else{
		if(start_offset != 0){
			int byte_number = (w/32)*y + first_full_byte - 1;
			screen[byte_number] |= start_mask;
		}
		if(end_offset != 31){
			int byte_number = (w/32)*y + last_full_byte + 1;
			screen[byte_number] |= end_mask;
		}
	}
	return screen;
}

这篇关于程序员面试金典---5.8 绘制直线（leetcode）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！