6.25_打开转盘锁_heapq(python)_HashMap(java)_char**(c的赋值)

本文主要是介绍6.25_打开转盘锁_heapq(python)_HashMap(java)_char**(c的赋值)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

6.25_打开转盘锁:

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

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

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

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

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

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

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1

提示：

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成

链接：https://leetcode-cn.com/problems/open-the-lock

1、java

import java.util.*;

class Solution {
    public static int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }

        Set<String> dead = new HashSet<>();
        for (String deadend : deadends) {
            dead.add(deadend);
        }
        if (dead.contains("0000")) {
            return -1;
        }

        int step = 0;
        Queue<String> queue = new LinkedList<String>();
        queue.offer("0000");
        Set<String> seen = new HashSet<String>();
        seen.add("0000");

        while (!queue.isEmpty()) {
            ++step;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                String status = queue.poll();
                for (String nextStatus : get(status)) {
                    if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
                        if (nextStatus.equals(target)) {
                            return step;
                        }
                        queue.offer(nextStatus);
                        seen.add(nextStatus);
                    }
                }
            }
        }

        return -1;
    }

    public static char numPrev(char x) {
        return x == '0' ? '9' : (char) (x - 1);
    }

    public static char numSucc(char x) {
        return x == '9' ? '0' : (char) (x + 1);
    }

    // 枚举 status 通过一次旋转得到的数字
    public static List<String> get(String status) {
        List<String> ret = new ArrayList<String>();
        char[] array = status.toCharArray();
        for (int i = 0; i < 4; ++i) {
            char num = array[i];
            array[i] = numPrev(num);
            ret.add(new String(array));
            array[i] = numSucc(num);
            ret.add(new String(array));
            array[i] = num;
        }
        return ret;
    }

    public static void main(String[] args) {
        String[] deadends = {"0201","0101","0102","1212","2002"};
        String target = "0202";
        System.out.println(openLock(deadends, target));
    }
}

View Code

// HashSet集合，contains
if (dead.contains("0000")) {
            return -1;
        }

Queue<String> queue = new LinkedList<String>();
// 添加元素
queue.offer("a");
// 遍历元素
for(String q : queue){
            System.out.println(q);
        }
// 返回第一个元素，并在队列中删除
queue.poll();
queue.element(); //返回第一个元素
queue.peek(); //返回第一个元素 


LinkedList<String> sites = new LinkedList<String>();
sites.add("Taobao");
// 使用 addFirst() 在头部添加元素
sites.addFirst("Wiki");
// 使用 addLast() 在尾部添加元素
sites.addLast("Wiki");
// 使用 removeFirst() 移除头部元素
sites.removeFirst();
// 使用 removeLast() 移除尾部元素
sites.removeLast();
// 使用 getFirst() 获取头部元素
System.out.println(sites.getFirst());
// 使用 getLast() 获取尾部元素
System.out.println(sites.getLast());
// 迭代元素
for (int size = sites.size(), i = 0; i < size; i++) {
            System.out.println(sites.get(i));
        }

// 创建 HashMap 对象 Sites
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
// 添加键值对
Sites.put(1, "Google");

// 使用 get(key) 方法来获取 key 对应的 value:
Sites.get(3)
// remove(key) 方法来删除 key 对应的键值对(key-value):
Sites.remove(4);
// 删除所有键值对(key-value)可以使用 clear 方法：
Sites.clear();
Sites.size();
// 输出 key 和 value
for (Integer i : Sites.keySet()) {
            System.out.println("key: " + i + " value: " + Sites.get(i));
        }
        // 返回所有 value 值
for(String value: Sites.values()) {
          // 输出每一个value
          System.out.print(value + ", ");
        }

2、c++

