首页 > 编程语言 >算法-代码随想录-哈希表

算法-代码随想录-哈希表

时间:2024-07-23 14:20:13浏览次数:14  
标签:遍历 哈希 int 随想录 ++ 算法 resSet 数组 new

有效的字母异位词

思路:

数组作为一个简单的哈希表,可以用来记录字符串中每个字符出现的次数。

可以设置一个数组,第一轮遍历s中的字符,字符每出现一次,在数组对应位置+1。第二轮遍历t中的字符,字符每出现一次,在数组对应位置-1。最后遍历作为哈希表的数组,如果都为0,则说明每个字符出现的次数相同,否则不满足题目要求。

代码:

class Solution {
    public boolean isAnagram(String s, String t) {
        //声明大小为26的数组。
        int[] record = new int[26];
        //第一轮遍历,出现的字符在对应位置+1
        for(int i = 0; i < s.length(); i++){
            record[s.charAt(i) - 'a']++;//只需要求出对应位置即可
        }
        //第二轮遍历,出现的字符在对应位置-1
        for(int i = 0; i < t.length(); i++){
            record[t.charAt(i) - 'a']--;
        }
        //只要有一个不为0.则不符合要求
        for(int i = 0; i < record.length; i++){
            if(record[i] != 0){
                return false;
            }
        }
        return true;
    }
}

两个数组的交集

数组法

用数组来做哈希表,前提条件:给定的两个数组大小要是确定的。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1 = new int[1005];
        int[] hash2 = new int[1005];
        //遍历第一个数组的所有元素,将出现的元素在hash1对应的位置+1
        for(int i:nums1){
            hash1[i]++;
        }
        //遍历第二个数组的所有元素,将出现的元素hash2对应的位置+1
        for(int i:nums2){
            hash2[i]++;
        }
        List<Integer> resList = new ArrayList<>();
        //如果hash1与hash2中同一位置元素个数大于1,说明在两个数组中都有存在,加入到list中
        for(int i = 0; i < 1005; i++){
            if(hash1[i] > 0 && hash2[i] > 0){
                resList.add(i);
            }
        }
        
        int[] res = new int[resList.size()];    
        int index = 0;
        for(int i: resList){
            res[index++] = i;
        }
        return res;
        }
}

hashset

根据题目要求,交集中的元素是不重复且没有顺序要求的,因此可以使用hashset来作为哈希表。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历nums1数组中的每一个元素,加入到hashset的哈希表中
        for(int i : nums1){
            set1.add(i);
        }
        //遍历nums2数组中的每一个元素,判断hashset中是否存在对应元素,存在就加入的resSet中
        for(int i : nums2){
            if(set1.contains(i)){
                resSet.add(i);
            }
        }
        //声明一个新数组,将resSet中的元素复制到该数组并输出
        int[] arr = new int[resSet.size()];
        int index = 0;
        for(int i : resSet){
            arr[index++] = i;
        }
        return arr;
        }
}

快乐数

题目中提示,可能是无限循环,也就是说平方和的数字会重复出现,重复出现时,说明得不到结果。也就是说,快速判断某个数是否出现在集合中,考虑哈希法。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> resSet = new HashSet<>();
        //判断n是否符合条件,是否已经出现过
        while(n != 1 && !resSet.contains(n)){
            resSet.add(n);
            n = getNextNumber(n);
        }
        //如果n=1,则说明n是快乐数,返回true。如果n!=1,则说明已经进入了无限循环,不可能再得到1的结果,返回false。
        return n == 1;
    }
    //获取下一个平方和
    private int getNextNumber(int n){
        int res = 0;
        while(n > 0){
            int temp = n % 10;
            res += temp * temp;
            n /= 10;
        }
        return res;
    }
}

标签:遍历,哈希,int,随想录,++,算法,resSet,数组,new
From: https://www.cnblogs.com/forest-pan/p/18318291

