Wie werden die Koordinaten der gegebenen Zeichenfolge gedruckt?

Question

Ich habe diese Frage in einem der Interviews, die ich besucht habe, und ich bin ratlos.

Bei einer Eingabezeichenfolge wie der folgenden müssen die Koordinaten gedruckt werden, die beim letzten Zeichen der Zeichenfolge erhalten wurden.

Anfahrt:

L-Left 
U-Up 
R-Right 
D-Down 
X-Delete the previous move. 

Annahme:

start with the coordinates (0,0) 

Hier ist, wie die Ausgabe zu berechnen.

Bei Eingabe:

3L5UR2DDX2LR 

uns Schritt für Schritt tun lassen.

3L - Move 3 points to the left of (0,0) i.e (-3,0) 

5U- Move 5 points upper to (-3,0) i.e (-3,5) 

R - Move 1 point to the right of (-3,5) i.e (-2,5) 

2D - Move 2 points down to (-2,5) i.e (-2,3) 

D - Move 1 point further down i.e (-2,2) 

x - Delete the previous move.(current value is (-2,3)) 

2L -Move 2 left to (-2,3) i.e(-4,3) 

R- Move 1 Right to (-4,3) i.e (-3,3) 

Der endgültige Ausgang ist (-3,3)

Ich versuche es jedoch in Code zu setzen, ich bin nicht einen Ausgangspunkt bekommen, wie this.Any Hilfe brechen sehr geschätzt werden würde .

Answer 1

würde ich das Problem als Anerkennung der Bewegungsbefehle sehen, von denen jeder einen optionalen Faktor hat (wie viele Stufen) und eine obligatorische Richtung. Wenn der Faktor weggelassen wird, bedeutet dies tatsächlich den Wert 1.

So können diese als Muster in regulären Ausdruck dargestellt werden:

String regex = "(?<factor>\\d*)" 
      + "(?<dir>[LURDX])"; 

Sobald dies geschehen ist, müssen wir nur noch die Richtung zum entsprechenden Änderung dy in Koordinaten (dx, zur Karte), und wenden Sie dann die Änderungen an (multipliziert mit dem Wert des Faktors), während wir die Verschiebeanweisungen in einer while-Schleife der Regex-Übereinstimmung verarbeiten.

Beachten Sie, dass X ein Sonderfall ist, der immer gehandhabt werden kann durch die letzte Position als lastX und lastY erinnern.

Das folgende ist meine Implementierung:

import java.util.regex.Matcher; 
import java.util.regex.Pattern; 

public class Walk { 
    enum Move { 
     L (-1, 0) 
     , U (0, 1) 
     , R (1, 0) 
     , D (0, -1) 
     , X (0, 0) 
     ; 
     private int dx; 
     private int dy; 
     private Move(int dx, int dy) { 
      this.dx = dx; 
      this.dy = dy; 
     } 
     public int getDx() { 
      return dx; 
     } 
     public int getDy() { 
      return dy; 
     } 

    } 

    public static void main(String[] args) { 
     String input = "3L5UR2DDX2LR"; 
     String regex = "(?<factor>\\d*)" 
       + "(?<dir>[LURDX])"; 
     Pattern p = Pattern.compile(regex); 
     Matcher m = p.matcher(input); 
     int x = 0; 
     int y = 0; 
     int lastX = 0; 
     int lastY = 0; 
     while (m.find()) { 
      String factorString = m.group("factor"); 
      int factor; 
      if (factorString.length()==0) { 
       factor=1; 
      } else { 
       factor=Integer.parseInt(factorString); 
      } 
      String dirString = m.group("dir"); 
      Move move = Move.valueOf(dirString); 
      System.out.format("(%d,%d) last was (%d, %d) %d %s -> " 
        , x, y 
        , lastX, lastY 
        , factor, move.name()); 
      if (move==Move.X) { 
       x = lastX; 
       y = lastY; 
      } else { 
       lastX = x; 
       lastY = y; 
       x += factor * move.getDx(); 
       y += factor * move.getDy(); 
      }   
      System.out.format("(%d,%d)%n", x, y); 
     } 
     System.out.format("finally arrive at (%d,%d)%n", x, y); 

    } 

} 

Die Ausgabe dieses Programms ist dies:

(0,0) last was (0, 0) 3 L -> (-3,0) 
(-3,0) last was (0, 0) 5 U -> (-3,5) 
(-3,5) last was (-3, 0) 1 R -> (-2,5) 
(-2,5) last was (-3, 5) 2 D -> (-2,3) 
(-2,3) last was (-2, 5) 1 D -> (-2,2) 
(-2,2) last was (-2, 3) 1 X -> (-2,3) 
(-2,3) last was (-2, 3) 2 L -> (-4,3) 
(-4,3) last was (-2, 3) 1 R -> (-3,3) 
finally arrive at (-3,3) 

Answer 2

Sie können Folgendes tun. Dies ist der Algorithmus, den ich verwenden würde.

1. Eingabezeichenfolge übernehmen.
2. Übergeben Sie es an eine Parser-Methode, die ein Array von Token zurückgibt. Jedes Token beginnt mit einer Zahl und endet mit einem Buchstaben. Wenn zwei Buchstaben aufeinander folgen, werden sie als zwei verschiedene Token betrachtet. X ist ein unabhängiges Token.
3. Übergeben Sie das Token-Array an eine Berechnungsmethode, die die endgültigen Koordinaten zurückgibt. Lesen Sie in der Methode calculate das in Punkt 2 zurückgegebene Array. Nachdem Sie alle Token gelesen haben, führen Sie die erforderliche Operation für die Koordinaten aus.

Entwerfen Sie die Koordinatenklasse wie. Dies wird Ihnen helfen, Ihr Problem einfach zu lösen.

public class Point { 

    private int x; 
    private int y; 

    public int getX() { 
     return x; 
    } 
    public void setX(int x) { 
     this.x = x; 
    } 
    public int getY() { 
     return y; 
    } 
    public void setY(int y) { 
     this.y = y; 
    } 

    public int modifyX(int xDiff){ 
     return (getX()+xDiff); 
    } 

    public int modifyY(int yDiff){ 
     return (getY()+yDiff); 
    } 

}