英文:
Open the Lock - BFS Application
问题
class Solution {
Queue<String> queue = new LinkedList<String>();
HashSet<String> deads = new HashSet<String>();
public int openLock(String[] deadends, String target) {
for(int i = 0; i < deadends.length; i++){
deads.add(deadends[i]);
}
if(deads.contains("0000")) return -1;
int level = bfs("0000", target);
return level;
}
public int bfs(String start, String target){
int level = 0;
queue.add(start); // add the start to the queue
deads.add(start);
while(!queue.isEmpty()){
int groupSize = queue.size();
while(groupSize > 0){
String current = queue.poll();
if(current.equals(target)) return level;
for(int i = 0; i < current.length(); i++){
char c = current.charAt(i);
char temp = c;
if(c == '9'){
c = '0';
temp = c;
}else{
c++;
}
String upString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(upString)){
queue.add(upString);
deads.add(upString);
}
c = temp;
if(c == '0'){
c = '9';
} else {
c--;
}
String downString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(downString)){
queue.add(downString);
deads.add(downString);
}
}
groupSize = groupSize - 1;
}
level = level + 1;
}
return -1;
}
}
英文:
I have just learned the BFS algorithm and I am trying to apply the BFS algorithm to solve the leetcode problem here Open the Lock
My algorithm works for some usecases and outputs a wrong answer for the others. Can anyone help me understand what I am missing?
Thanks in advance
class Solution {
Queue<String> queue = new LinkedList<String>();
HashSet<String> deads = new HashSet<String>();
public int openLock(String[] deadends, String target) {
for(int i = 0; i < deadends.length; i++){
deads.add(deadends[i]);
}
if(deads.contains("0000"))return -1;
int level = bfs("0000", target);
return level;
}
public int bfs(String start, String target){
int level = 0;
queue.add(start); // add the start to the queue
deads.add(start);
while(!queue.isEmpty()){
int groupSize = queue.size();
while(groupSize >0){
String current = queue.poll();
if(current.equals(target)) return level;
for(int i = 0; i < current.length(); i++){
char c = current.charAt(i);
char temp = c;
if( c == '9'){
c = '0';
temp = c;
}else{
c++;
}
String upString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(upString)){
queue.add(upString);
deads.add(upString);
}
c = temp;
if( c == '0'){
c = '9';
}
else{
c--;
}
String downString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(downString)){
queue.add(downString);
deads.add(downString);
}
}
groupSize = groupSize - 1;
}
level = level + 1;
}
return -1;
}
}
答案1
得分: 3
以下是翻译好的内容：
不太确定算法可能出了什么问题，我觉得看起来还挺好的，可能只是需要修复一些小问题。
几乎相同的方法，只是我们会在Java中使用三个集合（Sets）来解决这个问题：
public final class Solution {
public static final int openLock(
final String[] deadends,
final String target
) {
Set<String> startSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
startSet.add("0000");
endSet.add(target);
int minTurns = 0;
Set<String> tempSet;
while (!startSet.isEmpty() && !endSet.isEmpty()) {
if (startSet.size() > endSet.size()) {
tempSet = startSet;
startSet = endSet;
endSet = tempSet;
}
tempSet = new HashSet<>();
for (String start : startSet) {
if (endSet.contains(start)) {
return minTurns;
}
if (deadSet.contains(start)) {
continue;
}
deadSet.add(start);
StringBuilder startSB = new StringBuilder(start);
for (int i = 0; i < 4; i++) {
final char character = startSB.charAt(i);
String s1 = startSB.substring(0, i) + (character == '9' ? 0 : character - '0' + 1) + startSB.substring(i + 1);
String s2 = startSB.substring(0, i) + (character == '0' ? 9 : character - '0' - 1) + startSB.substring(i + 1);
if (!deadSet.contains(s1)) {
tempSet.add(s1);
}
if (!deadSet.contains(s2)) {
tempSet.add(s2);
}
}
}
minTurns++;
startSet = tempSet;
}
return -1;
}
}
好的！这是LeetCode的广度优先搜索（BFS）解法，你可以根据这个找出答案：
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet();
for (String d: deadends) dead.add(d);
Queue<String> queue = new LinkedList();
queue.offer("0000");
queue.offer(null);
Set<String> seen = new HashSet();
seen.add("0000");
int depth = 0;
while (!queue.isEmpty()) {
String node = queue.poll();
if (node == null) {
depth++;
if (queue.peek() != null)
queue.offer(null);
} else if (node.equals(target)) {
return depth;
} else if (!dead.contains(node)) {
for (int i = 0; i < 4; ++i) {
for (int d = -1; d <= 1; d += 2) {
int y = ((node.charAt(i) - '0') + d + 10) % 10;
String nei = node.substring(0, i) + ("" + y) + node.substring(i+1);
if (!seen.contains(nei)) {
seen.add(nei);
queue.offer(nei);
}
}
}
}
}
return -1;
}
}
看起来他们为这个问题添加了新的测试用例。
参考资料：
英文:
Not really sure what might be wrong with your algorithm, looks pretty OK to me, might be something small that needs to be fixed.
Almost the same method, except we'd be using three Sets to solve the problem in Java:
public final class Solution {
public static final int openLock(
final String[] deadends,
final String target
) {
Set<String> startSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
startSet.add("0000");
endSet.add(target);
int minTurns = 0;
Set<String> tempSet;
while (!startSet.isEmpty() && !endSet.isEmpty()) {
if (startSet.size() > endSet.size()) {
tempSet = startSet;
startSet = endSet;
endSet = tempSet;
}
tempSet = new HashSet<>();
for (String start : startSet) {
if (endSet.contains(start)) {
return minTurns;
}
if (deadSet.contains(start)) {
continue;
}
deadSet.add(start);
StringBuilder startSB = new StringBuilder(start);
for (int i = 0; i < 4; i++) {
final char character = startSB.charAt(i);
String s1 = startSB.substring(0, i) + (character == '9' ? 0 : character - '0' + 1) + startSB.substring(i + 1);
String s2 = startSB.substring(0, i) + (character == '0' ? 9 : character - '0' - 1) + startSB.substring(i + 1);
if (!deadSet.contains(s1)) {
tempSet.add(s1);
}
if (!deadSet.contains(s2)) {
tempSet.add(s2);
}
}
}
minTurns++;
startSet = tempSet;
}
return -1;
}
}
OK! Here is LeetCode's BFS solution, based on which you can figure it out:
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet();
for (String d: deadends) dead.add(d);
Queue<String> queue = new LinkedList();
queue.offer("0000");
queue.offer(null);
Set<String> seen = new HashSet();
seen.add("0000");
int depth = 0;
while (!queue.isEmpty()) {
String node = queue.poll();
if (node == null) {
depth++;
if (queue.peek() != null)
queue.offer(null);
} else if (node.equals(target)) {
return depth;
} else if (!dead.contains(node)) {
for (int i = 0; i < 4; ++i) {
for (int d = -1; d <= 1; d += 2) {
int y = ((node.charAt(i) - '0') + d + 10) % 10;
String nei = node.substring(0, i) + ("" + y) + node.substring(i+1);
if (!seen.contains(nei)) {
seen.add(nei);
queue.offer(nei);
}
}
}
}
}
return -1;
}
}
It seems that they have added new test cases for this problem.
References
答案2
得分: 0
class Solution {
Queue<String> queue = new LinkedList<String>();
HashSet<String> deads = new HashSet<String>();
public int openLock(String[] deadends, String target) {
for(int i = 0; i < deadends.length; i++){
deads.add(deadends[i]);
}
if(deads.contains("0000")) return -1;
int level = bfs("0000", target);
return level;
}
public int bfs(String start, String target){
int level = 0;
queue.add(start); // add the start to the queue
deads.add(start);
while(!queue.isEmpty()){
int groupSize = queue.size();
while(groupSize > 0){
String current = queue.poll();
if(current.equals(target)) return level;
for(int i = 0; i < current.length(); i++){
char c = current.charAt(i);
char temp = c;
if(c == '9'){
c = '0';
temp = c; // THIS LINE IS THE ISSUE. REMOVING IT HELPED!!!!
}else{
c++;
}
String upString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(upString)){
queue.add(upString);
deads.add(upString);
}
c = temp;
if(c == '0'){
c = '9';
}else{
c--;
}
String downString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(downString)){
queue.add(downString);
deads.add(downString);
}
}
groupSize = groupSize - 1;
}
level = level + 1;
}
return -1;
}
}
英文:
class Solution {
Queue<String> queue = new LinkedList<String>();
HashSet<String> deads = new HashSet<String>();
public int openLock(String[] deadends, String target) {
for(int i = 0; i < deadends.length; i++){
deads.add(deadends[i]);
}
if(deads.contains("0000"))return -1;
int level = bfs("0000", target);
return level;
}
public int bfs(String start, String target){
int level = 0;
queue.add(start); // add the start to the queue
deads.add(start);
while(!queue.isEmpty()){
int groupSize = queue.size();
while(groupSize >0){
String current = queue.poll();
if(current.equals(target)) return level;
for(int i = 0; i < current.length(); i++){
char c = current.charAt(i);
char temp = c;
if( c == '9'){
c = '0';
temp = c; // THIS LINE IS THE ISSUE. REMOVING IT HELPED!!!!
}else{
c++;
}
String upString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(upString)){
queue.add(upString);
deads.add(upString);
}
c = temp;
if( c == '0'){
c = '9';
}
else{
c--;
}
String downString = current.substring(0, i) + c + current.substring(i + 1);
if(!deads.contains(downString)){
queue.add(downString);
deads.add(downString);
}
}
groupSize = groupSize - 1;
}
level = level + 1;
}
return -1;
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论