首页 > 代码库 > [JAVA][ZOJ 1004][Anagrams by Stack]

[JAVA][ZOJ 1004][Anagrams by Stack]

2024-08-04 12:15:58   214人阅读

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. import java.io.BufferedInputStream;  
  2. import java.util.Scanner;  
  3.   
  4. public class Main {  
  5.     static String start;// record the first str  
  6.     static String end;// record the rearranged str  
  7.   
  8.     public static void dfs(char[] stack, char[] sequence, int posInStart, int posInEnd, int posInStack) {  
  9.         if (posInStart + posInEnd == start.length() * 2) {// if all the letter has been rearranged  
  10.             for (int i = 0; i < sequence.length; i++) {  
  11.                 System.out.print(sequence[i] + " ");// output the sequence  
  12.             }  
  13.             System.out.println();  
  14.         }  
  15.         if (posInStart < start.length()) {  
  16.             sequence[posInStart + posInEnd] = ‘i‘;  
  17.             stack[++posInStack] = start.charAt(posInStart);// push in  
  18.             dfs(stack, sequence, posInStart + 1, posInEnd, posInStack);  
  19.             posInStack--;// pop out  
  20.         }  
  21.         if (posInStack >= 0 && posInEnd < end.length() && stack[posInStack] == end.charAt(posInEnd)) {// pop out  
  22.             sequence[posInStart + posInEnd] = ‘o‘;  
  23.             posInStack--;// pop out  
  24.             dfs(stack, sequence, posInStart, posInEnd + 1, posInStack);  
  25.             stack[++posInStack] = end.charAt(posInEnd);  
  26.         }  
  27.     }  
  28.   
  29.     public static void main(String[] args) {  
  30.         Scanner sc = new Scanner(new BufferedInputStream(System.in));  
  31.         while (sc.hasNext()) {  
  32.             start = sc.next();  
  33.             end = sc.next();  
  34.             char[] stack = new char[start.length() * 2];// use array as the stack  
  35.             char[] sequence = new char[start.length() * 2];// record the operation seq, it will have (start.length() * 2) times operations  
  36.             System.out.println("[");  
  37.             dfs(stack, sequence, 0, 0, -1);  
  38.             System.out.println("]");  
  39.         }  
  40.     }  
  41. }  





最近写的几道题都用到了dfs，用数组代替栈的使用，控制好stack数字下标就没什么大问题，难得一次AC

[JAVA][ZOJ 1004][Anagrams by Stack]


联系
我们