LeetCode刷题 --- 哈希表

这篇具有很好参考价值的文章主要介绍了LeetCode刷题 --- 哈希表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 两数之和

解题思路:

  1. 利用哈希表,key存数组当前值,value存数组下标
  2. 两数之和等于target,可以看做是两个数是配对
  3. 遍历数组,看哈希表中有没有值和这个当前值配对,如果没有,就存入哈希表
  4. 如果有,当前数,和配对的数,就是所求值。
    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. 无重复字符的最长子串

解题思路 -- 哈希表

  1. 定义两个指针,分别是左指针和右指针,for循环遍历字符串
  2. 定义一个hashMap存放数据(用于判断重复)
  3. 右指针不断往后遍历
    1. 如果当前元素不存在,就添加到哈希表中,然后继续遍历
    2. 如果当前元素存在,就把左指针更新成哈希表中value的值+1
      1. ----注意这个位置,如果value的值+1 小于当前left,则不需要更新
  4. 每次循环的时候,计算左右指针之差,获取较大的值
    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;
    }

解题思路 --- 滑动窗口

上面是用双指针解题,其实双指针的题目很容易用滑动窗口的模板来套用解题

  1. 外层右指针向右滑动
  2. 内层左指针向右滑动
    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. 字母异位词分组

解题思路:

看题意,其实就是要把字母相同顺序不同的字符串进行分组。

  1. 先对每个字符串中的字母按照顺序进行排列,得到一个key,这个字符串就作为value中的一个数据
  2. 遍历数组,把所有的字符串都存入到value中
  3. 最后返回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

  1. 数组排序,当前值和后面一个值进行比较,相同则说明有重复的,不同则说明没有重复
  2. 循环遍历,每次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

  1. 做一个set,遍历数组,如果set不存在元素,就存入
  2. 如果存在,就删除元素
  3. 最后剩下的一个,就是只出现一次的数字
    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 --- 位运算

LeetCode刷题 --- 哈希表

 LeetCode刷题 --- 哈希表

    public static int singleNumber4(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single = single ^ num;
        }
        return  single;
    }

387. 字符串中的第一个唯一字符

解题思路:

  1. 定义一个map,key存放字符,value存放下标
  2. 遍历字符串,如果map不存在,就存入
  3. 如果map存在,就把value值改为字符串长度
  4. 遍历map的value,每次取value较小的一个值
  5. 如果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

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录第6天| 哈希表理论基础 ,LeetCode242.有效的字母异位词,LeetCode349. 两个数组的交集,LeetCode202. 快乐数,LeetCode1. 两数之和

    哈希表(散列表)理论基础 : 哈希表是根据关键码的值而直接进行访问的数据结构。 直白来讲其实数组就是一张哈希表。   什么时候想到用哈希法, 当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法 。 当我们遇到了要快速判断一个元素是否出现集

    2024年02月10日
    浏览(66)
  • 哈希-力扣01两数之和

    给定一个整数数组  nums  和一个整数目标值  target ,请你在该数组中找出  和为目标值  target   的那  两个  整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1:

    2024年01月20日
    浏览(41)
  • 代码随想录 -- 哈希表--两数之和

    力扣hot1:两数之和 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] +

    2024年02月09日
    浏览(38)
  • 解决两数之和问题的哈希表方法

    在给定整数数组中寻找和为目标值的两个整数,并返回它们的数组下标。通过暴力枚举或哈希表方法,时间复杂度小于O(n^2)。Java和C++代码解决方案。

    2024年02月01日
    浏览(48)
  • leetcode - 01两数之和

    时间复杂度读 O ( n 2 ) O(n^2) O ( n 2 ) 空间复杂度 O ( 1 ) O(1) O ( 1 )

    2024年02月12日
    浏览(62)
  • Leetcode 1.两数之和

    暴力、哈希 题目描述 给定一个整数数组  nums  和一个整数目标值  target ,请你在该数组中找出  和为目标值  target   的那  两个  整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序

    2024年04月10日
    浏览(38)
  • [LeetCode] 1.两数之和

    给定一个整数数组 nums 和一个目标值 target ,请你在该数组中找出和为目标值 target 的那两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1: 示例 2: 示例 3: 提示: 2 =

    2024年02月05日
    浏览(54)
  • LeetCode两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1: 输入:nums =

    2024年02月11日
    浏览(43)
  • leetcode--1--两数之和

            给定一个整数数组  nums  和一个整数目标值  target ,请你在该数组中找出  和为目标值  target   的那  两个  整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

    2024年04月25日
    浏览(35)
  • leetcode 1两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1: 输入:nums =

    2024年02月01日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包