有一个单色屏幕储存在一维数组中,给定表示屏幕的数组screen(数组中元素二进制表达的每一位分别对应连续的8个像素,二进制位数的从低到高对应像素的从左到右),用函数实现将第x到第y个像素涂上颜色(像素标号从零开始),返回涂色后的新的屏幕数组。请尝试尽量使用最快的办法并保证输入数据合法性。
测试样例:
[0,0,0,0,0,0],0,47
返回:[255,255,255,255,255,255]
有一个单色屏幕储存在一维数组中,给定表示屏幕的数组screen(数组中元素二进制表达的每一位分别对应连续的8个像素,二进制位数的从低到高对应像素的从左到右),用函数实现将第x到第y个像素涂上颜色(像素标号从零开始),返回涂色后的新的屏幕数组。请尝试尽量使用最快的办法并保证输入数据合法性。
[0,0,0,0,0,0],0,47
返回:[255,255,255,255,255,255]
# -*- coding:utf-8 -*- class Render: def renderPixel(self, screen, x, y): px = ('0' * x + '1' * (y - x + 1)).ljust(8 * len(screen), '0') return [(int(px[i:i+8][::-1], 2) | screen[i//8]) for i in range(0, len(px), 8)]
# -*- coding:utf-8 -*- class Render: def renderPixel(self, screen, x, y): for i in range(x, y + 1): # 找出处于元素的哪一位 (从低到高) k = i % 8 # 找出哪一个元素 t = i / 8 screen[t] = screen[t] | (1 << k) return screen
public int[] renderPixel(int[] screen, int x, int y) { int start = x / 8, end = y / 8; int f1 = x % 8, f2 = y % 8 + 1;//f1表示起始位0的个数,f2表示终止位1的个数 if (end - start > 0) { for (int i = start + 1; i < end; i++) { screen[i] = 0xff; } screen[start] |= 0xff & ~((1<<f1)-1); screen[end] |= (1<<f2) - 1; } else { screen[start] |= 0xff & ~((1<<f1)-1) & ((1<<f2)-1); } return screen; }
class Render { public: vector<int> renderPixel(vector<int> screen, int x, int y) { // write code here for(int i = x / 8 + 1; i < y / 8 ; i ++ ) screen[i] = 255; for(int i = x % 8; i < 8; i++) screen[x / 8] = screen[x / 8] | (1 << i); for(int i = y % 8; y / 8 != x / 8 && i >= 0; i--) screen[y / 8] = screen[y / 8] | (1 << i); return screen; } };
思路:首先解释一下题目的意思,我刚开始没搞懂,怀疑自己是不是中国人了hh,题目给的全是0的 二维数组,x和y代表需要让填充颜色的像素点,在x-y这个范围的像素点变为1(即数组元素的对应二进制位 变为1),这个就可以用位运算符,|来进行操作了,对吧,t是行数,k是在行中的位置。 class Render { public: vector<int> renderPixel(vector<int> screen, int x, int y) { for(int i = x ; i <= y ; i ++) { int k = i % 8 ; int t = i / 8 ; screen[t] = screen[t] | (1<< k); } return screen ; } };
//题目要求高效,中间连续8位的可以整个设置,而不是一个bit一个bit的设置,提高了效率 class Render { public: vector<int> renderPixel(vector<int> screen, int x, int y) { int size = screen.size(); vector<int> ans; if(x<0 || y/8 > size || x>y)//异常检验 return screen; int startOffset = x%8;//初始offset int firstFullByte = x/8 + 1;//第一个完整位置 int endOffset = y%8;//末端offset int lastFullByte = y/8 - 1;//最后一个完整位置 for(int i = firstFullByte; i <= lastFullByte; ++i){ screen[i] = 255;//中间部分是完整8位的一次性设置 } int startMask = (255<<startOffset) & 255;//头掩码 int endMask = 255>>(7-endOffset);//尾掩码,注意是从低位到高位设置 //最后是第一个节点和最后一个节点的设置 if( x/8 == y/8){//处于同一个字节内的特殊情况处理 int mask = startMask & endMask; screen[x/8] |= mask; } else{ screen[x/8] |= startMask; screen[y/8] |= endMask; } return screen; } };
/*这题很恶心,screen中存放的数字都是以8位二进制数表示 x为开始涂色的起点,y为终点 先定好下标,startIndex=x/8和endIndex = y/8找到screen中位置 然后看该数的那几位需要涂色。 1. endIndex - startIndex == 0且x <= y,将startIndex对应 下标下的数的第x到第y位涂色 2. endIndex - startIndex > 0且x <= y,将startIndex对应 下标的数从x到最高位进行涂色; 将endIndex对应下标的数从最低位到y进行涂色,startIndex 到endIndex之间的数全部为涂色,都为255 */ public int[] renderPixel(int[] screen, int x, int y) { // write code here int[] res = new int[screen.length]; int len = screen.length; int startIndex = x/8; int endIndex = y/8; for(int i = 0; i < screen.length; i++){ if(i < startIndex){ res[i] = screen[i]; }else if( i >= startIndex && i <= endIndex){ if(endIndex - startIndex > 0){//覆盖多于一个像素 if(i == startIndex){ res[i] = screen[i] | getNumStart(x%8); }else if(i == endIndex){ res[i] = screen[i] | getNumEnd(y%8); }else{ res[i] = 255; } }else{//覆盖少于一个像素 res[i] = screen[i] | (getNumStart(x%8)&(getNumEnd(y%8))); } }else if(i > endIndex && i < len){ res[i] = screen[i]; } } return res; } public int reverseBit(int num) { // TODO Auto-generated method stub int round = 7; int res = 0; while(round >= 0){ res |= (((num >> round) & 1)==0) ? 0: (1 << (7-round)); round--; } return res; } public int getNumStart(int bit) { // TODO Auto-generated method stub return reverseBit((int) (Math.pow(2, 8-bit)-1)); } public int getNumEnd(int bit){ return (int) (Math.pow(2, bit+1)-1); }
public class Render { public int[] renderPixel(int[] screen, int x, int y) { int start = x / 8, startPos = x % 8, end = y / 8, endPos = y % 8; screen[start] = (0xFF << startPos) & 0xFF | screen[start]; for (int i = start + 1; i < end; ++i) { screen[i] = 255; } screen[end] = (~(0xFF << (endPos + 1))) & (start == end ? screen[start] : 0xFF) | screen[end]; return screen; } }
//还是这种方法简单明了,Java版本
import java.util.*; public class Render {
public int[] renderPixel(int[] screen, int x, int y) {
for(int i = x; i <= y; i++){
int n = i / 8;
int nBit = i % 8;
screen[n] |= (1 << nBit);
}
return screen;
}
}
public int[] renderPixel(int[] screen, int x, int y) {
int index = 0;
int position = 0;
for (int i = x; i <= y; i++) {
index = i/8;//计算索引
position =i % 8;//计算位置
screen[index]|=(1<<position);//或操作,因为该位置如果是0则变成1,如果是1则仍为1
}
return screen;
}
public int[] renderPixel(int[] screen, int x, int y) {
// write code here
for (int i = x; i <= y; i++) {
int num = i / 8;
int bit = i % 8;
screen[num] |= (1 << bit);
}
return screen;
}
vector<int> renderPixel(vector<int> screen, int x, int y) { int start = x/8; int end = y/8; int i; if(start<end){ for(i=x%8;i<8;i++) screen[start] |= (0x1<<i); for(i=start+1;i<end;i++) screen[i] |= 0xff; for(i=0;i<=y%8;i++) screen[end] |= (0x1<<i); }else{ for(i=x%8;i<=y%8;i++) screen[start] |= (0x1<<i); } return screen; }
class Render { public: vector<int> renderPixel(vector<int> screen, int x, int y) { // 低8位有效 constexpr unsigned int BitWidth = 8U; constexpr unsigned int BitMask = ~(UINT_MAX << BitWidth); const size_t size = screen.size(); // 题目说了检查输入合法性,没说不合法怎么办 // 于是默认什么也不做 if ( size < 1U || x < 0 || x > size * BitWidth || y < 0 || y > size * BitWidth ) { return screen; } // 操作原生数组,也许比通过vector快一些? // 不知道,但是原生数组的速度绝不会慢 int* const data = screen.data(); const unsigned int l = x / BitWidth; const unsigned int r = y / BitWidth; // 左右边界之后单独处理,中间部分先直接填满 for (unsigned int i = l + 1; i < r; ++i) { data[i] = BitMask; } // 最后额外的&BitMask,是要把更高位的数值抹掉, // 因为int通常不止8位,但这题让int屈尊表示只有8位的数 const int mask_left = static_cast<int>( (BitMask << ((x % BitWidth))) & BitMask ); const int mask_right = static_cast<int>( (BitMask >> (BitWidth - (y % BitWidth) - 1)) & BitMask ); if (l == r) { data[l] |= mask_left & mask_right; } else { data[l] |= mask_left; data[r] |= mask_right; } return screen; } };
class Render { public: vector<int> renderPixel(vector<int> screen, int x, int y) { int length=screen.size(); vector<int>res; for(int i=0;i<length;++i) { int num=0; for(int j=0;j<8;++j) { if(i*8+j>=x&&i*8+j<=y) { num+=pow(2,j); } } res.push_back(screen[i]|num); } return res; } }; //两层循环,第一层循环遍历screen中的每一个数,第二层循环遍历8位像素值,在第二层循环中i*8+j判的像素断当前的j是位于从最左开始第几位,并判断j位是否介于x和y之间,即是否被设置成1,代表每8位为一组,每组中涂色所代表的的数字,把num和screen[i]做位或运算求出来的结果即为涂改后的数字
//[0,0,0,0,0,0],1,45 vector<int> renderPixel(vector<int> screen, int x, int y) { const int max_val = 255; // write code here if(y<x) return screen; int n = screen.size(); int x_index = x/8,x_bit = x%8;//x开始涂色的元素位置,开始涂色的位号 if(x_index>=n) return screen; int y_index = y/8,y_bit = y%8;//终止涂色的元素位置 终止的位号 //从screen中x_index的x_bit位开始涂色,直到y_index的y_bit //为了加速涂色,将满8bit的一次处理,只有x_index或y_index的位有可能要单独处理,(x_index,y_index)一起处理 for(auto i=x_index+1;i<n and i<y_index;i++){ screen[i]=255; } screen[x_index] |= max_val^((1<<x_bit)-1); if(y_index>=n&nbs***bsp;x_index==y_index) return screen; if(y_bit==7) screen[y_index] = 255; else screen[y_index] |= (1<<(y_bit+1))-1; return screen; }
// 且从左至右的像素分别对应元素的二进制的从低到高位 // 最开始被这个误导了。 class Render { public: vector<int> renderPixel(vector<int> screen, int x, int y) { // write code here int numberIndex; int siteIndex; for (int i = x; i <= y; i++) { numberIndex = i / 8; siteIndex = i % 8; screen[numberIndex] = screen[numberIndex] | (1 << siteIndex); } return screen; } };