楼主: yanyan2060
跳转到指定楼层
上一主题 下一主题
收起左侧

G家面经,已跪

🔗
nevets 2016-6-15 10:29:26 | 只看该作者
全局:
woshiee123 发表于 2016-6-15 08:23
那有墙的地方怎么处理呢 ?

所以说是按照线段来更新,而不是直接行或者列。所谓线段就是一堵墙到另一堵墙,比如下面这个1维的例子,0是可走,1是有人,#是墙:
011#0#111#
这个例子就有3个横线段,可以在一个新矩阵记录为:
222-10-1333-1
纵线段同理。来看一个2D的例子:
011#1#111#
01#0101##1
001#0#000#
先处理横线段,得到:
2  2  2  -1  1 -1  3  3  3  -1
1  1 -1   2  2  2  2 -1 -1   1
1  1  1  -1  0 -1  0  0  0  -1
再处理纵线段,得到:
0  2  1  -1  2  -1  2  1  1  -1
0  2 -1   0  2   0  2 -1 -1   1
0  2  1  -1  2  -1  2  0  0  -1
最后横纵相加取最大,但是要注意减去本身,因为如果本身为1的话,横纵都会被算一遍:
ans = max(horizontal[i][j] + vertical[i][j] - map[i][j])

补充内容 (2016-6-15 10:30):
ans = max(horizontal[ i ][ j ] + vertical[ i ][ j ] - map[ i ][ j ]),之前被转换了
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
neoxle 2016-6-15 13:39:31 | 只看该作者
全局:
nevets 发表于 2016-6-15 10:29
所以说是按照线段来更新,而不是直接行或者列。所谓线段就是一堵墙到另一堵墙,比如下面这个1维的例子,0 ...

感谢层主分享。。。题目意思是炸弹只能放在空(0)的位置,所以不需要减去自身为1的值吧?
回复

使用道具 举报

🔗
wllnju 2016-6-15 14:28:55 | 只看该作者
全局:
blackrose 发表于 2016-6-14 06:46
Dp 解第一题,不知道对不对,测了点cases,没差。

如果 string str = "bbbbaaaa", 最小操作应该是4,但你的程序输出的结果是1.
不知道我的理解对不对?
回复

使用道具 举报

🔗
nevets 2016-6-15 14:47:28 | 只看该作者
全局:
neoxle 发表于 2016-6-15 13:39
感谢层主分享。。。题目意思是炸弹只能放在空(0)的位置,所以不需要减去自身为1的值吧?

啊是的,之前忽略了多谢提醒!
回复

使用道具 举报

🔗
nevets 2016-6-15 14:54:26 | 只看该作者
全局:
blackrose 发表于 2016-6-14 06:46
Dp 解第一题,不知道对不对,测了点cases,没差。

你的条件似乎是有问题的,数组计算的应该是a和b的个数,但是str[ i ] >= str[ i - 1]计算的不是这个。
回复

使用道具 举报

🔗
wllnju 2016-6-15 15:23:49 | 只看该作者
全局:
贴一个我的code:
  1. int minichange (string str) {
  2. int N = str.size();
  3. if (N <= 1) return 0;
  4. vector<int> B(N+1, 0);// B[i+1] counts # of 'b' for string from position 0 to i
  5. vector<int> A(N+1, 0);// A[i] counts # of 'a' for string from position N-1 to i
  6. for (int i = 1; i < N+1; i++) {
  7. if(str[i-1]=='b') B[i]=B[i-1]+1;
  8. else B[i]=B[i-1];
  9. }
  10. for (int i = N; i>0; i--) {
  11. if(str[i-1]=='a') A[i-1] = A[i]+1;
  12. else A[i-1]=A[i];
  13. }
  14. int result = N;
  15. for(int i =0; i<N; i++) {
  16. if(str[i]=='b') result = min(result, B[i]+A[i]); // if this 'b' is the first 'b' in the sorted string, then we need replace all of the 'b' before position i, and also replace all of the 'a' after position i
  17. }
  18. return result;
复制代码
回复

使用道具 举报

🔗
woshiee123 2016-6-19 21:18:58 | 只看该作者
全局:
nevets 发表于 2016-6-15 10:29
所以说是按照线段来更新,而不是直接行或者列。所谓线段就是一堵墙到另一堵墙,比如下面这个1维的例子,0 ...

太感谢了  !
回复

使用道具 举报

🔗
woshiee123 2016-6-19 21:27:57 | 只看该作者
全局:
nevets 发表于 2016-6-15 10:29
所以说是按照线段来更新,而不是直接行或者列。所谓线段就是一堵墙到另一堵墙,比如下面这个1维的例子,0 ...

有没有可能horizontal[ i ][ j ] + vertical[ i ][ j ]  最大  但是此时 i行 j列 都是1  并没有0 呢  也就是没有位置放炸弹呢 ?  谢谢
回复

使用道具 举报

🔗
zjuzqh 2016-6-19 21:36:26 | 只看该作者
全局:
July09 发表于 2016-6-14 11:21
第一题
int convertSortedString(String s) {
        int length = s.length();

One pass。妙
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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