LeetCode Hot 100 第一天
1. 1.两数之和
链接：题目链接
题解：
要求时间复杂度小于O(n^2)。知道x、target，那么 y = target - x，肯定需要枚举x，如果通过O(1)的时间复杂度找到y的位置，那么整体时间复杂度就在O(n)，通过O(1)时间复杂度不可避免的想到HashMap，其中key存y值，value存y的位置，那么通过Hash快速找到需要的值。
代码：
public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> numberIndexMap = new HashMap<>();int len = nums.length;int l = 0, r = 0;for (int i = 0; i < len; ++ i) {int preNum = target - nums[i];// 答案元素 肯定一前一后,所以边遍历边找前面的元素就行了,肯定能覆盖整个集合Integer index = numberIndexMap.get(preNum);if (index != null) {l = index;r = i;break;}numberIndexMap.put(nums[i], i);}return new int[]{l, r};}
1. 49 字母异味词分组
链接：题目链接
题解：
其实就是把不同的字符串（相同字符数），根据某种
规则转换为同一个字符串，那么就可以进行分组了，选用HashMap存储转换后的字符串与原字符串，key为转换后的字符串，value为原字符串集合。这个规则有两种方式，1. 对字符串的字符进行排序 2. 对字符串的字符进行计数，按照abcd…规律 + 计数生成新的字符串。
代码：
// 规则1
public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> stringListMap = new HashMap<>();for (String str : strs) {// 排序char[] charArray = str.toCharArray();Arrays.sort(charArray);List<String> sortStrs = stringListMap.computeIfAbsent(new String(charArray), key -> new ArrayList<>());sortStrs.add(str);}return new ArrayList<>(stringListMap.values());}// 规则2
public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> sortStrMap = new HashMap<>();int[] counts = new int[26];int len = strs.length;for (int i = 0; i < len; ++ i) {Arrays.fill(counts, 0);int strLen = strs[i].length();for (int j = 0; j < strLen; ++ j) {counts[(int)(strs[i].charAt(j) - 'a')] ++;}// 生成规则StringBuilder strKey = new StringBuilder();for (int j = 0; j < 26; ++ j) {if (counts[j] != 0) {strKey.append('a' + j);strKey.append(counts[j]);}}List<String> sameStrs = sortStrMap.computeIfAbsent(strKey.toString(), k -> new ArrayList<>());sameStrs.add(strs[i]);}return new ArrayList<>(sortStrMap.values());}
3. 128.最长连续序列
链接：题目链接
题解：
方案1：要求时间复杂度为O(n)，显而易见我们遍历整个集合，到x元素时，假设x为连续列表的起点，那么直接枚举是否存在x+1、x+2、x+3…等元素即可，同时维护一个最大值MaxValue，但是此时会发现假设x+1元素为连续列表的起点时，那么就会出现无效枚举，因为x为连续列表起点时包含了x+1的情况。所以要排除掉x+1、x+2、x+3…的枚举，有一个共同点，那就是存在前元素。
方案2：可以维护连续区间，把每个数字看成一个节点，枚举x为连续列表的起点，如果x+1也在数组中，那么将x、x+1 union在一起，并且维护区间最大值，最后统计联通块的最大值，这里可以用到并查集来进行维护区间。
代码：
// 方案1public int longestConsecutive(int[] nums) {Set<Integer> numExistSet = new HashSet<>();for (int num: nums) {numExistSet.add(num);}int result = 0;// 这里需要遍历numExistSet，过滤掉重复元素，如果遍历nums，leetcode会超时for (int num: numExistSet) {if (numExistSet.contains(num - 1)) {continue;}int maxCount = 1;int maxInterval = num + 1;while (numExistSet.contains(maxInterval)) {maxCount += 1;maxInterval += 1;}result = Math.max(maxCount, result);}return result;}// 方案2
private Map<Integer, Integer> parentMap = new HashMap<>();private Map<Integer, Integer> sizeMap = new HashMap<>();public int find(int x) {if (parentMap.get(x) != x) {parentMap.put(x, find(parentMap.get(x)));}return parentMap.get(x);}public void union(int x, int y) {int parentX = find(x);int parentY = find(y);if (parentX == parentY) {return;}// 将maxValue维护在父节点上if (sizeMap.get(parentX) < sizeMap.get(parentY)) {parentMap.put(parentX, parentY);sizeMap.put(parentY, sizeMap.get(parentY) + sizeMap.get(parentX));} else {parentMap.put(parentY, parentX);sizeMap.put(parentX, sizeMap.get(parentY) + sizeMap.get(parentX)); }}public int longestConsecutive(int[] nums) {// 初始化for (int num: nums) {parentMap.put(num, num);sizeMap.put(num, 1);}// 区间连接for (int num: nums) {if (parentMap.containsKey(num + 1)) {union(num, num + 1);}}// 求最大值int result = 0;for (int num: nums) {if (parentMap.get(num) == num) {result = Math.max(result, sizeMap.get(num));}}return result;}如果对你有帮助，辛苦点个赞，谢谢啦，朋友！！！