//#include "iostream"
//#include "vector"
//#include "unordered_set"
//#include "queue"
//using namespace std;
//
//class Solution {
//public:
//    int openLock(vector<string>& deadends, const string& target) {
//        if (target == "0000") {
//            return 0;
//        }
//
//        unordered_set<string> dead(deadends.begin(), deadends.end());
//        if (dead.count("0000")) {
//            return -1;
//        }
//
//        auto num_prev = [](char x) -> char {
//            return (x == '0' ? '9' : x - 1);
//        };
//        auto num_succ = [](char x) -> char {
//            return (x == '9' ? '0' : x + 1);
//        };
//
//        // 枚举 status 通过一次旋转得到的数字
//        auto get = [&](string& status) -> vector<string> {
//            vector<string> ret;
//            for (int i = 0; i < 4; ++i) {
//                char num = status[i];
//                status[i] = num_prev(num);
//                ret.push_back(status);
//                status[i] = num_succ(num);
//                ret.push_back(status);
//                status[i] = num;
//            }
//            return ret;
//        };
//
//        queue<pair<string, int>> q;
//        q.emplace("0000", 0);
//        unordered_set<string> seen = {"0000"};
//
//        while (!q.empty()) {
//            auto [status, step] = q.front();
//            q.pop();
//            for (auto&& next_status: get(status)) {
//                if (!seen.count(next_status) && !dead.count(next_status)) {
//                    if (next_status == target) {
//                        return step + 1;
//                    }
//                    q.emplace(next_status, step + 1);
//                    seen.insert(move(next_status));
//                }
//            }
//        }
//
//        return -1;
//    }
//};
//
//// 报错的，为啥？？
//int main() {
//    vector<string> deadends = {"0201","0101","0102","1212","2002"};
//    string target = "0202";
//    cout << Solution().openLock(deadends, target) << endl;
//}

#include "iostream"
#include "vector"
#include "unordered_set"
#include "queue"
using namespace std;

struct AStar {
    // 计算启发函数
    static int getH(const string& status, const string& target) {
        int ret = 0;
        for (int i = 0; i < 4; ++i) {
            int dist = abs(int(status[i]) - int(target[i]));
            ret += min(dist, 10 - dist);
        }
        return ret;
    };

    AStar(const string& status, const string& target, int g): status_{status}, g_{g}, h_{getH(status, target)} {
        f_ = g_ + h_;
    }

    bool operator< (const AStar& that) const {
        return f_ > that.f_;
    }

    string status_;
    int f_, g_, h_;
};

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if (target == "0000") {
            return 0;
        }

        unordered_set<string> dead(deadends.begin(), deadends.end());
        if (dead.count("0000")) {
            return -1;
        }

        auto num_prev = [](char x) -> char {
            return (x == '0' ? '9' : x - 1);
        };
        auto num_succ = [](char x) -> char {
            return (x == '9' ? '0' : x + 1);
        };

        auto get = [&](string& status) -> vector<string> {
            vector<string> ret;
            for (int i = 0; i < 4; ++i) {
                char num = status[i];
                status[i] = num_prev(num);
                ret.push_back(status);
                status[i] = num_succ(num);
                ret.push_back(status);
                status[i] = num;
            }
            return ret;
        };

        priority_queue<AStar> q;
        q.emplace("0000", target, 0);
        unordered_set<string> seen = {"0000"};

        while (!q.empty()) {
            AStar node = q.top();
            q.pop();
            for (auto&& next_status: get(node.status_)) {
                if (!seen.count(next_status) && !dead.count(next_status)) {
                    if (next_status == target) {
                        return node.g_ + 1;
                    }
                    q.emplace(next_status, target, node.g_ + 1);
                    seen.insert(move(next_status));
                }
            }
        }

        return -1;
    }
};

// 这个就可以运行!!
int main() {
    vector<string> deadends = {"0201","0101","0102","1212","2002"};
    string target = "0202";
    cout << Solution().openLock(deadends, target) << endl;
}

View Code

3、c

#include "stdio.h"
#include ".\lib\uthash-master\src\uthash.h" /* UT_hash_handle */

struct HashTable {
    char str[5];
    UT_hash_handle hh;
};

struct Node {
    char str[5];
    int val;
};

char num_prev(char x) {
    return (x == '0' ? '9' : x - 1);
}

char num_succ(char x) {
    return (x == '9' ? '0' : x + 1);
}

