C国演义 [第十一章]

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

有效的字母异位词

力扣链接
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词

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

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

  • 提示:
    1 <= s.length, t.length <= 5 * 104
    s 和 t 仅包含小写字母

题目理解

因为题目的要求是:

  • 两个数组 仅仅包含小写字母 ⇒ 一共才26个英语字母
  • 两个数组的大小是 1 <= length <= 5*10的四次方

⇒ 我们可以采用 哈希的思想
我们可以用一个数组(利用下标)来记录两个数组中每个字母出现的次数
然后通过比较 每个字母出现的次数 和 0 进行比较

🗨️那小写字母如何装换为数组下标?

  • 通过ASCLL码来进行转化 ⇒ 字母 - 'a'

代码

class Solution {
public:
    bool isAnagram(string s, string t) 
    {
        int sum[26] = {0};
        
        // 如果两个数组的大小都不一样, 那就直接返回 false
        if(s.size() != t.size())
            return false;
        
        for(int i = 0; i < s.size(); i++)
        {
            sum[s[i] - 'a']++; // a数组的此字母对应的下标++
            sum[t[i] - 'a']--; // b数组的此字母对应的下标--
        }
        
        // 如果两个数组每个字符出现的次数是一样的, 每个下标对应的都是 0
        for(int i = 0; i < 26; i++)
        {
            if(sum[i] != 0)
                return false;
        }
        return true;
    }
};

C国演义 [第十一章],c语言,哈希算法,算法,leetcode,数据结构


两数之和

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

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

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

示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]

示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]

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

题目理解(暴力篇)

这题一看就是 低配版 ⇒ 2 <= size( ) <= 10^4, 这个数组的大小就是很巴适
暴力解法就是 两个for循环 ⇒ 最大时间也是 10^8, 不会爆时间的

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        vector<int> sum;
        for(int i = 0; i < nums.size(); i++)
        {
            for(int j = i + 1; j < nums.size(); j++)
            {
                if(nums[j] == target - nums[i])
                {
                    sum.push_back(i);
                    sum.push_back(j);
                    break;
                }
            }
        }
        
        return sum;
    }
};

C国演义 [第十一章],c语言,哈希算法,算法,leetcode,数据结构

题目理解(哈希篇)

我们就会发现, 暴力解法虽然可以, 但是执行时间很长, 那有没有执行时间短的方法呢?

我们的一个思路是:
当我们顺序遍历该数组时, 当我们遍历到一个特定的下标(nums[i])时, 我们需要知道 target - nums[i] 这个数字是否在之前遍历过的数字里面出现过

  1. 如果出现 — — 返回 (target - nums[i]) 的下标 和 nums[i]的下标 (i)
  2. 如果没有出现 — — 不返回,
    • 如果直至数组的结尾, 也没有出现, 那就返回空

当我们查询一个元素是否出现过, 或者一个元素在一个集合中是否存在 — — 那就可以使用哈希

在本题中, 我们不仅需要知道 (target - nums[i])这个数是否遍历过, 也要知道 (target - nums[i]) 的下标

那么我们就不能用数组来进行存储了, 可以采用 map的方式进行存储 (key, value)

⇒ key该存储什么, value又该存储什么呢?
由于本题需要返回的是下标, 所以 key应该存储下标, valu来存储数值

⇒ 那map有三种形式, 我们应该选取哪一种呢? map, unordered_map, multimap
C国演义 [第十一章],c语言,哈希算法,算法,leetcode,数据结构

由于unordered_map的查询效率是三个当中最快的, 那么我们就选用 unordered_map

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        // 选用unordered_map这个数据结构
        std::unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); i++)
        {
            // 查询 target - nums[i]是否被遍历过
            auto cur = map.find(target - nums[i]);

            // 之前有被遍历过, 那就直接返回
            if(cur != map.end())
            {
                return {cur->second, i};
            }

            // 没有遍历过, 那就收入map里面
            map.insert(pair<int, int> (nums[i], i));
        }

        // 最后在map里面都没有找到, 那就返回空
        return {}; 
    }
};

C国演义 [第十一章],c语言,哈希算法,算法,leetcode,数据结构

  • 这个题目要搞懂的四个点:
  1. 为什么要选取哈希的算法
  2. 哈希为啥要用map的数据结构
  3. map是用来干什么的
  4. map中的key是用来存放什么的, value是用来存放什么的

个人感觉, 搞懂这四个点, 那么此题目就理得条条顺顺喽!!!


