Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

队列&栈-02

题目:打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有 10 个数字:’0’到’9’。每个拨轮可以自由旋转:例如把’9’变为’0’,’0’变为’9’。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为’0000’,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回-1。

示例:

1
2
3
输入:deadends=["8888"],target="0009"
输出:1
解释:把最后一位反向旋转一次即可"0000"->"0009"。

提示:

  1. 死亡列表 deadends 的长度范围为[1,500]。
  2. 目标数字 target 不会在 deadends 之中。
  3. 每个 deadends 和 target 中的字符串的数字会在 10000 个可能的情况’0000’到’9999’中产生。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
int turnToNumber(string a){ // 将数字字符串转变为纯数字
int a = a[0]; // 个十百千,分别减去 '0' 变为数字。
int b = a[1];
int c = a[2];
int d = a[3];
int res = (a - '0') * 1000 + (b - '0') * 100 + (c - '0') * 10 + (d - '0');
return res;
}
int openLock(vector<string>& deadends, string target) { // 开锁
string input = "0000";
unordered_set<string> deadset(deadends.begin(),deadends.end()); // 无序set
if(deadset.count(input)) return -1; // 如果deadend内部有‘0000’,直接return -1
queue<string> q; // 定义队列q
bool visited[10000];
memset(visited,0,sizeof(visited)); // 标记是否被访问过
visited[0] = true;
q.push("0000");
int count = 0;
while(!q.empty()){ // 只要队列不为空,就一直索引
count++;
int size = q.size();
for(int i = 0; i < size;i++){ // 判断队列中的每一串数字
string s = q.front();
for(int i = 0; i < 4; i++){
for(auto step:{-1,1}){ // 都+1或-1,相当于一次 +1 一次 -1
string temp = s;
temp[i] = (temp[i]-'0' + step + 10) % 10 + '0';
if(temp == target) return count; // 如果是目标则返回count
if(!deadset.count(temp)&& visited[turnToNumber(temp)] == false){
q.push(temp); // 推入队列中
visited[turnToNumber(temp)] = true; // 标记为已经访问过
}
} // 若是deadend不做处理,不继续向下搜索,相当于绕过deadend
}
q.pop(); // q.front已经处理过,出列,更新q.front()
}
}
return -1;
}
};

memset 常用作初始化工作,void *memset(void *s, int ch, size_t n); 将 s 中当前位置后面的 n 个字节用 ch 替换并返回 s.
函数原型是 extern void *memset(void *buffer, int c, int count); buffer: 为指针或是数组,c: 是赋给 buffer 的值,count: 是 buffer 的长度。

官方 python 解答:看着挺简单,让人头大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
def openLock(self, deadends, target):
"""
:type deadends: List[str]
:type target: str
:rtype: int
"""
def neighbors(node):
for i in xrange(4):
x = int(node[i])
for d in (-1,1):
y = (x + d) % 10
yield node[:i]+str(y) + node[i+1:]
dead = set(deadends)
queue = collections.deque([('0000',0)])
seen = {'0000'}
while queue:
node, depth = queue.popleft()
if node == target: return depth
if node in dead: continue
for nei in neighbors(node):
if nei not in seen:
seen.add(nei)
queue.append((nei, depth+1))
return -1

完全平方数

给定正整数 n,找到若干个完全平方数(比如 1,4,9,16…)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

1
2
3
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:

1
2
3
输入:n = 13
输出:2
解释:13 = 4 + 9

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int numSquares(int n) {
if(n <= 0){ // 如果输入值 小于 0 返回。
return 0;
}
int ans = 0; // 记录步数
queue<int> Q; // 定义队列
Q.push(n); // 将目标结果输入队列进行搜索。
while(!Q.empty()){ // 只要队列不为空,就一直搜索
int Qsize = Q.size(); // 查看队列大小
for(int i = 0; i < Qsize; i++){ // 进行遍历
float temp = Q.front(); // temp是队列的第一个元素
Q.pop(); // 推出第一个元素
for(int i = sqrt(temp); i > 0; i--){ // 循环处理第一个元素,判断从大到小哪个可以是平方
if(temp == i*i){ // 如果相等,则结束
ans++;
return ans; // 步数加一,返回
}else{ // 如果不相等
Q.push(temp-i*i); // 去掉一个完全平方数后的值推入队列汇总。
}
}
}
ans++;
}
return 0;
}
};

看到 BFS 的题,脑子里知道怎么搞了,就是不知道从何入手。偶然看到了 labuladong 大神编写的 BFS 算法框架,摘过来,背就完事了。

BFS 的核心思想应该不难理解的,就是把一些问题抽象成图,从一个点开始,向四周开始扩散。一般来说,我们写 BFS 算法都是用「队列」这种数据结构,每次将一个节点周围的所有节点加入队列。

BFS 相对 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度比 DFS 大很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路

q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数

while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点:这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点:更新步数在这里 */
step++;
}
}

队列 q 就不说了,BFS 的核心数据结构;cur.adj()泛指 cur 相邻的节点,比如说二维数组中,cur 上下左右四面的位置就是相邻节点;
visited 的主要作用是防止走回头路,大部分时候都是必须的,但是像一般的二叉树结构,没有子节点到父节点的指针,不会走回头路就不需要 visited。

大概看完就是一种感觉,啊,这就是我要的,balabala 开始 。。。我真笨。。。

感谢开源让我们生活更美好。

声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~