Day01 集合 | 1. 两数之和、874. 模拟行走机器人、49. 字母异位词分组

1. 两数之和

1、思路

遍历数组，使用map存储target 与元素之差，value存储数组下标

2、代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int result = nums[i];
            if (map.containsKey(result)) {
                return new int[] { i, map.get(result) };
            }
            map.put(target - nums[i], i);

        }
        return new int[0];
    }
}

二、874. 模拟行走机器人

1、思路

将障碍物hash存储到set集合中,然后将左转右转 转换为每次获取当前位置（在新建的一维数组中的位置） 新建2个一维数组,分别表示北 东 南 西 向前一步的数据,然后，每次累加坐标值，并获取最大值

2、代码

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set <String>set = new HashSet();
        for(int i = 0; i< obstacles.length; i++){
            set.add(toHash(obstacles[i][0],obstacles[i][1]));
        }
        int result = 0;
        int x = 0;
        int y = 0;
        int cur = 0; // N=0,E=1,S=2,W=3
        // (cur + 1) % 4 右转
        // (cur + 3) % 4 左转
        // 网格行走，使用2个一位数组代表坐标
        int [] dx = {0, 1, 0, -1};  // 北 东  南 西 下标对应 0 1 2 3 
        int [] dy = {1, 0, -1, 0};
        for (int c : commands) {
            if(c == -1){
                cur =  (cur + 1) % 4;
            }else if(c == -2){
                cur =  (cur + 3) % 4;
            }else{
                for(int i = 0; i< c; i++){
                   int nx = x + dx[cur];
                   int ny = y + dy[cur];
                    // 如果下一步遇到障碍物,则停止
                    if(set.contains(toHash(nx,ny))){
                        break;
                    }
                    x =  nx; // 0 0 1 3
                    y =  ny; // 1 4 4 4
                    result = Math.max(result, x * x + y * y);
                }  
            }
        }
        return result;
    }

       public String toHash(int x , int y) {
            return x + "#" + y;
       }
}

3.优化hash.提示性能(行号 * 列数 + 列号，60001 为题目中最大网格列数)

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set <Long>set = new HashSet();
        for(int i = 0; i< obstacles.length; i++){
            set.add(toHash(obstacles[i][0],obstacles[i][1]));
        }
        int result = 0;
        int x = 0;
        int y = 0;
        int cur = 0; // N=0,E=1,S=2,W=3
        // (cur + 1) % 4 右转
        // (cur + 3) % 4 左转
        // 网格行走，使用2个一位数组代表坐标
        int [] dx = {0, 1, 0, -1};  // 北 东  南 西 下标对应 0 1 2 3 
        int [] dy = {1, 0, -1, 0};
        for (int c : commands) {
            if(c == -1){
                cur =   (cur + 1) % 4;
            }else if(c == -2){
                cur =   (cur + 3) % 4;
            }else{
                for(int i = 0; i< c; i++){
                   int nx = x + dx[cur];
                   int ny = y + dy[cur];
                    // 如果下一步遇到障碍物,则停止
                    if(set.contains(toHash(nx,ny))){
                        break;
                    }
                    x =  nx; // 0 0 1 3
                    y =  ny; // 1 4 4 4
                    result = Math.max(result, x * x + y * y);
                }  
            }
        }
        return result;
    }

    //    public String toHash(int x , int y) {
    //         return x + "#" + y;
    //    }

        public Long toHash(int x , int y) {
            return (x + 3000) * 60001L + (y + 3000);
       }
}

三、49. 字母异位词分组

1、思路

遍历数组，对每个字符串进行排序，map判断是否存在排序后的key,若存在，则将该元素放入map value中，否则新增数组，也放入数组中，最后将map的所有values取出放入数组中返回

2、代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList();
        Map<String, List<String>> map = new HashMap();
        for (String str : strs) {
            String strSort = sort(str);
            List<String> list1 = new ArrayList();
            if (map.containsKey(strSort)) {
                list1 = map.get(strSort);
            }
            list1.add(str);
            map.put(strSort, list1);
        }
        return new ArrayList<>(map.values());
    }

    public String sort(String str) {
        char[] cha = str.toCharArray();
        Arrays.sort(cha);
        return new String(cha);
    }
}