G家面经，已跪

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 ])，之前被转换了

nevets 发表于 2016-6-15 10:29
所以说是按照线段来更新，而不是直接行或者列。所谓线段就是一堵墙到另一堵墙，比如下面这个1维的例子，0 ...

感谢层主分享。。。题目意思是炸弹只能放在空（0）的位置，所以不需要减去自身为1的值吧？

blackrose 发表于 2016-6-14 06:46
Dp 解第一题，不知道对不对，测了点cases，没差。

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

neoxle 发表于 2016-6-15 13:39
感谢层主分享。。。题目意思是炸弹只能放在空（0）的位置，所以不需要减去自身为1的值吧？

啊是的，之前忽略了多谢提醒！

blackrose 发表于 2016-6-14 06:46
Dp 解第一题，不知道对不对，测了点cases，没差。

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

贴一个我的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;
    

复制代码

nevets 发表于 2016-6-15 10:29
所以说是按照线段来更新，而不是直接行或者列。所谓线段就是一堵墙到另一堵墙，比如下面这个1维的例子，0 ...

太感谢了  ！

nevets 发表于 2016-6-15 10:29
所以说是按照线段来更新，而不是直接行或者列。所谓线段就是一堵墙到另一堵墙，比如下面这个1维的例子，0 ...

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

July09 发表于 2016-6-14 11:21
第一题
int convertSortedString(String s) {
        int length = s.length();

One pass。妙