首页 > 代码库 > 程序设计1
程序设计1
1.有一串首位相连的珠子，总共m颗，每颗珠子都有自己的颜色，全部颜色共有n（n<=10）,现在要在里面截取一段，要求包含所有不同的颜色，并且长度越短越好。求如何截取。请详细描述算法思路，可 以用伪代码来辅助描述。并求得时间复杂度和空间复杂度！
伪代码
for 每个珠子
出现新颜色的珠子，该颜色计数器加1，（初始为0）；
总颜色计数器加1,初始为0；
if(总颜色数==N)
while(序列首位珠子的颜色不唯一）
序列起始位后移1位，
相应颜色计数器值减1；
更新最佳序列长度
更新序列起始位置
输出起始位置，最佳序列长度，打印序列元素；
#include <iostream>
#include <stdlib#include <time.h>
using namespace std;int GetRandomNumber(int N){ int RandomNumber; //srand((int)time(NULL));//为rand()函数生成不同的随机种子 //每产生一个随机数之前 都调用一次srand而由于计算机运行很快 //所以你每次用time得到的时间都是一样的（time的时间精度较低，只有55ms）。 //这样相当于使用同一个种子产生随机序列，所以产生的随机数总是相同的。应该把srand放在循环外 RandomNumber = rand() % N;//生成随机数 return RandomNumber;}int main(){ int N,M; int i, j; int colorsCount = 0; int lastStartindex = 0; int bestStartIndex = 0; cout << "Enter the total number M:"; //int N; cin >> M; cout << endl; cout << "The number of selected N:"; cin >> N; int bestlen = M; int *arr = new int[M]; int *colors = new int[N]; for (i = 0; i < N; i++) { colors[i] = 0; } for (i = 0; i < N; i++) { cout << colors[i] << " "; } cout << endl; srand((unsigned)time(NULL)); //为rand()函数生成不同的随机种子 for (i = 0; i < M; i++) { arr[i] = GetRandomNumber(N); } for (i = 0; i < M; i++) { cout << arr[i] << " "; } cout << endl; for (i = 0; i < M; i++) { if (!colors[arr[i]]) // 如果珠子 arr[i]的颜色还未曾遇到过，颜色总数colorsCount++ { colorsCount++; //colors[arr[i]]++; } colors[arr[i]]++; //相应的颜色计数器加1 if (colorsCount == N) //如果已查询到的颜色数量==给定值 { int j = lastStartindex; //检查第一颗珠子的颜色是否是唯一的，若不是则查询位置后移 while (colors[arr[j]]>1) { colors[arr[j]]--; j++; } //bestStartIndex = j; if (i - j + 1 < bestlen) //如果此次选定的序列长度小于上次选定的长度，更新最小长度 { bestStartIndex = j; // 记录开始位置 bestlen = i - j + 1; //记录最佳长度 if (bestlen == N) //如果正好等于需要颜色数，则说明每一个正好一个。则退出 break; } lastStartindex = j; } //lastStartindex = j; } cout << "bestStartIndex: " << bestStartIndex << endl; cout << "bestLen: " << bestlen << endl; for (int i = bestStartIndex; i < bestlen + bestStartIndex; ++i) cout << arr[i] << " "; cout << endl; system("pause"); return 0;}
后记：
（1）、初始化指定大小的数组
数组的维度在编译的时候应该是已知的，维度必须是常量表达式。
例如： int cnt =10; int arr[cnt] //wrong,cnt不是常亮表达式 <C++ Primer 101>
上面程序中运用new创建动态数组（不是太清楚），不过程序通过了。
（2）、生成随机数
A:srand((unsigned)time(NULL));//为rand()函数生成不同的随机种子
头文件：<stdlib.h> <time.h>
B:从X到Y，有Y－X＋1个数，所以要产生从X到Y的数，只需要这样写：
randomNumber=rand()%(Y-X+1)+X; 这样，就可以产生你想要的任何范围内的随机数了。
(3)、Bug
如果珠子的总数M和总颜色数N相差不大时，产生的随机数可能并不包含 [0,N]中所有的数，在while（colorsCount ==N）时会出错，程序无法进入循环。
参考
1、http://blog.csdn.net/hai8902882/article/details/8299995
程序设计1