// 枚举 status 通过一次旋转得到的数字
char** getNextStatus(char* status, int* retSize) {
    char** ret = malloc(sizeof(char*) * 8);
    *retSize = 0;
    for (int i = 0; i < 4; ++i) {
        char num = status[i];
        status[i] = num_prev(num);
        ret[(*retSize)] = malloc(sizeof(char) * 5);
        strcpy(ret[(*retSize)++], status);
        status[i] = num_succ(num);
        ret[(*retSize)] = malloc(sizeof(char) * 5);
        strcpy(ret[(*retSize)++], status);
        status[i] = num;
    }
    return ret;
}

int openLock(char** deadends, int deadendsSize, char* target) {
    char str_0[5] = "0000";
    if (strcmp(target, str_0) == 0) {
        return 0;
    }
    struct HashTable* dead = NULL;
    struct HashTable* tmp;
    for (int i = 0; i < deadendsSize; i++) {
        HASH_FIND(hh, dead, deadends[i], sizeof(char) * 5, tmp);
        if (tmp == NULL) {
            tmp = malloc(sizeof(struct HashTable));
            strcpy(tmp->str, deadends[i]);
            HASH_ADD(hh, dead, str, sizeof(char) * 5, tmp);
        }
    }
    HASH_FIND(hh, dead, str_0, sizeof(char) * 5, tmp);

    if (tmp != NULL) {
        return -1;
    }

    struct Node q[10001];
    int left = 0, right = 0;
    strcpy(q[right].str, str_0);
    q[right++].val = 0;

    struct HashTable* seen = NULL;
    tmp = malloc(sizeof(struct HashTable));
    strcpy(tmp->str, str_0);
    HASH_ADD(hh, seen, str, sizeof(char) * 5, tmp);

    while (left < right) {
        char* status = q[left].str;
        int step = q[left++].val;
        int nextStatusSize;
        char** nextStatus = getNextStatus(status, &nextStatusSize);
        for (int i = 0; i < nextStatusSize; i++) {
            struct HashTable *tmp1, *tmp2;
            HASH_FIND(hh, dead, nextStatus[i], sizeof(char) * 5, tmp1);
            HASH_FIND(hh, seen, nextStatus[i], sizeof(char) * 5, tmp2);
            if (tmp1 == NULL && tmp2 == NULL) {
                if (strcmp(nextStatus[i], target) == 0) {
                    return step + 1;
                }
                strcpy(q[right].str, nextStatus[i]);
                q[right++].val = step + 1;
                tmp = malloc(sizeof(struct HashTable));
                strcpy(tmp->str, nextStatus[i]);
                HASH_ADD(hh, seen, str, sizeof(char) * 5, tmp);
            }
        }
    }

    return -1;
}

int main() {
    char* deadends[] = {"0201", "0101", "0102", "1212", "2002"};
    int deadendsSize = sizeof(deadends) / sizeof(deadends[0]);
    char* target = "0202";
    printf("%d ", openLock(deadends, deadendsSize, target));
}

View Code

4、python

import heapq # 堆
from typing import Generator, List


class AStar:
    # 计算启发函数
    @staticmethod
    def getH(status: str, target: str) -> int:
        ret = 0
        for i in range(4):
            dist = abs(int(status[i]) - int(target[i]))
            ret += min(dist, 10 - dist)
        return ret

    def __init__(self, status: str, target: str, g: str) -> None:
        self.status = status
        self.g = g
        self.h = AStar.getH(status, target)
        self.f = self.g + self.h

    def __lt__(self, other: "AStar") -> bool:
        return self.f < other.f

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if target == "0000":
            return 0

        dead = set(deadends)
        if "0000" in dead:
            return -1

        def num_prev(x: str) -> str:
            return "9" if x == "0" else str(int(x) - 1)

        def num_succ(x: str) -> str:
            return "0" if x == "9" else str(int(x) + 1)

        def get(status: str) -> Generator[str, None, None]:
            s = list(status)
            for i in range(4):
                num = s[i]
                s[i] = num_prev(num)
                yield "".join(s)
                s[i] = num_succ(num)
                yield "".join(s)
                s[i] = num

        q = [AStar("0000", target, 0)]
        seen = {"0000"}
        while q:
            node = heapq.heappop(q)
            for next_status in get(node.status):
                if next_status not in seen and next_status not in dead:
                    if next_status == target:
                        return node.g + 1
                    heapq.heappush(q, AStar(next_status, target, node.g + 1))
                    seen.add(next_status)

        return -1


