NC363. 开锁
描述
示例1
输入:
["9999","9998","1000"],"1001"
输出:
2
C 解法, 执行用时: 4ms, 内存消耗: 544KB, 提交时间: 2022-06-27
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param vec string字符串一维数组
* @param vecLen int vec数组长度
* @param tar string字符串
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int min(int a, int b) {
return a > b ? b : a;
}
int strToInt(char *str) {
int sLen = strlen(str), sum = 0;
for (int i = 0; i < sLen; i++) {
sum = sum * 10 + str[i] - '0';
}
return sum;
}
void bfs(int forbid[10000], int visited[10000], int start, int target, int pathLen, int *minLen) {
int queue[20000] = { start, -1 }, front = 0, rear = 2, level = 0;
visited[start] = 1;
while(front < rear) {
int c = queue[front++];
if (c == -1) {
if (front == rear) {
break;
}
queue[rear++] = -1;
level++;
} else {
if (c == target) {
*minLen = level;
break;
}
int next[8], index = 0, mod, x = c, suffix = 1;
while(suffix <= 1000) {
mod = x % 10;
x = x / 10;
if (mod == 0) {
next[index++] = c + 1 * suffix;
next[index++] = c + 9 * suffix;
} else if (mod == 9) {
next[index++] = c - 1 * suffix;
next[index++] = c - 9 * suffix;
} else {
next[index++] = c - 1 * suffix;
next[index++] = c + 1 * suffix;
}
suffix *= 10;
}
for (int i = 0; i < 8; i++) {
if (visited[next[i]] == 0 && forbid[next[i]] == 0) {
queue[rear++] = next[i];
visited[next[i]] = 1;
}
}
}
}
}
int open(char** vec, int vecLen, char* tar ) {
int minLen = 10000;
int visited[10000] = { 0 }, forbid[10000] = { 0 }, target = strToInt(tar);
for (int i = 0; i < vecLen; i++) {
forbid[strToInt(vec[i])] = 1;
}
if (forbid[target] == 1) {
return -1;
}
bfs(forbid, visited, 0, target, 0, &minLen);
if (minLen == 10000) {
return -1;
} else {
return minLen;
}
}
C 解法, 执行用时: 4ms, 内存消耗: 556KB, 提交时间: 2022-07-08
int min(int a, int b) {return a > b ? b : a;}
int strToInt(char *str) {
int sLen = strlen(str), sum = 0;
for (int i = 0; i < sLen; i++) {
sum = sum * 10 + str[i] - '0';
}
return sum;
}
void bfs(int f[10000], int v[10000], int start, int t, int pathLen, int *minLen) {
int queue[20000] = { start, -1 }, front = 0, rear = 2, level = 0;
v[start] = 1;
while(front < rear) {
int c = queue[front++];
if (c == -1) {
if (front == rear) {
break;
}
queue[rear++] = -1;
level++;
} else {
if (c == t) {
*minLen = level;
break;
}
int next[8], index = 0, mod, x = c, suffix = 1;
while(suffix <= 1000) {
mod = x % 10;
x = x / 10;
if (mod == 0) {
next[index++] = c + 1 * suffix;
next[index++] = c + 9 * suffix;
} else if (mod == 9) {
next[index++] = c - 1 * suffix;
next[index++] = c - 9 * suffix;
} else {
next[index++] = c - 1 * suffix;
next[index++] = c + 1 * suffix;
}
suffix *= 10;
}
for (int i = 0; i < 8; i++) {
if (v[next[i]] == 0 && f[next[i]] == 0) {
queue[rear++] = next[i];
v[next[i]] = 1;
}
}
}
}
}
int open(char** vec, int vecLen, char* tar ) {
int minLen = 10000;
int v[10000] = { 0 }, f[10000] = { 0 }, t = strToInt(tar);
for (int i = 0; i < vecLen; i++) {
f[strToInt(vec[i])] = 1;
}
if (f[t] == 1) {
return -1;
}
bfs(f, v, 0, t, 0, &minLen);
if (minLen == 10000) {
return -1;
} else {
return minLen;
}
}
C++ 解法, 执行用时: 7ms, 内存消耗: 776KB, 提交时间: 2022-07-08
class Solution {
public:
string M(string s, int j) {
if (s[j] == '9') s[j] = '0';
else s[j] = (int)s[j] + 1;
return s;
}
string m(string s, int j) {
if (s[j] == '0') s[j] = '9';
else s[j] = (int)s[j] - 1;
return s;
}
int open(vector<string>& vec, string tar) {
int n = tar.length();
int step = 0;
unordered_set<string> a, b;
unordered_set<string> v;
for (auto dead : vec) v.insert(dead);
a.insert("0000");
b.insert(tar);
while (!a.empty() && !b.empty()) {
unordered_set<string> t;
for (string i : a) {
if (v.count(i)) continue;
if (b.count(i)) return step;
v.insert(i);
for (int j = 0; j < n; j++) {
string H = M(i, j);
if (!v.count(H)) t.insert(H);
string h = m(i, j);
if (!v.count(h)) t.insert(h);
}
}
a = b;
b = t;
step++;
}
return -1;
}
};
C++ 解法, 执行用时: 7ms, 内存消耗: 784KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param vec string字符串vector
* @param tar string字符串
* @return int整型
*/
string M(string s,int j)
{
if(s[j]=='9')
s[j]='0';
else
s[j]=(int)s[j]+1;
return s;
}
string m(string s,int j)
{
if(s[j]=='0')
s[j]='9';
else
s[j]=(int)s[j]-1;
return s;
}
int open(vector<string>& vec, string tar) {
// write code
int n=tar.length();
int step=0;
unordered_set<string> a,b;
unordered_set<string> v;
for(auto dead:vec)
v.insert(dead);
a.insert("0000");
b.insert(tar);
while(!a.empty()&&!b.empty())
{
unordered_set<string> t;
for(string i:a)
{
if(v.count(i))
continue;
if(b.count(i))
return step;
v.insert(i);
for(int j=0;j<n;j++)
{
string H=M(i,j);
if(!v.count(H))
t.insert(H);
string h=m(i,j);
if(!v.count(h))
t.insert(h);
}
}
a=b;
b=t;
step++;
}
return -1;
}
};
Go 解法, 执行用时: 7ms, 内存消耗: 1416KB, 提交时间: 2022-07-08
package main
func open(vec []string, tar string) int {
a := make(map[string]bool)
b := make(map[string]bool)
v := make(map[string]bool)
dead := make(map[string]bool)
for _, num := range vec {
dead[num] = true
}
a["0000"] = true
b[tar] = true
step := 0
v["0000"] = true
v[tar] = true
for len(a) > 0 && len(b) > 0 {
if len(a) > len(b) {
a, b = b, a
}
t := make(map[string]bool)
for i, _ := range a {
if dead[i] {
continue
}
if b[i] {
return step
}
v[i] = true
for j := 0; j < 4; j++ {
H:= M(i, j)
if !v[H] {
t[H] = true
}
h:= m(i, j)
if !v[h] {
t[h] = true
}
}
}
a = b
b = t
step++
}
return -1
}
func M(s string, j int) string {
z := []byte(s)
if z[j] == '9' {
z[j] = '0'
} else {
z[j] = z[j] + 1
}
return string(z)
}
func m(s string, j int) string {
z := []byte(s)
if z[j] == '0' {
z[j] = '9'
} else {
z[j] = z[j] - 1
}
return string(z)
}