C/C++教程
C刷题：LeetCode 752. 打开转盘锁 （中等） || BFS广搜详解
本文主要是介绍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广搜详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
