6: String with Alternate 0 and 1

uuuouou

对这种第n个决策只和第n-1个决策相关的情况，很容易想到dp，这里令f[0]【i】表示让s[0~i]以0为结尾所需进行的删除操作，用f[1]【i】表示以1为结尾所需进行的删除操作，对s【i】分类讨论我们容易得出：
（1）s【i】=0，则f[0]【i】=min(f[0][i-1]+1, f[1][i-1])，且f[1]【i】=f[1][i-1]+1
（2）s【i】=1，则f[1]【i】=min(f[1][i-1]+1, f[0][i-1])，且f[0]【i】=f[0][i-1]+1
需要注意的是转移方程中的边界条件，如果s[0~i]都是0的话，则f[1]【i】就是Inf，如果s[0~i]都是1的话，则f[0][1]就是Inf，因为这两种情况下无论如何都不能让删除后的string以0或1结尾

1. #include <vector>
   
2. using std::vector;
   
3. 
   
4. class Solution {
   
5.         /*
   
6.                 f[0]【i】 represents the minimum deletes we need to make s[0~i] meet the requirements and ends with '0'
   
7.                 f[1]【i】 represents the minimum deletes we need to make s[0~i] meet the requirements and ends with '1'
   
8.         */
   
9.         vector<int> f[2];
   
10. public:
    
11.         int leastDeletion(string &s) {
    
12.                 int n = s.size();
    
13.                 if(n < 2) return 0;
    
14.                
    
15.                 //allocate memory
    
16.                 f[0].resize(n);
    
17.                 f[1].resize(n);
    
18.                 //initialize
    
19.                 if(s[0] == '0'){
    
20.                         f[0][0] = 0;
    
21.                         f[1][0] = n;
    
22.                 }
    
23.                 else{
    
24.                         f[0][0] = n;
    
25.                         f[1][0] = 0;
    
26.                 }
    
27.                 //dp
    
28.                 for(int i = 1; i < n; ++i){
    
29.                         if(s【i】 == '0'){
    
30.                                 f[0]【i】 = min(i, min(f[0][i-1] + 1, f[1][i-1]));
    
31.                                 f[1]【i】 = min(n, f[1][i-1] + 1);
    
32.                         }
    
33.                         else{
    
34.                                 f[0]【i】 = min(n, f[0][i-1] + 1);
    
35.                                 f[1]【i】 = min(i, min(f[0][i-1], f[1][i-1] + 1));
    
36.                         }
    
37.                 }
    
38.                 return min(f[0][n-1], f[1][n-1]);
    
39.         }
    
40. };

复制代码

yimingzi

其实没必要用DP..就是一道简单的扫描..

1. class Solution {
   
2.         public int leastDeletion(String s) {
   
3.                 int count = 0;
   
4.                 for(int i=0;i<s.length()-1;i++){
   
5.                    if(s.charAt(i)==s.charAt(i+1)){
   
6.                       int index = i+1;
   
7.                       while(index<s.length()&&s.charAt(i)==s.charAt(index)){
   
8.                               index++;
   
9.                               count++;
   
10.                       }
    
11.                       i = index-1;
    
12.                    }
    
13.                 }
    
14.                 return count;
    
15.         }
    
16. }

复制代码