美文网首页
爱奇艺-笔试刷题2018-07-22

爱奇艺-笔试刷题2018-07-22

作者: Dodo159753 | 来源:发表于2018-07-22 08:09 被阅读0次

题目描述:

/**
牛牛又从生物科研工作者那里获得一个任务,
这次牛牛需要帮助科研工作者
从DNA序列s中找出最短没有出现在DNA序列s中的DNA片段的长度。
例如:s = AGGTCTA
序列中包含了所有长度为1的('A','C','G','T')片段,
但是长度为2的没有全部包含,
例如序列中不包含"AA",所以输出2。
输入描述:
输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 2000),其中只包含'A','C','G','T'这四种字符。
输出描述:
输出一个正整数,即最短没有出现在DNA序列s中的DNA片段的长度。
输入例子1:
AGGTCTA
输出例子1:
2
*/

思路如下:

从片段长度为1开始
计算长度为d的片段(只计算片段不同的,相同片段不重复算)的数目
对于长度为len的字符串中d长度的片段只有
len-d+1个片段,而d长度的片段一共有2^d个排列的片段
len>=2^d+d-1
对于长度为len的字符串最多满足其长度为1 2 3 ...ceil(log(len))这些片段所有都取到

代码如下:

#include<stdio.h>
#include<iostream>
#include<set>
 
using namespace std;
 
int main()
{
    string line;
    cin>>line;
    int targetNum=1;
    for(int d=1; d<=line.size(); d++){
        targetNum*=4;
        set<string> cntSet;
        for(int i=0; i<line.size(); i++){
            if(i+d>=line.size())
                break;
            string subStr=line.substr(i, d);
            cntSet.insert(subStr);
        }
        if(cntSet.size()<targetNum){
            printf("%d", d);
            break;
        }
    }
    return 0;
}

相关文章

  • 爱奇艺-笔试刷题2018-07-22

    题目描述: 思路如下: 从片段长度为1开始计算长度为d的片段(只计算片段不同的,相同片段不重复算)的数目对于长度为...

  • 爱奇艺-笔试刷题2018-07-13

    题目描述: 思路如下: 把原来字符串分割成长度为len1和len2的两个字符串求这两个字符串最大的公共子序列时间复...

  • 爱奇艺-笔试刷题2018-07-12

    题目描述: 思路如下: 对x[i]升序排序,然后按着升序顺序遍历x[i]<=x[i+1]说明x[i]选择就会影响x...

  • 爱奇艺-笔试刷题2018-07-14

    题目描述: 思路如下: 方案一:DFS暴力枚举情况求解(超时)方案二:暴力DFS先找写,然后打表找规律为没5个ni...

  • 笔试刷题-爱奇艺2018-07-20

    题目描述: 思路如下: 若v1.lenk1!=v2.lenk2那么返回更长的一个一个组合出来的数最多9*50位用m...

  • 爱奇艺-笔试刷题2018-07-21

    题目描述: 思路如下: 其实就是找给定范围内的数,组成对(A, B)使得 AB为完全平方数枚举A B首先建立素数表...

  • 爱奇艺-笔试刷题2018-07-11

    题目描述: 思路如下: 题目要求的深度其实就是判断合法性的时候,'('入栈的最大数目用一个指针模拟栈的大小即可 代...

  • 爱奇艺-笔试刷题2018-07-16

    题目描述: 思路如下: 维护单调递减栈若有一个新的数来高于当前的栈顶,那么这个数就可以向左延伸,同时出栈找出所有最...

  • 爱奇艺-笔试刷题2018-07-18

    题目描述: 思路如下: 对于一个数x, 是digit位那么其对应的sum为x+x/10+x/100+...+(x/...

  • 爱奇艺-笔试刷题2018-07-19

    题目描述: 思路如下: dp[i][k]表示0-i这一段操作k次以内操作后数组0-i里面得到最少的逆序数具体更新见...

网友评论

      本文标题:爱奇艺-笔试刷题2018-07-22

      本文链接:https://www.haomeiwen.com/subject/xsqlmftx.html