找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 778|回复: 1
收起左侧

[资源分享] 6: String with Alternate 0 and 1

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 11:29 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

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


0

主题

0

精华

12

积分

新米人

Rank: 1

积分
12
发表于 10-13-2015 05:50 PM | 显示全部楼层
其实没必要用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. }
复制代码


回复 支持 1 反对 0

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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