一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 858|回复: 8
收起左侧

[CareerCup] 【第三轮】7.24-7.31 CareerCup 5.8

[复制链接] |试试Instant~ |关注本帖
林微熙 发表于 2014-7-25 06:36:27 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
5.8 A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte. The screen has width w, where w is divisible by 8 (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 drawHorizontalLine(byte[] screen, int width, intxl, intx2, inty) which draws a horizontal line from (x 1, y) to (x2, y).
回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】



Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


renli3000 发表于 2014-7-27 03:16:00 | 显示全部楼层
【解题思路】最笨的方法,分情况讨论,题不难容但易出错
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/Noahsark/475ced1f7807f07c6f2e
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-27 21:38:54 | 显示全部楼层
【解题思路】
set the middle blocks as 0xFF
treat the first block and last block differently because only set parts of it as 1


【时间复杂度】
O(x2 - x1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/aace24b9511a40db764f
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-7-28 09:26:48 | 显示全部楼层
【解题思路】
Find which row x1, x2 belongs to =>
if x1, x2 in same byte, set bits between x1 and x2 to 1;
if x1, x2 in different byte, set the byte of x1, x2, then set all bytes between x1 and x2 to 1

PS: the byte type has range from -128(10000000) ~ 127(01111111), in order to fit the requirement for the problem, we need use int[] rather than byte[]

【时间复杂度】
O(width)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/c5606ab2c161c69f0f37

---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
Wrote a function to print the screen
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-30 05:43:26 | 显示全部楼层
【解题思路】
draw a rough line first, then clear the leading pixels and fill in the tailing pixels
【时间复杂度】
O(W)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/cd8fccd3bc997b159ee0
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-30 06:36:29 | 显示全部楼层
【解题思路】
same method as in the book. find the bytes and use mask to change their values;
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/jyhjuzi/9588ff61cd446a9761a3
回复 支持 反对

使用道具 举报

 楼主| 林微熙 发表于 2014-8-3 11:20:54 | 显示全部楼层
【解题思路】书
【时间复杂度】o(n)
【空间复杂度】o(1)
【gist link】https://gist.github.com/hilda8519/3035c75c8500c22dccf5
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-8-6 01:17:11 | 显示全部楼层
【解题思路】
1. Find the position of x1,y; x2,y in the screen, then set the bits between them as 1
2. Set the bytes between x1,x2 as 0xFF, then set the bits after x1 as 1, the bits before x2 but not in a whole bytes as 1
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/bitcpf/5a7b7b9f08f0d47b1b8d
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-8-7 09:29:00 | 显示全部楼层
【解题思路】
find the index for x1 and x2, if they are the same, just & two mask, if not, or the mask1 with first index and or the mask2 with the second index, and set all 1s for between the two indices.
【时间复杂度】
O(W)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/da3752677be59a63da20
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表