代码随想录训练营 Day06 - 哈希表(上)

简介: 代码随想录训练营 Day06 - 哈希表(上)

概念


哈希表(Hash Table)用的是数组支持按照下标随机访问数据的特性,所以哈希表其实就是数组的一种扩展,由数组演化而来的一种数据结构。

散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。


作业题


242. 有效的字母异位词

package jjn.carl.hashtable;
/**
 * @author Jjn
 * @since 2023/7/3 14:18
 */
public class LeetCode242 {
    public boolean isAnagram(String s, String t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return true;
        }
        if (s.length() != t.length()) {
            return false;
        }
        char[] firstIndex = new char[26];
        for (char c : s.toCharArray()) {
            firstIndex[c - 'a']++;
        }
        char[] secondIndex = new char[26];
        for (char c : t.toCharArray()) {
            secondIndex[c - 'a']++;
        }
        for (int i = 0; i < firstIndex.length; i++) {
            if (firstIndex[i] != secondIndex[i]) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println("new LeetCode242().isAnagram(\"rat\", \"tar\") = " + new LeetCode242().isAnagram("rat", "tar"));
    }
}


349. 两个数组的交集

package jjn.carl.hashtable;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
 * @author Jjn
 * @since 2023/7/3 14:40
 */
public class LeetCode349 {
    public int[] intersection(int[] nums1, int[] nums2) {
        boolean[] numCount = new boolean[1001];
        for (int j : nums1) {
            numCount[j] = true;
        }
        Set<Integer> result = new HashSet<>();
        for (int j : nums2) {
            if (numCount[j]) {
                result.add(j);
            }
        }
        int[] res = new int[result.size()];
        int i = 0;
        for (Integer num : result) {
            res[i] = num;
            i++;
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums1 = new int[]{2, 3, 4, 4};
        int[] nums2 = new int[]{3, 4, 4, 5, 5};
        int[] intersection = new LeetCode349().intersection(nums1, nums2);
        System.out.println("Arrays.toString(intersection) = " + Arrays.toString(intersection));
    }
}


202. 快乐数

package jjn.carl.hashtable;
import java.util.HashSet;
import java.util.Set;
/**
 * @author Jjn
 * @since 2023/7/3 17:11
 */
public class LeetCode202 {
    public boolean isHappy(int n) {
        Set<Integer> existed = new HashSet<>();
        while (n != 1 && existed.add(n)) {
            n = getNextNumber(n);
        }
        return n == 1;
    }
    private int getNextNumber(int n) {
        int total = 0;
        while (n > 0) {
            int rest = n % 10;
            total += rest * rest;
            n = n / 10;
        }
        return total;
    }
    public static void main(String[] args) {
        System.out.println("new LeetCode202().isHappy(19) = " + new LeetCode202().isHappy(19));
        System.out.println("new LeetCode202().isHappy(2) = " + new LeetCode202().isHappy(2));
    }
}


1. 两数之和

package jjn.carl.hashtable;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
 * @author Jjn
 * @since 2023/7/3 19:04
 */
public class LeetCode1 {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer val = map.get(target - nums[i]);
            if (val != null) {
                return new int[]{val, i};
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }
    public static void main(String[] args) {
        int[] nums = new int[]{2, 7, 11, 15};
        int target = 9;
        int[] result = new LeetCode1().twoSum(nums, target);
        System.out.println("Arrays.toString(result) = " + Arrays.toString(result));
    }
}



目录
相关文章
|
缓存 监控 小程序
App性能测试揭秘(Android篇)
性能测试在移动测试领域一直是一个大难题,它最直观的表现是用户在前台使用 App 时的主观体验,然而决定体验优劣的背后,涉及到了许许多多的技术变迁。阅读此文,带你揭秘App性能测试。
5414 0
App性能测试揭秘(Android篇)
|
存储 容器
HashMap什么时候扩容,如何扩容?怎么轻松化解?
一位2年工作经验的小伙伴面试时被问到,说,HashMap什么时候扩容,为什么要扩容?这个问题本身不是很难,但是这位小伙伴对底层实现原理没有太多关注,所以,被这个问题难住了。 下面我给大家分析一下这个问题的底层逻辑。
298 2
|
监控 数据处理 调度
使用Apache Airflow进行工作流编排:技术详解与实践
【6月更文挑战第5天】Apache Airflow是开源的工作流编排平台,用Python定义复杂数据处理管道,提供直观DAGs、强大调度、丰富插件、易扩展性和实时监控。本文深入介绍Airflow基本概念、特性,阐述安装配置、工作流定义、调度监控的步骤,并通过实践案例展示如何构建数据获取、处理到存储的工作流。Airflow简化了复杂数据任务管理,适应不断发展的数据技术需求。
2375 3
|
机器学习/深度学习 人工智能 算法
量子计算的潜力与挑战:开启计算新时代
这篇文章探讨了量子计算的基本原理、潜在应用及其面临的主要挑战。通过对量子比特(qubit)的介绍和量子叠加、纠缠现象的解释,揭示了量子计算在处理复杂问题上的革命性优势。同时,文章也指出了目前量子计算技术发展中所遇到的障碍,如量子退相干和纠错问题,并展望了未来的发展方向。
|
存储 机器学习/深度学习 边缘计算
边缘计算:一文理解云边端协同架构中的高性能云计算、边缘计算、云边协同
边缘计算:一文理解云边端协同架构中的高性能云计算、边缘计算、云边协同
17286 0
边缘计算:一文理解云边端协同架构中的高性能云计算、边缘计算、云边协同
|
算法 安全 调度
写给大忙人看的死锁详解(3)
写给大忙人看的死锁详解(3)
70 0
写给大忙人看的死锁详解(3)
|
druid Java 测试技术
|
缓存 监控
varnish缓存初探(2)—基础配置
varnish缓存学习的第二步
1723 0
|
Web App开发 Java
jfinal搭建(一)
本文为eclipse开发    1、创建Dynamic Web Project 2、填入项目基本信息 注意上图中:Target runtime 一定要选择 3、修改Default Output Folder,推荐输入WebRoot\WEB-INF\classes 特别注意:此处的 Default out folder必须要与 WebRoot\WEB-INF\classes 目录完全一致才可以使用 JFinal 集成的 Jetty 来启动项目。
1717 0
|
移动开发 前端开发 JavaScript
优秀网页设计:带给你灵感的联系页面设计
  在设计网站的时候,我们需要考虑到各个方面,从页眉到脚,从着陆页(landing page)到关于页(about us page),还有联系页面(contact page)都要考虑。联系页面是网站重要的组成部分之一,访客通过联系表单和网站所有者取得联系,反馈信息。
1030 0