相关文章

  • Day7 哈希表part2
    任务454.四数相加II给你四个整数数组nums1、nums2、nums3和nums4,数组长度都是n,请你计算有多少个元组(i,j,k,l)能满足:0<=i,j,k,l<nnums1[i]+nums2[j]+nums3[k]+nums4[l]==0思路暴力法的时间复杂度为O(n^4),我们利用dic来优化,首先用dic存储前两个......
  • 从零开始学数据结构系列之第四章《prim算法(普里姆算法)总代码》
    文章目录回顾初始化寻找最小权值算法主体总代码往期回顾回顾我们用这张图来进行算法讲解初始化/**vex-存储顶点*weight-存储权值*/typedefstructEdge{charvex;intweight;}Edge;/**开辟数组大小得空间,大小具体为vexNum的个数*......
  • 算法识别(一)--TEA及其魔改
    0x01算法概要TEA(tinyencryptionalgorithm),属于分组算法,每次操作64位数,分成2个4字节无符号整数(unsignedint),密钥128位,为4个4字节无符号整型(unsignedint),delta(unsignedint)一般为0x9e3779b9,进行轮数一般>=32轮.0x02算法实现c实现#include<cstdint>unsigne......
  • 快速学习一个算法,Transformer
    今天给大家介绍一个强大的算法模型,TransformerTransformer模型是由Vaswani等人在2017年提出的一种用于自然语言处理的深度学习模型,特别擅长于处理序列到序列的任务,如机器翻译、文本生成等。今天,我们主要从编码的角度来进行说明。Transformer模型架构Transformer......
  • 【数据结构】排序算法——Lessen1
    Hi~!这里是奋斗的小羊,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎~~......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(2)1003
    绝对不模拟的简单魔方要相信题目的提示(直接模拟的代码长达300行),由于魔方的特性,不论如何转动脚上的色块颜色不会变动,只要枚举8个角块看看是否一致即可,枚举角块时需确定访问角块颜色的顺序,例如以3号为顶,后左上访问顺序为123即坐标为\((3,4)->(4,3)-(4,4)\),那么可以通过此角......
  • 素性测试算法
    素数拥有许多特殊的性质,这让它在计算机科学中被广泛应用。例如,著名的RSA加密算法基于两个质数的乘积的难分解性;同时,其正确性基于质数的费马小定理和一些推论。因此,快速判定一个大整数是否是质数是重要的课题。试除法由于质数\(p\)只有\(1\)和\(p\)两个正因数,对于正整......
  • 「代码随想录算法训练营」第十八天 | 二叉树 part8
    669.修剪二叉搜索树题目链接:https://leetcode.cn/problems/trim-a-binary-search-tree/题目难度:中等文章讲解:https://programmercarl.com/0669.修剪二叉搜索树.html视频讲解:https://www.bilibili.com/video/BV17P41177ud?share_source=copy_web题目状态:没有思路,看题解过......
  • [UE 虚幻引擎] DTHmacSha 蓝图HMACSHA加密算法插件说明
    本插件可以在虚幻引擎中使用蓝图对字符串和文件进行HMACSHA加密。1.节点说明HMACSHA一共有5种加密方式,分辨是HMACSHA-1,HMACSHA-224,HMACSHA-256,HMACSHA-384,HMACSHA-512。本插件对每种加密方式提供3个节点,一般节点返回通用值,如7c4a8d09ca3762af61e59520943dc26494f8941b;t......
  • 【视频】Python遗传算法GA优化SVR、ANFIS预测证券指数ISE数据-CSDN博客
    全文链接:https://tecdat.cn/?p=37060本文旨在通过应用多种机器学习技术,对交易所的历史数据进行深入分析和预测。我们帮助客户使用了遗传算法GA优化的支持向量回归(SVR)、自适应神经模糊推理系统(ANFIS)等方法,对数据进行了特征选择、数据预处理、模型训练与评估。实验结果表明,这些方法......