首页 > 编程语言 >代码随想录算法训练营day06|242.有效的字母异位词,349.两个数组的交集,202.快乐数,1.两数之和

代码随想录算法训练营day06|242.有效的字母异位词,349.两个数组的交集,202.快乐数,1.两数之和

时间:2024-08-07 15:18:30浏览次数:8  
标签:202 return int 随想录 record vector set unordered 两数

242.有效的字母异位词

题目链接:https://leetcode.cn/problems/valid-anagram/description/

我的代码:

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() == t.size()) {
            int record[26] = {0};
            for (int i = 0; i < s.size(); i++) {
                record[s[i] - 'a']++;
                record[t[i] - 'a']--;
            }
            for (int i = 0; i < 26; i++) {
                if (record[i] != 0)
                    return false;
            }
            return true;
        } else
            return false;
    }
};

先比较两字符串长度,长度相同则定义一个数组哈希表,索引值就是字母对于‘a’的相对位置,s遇字母加1,t遇字母减1,若循环结束后哈希数组内值全为0则说明两字符串是字母异位词。

349.两个数组的交集

题目链接:https://leetcode.cn/problems/intersection-of-two-arrays/description/

使用set:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> nums(nums1.begin(), nums1.end());
        for (int num : nums2) {
            if (nums.find(num) != nums.end()) { // 在nums中查找num值,返回一个迭代器,如果找到,迭代器指向该元素,没有找到,迭代器指向nums.end()
                result.insert(num);
            }
        }
        return vector<int>(result.begin(), result.end());
    }
};

std::set和std::multiset底层实现都是红黑树,std::unordered_set的底层实现是哈希表, 使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set。

使用数组:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int hash[1005] = {0};
        for (int i = 0; i < nums1.size(); i++) {
            hash[nums1[i]] = 1;
        }
        unordered_set<int> result;
        for (int i = 0; i < nums2.size(); i++) {
            if (hash[nums2[i]] == 1)
                result.insert(nums2[i]);
        }
        return vector<int>(result.begin(), result.end());
    }
};

定义哈希数组,全部置0,遍历nums1,给索引置1,遍历nums2,检索到哈希数组元素为1,插入result,其中unordered_set result可以自动去重。

202.快乐数

题目链接:https://leetcode.cn/problems/happy-number/description/

我的代码:

class Solution {
public:
    int getSum(int n) { // 求各位数字平方和的函数
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> record;
        while (1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            } else if (record.find(sum) != record.end()) {
                return false;
            } else {
                record.insert(sum);
            }
            n = sum;
        }
    }
};

此题关键在于判断sum是否重复出现,若出现1,则return true,若重复出现,则出现无限循环,直接return false,同时对求各位数字平方和的函数也要熟练。

1.两数之和

题目链接:https://leetcode.cn/problems/two-sum/description/

我的代码:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> record;
        for (int i = 0; i < nums.size(); i++) {
            auto iter = record.find(target - nums[i]);
            if (iter != record.end()) {
                return {i, iter->second};
            }
            record.insert(pair<int, int>(nums[i], i));
        }
        return {};
    }
};

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树,这道题目中并不需要key有序,选择std::unordered_map 效率更高。

标签:202,return,int,随想录,record,vector,set,unordered,两数
From: https://www.cnblogs.com/kurumaruq/p/18345320

相关文章

  • 2024美团官方霸王餐API接口
    在数字化日益深入的今天,餐饮行业正经历着一场前所未有的变革。作为行业内的领军企业,美团不断推出创新服务以优化用户体验,提升商家运营效率。其中,2024年美团官方推出的霸王餐API接口便是这一趋势下的重要产物。本文将从接口的背景、功能、优势、应用场景以及未来展望等方面,深入剖析......
  • 2024.08 别急记录
    1.ARC072F-Dam发现当\(t\)递增时优先倒掉前面的,再选后面的;否则优先选后面的,再一起倒掉。所以维护单调队列中\(t\)递增,每次弹出队首\(>L\)的部分,然后插入队尾。若队尾\(t_{i-1}>t_i\)则将两个合并。点击查看代码//AT_arc072_d#include<bits/stdc++.h>usingnames......
  • 2024.8.7 模拟赛题解
    T1过于简单,不必阐述。T2给定一个仅包含\(A\)和\(P\)的字符串,每次操作可以删除相邻的\(AP\)或者\(PP\),问字符串最后的最小长度。$Sol:$为求最值问题,考虑贪心。先给出考场做法。发现若干的\(P\)是一定能合并掉的,于是贪心策略,就是如何最小化\(A\)的个数。对于每个......
  • 【ACM独立出版 | EI&Scopus检索稳定 | 高录用】2024年数字经济,区块链与人工智能国际学
    2024年数字经济,区块链与人工智能国际学术会议(DEBAI2024)为第五届大数据与社会科学国际学术会议(ICBDSS2024)的分会,将于2024年8月23-25日在中国-广州隆重举行。为了让更多的学者有机会参与会议分享交流经验。本次会议主要围绕“数字经济,区块链与人工智能等研究领域展开讨论......
  • 2024最新Mysql锁机制与优化实践以及MVCC底层原理剖析
    锁机制详解锁是计算机协调多个进程或线程并发访问某一资源的机制。在数据库中,除了传统的计算资源(如CPU、RAM、I/O等)的争用以外,数据也是一种供需要用户共享的资源。如何保证数据并发访问的一致性、有效性是所有数据库必须解决的一个问题,锁冲突也是影响数据库并发访问性能的一......
  • 2024MySQL最新索引优化实战二
    分页查询优化示例表:CREATETABLE`employees`(`id`int(11)NOTNULLAUTO_INCREMENT,`name`varchar(24)NOTNULLDEFAULT''COMMENT'姓名',`age`int(11)NOTNULLDEFAULT'0'COMMENT'年龄',`position`varchar(20)NOTN......
  • Java计算机毕业设计个人博客微信小程序演示录像220239(开题报告+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着互联网技术的飞速发展和智能手机的普及,个人博客作为一种重要的网络表达和信息分享方式,逐渐从传统的PC端向移动端延伸。微信小程序作为一种轻量级......
  • 【AI资讯早报】AI科技前沿资讯概览:2024年8月7日早报
    【AI资讯早报,感知未来】AI科技前沿资讯概览,涵盖了行业大会、技术创新、应用场景、行业动态等多个方面,全面展现了AI领域的最新发展动态和未来趋势。一、全球AI投资持续增长据国际数据公司(IDC)最新预测,到2027年,全球在人工智能解决方案上的支出预计将超过5000亿美元。这一数据揭......
  • 代码随想录Day8
    344.反转字符串编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用\(O(1)\)的额外空间解决这一问题。示例1:输入:s=["h","e","l","l","o"]输出:["o","l","l","e",&q......
  • 【题解】Solution Set - NOIP2024集训Day1 数据结构
    【题解】SolutionSet-NOIP2024集训Day1数据结构https://www.becoder.com.cn/contest/5429「CF1428F」FruitSequences线段树是可以维护区间最长子段的1。记固定右端点在\(i\),的答案为\(f_i\)。那么:\(a_i=0\),\(f_i=f_{i-1}\);\(a_i=1\),打一个单调栈维护所有的最长子......