《五月集训》第十五日——广度优先搜索

这是五月集训的第十五日，今日的训练内容是 广度优先搜索

565. 数组嵌套

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], … }且遵守以下的规则。

假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]… 以此类推，不断添加直到S出现重复的元素。

使用题目所给的方式对数组进行遍历就可以了，为了防止遍历过程中出现重复，只需要在遍历的同时把被使用过的元素赋值为 -1 即可。

int arrayNesting(int* nums, int numsSize)
{
    int cnt = 0;
    int max = 0, tmp;
    int i,j;
    if (nums == NULL) {
        return -1;
    }
    for (i = 0; i < numsSize; i++){
        j = i;
        while (j < numsSize && nums[j] != -1) {
            cnt++;
            tmp = nums[j];
            nums[j] = -1;
            j = tmp;
        }
        max = cnt > max ? cnt : max;
        cnt = 0;
    }
    return max;
}

将当前位置的值赋予下标，并标记下当前的数据，使其变成 -1。

401. 二进制手表

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

例如，“01:00” 是无效的时间，正确的写法应该是 “1:00” 。
分钟必须由两位数组成，可能会以零开头：

例如，“10:2” 是无效的时间，正确的写法应该是 “10:02” 。

暴力枚举

 int countbit(int n)
 {
     int count=0;
     while(n)
     {
         count++;
         n=n&(n-1);
     }
     return count;
 }
char ** readBinaryWatch(int turnedOn, int* returnSize)
{
    char**ret=(char**)malloc(sizeof(char*)*12*60);
    *returnSize=0;
    for(int i=0;i<12;i++)
    {
        for(int j=0;j<60;j++)
        {
            if(countbit(i)+countbit(j)==turnedOn)
            {
                ret[(*returnSize)]=malloc(sizeof(char)*6);
                sprintf(ret[(*returnSize)++],"%d:%02d",i,j);
            }
        }
    }
    return ret;
}

1079. 活字印刷

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

先做记录，预计在这两天学完图的广度优先搜索相关知识之后回来重刷

1219. 黄金矿工

同上