我需要构建一个算法(不一定有效),给定一个字符串找到并打印两个相同的子序列(通过打印,我的意思是颜色).此外,这两个子序列的索引集合的联合必须是一组连续的自然数(整数的整数).

在数学中,我正在寻找的东西被称为“紧身双胞胎”,如果它有帮助的话. (例如,参见paper (PDF) here.)

我举几个例子:

1)考虑字符串231213231

它有两个子序列,我正在寻找“123”的形式.要更好地查看此图片:

第一个子序列标有下划线,第二个子序列标有上划线.如你所见,他们拥有我需要的所有属性.

2)考虑字符串12341234

3)考虑字符串12132344.

现在它变得更加复杂:

4)考虑字符串:13412342

它也不是那么容易:

我认为这些例子很好地解释了我的意思.

我一直在思考一个可以做到这一点但却没有成功的算法.

为了着色,我想使用这段代码:

using namespace std;
HANDLE  hConsole;
        hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole,k);

其中k是颜色.

任何帮助,甚至提示,都将受到高度赞赏.

解决方法

这是一个简单的递归,测试紧身双胞胎.当存在重复时,它会拆分决策树,以防副本仍然是第一个双胞胎的一部分.你必须在偶数长度的每个子串上运行它.对较长子串的其他优化可能包括对char计数进行散列测试,以及匹配候选双胞胎的非重复部分(仅在整个子字符串中出现两次的字符).

功能说明:

首先,创建一个散列,每个字符作为键,索引以值的形式出现.然后我们遍历哈希:如果字符计数是奇数,则该函数返回false;并且计数大于2的字符的索引被添加到重复列表中 – 其中一半字符属于一个双胞胎,但我们不知道哪个.

递归的基本规则是仅在字符串中稍后找到匹配时增加i,同时保持所选匹配(js)的记录,我必须跳过该记录而不查找匹配.这是有效的,因为如果我们找到n / 2个匹配,按顺序,到j到达结尾时,这基本上只是另一种说法是字符串由紧孪生组成的方式.

JavaScript代码:

function isTightTwins(s){
  var n = s.length,char_idxs = {};

  for (var i=0; i<n; i++){
    if (char_idxs[s[i]] == undefined){
      char_idxs[s[i]] = [i];
    } else {
      char_idxs[s[i]].push(i);
    }
  }

  var duplicates = new Set();

  for (var i in char_idxs){

    // character with odd count
    if (char_idxs[i].length & 1){
      return false;
    }

    if (char_idxs[i].length > 2){
      for (let j of char_idxs[i]){
        duplicates.add(j);
      }      
    }
  }

  function f(i,j,js){

    // base case positive
    if (js.size == n/2 && j == n){
      return true;
    }

    // base case negative
    if (j > n || (n - j < n/2 - js.size)){
      return false;
    }

    // i is not less than j
    if (i >= j) {
      return f(i,j + 1,js);
    }

    // this i is in the list of js
    if (js.has(i)){
      return f(i + 1,js);

    // yet to find twin,no match
    } else if (s[i] != s[j]){
      return f(i,js);

    } else { 

      // maybe it's a twin and maybe it's a duplicate
      if (duplicates.has(j)) {
        var _js = new Set(js);
        _js.add(j);
        return f(i,js) | f(i + 1,_js);          

      // it's a twin
      } else {
        js.add(j);
        return f(i + 1,js);
      }
    }
  }

  return f(0,1,new Set());
}

console.log(isTightTwins("1213213515")); //  true
console.log(isTightTwins("11222332")); // false

给定一个字符串,找到两个具有连续索引C的相同子序列的更多相关文章

  1. html5 拖拽及用 js 实现拖拽功能的示例代码

    这篇文章主要介绍了html5 拖拽及用 js 实现拖拽,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下

  2. Html5 canvas实现粒子时钟的示例代码

    这篇文章主要介绍了Html5 canvas实现粒子时钟的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

  3. amaze ui 的使用详细教程

    这篇文章主要介绍了amaze ui 的使用详细教程,本文通过多种方法给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下

  4. HTML5适合的情人节礼物有纪念日期功能

    这篇文章主要介绍了HTML5适合的情人节礼物有纪念日期功能,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下

  5. 如何在iOS中检测文本(字符串)语言?

    例如,给定以下字符串:我想检测每个声明的字符串中使用的语言.让我们假设已实现函数的签名是:如果没有检测到语言,则返回可选字符串.因此,适当的结果将是:有一个简单的方法来实现它吗?

  6. ios – 如何在swift3中增加String.Index?

    在swift2.3中运算符用于string.index增加例如.一世我改为swift3代码发生了“一元运算符”不能应用于’@valueString.Index’类型的操作数(又名’@lvalueString.CharacterView.Index’)“在swift3中我改写了例如.i=1但是这段代码无法解决.请帮我.解决方法String.Index是String.CharacterView.Ind

  7. ios – CoreData有序关系 – 使用NSFetchRequest批量取消

    或者,是否存在批量不支持的API,它不是私有的?解决方法目前我有一个解决方案,但不是一个干净的解决方案:我希望按照有序关系中的20个小组进行批量修改.所以,每次我索引一个索引,它的索引除以20,我为接下来的20使用新的NSFetchRequest,并通过调用公共字段名称来解除它们.

  8. 在Xcode4中,你可以更改用于显示隐形字符的字符吗?

    我更喜欢VisualStudio显示隐形的方式……

  9. ios – 应用程序商店描述特殊字符

    是不是可以在AppStore描述中使用像星星这样的特殊字符了?我得到这个错误:描述不得包含标记语言.说明不得包含以下字符:★提前致谢:)解决方法仍然允许一些unicode字符.以下字符已经过测试并仍然有效:◆√至于现在他们工作正常,但苹果可以随时再次改变条件.

  10. ios – 将数组中的字符转换为整数

    即使我搜索了文档,我似乎无法弄清楚如何做到这一点.我试图弄清楚如何将数组中索引处的字符转换为整数.例如,假设我有一个名为“容器”的字符数组,我无法弄清楚该怎么做:谢谢您的帮助!解决方法Swift并不容易在原始和类型表示之间进行转换.这是一个在此期间应该有所帮助的扩展:这使您可以非常接近您想要的:对于遇到此问题的任何工程师,请参阅rdar://17494834

