[Leetcode][第657题][JAVA][机器人能否返回原点][数组][HashMap]

Love The Way You Lie 2022-12-01 15:53 116阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

遍历方向 看是否回到原点 或者 “上下” “左右”两个方向的数量是否相等

###### 1. 方向 ######

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public boolean judgeCircle(String moves) { 
           int x = 0,y= 0;
            int len = moves.length();
            if(len == 0){ 
                return true;
            }
            if(len%2!=0){ 
                return false;
            }
            char[] a = moves.toCharArray();
           for(int i=0;i<moves.length();i++){ 
                char c=a[i];
                if(c=='U')x+=1;
                if(c=='D')x-=1;
                if(c=='L')y-=1;
                if(c=='R')y+=1;
            }
            return x==0&&y==0;
        }
    }

###### 2. 数组 ######

**时间复杂度：O(N) 空间复杂度：O(N)**

class Solution { 
        public boolean judgeCircle(String moves) { 
           int[] res = new int[26];
            int len  = moves.length();
            if(len == 0){ 
                return true;
            }
            if(len%2!=0){ 
                return false;
            }
            char[] c = moves.toCharArray();
            for(char ch :c){ 
                res[ch-'A']++;
            }
            
        return res['U'-'A']==res['D'-'A']&&res['L'-'A']==res['R'-'A'];
    
        
        }
    }

###### 3. HashMap ######

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public boolean judgeCircle(String moves) { 
           
            HashMap<Character,Integer> map = new  HashMap<Character,Integer>(); 
            //一定要先放入 不最后判断可能找不到 因为 可能没有某个方向 
            map.put('U', 0);
            map.put('D', 0);
            map.put('L', 0);
            map.put('R', 0);
    
    
            int len  = moves.length();
            if(len == 0){ 
                return true;
            }
            if(len%2!=0){ 
                return false;
            }
            char[] c = moves.toCharArray();
            for(int i =0 ;i<len;i++ ){ 
                if(map.containsKey(c[i])){ 
                    map.put(c[i],map.get(c[i])+1);
                }
            }
            
        return (map.get('U').equals(map.get('D')))&&(map.get('L').equals(map.get('R')));
    
        }
    }

#### 【总结】 ####

###### 1. 反思 ######

没有想清楚就开始动手 简单题！！！硬是搞了半天！！！  
输出最后的判断不一定要遍历 要学会思考特判

###### 2.hashmap最后判断equals ######

值得注意的是最后判断要用.equals不能用==。  
Integer是int的包装类，虽然能自动拆箱，但是Integer本质上是一个对象，我们==比较的是堆中的地址。  
我们看一下jdk中Integer的源码

public static Integer valueOf(int i) { 
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

默认IntegerCache.low = -127, IntegerCache.high = 128, 所以在这个范围内比较的是值，如果不在这个范围内他回去new一个新的Integer对象，这时候比的就是地址了。

参考链接：https://leetcode-cn.com/problems/robot-return-to-origin/solution/hen-rong-yi-li-jie-de-liang-chong-jie-ti-si-lu-by-/  
参考链接：https://leetcode-cn.com/problems/robot-return-to-origin/solution/java-hashmap-by-jolyne-3/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1f2846711d994b60baf774b5cddae8b7.png