中级农民
- 积分
- 172
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2021-10-12
- 最后登录
- 1970-1-1
|
我刚刚复习了这个题目: 752. Open the Lock
按照bfs 的框架写就行,triky 的地方是有写小细节、corner case 可能会忘记处理。
从current state 走向下一个state 的时候,原本对每个数字进行加一或者减一就行,但是这里有个特殊情况是 0 - 1 之后是9, 9 + 1 之后是0. 这个循环的部分需要特殊处理一下。第一遍写的时候因为没有处理这个特殊情况导致访问范围特别大,超时了。
问了一下chatgpt, 给出的办法是加10 再对10取余。
int next_digit = (digit + 10 + change[j]) % 10;
还有就是corner case: 如果target 就是起始点直接返回0,如果deadends 里有起始点,直接返回不能打开。
class Solution {
int change[2] = {1, -1};
public:
int openLock(vector<string>& deadends, string target) {
if (target == "0000") return 0;
unordered_set<string> dead_set;
for (int i = 0; i < deadends.size(); i++) {
dead_set.insert(deadends[i]);
}
if (dead_set.count("0000")) return -1;
// we need an unordered_set to record visited state of the 4 wheels.
unordered_set<string> visited;
visited.insert("0000");
queue<string> q;
q.push("0000");
int steps = 0;
while(!q.empty()) {
int len = q.size();
for (int k = 0; k < len; k++) {
string cur = q.front();
q.pop();
// visit all neighbors of the current state.
for (int i = 0; i < 4; i++) {
int digit = cur[i] - '0';
for (int j = 0; j < 2; j++) {
int next_digit = (digit + 10 + change[j]) % 10;
char next = next_digit + '0';
string str = cur;
str[i] = next;
// skip if found dead ends or visited before.
if (dead_set.count(str) || visited.count(str)) continue;
// if found the target, return the steps.
if (target == str) return ++steps;
// if not found the target, mark visited, enque the neighbor.
visited.insert(str);
q.push(str);
}
}
}
steps++;
}
return -1;
}
}; |
|