实习日常刷代码

实习过程中也不能忘记刷题呀！！好久没写题，我连HashMap的创建都不会写了，还是细微之处见真章，每天稍微巩固一下所学习的东西吧。

1.两数之和

关键的优化：

用x表示target - nums[ i ], 省略了重复计算nums[i]的时间。
不用先存完再比较（在比较的时候需要注意不能使用两次相同的元素），而是边存边比较

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if (map.containsKey(x)) { // 这里肯定取不到同样的值，因为当前值还没有存进去
                res[0] = i;
                res[1] = map.get(x);
                break;
            } else {
                map.put(nums[i], i);
            }
        }
        return res;
    }

2.字母异位词分组

需要注意的点:

数组不能作为map的key，Arrays.sort对字符串排序，再通过new String() 转为字符串，而不是toString（）
map的values即为分组之后的字母异位词

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public List<List<String>> groupAnagrams(String[] strs) {
     HashMap<String, List<String>> map = new HashMap<>();
     int n = strs.length;
     for (int i = 0; i < n; i++) {
         String str = strs[i];
         char[] charArray = str.toCharArray();
         Arrays.sort(charArray);
         String new_str = new String(charArray); // 注意不是 charArray.toString()
         if (map.containsKey(new_str)) {
             map.get(new_str).add(str);
         } else {
             List<String> arrayList = new ArrayList<>();
             arrayList.add(str);
             map.put(new_str, arrayList); // 数组不能当map的key！
         }
     }
     return new ArrayList<List<String>>(map.values());
 }