队列&栈-02

题目：打开转盘锁

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

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

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

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

示例：

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

提示:

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

代码如下(C++)：

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 解答:看着挺简单，让人头大。

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:

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2:

输入：n = 13
输出：2
解释：13 = 4 + 9

代码如下(C++)：

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 大很多。

// 计算从起点 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 开始 。。。我真笨。。。

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

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