一亩三分地论坛

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

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

[其他] 题目稍微变一下就懵B,怎么提高?

[复制链接] |试试Instant~ |关注本帖
TonyLic 发表于 2016-7-3 14:44:52 | 显示全部楼层 |阅读模式

2016(7-9月)-[13]CS硕士+3个月-1年 - 网上海投| 码农类全职@在职跳槽

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

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

x
工作一年LC一直在刷,刷了有三五遍了吧
最近准备跳槽拿了几个面试,包括Google Twosigma这些Bar挺高的
于是今天早上做了第一个小公司的OA练手,5个题90分钟,前面还挺简单,最后一题的时候还剩差不多一个小时
求一个01数组翻转一个区间让1最多,其实就是一个Kadane's Algorithm的变种吧,LC上那道求Max subarray sum的题目刷了会有五六遍了,但一碰见变形题,还是联想不到
最后还是没做出来,包括其他时候看面经,碰见一些变种题,在放松的情况下都难一下想到解法,要面试碰到更完了,有点感觉信心受挫啊
面试都还没约时间,求问短时间应该怎么提高比较好?-google 1point3acres
dajiang 发表于 2016-7-4 21:31:54 | 显示全部楼层
0用1 代替,1用-1代替,最大子段和。
回复 支持 1 反对 0

使用道具 举报

iamstone 发表于 2016-7-3 14:54:19 | 显示全部楼层
很多时候都是在背答案吧,没有按照很好的逻辑想想,可以发给我email michard.su2015@gmail.com
回复 支持 反对

使用道具 举报

 楼主| TonyLic 发表于 2016-7-3 15:03:03 | 显示全部楼层
iamstone 发表于 2016-7-3 14:54
很多时候都是在背答案吧,没有按照很好的逻辑想想,可以发给我email

有可能,刷到后面很多题是在背答案
但我尽力在解题之前注释写好完整的思路再动手了。。。
需要发什么兄弟?
回复 支持 反对

使用道具 举报

iamstone 发表于 2016-7-3 15:30:11 | 显示全部楼层
TonyLic 发表于 2016-7-3 15:03
有可能,刷到后面很多题是在背答案
但我尽力在解题之前注释写好完整的思路再动手了。。。
需要发什么兄 ...

写的code 我看下
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-3 20:45:01 | 显示全部楼层
我觉得吧...
cs的问题都可以被"规约"到一类问题或者几类问题的交际. 然后学会解这几类就好了
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-3 20:47:12 | 显示全部楼层
翻转是啥? 0->1 1->0?
回复 支持 反对

使用道具 举报

bcc 发表于 2016-7-3 21:07:54 | 显示全部楼层
求问这个题该怎么做? 是求连续1最长的区间index么? sliding window?
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-7-4 00:47:49 | 显示全部楼层
bcc 发表于 2016-7-3 21:07
求问这个题该怎么做? 是求连续1最长的区间index么? sliding window?

感觉用一个counter,一个初始位置beg,一个结束位置end,再加上一个最大长度maxLen。遇0就加1,遇1就减1

补充内容 (2016-7-4 00:48):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
没打完不小心点发送了。。。。
然后每次统计之后就更新最大长度和end位置。一旦counter<=0,就可以重置counter和beg,继续计算了。因为0和-1不能对后续有任何contribution

补充内容 (2016-7-4 00:51):
初始位置和结束位置是为了返回整个区间,当然这里只是返回其中一个最长区间,如果只返回1的个数就不用了。

补充内容 (2016-7-4 00:55):
哦对,如果还要要求结果最长/最短,应该就可以再counter>=0这里的等号做文章了,还有在判断当前最多1的个数和全局最多1的个数那里,同样是对等号做一些判断。
回复 支持 反对

使用道具 举报

 楼主| TonyLic 发表于 2016-7-4 01:27:18 | 显示全部楼层
bcc 发表于 2016-7-3 21:07
求问这个题该怎么做? 是求连续1最长的区间index么? sliding window?

是求哪个区间0-1的difference最大,这样在这个区间翻转01就能得到整体最多的1,下面那兄弟的解法没错
回复 支持 反对

使用道具 举报

 楼主| TonyLic 发表于 2016-7-4 01:29:32 | 显示全部楼层
readman 发表于 2016-7-3 20:45
我觉得吧...
cs的问题都可以被"规约"到一类问题或者几类问题的交际. 然后学会解这几类就好了
. from: 1point3acres.com/bbs
有这样类似归纳的资料么
我自己也有一些思考 比如最短路径最小值之类考虑BFS,求什么个数多少用DP,tree基本考虑recursion,但总感觉这种归纳还是不足以应付千变万化的题目啊
回复 支持 反对

使用道具 举报

 楼主| TonyLic 发表于 2016-7-4 01:35:44 | 显示全部楼层

看哪个?我说的那个题目?
回复 支持 反对

使用道具 举报

phantom 发表于 2016-7-4 10:59:24 | 显示全部楼层
就是两个指针维持一个区间吧?。。只要区间sum值还是正的。。就接着增大区间。。然后记录最大值就行了
回复 支持 反对

使用道具 举报

cherishsunyi 发表于 2016-7-4 22:08:04 | 显示全部楼层
同问,我也是LC刷了几遍,但是题目稍微变形就不知道怎么做了
回复 支持 反对

使用道具 举报

caoyi 发表于 2016-7-5 00:52:05 | 显示全部楼层
这道题的意思是在求:翻转某一个子段使得连续的1最多么? 要求的是翻转后的max subarray sum 还是返回翻转后连续1的起止index 还是返回要翻转的那个区间的index?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 08:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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