文章目录

• 前言
• 💎一、题目一
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎二、题目二
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎三、题目三
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎四、星球推荐

前言

        深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。由此可见，把通常问题转化为树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。
在题解里借鉴了大佬代码的思路，刷题坚持每一天，以下题目引用自：力扣（LeetCode）

💎一、题目一

🏆1.题目描述

原题链接：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：
输入: A = [5,4,0,3,1,6,2]
输出: 4
解释:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

🏆2.解题思路

🔑思路：

​         嵌套最长只有数组只有一各，对遍历到的元素进行标记。下次遇到重复的返回嵌套层数。

🏆3.代码详解

void dfs(int* nums, int i, int* hash, int* value){    if(hash[i] == 1) return;    hash[i] = 1;    ++(*value);    dfs(nums, nums[i], hash, value);}int arrayNesting(int* nums, int numsSize){    int* hash = malloc(sizeof(int)*numsSize);    memset(hash, 0 , sizeof(int)*numsSize);    int i;    int max = 0, value = 0;    for(i = 0; i < numsSize; ++i){ value = 0; dfs(nums, i, hash, &value); max = max > value ? max : value;    }    return max;}

💎二、题目二

🏆1.题目描述

原题链接：401. 二进制手表

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

• 例如，下面的二进制手表读取 “3:25” 。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
小时不会以零开头：

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

示例 1：
输入：turnedOn = 1
输出：[“0:01”,“0:02”,“0:04”,“0:08”,“0:16”,“0:32”,“1:00”,“2:00”,“4:00”,“8:00”]

🏆2.解题思路

🔑思路：

​         array前 4 个元素为LED小时数值，后六个元素为LED分钟数值，在递归中添加当前小时和分钟两个参数。对小时大于 11 与分钟大于等于 60 进行剪枝。对递归可选LED亮灯的数量不等少于当前亮着的 LED 的数量(turnedOn)，剪枝处理。

🏆3.代码详解

void dfs(int turnedOn, int pos, int hour, int minute, int* count, char** ans) {    int array[] = { 1, 2, 4, 8, 1, 2, 4, 8, 16, 32 };    if (hour > 11 || minute >= 60) return;    if (turnedOn  <= 0) { ans[*count] = calloc(6, sizeof(char)); sprintf(ans[(*count)++], "%d:%02d", hour, minute); return;    }    for (int i = pos; i + turnedOn  <= 10; ++i) { if (i < 4) {     dfs(turnedOn  - 1, i + 1, hour + array[i], minute, count, ans); } else {     dfs(turnedOn  - 1, i + 1, hour, minute + array[i], count, ans); }    }}char **readBinaryWatch(int turnedOn , int *returnSize) {    int count = 0;    char** ans = (char**)malloc(sizeof(char*)*256);    dfs(turnedOn , 0, 0, 0, &count, ans);    *returnSize = count;    return ans;}

💎三、题目三

🏆1.题目描述

原题链接：1079. 活字印刷

        你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
        注意：本题中，每个活字字模只能使用一次。

示例 1：
输入：“AAB”
输出：8
解释：可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。

🏆2.解题思路

🔑思路：

​        每次递归之前把当前字模减去，防止重复。递归回来之后，再把当前字模加回来。

🏆3.代码详解

void dfs(int* hash, int* ans){    int i;    for(i = 0; i < 26; ++i){ if(hash[i] != 0){     ++(*ans);     --hash[i];     dfs(hash, ans);     ++hash[i]; }    }}int numTilePossibilities(char * tiles){    int ans = 0;    int* hash = (int*)malloc(sizeof(int)*26);    memset(hash, 0, sizeof(int)*26);    for(int i = 0; tiles[i] != '\0'; ++i){ ++hash[tiles[i]-'A'];    }    dfs(hash, &ans);    return ans;}

💎四、星球推荐

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到420+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。