微软C++编程题目求源码与注释

【编程题目】一串首尾相连的珠子(m 个)，有 N 种颜色(N<=10)，取出其中一段，要求包含所有 N 中颜色，并使长度最短。

/*
一串首尾相连的珠子(m ä¸ª)，有 N ç§é¢œè‰²(N<=10)，
设计一个算法，取出其中一段，要求包含所有 N ä¸­é¢œè‰²ï¼Œå¹¶ä½¿é•¿åº¦æœ€çŸ­ã€‚
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int shortestlengh(char * in, char ** dst, int N)
{
    //变成inin的形式，避免求余
    int nlen = strlen(in);
    char * in2 = (char *)malloc(2 * nlen * sizeof(char)); 
    memcpy(in2, in, nlen * sizeof(char));
    memcpy(in2 + nlen, in, nlen * sizeof(char));

    int start = 0, end = nlen - 1;
    int shortestlen = nlen;
    int hash[256] = {0};
    int colornum = 0;
    int s = 0, e = -1;
    //遍历所有可能的起始点
    while(s < nlen)
    {
        while(colornum < N && e <= 2 * nlen) //找到在当前起点下找到所有颜色的结尾
        {    
            e++;
            if(hash[int(in2[e])] == 0)
            {
                colornum++;
            }
            hash[int(in2[e])]++;
        }
        //去掉前面相同的部分
        while(in2[s] == in2[s + 1])
        {
            s++;
            hash[(int)in2[s]]--;
        }

        //更新最短的串
        if(shortestlen > e - s + 1)
        {
            shortestlen = e - s + 1;
            start = s;
            end = e;
        }

        //更新s,从下一个颜色开始
        hash[(int)in2[s]]--;
        if(hash[(int)in2[s]] == 0)
        {
            colornum--;
        }
        s = s + 1;
    }

    *(dst) = (char *)malloc(end - start + 2);
    memcpy(*dst, in2 + start, end - start + 1);
    (*dst)[end - start + 1] = '\0'; //注意

    free(in2);

    return end - start + 1;
}

int main()
{
    char * s = "addcddcbccbba";
    char * d = NULL;
    int n = shortestlengh(s, &d, 4);
    printf("%d\n%s\n", n, d);
    return 0;
}追问

这个不对吧。网上的代码 char * s = "addcddcbfgccbba"; 输出的不含fg呀。

追答#include<iostream>
#include<string.h>
using namespace std;

//m string a:0,1,...,m-1
//N colors:0,1,...,N-1
//
#define m 10
#define N 3
int findmin(int a[m], int colors[N], int& begin, int& end)
{
begin = 0;
end = -1;
int i = 0;
int j = 0;
int cn = 0;
int minlen = m;
colors[a[0]] ++;
cn++;
while (i < m)
{
//memset(colors, 0, N*sizeof(int));
//j = i;
bool bl = false;
while (j == 0 || j != i)
{
if (bl)
{
if (colors[a[j]] == 0)
cn++;
colors[a[j]] ++;
}
bl = true;
if (cn == N)
{
int len = j - i + 1;
if (len < 0)
len += m;
if (len < minlen)
{
begin = i;
end = j;
minlen = j - i + 1;
}
break;
}
j = (j + 1) % m;
}

if (i == j && minlen == m)
break;
colors[a[i]] = colors[a[i]] - 1;
if (colors[a[i]] == 0)
cn--;
i++;
}
return minlen;
}



int main()
{
int a[m] = { 2,1,0,1,1,2,1,0,1,1 };
int c[N] = { 0,0,0 };
int begin = 0, end = 0;
int minlen = findmin(a, c, begin, end);
int i = 0;
cout << "string: ";
while (i < m)
{
cout << a[i] << ",";
i++;
}
cout << " minlen: " << minlen << endl;
cout << begin << "," << end << endl;
}追问

int a[m] = { 2,1,0,1,1,9,1,0,1,1 }; 换成这个怎么输出1，0 ？

温馨提示：内容为网友见解，仅供参考

当前网址：https://11.t2y.org/zz/f42vqm8qfsvffv8f4q7.html