查找是否存在给定移动的圆

Question

我在 HackerRank 上被问到一个与此类似的问题：

区别是F被G代替了（即G代表前进一步）

我实现了一种类似于已接受答案中描述的算法，但我没有通过一个测试用例。有人可以帮我找到错误吗？

static String checkIfCircleExists(String s) {
        int x = 0;
        int y = 0;
        int dir = 0;

        for (char c : s.toCharArray()) {
            switch (c) {
                case 'G':
                    switch (dir) {
                        case 0:
                            y++;
                            break;
                        case 1:
                            x++;
                            break;
                        case 2:
                            y--;
                            break;
                        case 3:
                            x--;
                            break;
                    }
                    break;
                case 'L':
                    dir = Math.abs((dir - 1) % 4);
                    break;
                case 'R':
                    dir = Math.abs((dir + 1) % 4);
                    break;
            }
        }

        if (x == 0 && y == 0) {
            return "YES";
        }
        return "NO";
    }

编辑

这是一个辅助方法。此辅助方法的输入是原始输入字符串与原始输入字符串的三个副本连接而成。例如，对于输入 "G"，"GGGG" 将传递到此助手中。

Answer 1

代码 (dir - 1) % 4 在您的语言中是否按预期运行？

如果没有，替换为(dir + 3) % 4

问题编辑后不是实际的，但可能有助于减少运行时间：

请注意，移动在两种情况下受到限制：

最终位移为零（您的解决方案检查这种情况）
最终方向与初始方向不同（在本例中对象 returns 在两轮或四轮后处于初始位置）

你似乎忽略了第二个。

Answer 2

static String[] doesCircleExist(String[] commands) {

    int initialX = 0;
    int initialY = 0;

    int x = 0;
    int y = 0;
    String direction = "north";
    ArrayList<String> res = new ArrayList<String>();
    for (int i = 0; i < commands.length; i++) {
        for (int j = 0; j < commands[i].length(); j++) {
            if (direction.equals("north")) {
                if (commands[i].charAt(j) == 'G') {
                    y++;
                } else if (commands[i].charAt(j) == 'L') {
                    direction = "west";
                } else if (commands[i].charAt(j) == 'R') {
                    direction = "east";
                } else {
                    System.out.println("Wrong command");
                }
            } else if (direction.equals("east")) {
                if (commands[i].charAt(j) == 'G') {
                    x++;
                } else if (commands[i].charAt(j) == 'L') {
                    direction = "north";
                } else if (commands[i].charAt(j) == 'R') {
                    direction = "south";
                } else {
                    System.out.println("Wrong command");
                }
            } else if (direction.equals("south")) {
                if (commands[i].charAt(j) == 'G') {
                    y--;
                } else if (commands[i].charAt(j) == 'L') {
                    direction = "east";
                } else if (commands[i].charAt(j) == 'R') {
                    direction = "west";
                } else {
                    System.out.println("Wrong command");
                }
            } else if (direction.equals("west")) {
                if (commands[i].charAt(j) == 'G') {
                    x--;
                } else if (commands[i].charAt(j) == 'L') {
                    direction = "south";
                } else if (commands[i].charAt(j) == 'R') {
                    direction = "north";
                } else {
                    System.out.println("Wrong command");
                }
            }
        }

        if (direction.equals("north")
                && (((x - initialX) * (x - initialX) + (y - initialY) * (y - initialY)) > 0)) {
            res.add("NO");
        } else {
            res.add("YES");
        }
    }
    return res.toArray((new String[res.size()]));

}

查找是否存在给定移动的圆

Find if there exists a circle given moves

java

algorithm

geometry

computational-geometry