首页 > 其他分享 >随想录Day5|242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

随想录Day5|242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

时间:2023-09-25 22:34:06浏览次数:48  
标签:map set return int sum 随想录 202 数组 两数

随想录Day5|242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

 

242. 有效的字母异位词

文章&视频讲解

给定两个字符串 st ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:st 中每个字符出现的次数都相同,则称 st 互为字母异位词。

  • 1 <= s.length, t.length <= 5 * 104
  • st 仅包含小写字母

 

来自卡尔的提示:用数组

 

第一想法

只要两个字符串的无序版本是一样的就可以了,本来脑子里浮现出的是类似Python的dict,形如{char: frequency, ...},然后再判断是否一致。但是既然只包含小写字母那就可以只开一个长度为26的数组,分别记录26个字母的出现次数。

悄悄看了一眼题解,更方便的方法是遍历s时在freq数组中++,遍历t时在freq数组中--,当且仅当数组最终全为0的时候两个字符串是异位词。数组第i个位置的值就是第i个字母出现的次数。

 

用时9min~

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

 

349. 两个数组的交集

文章&视频讲解

给定两个数组 nums1nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

 

来自卡尔的提示:用set

 

直接看题解了

感觉这个就是学用容器的事情,以及学到了range-based for循环的写法。主要就是熟悉接口和写法用的。

 

用时9min~

vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
{
    unordered_set<int> result;
    unordered_set<int> nums1_set(nums1.begin(), nums1.end());
    for (int num : nums2)
    {
        if (nums1_set.find(num) != nums1_set.end()) // nums2中的元素nums1中出现过
            result.insert(num);
    }
    return vector<int>(result.begin(), result.end());
}

 

202. 快乐数

文章讲解

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n快乐数 就返回 true ;不是,则返回 false

提示:1 <= n <= 2^31 - 1

 

来自卡尔的提示:用set

 

第一想法

有点没头绪,由于是int类型,取得每一个数位的值,就是while循环不断除以10直到最高位?那是不是专门写个处理这个逻辑的函数比较好,输入数字,输出每个数位的平方和。然后在isHappy中循环,如果有1就直接true,如果无限循环怎么办呢?

那就把之前的中间结果都存在unordered_set中,如果出现重复的就说明循环?并不是,不一定有重复结果就说明陷入了无限循环。

 

看了随想录题解的想法

题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!

所以这道题目使用哈希法,来判断这个sum是否重复出现,如果重复了就是return false, 否则一直找到sum为1为止。

所以可以保证这个过程得到的数字总是无限循环的,相当于题目告诉我们这个性质总是成立,所以确实一旦有重复结果就说明陷入了无限循环。1的平方还是1,所以1不会出现在这个循环中。

 

用时20min~

int getSum(int n)
{
    int sum = 0;
    while (n)
    {
        sum += (n % 10) * (n % 10);
        n /= 10;
    }
    return sum;
}

bool isHappy(int n)
{
    unordered_set<int> set;
    while (true)
    {
        int sum = getSum(n);
        if (sum == 1)
            return true;
        // sum重复了,已经陷入无限循环
        if (set.find(sum) != set.end())
            return false;
        else
            set.insert(sum);
        n = sum;
    }
}

 

1. 两数之和

文章&视频讲解

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

 

来自卡尔的提示:用map

 

第一想法

如果暴力扫描就是\(O(n^2)\),那就没意思了!如果化为map则按照“值:下标”的格式,在数值num的时候在map中寻找target - num,如果不存在则下一个,否则返回答案。感觉很合理!

 

看了随想录题解的想法

可以用autoiter好方便!并且学到了返回的比较好的写法!问了poe assistant,得到如下回答:

在C++中,return {i, j}表示返回一个初始化了两个值 ij 的匿名对象。这个匿名对象的类型是根据花括号中的值进行推断的。

如果 ij 具有相同的类型,那么返回的匿名对象类型将是一个std::pair(或者是其它的元组类型,具体取决于编译器的实现)。例如,如果 ij 都是整数类型,那么返回的类型将是 std::pair<int, int>

如果 ij 具有不同的类型,那么返回的匿名对象类型将是一个std::tuple(或者是其它的元组类型)。例如,如果 i 是整数类型,而 j 是浮点数类型,那么返回的类型将是 std::tuple<int, float>

时空复杂度均为\(O(n)\)。

 

用时13min~

vector<int> twoSum(vector<int> &nums, int target)
{
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++)
    {
        auto iter = map.find(target - nums[i]);
        // auto其实是unordered_map<int, int>::iterator
        if (iter != map.end())
            return {iter->second, i};
        map.insert(pair<int, int>(nums[i], i));
    }
    return {};
}

 