随机推荐

  1. 从C到C#的zlib(如何将byte []转换为流并将流转换为byte [])

    我的任务是使用zlib解压缩数据包(已接收),然后使用算法从数据中生成图片好消息是我在C中有代码,但任务是在C#中完成C我正在尝试使用zlib.NET,但所有演示都有该代码进行解压缩(C#)我的问题:我不想在解压缩后保存文件,因为我必须使用C代码中显示的算法.如何将byte[]数组转换为类似于C#zlib代码中的流来解压缩数据然后如何将流转换回字节数组?

  2. 为什么C标准使用不确定的变量未定义?

    垃圾价值存储在哪里,为什么目的?解决方法由于效率原因,C选择不将变量初始化为某些自动值.为了初始化这些数据,必须添加指令.以下是一个例子:产生:虽然这段代码:产生:你可以看到,一个完整的额外的指令用来移动1到x.这对于嵌入式系统来说至关重要.

  3. 如何使用命名管道从c调用WCF方法?

    更新:通过协议here,我无法弄清楚未知的信封记录.我在网上找不到任何例子.原版的:我有以下WCF服务我输出添加5行,所以我知道服务器是否处理了请求与否.我有一个.NET客户端,我曾经测试这一切,一切正常工作预期.现在我想为这个做一个非托管的C客户端.我想出了如何得到管道的名称,并写信给它.我从here下载了协议我可以写信给管道,但我看不懂.每当我尝试读取它,我得到一个ERROR_broKEN_P

  4. “这”是否保证指向C中的对象的开始?

    我想使用fwrite将一个对象写入顺序文件.班级就像当我将一个对象写入文件时.我正在游荡,我可以使用fwrite(this,sizeof(int),2,fo)写入前两个整数.问题是:这是否保证指向对象数据的开始,即使对象的最开始可能存在虚拟表.所以上面的操作是安全的.解决方法这提供了对象的地址,这不一定是第一个成员的地址.唯一的例外是所谓的标准布局类型.从C11标准:(9.2/20)Apointe

  5. c – 编译单元之间共享的全局const对象

    当我声明并初始化一个const对象时.两个cpp文件包含此标头.和当我构建解决方案时,没有链接错误,你会得到什么如果g_Const是一个非const基本类型!PrintInUnit1()和PrintInUnit2()表明在两个编译单元中有两个独立的“g_Const”具有不同的地址,为什么?

  6. 什么是C名称查找在这里? (&amp;GCC对吗?)

    为什么在第三个变体找到func,但是在实例化的时候,原始变体中不合格查找找不到func?解决方法一般规则是,任何不在模板定义上下文中的内容只能通过ADL来获取.换句话说,正常的不合格查找仅在模板定义上下文中执行.因为在定义中间语句时没有声明func,并且func不在与ns::type相关联的命名空间中,所以代码形式不正确.

  7. c – 在输出参数中使用auto

    有没有办法在这种情况下使用auto关键字:当然,不可能知道什么类型的.因此,解决方案应该是以某种方式将它们合并为一个句子.这可用吗?解决方法看起来您希望默认初始化给定函数期望作为参数的类型的对象.您无法使用auto执行此操作,但您可以编写一个特征来提取函数所需的类型,然后使用它来声明您的变量:然后你就像这样使用它:当然,只要你重载函数,这一切都会失败.

  8. 在C中说“推动一切浮动”的确定性方式

    鉴于我更喜欢将程序中的数字保留为int或任何内容,那么使用这些数字的浮点数等效的任意算术最方便的方法是什么?说,我有我想写通过将转换放在解析的运算符树叶中,无需将表达式转化为混乱是否可以使用C风格的宏?应该用新的类和重载操作符完成吗?解决方法这是一个非常复杂的表达.更好地给它一个名字:现在当您使用整数参数调用它时,由于参数的类型为double,因此使用常规的算术转换将参数转换为double用C11lambda……

  9. objective-c – 如何获取未知大小的NSArray的第一个X元素?

    在objectiveC中,我有一个NSArray,我们称之为NSArray*largeArray,我想要获得一个新的NSArray*smallArray,只有第一个x对象…

  10. c – Setprecision是混乱

    我只是想问一下setprecision,因为我有点困惑.这里是代码:其中x=以下:方程的左边是x的值.1.105=1.10应为1.111.115=1.11应为1.121.125=1.12应为1.131.135=1.14是正确的1.145=1.15也正确但如果x是:2.115=2.12是正确的2.125=2.12应为2.13所以为什么在一定的价值是正确的,但有时是错误的?请启发我谢谢解决方法没有理由期望使用浮点系统可以正确地表示您的帖子中的任何常量.因此,一旦将它们存储在一个双变量中,那么你所拥有的确切的一

返回
顶部