个人网站可以做企业网站吗,手机网站logo,网站打不开建设中哪的问题,个人摄影网站模版本篇博客讲解 LeetCode热题100道中的哈希篇中的三道题。分别是 1.第一道#xff1a;两数之和#xff08;简单#xff09; 2.第二道#xff1a;字母异位词分组#xff08;中等#xff09; 3.第三道#xff1a;最长连续序列#xff08;中等#xff09; 第一道#xff1… 本篇博客讲解 LeetCode热题100道中的哈希篇中的三道题。分别是 1.第一道两数之和简单 2.第二道字母异位词分组中等 3.第三道最长连续序列中等 第一道两数之和简单 class Solution {public int[] twoSum(int[] nums, int target) {int left 0,right nums.length-1;Arrays.sort(nums);while (left right){if(nums[left] nums[right] target) {left;}else if(nums[left] nums[right] target){right--;}else {return new int[]{left,right};}}return new int[]{left,right};}
}
方法一暴力枚举
class Solution {public int[] twoSum(int[] nums, int target) {int n nums.length;for (int i 0; i n; i) {for (int j i 1; j n; j) {if (nums[i] nums[j] target) {return new int[]{i, j};}}}return new int[0];}
}我们通过双循环。遍历数组中每一个两数之和。若和等于target。 此时我们返回数组两个数的数组下标。这样的思想很简单不过效率不高。 方法二哈希表
注
java的官方文档建议我们在初始化哈希表的时候尽量写入哈希表的容量避免哈希表扩容所带来的性能消耗。
class Solution {public int[] twoSum(int[] nums, int target) {int len nums.length;MapInteger, Integer hashTable new HashMapInteger, Integer(len-1);hashTable.put(nums[0],0);//向哈希表存入数组第一个数//从第二个数开始遍历数组看哈希表中是否存在target减去此时数组的数所对应的值//如果有则返回下标。//没有则将这个数放进哈希表。并存入数组下标。for (int i 1; i len; i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
} 我们通过Map类创建一个哈希表。 1.向哈希表存入数组第一个数 2.从第二个数开始遍历数组看哈希表中是否存在target减去此时数组的数所对应的值 3.如果有则返回下标。 4.没有则将这个数放进哈希表。并存入数组下标。 第二道字母异位词分组中等 方法一哈希排序
class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ListString map new HashMapString, ListString();for (String str : strs) {char[] array str.toCharArray();Arrays.sort(array);String key new String(array);ListString list map.getOrDefault(key, new ArrayListString());list.add(str);map.put(key, list);}return new ArrayListListString(map.values());}
}遍历其中的字符串。将他们转换为数组方便操作。对于每个单词。进行排序。 作为哈希表的键。将单词加入哈希表。返回的就是答案。 方法二哈希计数
class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ListString map new HashMapString, ListString();for (String str : strs) {int[] counts new int[26];int length str.length();for (int i 0; i length; i) {counts[str.charAt(i) - a];}// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串作为哈希表的键StringBuffer sb new StringBuffer();for (int i 0; i 26; i) {if (counts[i] ! 0) {sb.append((char) (a i));sb.append(counts[i]);}}String key sb.toString();ListString list map.getOrDefault(key, new ArrayListString());list.add(str);map.put(key, list);}return new ArrayListListString(map.values());}
}将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串作为哈希表的键。 第三道最长连续序列中等
暴力的方法是 O(n) 遍历数组去看是否存在这个数我们就不多说了这里我们来看更高效的哈希表法。
哈希表
class Solution {public int longestConsecutive(int[] nums) {SetInteger set new HashSetInteger();for (int num : nums) {set.add(num);}int longestStreak 0;for (int num : set) {if (!set.contains(num - 1)) {int currentNum num;int currentStreak 1;while (set.contains(currentNum 1)) {currentNum 1;currentStreak 1;}longestStreak Math.max(longestStreak, currentStreak);}}return longestStreak;}
} 1.首先定义一个Set类去重并将去重后的数组放入Set中 2.初始化最长连续序列longestStreak令其为0。 3.遍历Set。去找是否存在num-1。这个数。 如果不存在则记录当前的num为currentNum。且令currentStreak为1。并且循环在set中查找是否包含currentNum。如果包含就一直更新currentStreak的值直到不包含为止。并每次取得currentStreak与longestStreak的最大值赋值给longestStreak 如果存在则跳过。 最终返回longestStreak