人是有惰性属性的动物,一旦过多地沉湎于温柔之乡,就更削弱了重新投入风暴的勇气和力量. — — 路遥<早晨从中午开始>文章来源地址https://www.toymoban.com/news/detail-603199.html

到了这里,关于C国演义 [第十一章]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 第十一章 请求响应

    将前端发送的请求封装为HttpServletRequest对象 在通过HttpServletResponse 在前后端分离开发中,后端每开发完一个功能,就想要对这个接口功能进行测试 由于是前后端分离开发,所以没有前端页面 我们一般是在浏览器中直接输入地址,来访问我们所开发的web应用 但是浏览器发起的

    2024年01月21日
    浏览(59)
  • shell 第十一章

    1.写一个库函数,用定时任务调用这个库函数,每月1号执行 1.sh:  1.1.sh:   2.以免交互的方式实现 ssh 远程登录,密码错误也直接退出,不用人干预 3.以免交互的方式,实现磁盘分区、格式化、挂载

    2024年02月08日
    浏览(59)
  • 第十一章:deque类

    deque是一种双开口的“连续空间”的容器。 deque(双端队列):是一种双开口的\\\"连续\\\"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高 。 deque并不是真正连

    2024年02月15日
    浏览(38)
  • 第十一章 后端编译与优化

    如果我们把字节码看作是程序语言的一种中间表示形式(Intermediate Representation, IR)的话,那编译器无论在何时、在何种状态下把 Class 文件转换成与 本地基础设施(硬件指令集、操作系统)相关的二进制机器码 ,它都可以视为整个编译过程的后端。 ​ 无论是提前编译器抑

    2024年01月23日
    浏览(48)
  • ChatGPT 之言情作家:第一章到第十一章

    原文:THE CHATGPT ROMANCE AUTHOR 译者:飞龙 协议:CC BY-NC-SA 4.0 和你一样,我喜欢写言情小说,在过去的二十年里,我对流派商业小说中故事构思和作者创业的力量产生了浓厚的兴趣。 我的目标很简单。我想了解如何将故事构思应用到塑造一个引人入胜的商业小说故事中,以吸引

    2024年01月19日
    浏览(64)
  • 【OpenCV】第十一章: 图像金字塔

    第十一章: 图像金字塔 一、什么是图像金字塔¶ 同一张图片不同分辨率的子图的集合。 图像金字塔底部是待处理的高分辨率图像,也就是原始图像,顶部是低分辨率的近似图像。一般情况下,都是每向上移动一级,图像的宽和高都降低为原来的1/2 。 二、为什么要生成图像金

    2024年02月03日
    浏览(50)
  • 第十一章 Unity Transform组件(上)

    本章节我们介绍Transform类,它是一个组件,每一个游戏对象有拥有该组件。因此,它值得我们重点介绍一下。Transform代表了游戏对象的世界变换,也就是移动,选择和缩放。 首先,我们先介绍它的属性(类变量),如下所示 1. gameObject 附加到的当前游戏对象,来自父类Compo

    2024年02月05日
    浏览(42)
  • 西瓜书读书笔记整理(十一) —— 第十一章 特征选择与稀疏学习

    11.1.1 基本概念 特征(feature) :在机器学习中, 特征 是指从数据中提取的用于描述样本的属性或信息。 相关特征(relevant feature) :对当前学习任务 有用 的属性称为 “ 相关特征 ”。 无关特征(inrelevant feature) :对当前学习任务 无用 的属性称为 “ 无关特征 ”。 冗余特

    2024年01月19日
    浏览(54)
  • 第十一章 Python第三方库纵览

    11.1 网络爬虫方向 网络爬虫是自动进行HTTP访问并捕获HTML页面的程序。Python语言提供了多个具备网络爬虫功能的第三方库。这里介绍两个常用的Python网络爬虫库: requests和scrapy 。 11.1.1 requests requests库是一个简洁且简单的处理HTTP请求的第三方库,其最大优点是程序编写过程更

    2024年02月08日
    浏览(39)
  • Vue 3 第十一章:组件二(组件通信)

    1.1. 父子组件之间的通信 1.1.1 父组件向子组件传值 方式一:父组件给子组件传值时,通过 v-on 绑定属性实现 子组件通过 defineProps 来接收接收父组件传递的值。 使用字符串的形式接收父组件传递的值 使用对象的形式接收父组件传递的值 使用对象的形式接收父组件传递的值

    2023年04月26日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包