JudgeRouteCircle [source code]

public class JudgeRouteCircle {
static
/******************************************************************************/
public class Solution {
    // static class Point {
    //     int x;
    //     int y;

    //     public Point(int x, int y){ this.x = x; this.y = y; }

    //     public StringtoString() {return "(" + x ", " + y + ")"; }
    // }

    public boolean judgeCircle(String moves) {
        char[] chs = moves.toCharArray();
        if (chs.length < 2 || chs.length % 2 == 1)
            return false;
        int x = 0, y = 0;
        for (char c : chs) {
            switch (c) {
                case 'L': x--; break;
                case 'R': x++; break;
                case 'U': y++; break;
                case 'D': y--; break;
                default: break;
            }
        }
        return x == 0 && y == 0;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        JudgeRouteCircle.Solution tester = new JudgeRouteCircle.Solution();
    }
}

这个貌似就是之前地里看到的亚麻的"东南西北"那道题的面经; 当时那个人给出的做法是一个set, 我觉得这个题用一个类似HashTable的做法也可以? 甚至说, 可以用一个hashing的思路来做? 不过可能要浪费很多的空间就是了;

而且用hashing来记录的方式有一个好处, 就是当时亚麻上面看到的那个Follow-Up, 也就是要区分在重复的位置是否是同方向, 这个也很好判断了, 而不用重新封装多一个变量; //这个Follow-Up可以rephrase一下: 判断这个重复点是否是corner.

注意一个问题, 如果用set来做, set的element不能指望直接用一个array来做:

java> s.add(new int[]{0,1})  
java.lang.Boolean res1 = true  
java> s  
java.util.Set<int[]> s = [[I@421eba45]  
java> s.add(new int[]{0,1})  
java.lang.Boolean res2 = true  
java> s  
java.util.Set<int[]> s = [[I@20104a72, [I@421eba45]

我觉得还是先用set的做法来写一个, set的做法感觉很多小细节我还是不清楚, 比如就算自己定义一个class来当point, 这个class是否需要实现equals?

另外, 关于int array的这个compare/equality的问题, 在HashMap里面好像也存在:

java> m.put(new int[]{0,1}, 1)  
java.lang.Object res4 = null  
java> m  
java.util.Map<int[], java.lang.Integer> m = {[I@f42ea3b=1}  
java> m.put(new int[]{0,1}, 2)  
java.lang.Object res5 = null  
java> m  
java.util.Map<int[], java.lang.Integer> m = {[I@1837d5f1=2, [I@f42ea3b=1}

这个在StackOverflow上面有所讨论:

You can't. arrays use the default identity-based Object.hashCode() implementation and there's no way you can override that. Don't use Arrays as keys in a HashMap / HashSet!
Use a Set of Lists instead.

这么一说好像也没多复杂? 而且如果list可以用, 那自己定义的class肯定也可以吧? 不过好像还是没有回答是否需要override equals的问题;

在StackOverflow上面也有类似的讨论:

From Object in one of the JVM implementations:

public boolean equals(Object object) {  
    return this == object;  
}  

public int hashCode() {  
    return VMMemoryManager.getIdentityHashCode(this);  
}

In both cases it's just comparing the memory addresses of the objects in question.

所以好像要自己实现一下equals;

发现一个问题, 好像这里这个问题实际上要实现的并不是我想的那个问题? 这里题目意思好像只要判断是否回到原点就行了? 那这个问题好蠢. //这个问题比我想的还要蠢, 不仅是只判断原点, 而且是只判断最后的一个位置是否是原点;

TODO: 实现亚马逊这个题目, 包括"是否是corner"的Follow-Up;

最后速度是13ms (90%), 没啥好说的这个题目. 一个小优化就是长度(move个数)是奇数的时候肯定是FALSE;

discussion一个解法:

def judgeCircle(self, moves):  
    c = collections.Counter(moves)  
    return c['L'] == c['R'] and c['U'] == c['D']

所以这个问题本身很简单, 所以其实也就随便做了, 他这个也是一种思路;

Problem Description

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:

Input: "UD"  
Output: true

Example 2:

Input: "LL"  
Output: false

Difficulty:Easy
Total Accepted:6.2K
Total Submissions:8.6K
Contributor: maxsteel
Companies
google
Related Topics
string
Similar Questions
Friend Circles

Problem Description

这个是我发帖在discussion上面的Follow-Up:

The problem itself is trivial. I know of a similar question that got asked in an Amazon intern interview. Here are some relevant follow-ups (though not so hard either) (not that all of them actually got asked in the interview)

• Can you tell whether the robot will return to (0,0) after any move of the sequence of moves rather than just the end?
• Can you tell whether the robot will ever repeat to any point after any move of the sequence?
  • Can you tell whether this repeating point is a corner of the circle or not?
  • What if we precludes lines like UUDD from the definition of "circle"?

Please inform me if any of these followups seems unreasonable. I can only recall these vaguely, based on somebody else's recount in the first place, so mistakes might occur. I don't have code for them, but I think most of these followups are doable and still within the ballpark of "easy" problems.