跟书上这道题目类似的是百度的一道笔试题:“一串首尾相连的珠子(m个),有N种颜色(N《=10),设计一个算法,取出其中一段,要求包含所有N中颜色,并使长度最短。”
第一次拿到这个题,忘记了手尾相连,题意都看错了,(在没有首尾相连的情况下解决方法是我的方法是求出每个结点为尾的最短长度,这样时间复杂度为n的平方)。有时候真是矛盾,之前嫌慢要求只读一遍题,读快了,又不能读懂,真是应该掌握这个尺度。
如果首尾相连的话我能想到的方法还是穷举法,即找出每个节点为尾的最短长度,时间复杂度为n*n,至于动态规划法比较复杂扫了一眼类似于kmp算法
一种比较简单的方法是采用两个指针。具体做法同编程之美的最短摘要的第二个解法应该一样。再就是网上出现的使用两个指针的类似的题目是
给出一个字符串,及一个字符集,求该字符串包含所有字符集的最短子串
答案是(以下方法摘抄自网络来源csdn):用两个变量 front rear 指向一个的子串区间的头和尾
用一个int cnt[255]={0}记录当前这个子串里 字符集a,b,c 各自的个数,一个变量sum记录字符集里有多少个了
rear 一直加,更新cnt[]和sum的值,直到 sum等于字符集个数
然后front++,直到cnt[]里某个字符个数为0,这样就找到一个符合条件的字串了
分享到:
相关推荐
Floyd算法的C++ 实现,终端输入终端输出
用最短路径算法实现求得快递小哥的最优路径问题,完整的工程。
蜂窝最短路径n种解法,蜂窝最短路径n种解法。
有限制最短路径算法分支定界解法c++实现 程序有说明,可运行,欢迎下载
编程之法:面试和算法心得 高清带完整书签201510版 程序员面试宝典 笔试金典 CSDN访问量过千万的博客结构之法算法之道博主July著作 作者:July 著出版社:人民邮电出版社出版时间:2015年10月 《编程之法:面试和算法...
在交互网络上任意节点对之间的最短路径不止一条的情况下,运用Floyd算法对已知加权交互网络的最短路径进行求解,对获得最短路径后的每一个节点对,在其中插入已知交互网络中的其余所有节点,并计算此时的节点对之间的...
我的解决方式是:a,三种解法,看结果是否一致。b,小数据(100个点),人工排查。第一种方法,暴力法适合小数据。第二种方法:我的改进 型。第三种方法:经典方法(分治法)。实验证明1000万数据时,我的算法有优势...
基于Matlab编程的一类指派问题解法
PLC图解法编程是靠画图进行PLC程序设计。常见的主要有梯形图法、逻辑流程图法、时序流程图法和步进顺控法。
基于Matlab编程的一类指派问题解法.pdf
提出了利用地图代数栅格路径距离变换原理求解欧氏障碍空间最短路径问题的方法(MA-ESPO),实现了二维障碍空间最短路径的一个栅格解法,并且把障碍物、源、汇图形都扩大到任意形态图形。给出了基于地图代数的障碍空间...
书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法,第7章介绍机器学习的两个算法—K近邻和...
July 最新巨著 编程之法:面试和算法心得.pdf 简介 本书涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、查找...
80.MATLAB编程 偏微分方程的数值解法 源程序代码.rar
问题解法 微积分学辞典
二维稳态导热问题数值解法.pdf
书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法,第7章介绍机器学习的两个算法—K近邻和...
July 最新巨著 编程之法:面试和算法心得-样章.pdf 简介 本书涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、...
2、HCIE LAB拓扑及解法,按照解法敲熟练两个月内去考稳定一次过人 拓扑包含 LAB optionC1 及 C2, 及 TS排错拓扑 及 TAC诊断拓扑。 包含完整拓扑+解法题库,拓扑下载里面的ENSP软件可以直接打开敲版本。 HCIE-RS3.0-...
用C++编的解一元二次方程的程序 // 求解二次方程a*x^2+b*x+c=0(a,b,c为任意系数); //delta=b^2-4*a*c;