碎碎念

今天好像也是速通流的,主要还是学习C++里面的一些写法,思路没有特别麻烦的。

再懒一天,从明天开始就要带上时空复杂度分析了!

标签:map,set,return,int,sum,随想录,202,数组,两数
From: https://www.cnblogs.com/alouette/p/17729025.html

相关文章

  • 2022年抖音最近很火的游戏直播:挤地铁教程+源码+软件
    音最近很火的游戏直播:挤地铁教程+源码+软件先上车先吃肉,卡好后带货,卖号,引私域,接星途广告,接小程序广告,带小游戏赚收益均可。有需要的材料自取:提取码:9jbw ......
  • 2023最新PS(photoshop)Win+Mac免费下载安装包及教程内置AI绘画-网盘下载
    2023最新PS(photoshop)Win+Mac免费下载安装包及教程内置AI绘画-网盘下载2023最新PS(photoshop)免费下载安装教程来咯~「PhotoShop」全套,win+mac:https://pan.quark.cn/s/9d8d8ef5c400#/list/share所有版本都有1,复制链接浏览器打开,选择一个合适的版本并下载安装包。通常情况下,建......
  • 百度之星 2023 初赛第三场
    开场很顺利,一度进了前十《与蝴蝶一起消散吧》一开始没看到每波怪物的血量一样,浪费了一些时间《染色游戏》做了1h,思路很快就有了但想不清楚计数细节。第一次WA了后写了暴力,调过手造的数据后又WA了,然后才写拍。感觉还是得拍,不过计数题也不归我管(一开始以为《魔法阵》是分治......
  • The 2023 ICPC Asia Regionals Online Contest (2) MDIELK
    The2023ICPCAsiaRegionalsOnlineContest(2)MDIELKMDirtyWork题意:总共有\(n\)个问题,对于第\(i\)个问题需要\(a_i\)分钟。你可以随便选择一个没过的题去写,写完以后马上交,你有\(p_i\)的概率会错,错了不能跳题,你要花额外\(b_i\)的时间去\(debug\)。问你以最佳策略的最小罚......
  • CCF第三十一次计算机软件能力认证202309-1坐标变换(其一)
    第一题第二题一般比较简单,需要对编程达到熟悉的要求即可,不要求了解过多的数据结构和算法使用C提交一直编译错误,相同的代码使用C++提交却能通过,真是醉了坐标变化(其一)题目描述1.需要创建一个操作符矩阵,行和列分别是n和22.需要创建一个操作数矩阵,行和列分别是m和23.求出操作符......
  • 20230925打卡
    今天我参加了传统工程实训,并学习了Java中的类与对象。在传统工程实训中,我们通过实践来加强实际操作能力和问题解决能力。另外,我还学习了Java中的类与对象,这是构建Java应用程序的基础。通过学习类与对象的概念、属性和方法等基本知识,我能够了解如何在Java中创建和使用类与对象,并运......
  • 日常记录--day9--2023-9月25日--周一
    日程:今天满课,累死了,早上7点起床,吃早饭,去工程实训课,今天上的是机器人实训,造了个小车。下午Java,学了类和对象,晚上7-8点复习了一下,之后进行经典力扣。学了什么:Java让人头疼,来了道力扣题,还要继续加油,继续学习Javaweb。PS:不想学习,想要成为鼠标垫......
  • 2023.9.25
    昨天才说过要去416自习,今天就不得不给自己请个假了,身体不适,一整天持续咳嗽,先不谈我的身体吃不吃得消,去了也感觉肯定会影响到其他人而且我的课突然有一节调到了今天晚上,只能不去了。刚刚吃了点药,今晚把事情都处理完毕,明天不出问题,一定去416自习。 ......
  • 每日总结20230925
    代码时间(包括上课)5h代码量(行):400行博客数量(篇):1篇相关事项:1、今天上午进行的是相关大数据的测试,老师具体讲了讲相关题目的注意事项。2、今天上午没有完成该题目的编程,只能下午继续努力了。3、晚上问了问编程大佬,对具体的代码的使用有了新的认识,对该题目也就编的差不多了,剩下的......
  • 活动回顾 | 暴雨也无法阻挡的奔赴,2023 Meet TVM · 深圳站完美收官!
    2023MeetTVM·深圳站于2023年9月16日在腾讯大厦成功举办,百余名参与者亲临现场,聆听讲师们的精彩分享。作者|xixi编辑|三羊<br>本文首发于HyperAI超神经微信公众平台~<br>**由MLC.AI社区和HyperAI超神经主办,Openbayes贝式计算和腾讯AILab协办的2023Mee......