if __name__ == "__main__":
    # openLock(self, deadends: List[str], target: str)
    deadends = ["0201", "0101", "0102", "1212", "2002"]
    target = "0202"
    print(Solution().openLock(deadends, target))

View Code

Python的富比较方法包括__lt__、__gt__分别表示：小于、大于，对应的操作运算符为:“<”、“>”。

当一个定义另一个未定义时，未定义的操作执行时会调用已经定义的方法求反。这个与__eq__和__ne__的关系还是有较大的不同。

heapq堆的常用方法：

import heapq

hList = []
# heapq.heappush(heap, item), heap为定义堆，item增加的元素
heapq.heappush(hList, 2)
print(hList)
# heapq.heapify(list), 将列表转换为堆
exampleList = [1,2,3,5,1,5,8,9,6]
print(exampleList)
heapq.heapify(exampleList) # 跟列表区别???
print(exampleList, type(exampleList))
# heapq.heappop(heap)，删除并返回最小值，
# 因为堆的特征是heap[0]永远是最小的元素，所以一般都是删除第一个元素。
print(heapq.heappop(exampleList))
print("heappop: ", exampleList)
# heapq.heapreplace(heap.item), 删除并返回最小元素值，添加新的元素值
print(heapq.heapreplace(exampleList, 99))
print("heapreplace: ", exampleList)
# heapq.heappushpop(list,item)
# 判断添加元素值与堆的第一个元素值对比；如果大，则删除并返回第一个元素，然后添加新元素值item.
# 如果小，则返回item.  原堆不变。
print(heapq.heappushpop(exampleList,6))
print("heappushpop：", exampleList)
# heapq.merge（…）,将多个堆合并
h = [1000]
heapq.merge(h,exampleList) # 不改变原来的列表
print("merge: ", h)
print("merge: ", exampleList)
for i in heapq.merge(h,exampleList):
    print(i,end=" ")
# heapq.nlargest(n,heap), 查询堆中的最大n个元素
print(heapq.nlargest(3,exampleList))

# heapq.nsmallest(n,heap),查询堆中的最小n个元素
print(heapq.nsmallest(3,exampleList))

# 使用heapq编写优先级队列
class PriorityQueue:
    def __init__(self):
        self.__queue = []
        self.__index = 0

    def push(self, item, priority):
        heapq.heappush(self.__queue, (-priority, self.__index, item))
        # 第一个参数：添加进的目标序列
        # 第二个参数：将一个元组作为整体添加进序列，目的是为了方便比较
        # 在priority相等的情况下，比较_index
        # priority为负数使得添加时按照优先级从大到小排序，因为堆排序的序列的第一个元素永远是最小的
        self.__index += 1

    def pop(self):
        # 返回按照-priority 和 _index 排序后的第一个元素(是一个元组)的最后一个元素(item)
        return heapq.heappop(self.__queue)[-1]



q = PriorityQueue()
q.push("bar", 2)
q.push("foo", 1)
q.push("gork", 3)
q.push("new", 1)
print(q.pop())
print(q.pop())
print(q.pop())
print(q.pop())

"""
gork  # 优先级最高
bar   # 优先级第二
foo   # 优先级与new相同，比较index，因为先加入，index比new小，所以排在前面
new
"""

# 回头用到再仔细研究队列

这篇关于6.25_打开转盘锁_heapq(python)_HashMap(java)_char**(c的赋值)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

6.25_打开转盘锁_heapq(python)_HashMap(java)_char**(c的赋值)

heapq堆的常用方法：

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