C刷题：LeetCode 752. 打开转盘锁 （中等） || BFS广搜详解
2021/7/11 23:37:47
本文主要是介绍C刷题：LeetCode 752. 打开转盘锁 （中等） || BFS广搜详解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
C刷题：LeetCode 752. 打开转盘锁 （中等）
- 思路分析
- 原始版本
- 版本一：BFS穷举所有可能
- 版本二：找到target即终止
- Hash版本
- Hash版本优化
- 展望
PS：
你以为的中等题，结果官方解答用了A*算法。没有现成的数据结构，用C语言实现，不亚于难题，哈哈怪不得连官方答案A*算法实现里都懒得写C版本了。。。
所以，我就不搞那么复杂啦，就用BFS一步步深入，并把分析的思路记录与此吧。
思路分析
- 先实现最简单的，遍历穷举所有可能
- 接着实现BFS遍历找到target
- 再加约束deadends跳过 + 最小次数
- 实现子函数加减功能
原始版本
独立实现一个遍历功能，思路是按一个位转动不同次数，然后第二个位转不同次数，往深处递归的，本质是DFS遍历，代码如下：
char AddOne(char ch)
{
char ans;
if (ch == '9') {
return '0';
}
ans = ch + 1;
return ans;
}
char MinusOne(char ch)
{
char ans;
if (ch == '0') {
return '9';
}
ans = ch - 1;
return ans;
}
int g_times;
void BfsFindMinTimes(char *cur, char *target, int depth)
{
// 终止条件
if (depth == 4) {
return;
}
// 迭代搜索
char ch1 = *cur;
char ch2 = *target;
while (ch1 != ch2) {
int tmp = ch1 - ch2;
tmp = abs(tmp);
if (tmp > 5) {
g_times += 10 - tmp; // need to rever dir
tmp = 10 - tmp;
while (tmp--) {
ch1 = MinusOne(ch1);
}
} else {
g_times += tmp;
while (tmp--) {
ch1 = AddOne(ch1);
}
}
}
*cur = *target;
BfsFindMinTimes(cur + 1, target + 1, depth + 1);
return;
}
// BFS
int openLock(char ** deadends, int deadendsSize, char * target)
{
g_times = 0;
char cur[5] = "0000"; // 初始值
// special case
if (strcmp(cur, target) == 0) {
return 0;
}
int i;
for (i = 0; i < deadendsSize; i++) {
if (strcmp(cur, deadends[i]) == 0) {
return -1;
}
}
BfsFindMinTimes(cur, target, 0);
return g_times;
}
版本一：BFS穷举所有可能
由于原始版本思路泛化能力较弱，参考labuladong的思路，真正的从BFS入手，穷举所有可能。代码如下：
char* AddOne(char *in, int j)
{
char *res = (char *)malloc(sizeof(char) * 5);
if (res == NULL) {
return NULL;
}
memcpy(res, in, 5);
char ch = res[j];
if (ch == '9') {
res[j] = '0';
return res;
}
res[j] = ch + 1;
return res;
}
char* MinusOne(char *in, int j)
{
char *s = (char *)malloc(sizeof(char) * 5);
if (s == NULL) {
return NULL;
}
memcpy(s, in, 5);
char ch = s[j];
if (ch == '0') {
s[j] = '9';
return s;
}
s[j] = ch - 1;
return s;
}
typedef struct QueList {
int cnt; // 转动次数
char *s; // 当前密码
struct QueList *next; // 下个可能密码
} StruQueList, *PtrStruQueList;
void Init(StruQueList **pQue, char *s, int cnt)
{
(*pQue) = (PtrStruQueList)malloc(sizeof(StruQueList));
(*pQue)->cnt = cnt;
char *str = (char *)malloc(sizeof(char) * (strlen(s) + 1));
if (str == NULL) {
return;
}
memcpy(str, s, strlen(s) + 1);
(*pQue)->s = str;
(*pQue)->next = NULL;
}
PtrStruQueList NodeExpand(StruQueList **queList, PtrStruQueList queListLastNode)
{
int i;
char *s;
// 临时转动1次, 当前节点演变出8种可能
char *cur = (*queList)->s;
int cnt = (*queList)->cnt;
for (i = 0; i < 4; i++) {
s = AddOne(cur, i);
printf("%s\n", s);
Init(&queListLastNode->next, s, cnt + 1);
queListLastNode = queListLastNode->next;
s = MinusOne(cur, i);
printf("%s\n", s);
Init(&queListLastNode->next, s, cnt + 1);
queListLastNode = queListLastNode->next;
}
printf("\n");
return queListLastNode;
}
// 按队列和BFS的方法来表达每次只转一次，对应的所有可能
void BfsFindMinTimes(char *cur, char *target)
{
// 初始化队列 0000
PtrStruQueList queList, queListCurLevelLast, queListLastNode;
queList = (PtrStruQueList)malloc(sizeof(StruQueList));
if (queList == NULL) {
return; // if malloc is failed
}
Init(&queList, cur, 0);
queListCurLevelLast = queList;
queListLastNode = NodeExpand(&queList, queListCurLevelLast);
queListCurLevelLast = queListLastNode;
queList = queList->next;
// 得到两个队列的指针，一个是当前指向，一个是层级对应的新开头
// 从所有层每个节点中迭代新的可能
while (queList != NULL) {
queListCurLevelLast = queListLastNode;
// 遍历当前层所有节点
while (queList != queListCurLevelLast) {
queListLastNode = NodeExpand(&queList, queListLastNode);
queList = queList->next;
}
queListLastNode = NodeExpand(&queList, queListLastNode); // 当前层最后一个节点
queList = queList->next;
printf("\n\n");
}
return;
}
// BFS
int openLock(char ** deadends, int deadendsSize, char * target)
{
char cur[5] = "0000"; // 初始值
// special case
if (strcmp(cur, target) == 0) {
return 0;
}
int i;
for (i = 0; i < deadendsSize; i++) {
if (strcmp(cur, deadends[i]) == 0) {
return -1;
}
}
BfsFindMinTimes(cur, target);
return 1;
}
版本二：找到target即终止
接着在此基础上继续改进，加上终止条件，实现找到target就停止遍历。
char* AddOne(char *in, int j)
{
char *res = (char *)malloc(sizeof(char) * 5);
if (res == NULL) {
return NULL;
}
memcpy(res, in, 5);
char ch = res[j];
if (ch == '9') {
res[j] = '0';
return res;
}
res[j] = ch + 1;
return res;
}
char* MinusOne(char *in, int j)
{
char *s = (char *)malloc(sizeof(char) * 5);
if (s == NULL) {
return NULL;
}
memcpy(s, in, 5);
char ch = s[j];
if (ch == '0') {
s[j] = '9';
return s;
}
s[j] = ch - 1;
return s;
}
typedef struct QueList {
int cnt; // 转动次数
char *s; // 当前密码
struct QueList *next; // 下个可能密码
} StruQueList, *PtrStruQueList;
void Init(StruQueList **pQue, char *s, int cnt)
{
(*pQue) = (PtrStruQueList)malloc(sizeof(StruQueList));
(*pQue)->cnt = cnt;
char *str = (char *)malloc(sizeof(char) * (strlen(s) + 1));
if (str == NULL) {
return;
}
memcpy(str, s, strlen(s) + 1);
(*pQue)->s = str;
(*pQue)->next = NULL;
}
// 大于0，则表示匹配成功，返回转动次数
// 等于0，则表示无异常
// 小于0，则表示出错
int NodeExpand(StruQueList **queList, StruQueList **ptrQueListLastNode, char *target)
{
int i;
char *s;
// 转动1次, 当前节点演变出8种可能
char *cur = (*queList)->s;
int cnt = (*queList)->cnt;
for (i = 0; i < 4; i++) {
s = AddOne(cur, i);
printf("%s\n", s);
Init(&(*ptrQueListLastNode)->next, s, cnt + 1);
if (strcmp(s, target) == 0) { // 终止条件
return cnt + 1;
}
*ptrQueListLastNode = (*ptrQueListLastNode)->next;
s = MinusOne(cur, i);
printf("%s\n", s);
Init(&(*ptrQueListLastNode)->next, s, cnt + 1);
if (strcmp(s, target) == 0) {
return cnt + 1;
}
*ptrQueListLastNode = (*ptrQueListLastNode)->next;
}
printf("\n");
return 0;
}
// 按队列和BFS的方法来表达每次只转一次，对应的所有可能
int BfsFindMinTimes(char *cur, char *target)
{
int ret;
// 初始化队列 0000
PtrStruQueList queList, queListCurLevelLast, queListLastNode;
queList = (PtrStruQueList)malloc(sizeof(StruQueList));
if (queList == NULL) {
return; // if malloc is failed
}
Init(&queList, cur, 0);
queListLastNode = queList;
ret = NodeExpand(&queList, &queListLastNode, target);
if (ret > 0) { // 终止条件
return ret;
}
queListCurLevelLast = queListLastNode;
queList = queList->next;
// 得到两个队列的指针，一个是当前指向，一个是层级对应的新开头
// 从所有层每个节点中迭代新的可能
while (queList != NULL) {
// 遍历当前层所有节点
while (queList != queListCurLevelLast) {
int ret = NodeExpand(&queList, &queListLastNode, target);
if (ret > 0) { // 终止条件
return ret;
}
queList = queList->next;
}
int ret = NodeExpand(&queList, &queListLastNode, target); // 当前层最后一个节点
if (ret > 0) { // 终止条件
return ret;
}
queList = queList->next;
queListCurLevelLast = queListLastNode;
printf("\n\n");
}
return -1; // 遍历完所有无匹配
}
// BFS
int openLock(char ** deadends, int deadendsSize, char * target)
{
char cur[5] = "0000"; // 初始值
// special case
if (strcmp(cur, target) == 0) {
return 0;
}
int i;
for (i = 0; i < deadendsSize; i++) {
if (strcmp(cur, deadends[i]) == 0) {
return -1;
}
}
int ret = BfsFindMinTimes(cur, target);
return ret;
}
Hash版本
添加HASH数据结构，熟悉uthash，添加约束条件。
主要约束条件：
- 不走回头路，比如往前转动了一次的结果，不允许再往后转动回去
- 不能越过deadends
- 加上终止条件，一旦匹配到target就返回
不走回头路，比如往前转动了一次的结果，不允许再往后转动回去。实现的主要思路是，增加一个visit记录所有已经有的遍历结果，如果出现相同的则跳过并且不记录。主要用uthash哈希表，减少查找时间。
不能越过deadends，也是类似visit的hash表查找思路实现。hash表时间复杂度为O(1)，不过是以空间换时间，减少时间同时会增长空间。
终止条件，由于该思路本身就是从转动次数0开始往外扩展的，类似一种贪心算法思想，每步都是最优的了。一旦匹配上目标，当前转动次数就是最小的，所以可以直接返回。
提交通过的hash版本代码如下：
typedef struct HashTable {
char str[5]; // key
UT_hash_handle hh; // table head
} StruHashTable;
typedef struct QueList {
int cnt; // 转动次数
char *s; // 当前密码
struct QueList *next; // 下个可能密码
} StruQueList, *PtrStruQueList;
#define STR_SIZE 5
#define STR_LEN 4
int g_curLevelCnt;
char* AddOne(char *in, int j)
{
char *res = (char *)malloc(sizeof(char) * STR_SIZE);
if (res == NULL) {
return NULL;
}
memcpy(res, in, STR_SIZE);
char ch = res[j];
if (ch == '9') {
res[j] = '0';
return res;
}
res[j] = ch + 1;
return res;
}
char* MinusOne(char *in, int j)
{
char *s = (char *)malloc(sizeof(char) * STR_SIZE);
if (s == NULL) {
return NULL;
}
memcpy(s, in, STR_SIZE);
char ch = s[j];
if (ch == '0') {
s[j] = '9';
return s;
}
s[j] = ch - 1;
return s;
}
void Init(StruQueList **pQue, char *s, int cnt)
{
(*pQue) = (PtrStruQueList)malloc(sizeof(StruQueList));
(*pQue)->cnt = cnt;
char *str = (char *)malloc(sizeof(char) * STR_SIZE);
if (str == NULL) {
return;
}
memcpy(str, s, STR_SIZE);
(*pQue)->s = str;
(*pQue)->next = NULL;
g_curLevelCnt++;
}
// 大于0，则表示匹配成功，返回转动次数
// 等于0，则表示无异常
// 小于0，则表示出错
int NodeExpand(StruQueList **queList, StruQueList **ptrQueListLastNode, char *target, StruHashTable **ptrDead, StruHashTable **ptrVisit)
{
int i;
char *s;
StruHashTable *hashTmp1, *hashTmp2;
// 转动1次, 当前节点演变出8种可能
char *cur = (*queList)->s;
int cnt = (*queList)->cnt;
for (i = 0; i < 4; i++) {
s = AddOne(cur, i);
// 如果与target匹配
if (strcmp(s, target) == 0) { // 终止条件
return cnt + 1;
}
// 如果在deadends
HASH_FIND(hh, *ptrDead, s, sizeof(char) * STR_SIZE, hashTmp1);
// 如果已遍历
HASH_FIND(hh, *ptrVisit, s, sizeof(char) * STR_SIZE, hashTmp2);
if (hashTmp1 == NULL && hashTmp2 == NULL) { // 不在dead里也没在visit里
Init(&(*ptrQueListLastNode)->next, s, cnt + 1);
*ptrQueListLastNode = (*ptrQueListLastNode)->next;
hashTmp1 = (StruHashTable *)malloc(sizeof(StruHashTable)); // 增加一个hash节点
if (hashTmp1 == NULL) {
return -1;
}
memcpy(hashTmp1->str, s, STR_SIZE);
HASH_ADD(hh, *ptrVisit, str, sizeof(char) * STR_SIZE, hashTmp1);
// printf("%s\n", s);
} else {
free(s);
}
s = MinusOne(cur, i);
// 如果与target匹配
if (strcmp(s, target) == 0) { // 终止条件
return cnt + 1;
}
// 如果在deadends
HASH_FIND(hh, *ptrDead, s, sizeof(char) * STR_SIZE, hashTmp1);
// 如果已遍历
HASH_FIND(hh, *ptrVisit, s, sizeof(char) * STR_SIZE, hashTmp2);
if (hashTmp1 == NULL && hashTmp2 == NULL) { // 不在dead里也没在visit里
Init(&(*ptrQueListLastNode)->next, s, cnt + 1);
*ptrQueListLastNode = (*ptrQueListLastNode)->next;
hashTmp1 = (StruHashTable *)malloc(sizeof(StruHashTable)); // 增加一个hash节点
if (hashTmp1 == NULL) {
return -1;
}
memcpy(hashTmp1->str, s, STR_SIZE);
HASH_ADD(hh, *ptrVisit, str, sizeof(char) * STR_SIZE, hashTmp1);
// printf("%s\n", s);
} else {
free(s);
}
}
// printf("\n");
return 0;
}
// 按队列和BFS的方法来表达每次只转一次，对应的所有可能
int openLock(char ** deadends, int deadendsSize, char * target)
{
char cur[STR_SIZE] = "0000"; // 初始值
int i, ret;
// special case
if (strcmp(cur, target) == 0) {
return 0;
}
// 初始化hash
StruHashTable *dead = NULL; // 表头最开始都为空
StruHashTable *hashTmp;
for (i = 0; i < deadendsSize; i++) {
HASH_FIND(hh, dead, deadends[i], sizeof(char) * STR_SIZE, hashTmp); // 键值所占空间sizeof(char) * 5
if (hashTmp == NULL) { // 之前未出现
hashTmp = (StruHashTable *)malloc(sizeof(StruHashTable)); // 增加一个hash节点
if (hashTmp == NULL) {
return -1;
}
memcpy(hashTmp->str, deadends[i], STR_SIZE);
HASH_ADD(hh, dead, str, sizeof(char) * STR_SIZE, hashTmp); // str表示操作结构体中的键值，追加到hashtable中
}
}
// special case
HASH_FIND(hh, dead, target, sizeof(char) * STR_SIZE, hashTmp);
if (hashTmp != NULL) {
return -1; // deanends contain target
}
HASH_FIND(hh, dead, cur, sizeof(char) * STR_SIZE, hashTmp);
if (hashTmp != NULL) {
return -1; // deanends contain target
}
// 初始化队列 0000
StruHashTable *visit = NULL; // 表头最开始都为空
PtrStruQueList queList, queListCurLevelLast, queListLastNode;
queList = (PtrStruQueList)malloc(sizeof(StruQueList));
if (queList == NULL) {
return -1; // if malloc is failed
}
g_curLevelCnt = 0;
Init(&queList, cur, 0);
hashTmp = (StruHashTable *)malloc(sizeof(StruHashTable)); // 增加一个hash节点
if (hashTmp == NULL) {
return -1;
}
memcpy(hashTmp->str, queList->s, STR_SIZE);
// printf("%p\n", visit);
HASH_ADD(hh, visit, str, sizeof(char) * STR_SIZE, hashTmp); // 增加一个已遍历状态
// printf("%p\n", visit);
g_curLevelCnt = 0;
queListLastNode = queList;
ret = NodeExpand(&queList, &queListLastNode, target, &dead, &visit);
if (ret > 0) { // 终止条件
return ret;
}
queListCurLevelLast = queListLastNode;
queList = queList->next;
// 得到两个队列的指针，一个是当前指向，一个是层级对应的新开头
// 从所有层每个节点中迭代新的可能
while (queList != NULL) {
// 遍历当前层所有节点
int len = g_curLevelCnt;
g_curLevelCnt = 0;
for (i = 0; i < len; i++) {
ret = NodeExpand(&queList, &queListLastNode, target, &dead, &visit);
if (ret > 0) { // 终止条件
return ret;
}
queList = queList->next;
}
// printf("\n\n");
}
return -1; // 遍历完所有无匹配
}
Hash版本优化
代码精简：删除和提炼冗余信息。
- 删除合并重复代码减少层序遍历冗余
- 将超50行的代码拆分成子功能函数
- 替换魔鬼数字为有意义的宏命名
- 优化while循环加lastNode判断为for循环，采用全局变量计数当前层个数作为len
typedef struct HashTable {
char str[5]; // key
UT_hash_handle hh; // table head
} StruHashTable;
typedef struct QueList {
int cnt; // 转动次数
char *s; // 当前密码
struct QueList *next; // 下个可能密码
} StruQueList, *PtrStruQueList;
#define STR_SIZE 5
#define STR_LEN 4
int g_curLevelCnt;
char* AddOne(char *in, int j)
{
char *res = (char *)malloc(sizeof(char) * STR_SIZE);
if (res == NULL) {
return NULL;
}
memcpy(res, in, STR_SIZE);
char ch = res[j];
if (ch == '9') {
res[j] = '0';
return res;
}
res[j] = ch + 1;
return res;
}
char* MinusOne(char *in, int j)
{
char *s = (char *)malloc(sizeof(char) * STR_SIZE);
if (s == NULL) {
return NULL;
}
memcpy(s, in, STR_SIZE);
char ch = s[j];
if (ch == '0') {
s[j] = '9';
return s;
}
s[j] = ch - 1;
return s;
}
void Init(StruQueList **pQue, char *s, int cnt)
{
(*pQue) = (PtrStruQueList)malloc(sizeof(StruQueList));
(*pQue)->cnt = cnt;
char *str = (char *)malloc(sizeof(char) * STR_SIZE);
if (str == NULL) {
return;
}
memcpy(str, s, STR_SIZE);
(*pQue)->s = str;
(*pQue)->next = NULL;
g_curLevelCnt++;
}
void InitDeadHash(char **deadends, int deadendsSize, StruHashTable **ptrDead)
{
int i;
StruHashTable *hashTmp;
for (i = 0; i < deadendsSize; i++) {
HASH_FIND(hh, *ptrDead, deadends[i], sizeof(char) * STR_SIZE, hashTmp); // 键值所占空间sizeof(char) * 5
if (hashTmp == NULL) { // 之前未出现
hashTmp = (StruHashTable *)malloc(sizeof(StruHashTable)); // 增加一个hash节点
if (hashTmp == NULL) {
return;
}
memcpy(hashTmp->str, deadends[i], STR_SIZE);
HASH_ADD(hh, *ptrDead, str, sizeof(char) * STR_SIZE, hashTmp); // str表示操作结构体中的键值，追加到hashtable中
}
}
return;
}
void InitQueAndVisitHash(char *cur, StruQueList **ptrQueList, StruHashTable **ptrVisit)
{
StruHashTable *hashTmp;
*ptrQueList = (PtrStruQueList)malloc(sizeof(StruQueList));
if (*ptrQueList == NULL) {
return; // if malloc is failed
}
g_curLevelCnt = 0;
Init(ptrQueList, cur, 0);
hashTmp = (StruHashTable *)malloc(sizeof(StruHashTable)); // 增加一个hash节点
if (hashTmp == NULL) {
return;
}
memcpy(hashTmp->str, (*ptrQueList)->s, STR_SIZE);
HASH_ADD(hh, *ptrVisit, str, sizeof(char) * STR_SIZE, hashTmp); // 增加一个已遍历状态
return;
}
int DealCurStr(char *s, char *target, int cnt, StruQueList **ptrQueListLastNode, StruHashTable **ptrDead, StruHashTable **ptrVisit)
{
StruHashTable *hashTmp1, *hashTmp2;
// 如果与target匹配
if (strcmp(s, target) == 0) { // 终止条件
return cnt + 1;
}
// 如果在deadends
HASH_FIND(hh, *ptrDead, s, sizeof(char) * STR_SIZE, hashTmp1);
// 如果已遍历
HASH_FIND(hh, *ptrVisit, s, sizeof(char) * STR_SIZE, hashTmp2);
if (hashTmp1 == NULL && hashTmp2 == NULL) { // 不在dead里也没在visit里
Init(&(*ptrQueListLastNode)->next, s, cnt + 1);
*ptrQueListLastNode = (*ptrQueListLastNode)->next;
hashTmp1 = (StruHashTable *)malloc(sizeof(StruHashTable)); // 增加一个hash节点
if (hashTmp1 == NULL) {
return -1;
}
memcpy(hashTmp1->str, s, STR_SIZE);
HASH_ADD(hh, *ptrVisit, str, sizeof(char) * STR_SIZE, hashTmp1);
// printf("%s\n", s);
} else {
free(s);
}
return 0;
}
// 大于0，则表示匹配成功，返回转动次数
// 等于0，则表示无异常
// 小于0，则表示出错
int NodeExpand(StruQueList *queList, StruQueList **ptrQueListLastNode, char *target, StruHashTable **ptrDead, StruHashTable **ptrVisit)
{
int i, ret;
char *s;
// 转动1次, 当前节点演变出8种可能
char *cur = queList->s;
int cnt = queList->cnt;
for (i = 0; i < 4; i++) {
s = AddOne(cur, i);
ret = DealCurStr(s, target, cnt, ptrQueListLastNode, ptrDead, ptrVisit);
if (ret > 0) {
return ret;
}
s = MinusOne(cur, i);
ret = DealCurStr(s, target, cnt, ptrQueListLastNode, ptrDead, ptrVisit);
if (ret > 0) {
return ret;
}
}
// printf("\n");
return 0;
}
int LevelTraverse(StruQueList *queList, StruQueList **ptrQueListLastNode, char *target, StruHashTable **ptrDead, StruHashTable **ptrVisit)
{
// 得到两个队列的指针，一个是当前指向，一个是层级对应的新开头
// 从所有层每个节点中迭代新的可能
int i, ret;
while (queList != NULL) {
// 遍历当前层所有节点
int len = g_curLevelCnt;
g_curLevelCnt = 0;
for (i = 0; i < len; i++) {
ret = NodeExpand(queList, ptrQueListLastNode, target, ptrDead, ptrVisit);
if (ret > 0) { // 终止条件
return ret;
}
queList = queList->next;
}
// printf("\n\n");
}
return 0;
}
// 按队列和BFS的方法来表达每次只转一次，对应的所有可能
int openLock(char ** deadends, int deadendsSize, char * target)
{
char cur[STR_SIZE] = "0000"; // 初始值
int ret;
// special case
if (strcmp(cur, target) == 0) {
return 0;
}
// 初始化dead hash
StruHashTable *dead = NULL; // 表头最开始都为空
StruHashTable *hashTmp, *hashTmp1, *hashTmp2;
InitDeadHash(deadends, deadendsSize, &dead);
// special case
HASH_FIND(hh, dead, target, sizeof(char) * STR_SIZE, hashTmp1);
HASH_FIND(hh, dead, cur, sizeof(char) * STR_SIZE, hashTmp2);
if (hashTmp1 != NULL || hashTmp2 != NULL) {
return -1; // deanends contain target
}
// 初始化队列0000和visit hash
StruHashTable *visit = NULL; // 表头最开始都为空
PtrStruQueList queList, queListLastNode;
InitQueAndVisitHash(cur, &queList, &visit);
queListLastNode = queList;
ret = LevelTraverse(queList, &queListLastNode, target, &dead, &visit);
if (ret > 0) { // 终止条件
return ret;
}
return -1; // 遍历完所有无匹配
}
展望
- 可以参考下官方解答的写法，简化openLock()主要循环的代码实现
- 可采用双向BFS进一步提高效率
- 可采用启发式搜索
A*算法
这篇关于C刷题：LeetCode 752. 打开转盘锁 （中等） || BFS广搜详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理，增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单（Context Menu）显示中文？-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次，但有时会渲染两次是什么原因？-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件？-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务？-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程：轻松入门与应用指南
- 2024-12-20Excel数据导出实战：新手必学的简单教程
- 2024-12-20RBAC的权限实战：新手入门教程
