G家面经，已跪

第一题可以先扫描一遍array，找到所有b的位置。然后循环所有的这些位置，看如果这个位置的b是排序后的数列的第一个b的话要进行多少操作，这一步可以O(1)得到，一个循环下来找到最小的步数。算法应该是O(n)

Dp 解第一题，不知道对不对，测了点cases，没差。

1. int miniChange(string str) {
   
2.   int n = str.size();
   
3.   vector<int> front(n, 0);
   
4.   for(int i = 1; i < n; ++i) {
   
5.     if(str[i] >= str[i-1]) front[i] = front[i-1];
   
6.     else {
   
7.       front[i] = front[i-1] + 1;
   
8.     }
   
9.   }
   
10. 
    
11.   vector<int> backward(n, 0);
    
12.   for(int i = n - 1; i > 0; --i) {
    
13.     if(str[i-1] <= str[i]) backward[i-1] = backward[i];
    
14.     else {
    
15.       backward[i-1] = backward[i] + 1;
    
16.     }
    
17.   }
    
18. 
    
19.   int minChange = str.size();
    
20.   for(int i = 0; i < n; ++i) {
    
21.     minChange = min(minChange, front[i] + backward[i]);
    
22.   }
    
23.   return minChange;
    
24. }
    
25. 
    
26. 
    
27. int main(void) {
    
28.   cout << miniChange("aaab") << endl;
    
29.   cout << miniChange("baab") << endl;
    
30.   cout << miniChange("abab") << endl;
    
31.   cout << miniChange("bbba") << endl;
    
32.   cout << miniChange("baba") << endl;
    
33. }

复制代码

第四题就是 dp

edcent 发表于 2016-6-14 03:05
第一题有点点像sort colors 就是不确定sort colors那种方法是不是最少操作

应该是的，类似于贪心吧，假设两端需要交换的b和a不交换，中间必然有另外一些ab需要去替换两端的值，所以必须要交换，不知道对不对哈

lz好运气，亚麻也不错

第一题
int convertSortedString(String s) {
        int length = s.length();
        if (length <= 1)
            return length;
        //I assume we want aaa...bbb, ret can be all a or all b
//        let A[n] ends with a, B[n] ends with b
        //We can improve it without array....
        int [] a = new int [1+length];
        int [] b = new int [1+length];
        for (int i = 1; i <= length; ++i) {
            if (s.charAt(i-1) == 'a') {
                a[i] = a[i-1];
                b[i] = 1 + Math.min(a[i-1], b[i-1]);
            } else {
                a[i] = 1 + a[i-1];
                b[i] = Math.min(a[i-1], b[i-1]);
            }
        }

        return Math.min(a[length], b[length]);
    }

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

厉害~~
感觉对头

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

...正准备贴代码, 一看几乎一样, 肯定是对啦, 从前往后, 从后往前各扫一遍, 看加和

dong882205 发表于 2016-6-14 12:51
...正准备贴代码, 一看几乎一样, 肯定是对啦, 从前往后, 从后往前各扫一遍, 看加和

第一题其实就1种情况：把一个字符串转换成若干个a之后若干个b，所以用一个数组B维护从0到i中b的个数，一个数组A维护从i到N－1中a的个数，然后循环一遍取min(B[i] + A[i + 1])

第四题其实只要知道每一个cell所在的横纵segment中有几个人就行，先预处理一遍然后NM求最大。