1. 两数之和
解题思路:
- 利用哈希表,key存数组当前值,value存数组下标
- 两数之和等于target,可以看做是两个数是配对
- 遍历数组,看哈希表中有没有值和这个当前值配对,如果没有,就存入哈希表
- 如果有,当前数,和配对的数,就是所求值。
public int[] twoSum(int[] nums, int target) { int[] res = {-1, -1}; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (!map.containsKey(target - nums[i])) { map.put(nums[i], i); continue; } res[0] = map.get(target - nums[i]); res[1] = i; return res; } return res; }
3. 无重复字符的最长子串
解题思路 -- 哈希表
- 定义两个指针,分别是左指针和右指针,for循环遍历字符串
- 定义一个hashMap存放数据(用于判断重复)
- 右指针不断往后遍历
- 如果当前元素不存在,就添加到哈希表中,然后继续遍历
- 如果当前元素存在,就把左指针更新成哈希表中value的值+1
- ----注意这个位置,如果value的值+1 小于当前left,则不需要更新
- 每次循环的时候,计算左右指针之差,获取较大的值
public static int lengthOfLongestSubstring1(String s) { byte[] bytes = s.getBytes(); int res = 0; Map<Byte, Integer> map = new HashMap<>(); int left = 0; int right = 0; for (; right < bytes.length; right++) { if (map.containsKey(bytes[right])) { left = Math.max(left, map.get(bytes[right]) + 1); map.put(bytes[right], right); } else { map.put(bytes[right], right); } res = Math.max(res, right - left + 1); } return res; }
解题思路 --- 滑动窗口
上面是用双指针解题,其实双指针的题目很容易用滑动窗口的模板来套用解题
- 外层右指针向右滑动
- 内层左指针向右滑动
public static int lengthOfLongestSubstring(String s) { byte[] bytes = s.getBytes(); int res = 0; Set<Byte> set = new HashSet<>(); int right = 0; int left = 0; while (right < bytes.length) { while (set.contains(bytes[right])) { set.remove(bytes[left]); left++; } res = Math.max(right - left, res); set.add(bytes[right]); right++; } return res; }
49. 字母异位词分组
解题思路:
看题意,其实就是要把字母相同顺序不同的字符串进行分组。
- 先对每个字符串中的字母按照顺序进行排列,得到一个key,这个字符串就作为value中的一个数据
- 遍历数组,把所有的字符串都存入到value中
- 最后返回map.values()集合即可。
public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String str : strs) { String sort = sort(str); if (map.containsKey(sort)) { List<String> strings = map.get(sort); strings.add(str); map.put(sort, strings); } else { ArrayList<String> strings = new ArrayList<>(); strings.add(str); map.put(sort, strings); } } return new ArrayList<>(map.values()); } private static String sort(String str) { char[] chars = str.toCharArray(); Arrays.sort(chars); return Arrays.toString(chars); }
136. 只出现一次的数字
给你一个 非空 整数数组 nums
,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
解题1
- 数组排序,当前值和后面一个值进行比较,相同则说明有重复的,不同则说明没有重复
- 循环遍历,每次i+2;
public static int singleNumber(int[] nums) { Arrays.sort(nums); int i = 0; while (i < nums.length - 1) { if (nums[i] == nums[i + 1]) { i = i + 2; } else { return nums[i]; } } // 解决长度仅为1的场景 return nums[nums.length - 1]; }
解题2
- 做一个set,遍历数组,如果set不存在元素,就存入
- 如果存在,就删除元素
- 最后剩下的一个,就是只出现一次的数字
public static int singleNumber3(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { if (set.contains(num)) { set.remove(num); } else { set.add(num); } } return (Integer) set.toArray()[0]; }
解题3 --- 位运算
public static int singleNumber4(int[] nums) { int single = 0; for (int num : nums) { single = single ^ num; } return single; }
387. 字符串中的第一个唯一字符
解题思路:
- 定义一个map,key存放字符,value存放下标
- 遍历字符串,如果map不存在,就存入
- 如果map存在,就把value值改为字符串长度
- 遍历map的value,每次取value较小的一个值
- 如果value等于字符串长度,说明不存在单个字符,返回-1,否则value值就是第一次出现的单个字符。
public static int firstUniqChar(String s) { char[] chars = s.toCharArray(); Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < chars.length; i++) { if (map.containsKey(chars[i])) { map.put(chars[i], chars.length); } else { map.put(chars[i], i); } } int res = s.length(); for (Integer value : map.values()) { res = Math.min(res, value); } return res == s.length() ? -1 : res; }
819. 最常见的单词
对字符串做一个分割,然后遍历,把单词存入到map中,最后取出符合要求的单词即可。文章来源:https://www.toymoban.com/news/detail-468101.html
易错点:单词的分割文章来源地址https://www.toymoban.com/news/detail-468101.html
class Solution { public String mostCommonWord(String paragraph, String[] banned) { String[] pars = paragraph.split(" |\\!|\\?|\\;|,|\\.|\\'"); Map<String, Integer> map = new HashMap<>(); for (String par : pars) { if (par.equals("")) { continue; } par = par.toLowerCase(); if (map.containsKey(par)) { map.put(par, map.get(par) + 1); } else { map.put(par, 1); } } Set<String> set = new HashSet<>(Arrays.asList(banned)); String res = null; int value = 0; for (Map.Entry<String, Integer> entry : map.entrySet()) { if (set.contains(entry.getKey())) { continue; } else { if (entry.getValue() > value) { value = entry.getValue(); res = entry.getKey(); } } } return res; } }
到了这里,关于LeetCode刷题 --- 哈希表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!