秋招突击——7/5——复习{}——新作{跳跃游戏II、划分字母区间、数组中的第K个大的元素(模板题,重要)、前K个高频元素}

文章目录

    • 引言
    • 正文
      • 贪心——45 跳跃游戏II
        • 个人实现
        • 参考实现
      • 划分字母区间
        • 个人实现
      • 参考实现
      • 数组中的第K个最大元素
        • 个人实现
        • 参考做法
      • 前K个高频元素
        • 个人实现
        • 参考实现
    • 总结

引言

  • 今天就开始的蛮早的,现在是九点多,刚好开始做算法,今天有希望能够将项目的内容整理一下,然后再修改丰富一下我的简历,这个已经拖了很久了,加把劲,累点就累点吧。

正文

贪心——45 跳跃游戏II

题目链接
在这里插入图片描述
注意

  • 所有测试用例都是可到达,所有不用考虑不能到达最终目标的情况
  • 边界存在的条件为1的情况,需要考虑一下
  • 返回的是最小跳数
  • f[i] = f[i -1] + 1,如果f[i-1]到达时已经是最小跳数,那么f[i]的最小跳数就是上一个状态的最小跳数+1
个人实现
  • 想着使用动态规划实现,因为上一个状态最小的情况下,到当前状态的最小就是默认加1,想想看怎么做的。
  • f[i]表示从0到i的最小跳数,当前是在节点i,那么就遍历在当前nums[i]范围内的所有的跳数,更新一下对应的数组就行了。
class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> f(nums.size() + 1,INT_MAX);
        f[0] = 0;
        for(int i = 0;i < nums.size();i ++){
            for(int j = 1;j <= nums[i];j ++){
                if(i + j < nums.size()) f[i + j] = min(f[i + j],f[i] + 1);
            }
        }
        return f[nums.size() - 1];
    }
};
  • 意料之外,居然没有超时,我靠,太意料之外了。这个计算量得是10的7次方最大,居然没有超时,没超时就没超时把!

在这里插入图片描述

参考实现

在这里插入图片描述
在这里插入图片描述

  • 这里是维护跳数的区间数组,在某一个区间内的最小跳数始终是固定的,而且随着往后遍历,区间的跳数是递增的,根据上述推论实现代码如下
class Solution {
public:
    int jump(vector<int>& nums) {
    vector<int> f(nums.size() + 1,0);
    for(int i = 1,j = 0;i < nums.size();i ++){
        while(j + nums[j] < i)  j ++;       // 不断将j向后移动,保证当前跳数范围包括了对应i
        f[i] = f[j] + 1;// 更新每一个节点所属的最少跳数段落信息,维护对应的数组
    }
    return f[nums.size() - 1];
    }
};

确实很巧妙,学到了,这个跳数这里应该不会再出问题了

这个可以看看之前的做的跳跃游戏原始版本,题目链接

  • 那道题也是使用类似方法,主要是通过最远距离和i之间的关系,判定能否到达最远距离,中间会不会出现断链的情况。

划分字母区间

  • 题目链接
    在这里插入图片描述
    在这里插入图片描述

注意

  • 同一个字母最多出现在一个片段中,每一个字母只能用一次
  • 片段数最多的情况
  • 所有划分结果顺序拼接,最终仍然是s
  • 小写英文字母组成
  • 长度最小是1
    保证每一个片段的字母是彼此不同的,而且要保证最终的片段数尽可能多
个人实现
  • 这里有一个约束,就是每一个字母只能在一个片段出现,不能横跨两个片段,这个怎么实现?
  • 这个题也是类似横跨区间的问题,保证一个字母出现的第一个索引和最后一个索引都是在同一个片段内部,不然就不满足约束条件,所以需要记录所有的字母的出现的两个位置。
  • 然后就是怎么合理的安排区间的问题。是否需要进行二次遍历,保证区间的相互包含,从而实现最多的划分。
  • 这里的时间复杂度目测是O(n),我需要遍历两次
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        
        // 更新记录每一个元素出现的最早的位置和
        vector<pair<int,int>> word(27,{s.size() - 1,0});
        for(int i = 0;i < s.size();i ++){
            word[s[i] - 'a'].first = min(i,word[s[i] - 'a'].first);
            word[s[i] - 'a'].second = max(i, word[s[i] - 'a'].second);
        }
        cout<<word[s[0] - 'a'].first<<endl;
        cout<<word[s[0] - 'a'].second<<endl;


        // 再次遍历计算区间的长度
        int beg = word[s[0] - 'a'].first , end = word[s[0] - 'a'].second;
        for(int i = 0;i < s.size();i ++){
            end = max(word[s[i] - 'a'].second,end);
            if(i == end){
                // 遍历到尾节点,直接添加结果
                res.push_back(end - beg + 1);
                beg = i + 1;
                if(i + 1 < s.size())    end = word[s[i + 1] - 'a'].second;
            }
        }
        return res;
    }
};

在这里插入图片描述

  • 这个方法中规中矩,没有任何异常,代码量也挺多的。不过做出来了。

参考实现

序列是无序的

  • 从前往后和从后往前效果是一样的
  • 是否需要进行排序,保证他是有序的,降低问题的难度

正式思路

  • 思路和我的差不多,只不过 他是仅仅记录了每一个字母出现的最终位置,而且使用的是hashmap,这里就得讨论一下,使用数组和hashmap哪个更快。理论上来时数组更快,但是写起来比较难看。

  • 具体实现代码如下,基本上都是一致的

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        
        // 更新记录每一个元素出现的最早的位置和
        vector<int> word(27,0);
        for(int i = 0;i < s.size();i ++){
            word[s[i] - 'a'] = max(i, word[s[i] - 'a']);
        }
        cout<<word[s[0] - 'a']<<endl;


        // 再次遍历计算区间的长度
        int beg = 0 , end = word[s[0] - 'a'];
        for(int i = 0;i < s.size();i ++){
            end = max(word[s[i] - 'a'],end);
            if(i == end){
                // 遍历到尾节点,直接添加结果
                res.push_back(end - beg + 1);
                beg = i + 1;
                if(i + 1 < s.size())    end = word[s[i + 1] - 'a'];
            }
        }
        return res;
    }
};

数组中的第K个最大元素

题目链接
在这里插入图片描述
注意

  • 规定了时间复杂度,O(n)只能遍历一次
  • 第K大的元素,是排序只有第K大的元素
  • 数组长度[1, 1 0 5 10^5 105]
  • 每一个元素范围是正负 1 0 4 10^{4} 104
  • 元素与元素之家存在重复的情况
个人实现
  • 这里是制定了,只能通过遍历来实现,想想看怎么做。
  • 转换一下问题思路,如果是找最大的元素,就是完整的遍历并且比较一遍,然后找最小的元素也使完整的遍历一遍,然后在比较一遍,确定一个最大值。
  • 如果是确定第二大的数字,就是如果一个数字比最大的大的话,就默认往后进行顺。
  • 所以这里想办法维护一个队列,每次都是从和队首元素进行比较,然后固定长度是K,如果超过了固定长度直接弹出最后一个元素。
  • 这样不一定是目标值。

对于队列的使用有点问题了,然后返回的是队首的元素。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        queue<int> q;
        for(auto x :nums){
            //队列是空的,直接添加
            if(q.empty())   q.push(x);
            // 如果大于队首元素,直接入队
            if(q.back() < x )   q.push(x);
            while(q.size() > k)    q.pop();
        }
       
        return q.front();

    }
};
  • 这里只能通过一半的样例,如果一开始就给我最大值,通不过测试样例,所以不行!
  • 这个方法根本就不行!
    在这里插入图片描述
  • 不会做!
  • 使用堆排序,肯定不对呀,是logN的操作复杂度
参考做法
  • 这里是一道模板题,是建立在快排的基础上实现的,所以需要背一下快排的模板,具体如下
    在这里插入图片描述
void quick_sort(int q[],int l,int r){
	if(l >= r)	return ;
	// 确定中间值、左边界、右边界
	// 中间元素不参加排序,i是从x的左侧一个开始,j是从x的右侧开始
	int i = l - 1,j = r + 1,x = q[l + r >> 1];
	while(i < j){
		do i ++; while(q[i] < x);
		do j -- ;while(q[j] > x);
		if(i < j)	swap(q[i],q[j]);
	}
	quick_sort(q,l,j),quick_sort(q,j + 1,r);
}
  • 这里的j就是最终的区分索引,所以k应该也是和j进行比较,然后再进行判定的是左边进行快排,还是右边进行快排。
  • 这是一道经典的模板题,需要好好背一下。
  • 根据模板题,好好做一下
class Solution {
public:
    int quickSort(vector<int> &nums,int l,int r,int k){
        if(l == r)  return  nums[k];
        int i = l - 1,j = r + 1 ,x = nums[(l + r) >> 1];
        while(i < j){
            do i ++ ;while(nums[i] > x);
            do j -- ; while(nums[j] < x);
            if(i < j) swap(nums[i],nums[j]);
        }   
        if(k <= j)   return quickSort(nums,l,j,k);
        else  return quickSort(nums,j + 1,r,k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        return quickSort(nums,0,nums.size() - 1,k-1);
    }
};
  • 这是一个模板题,只能说是超过了我的知识范围,所以还是得不断补充完善。

前K个高频元素

题目链接

在这里插入图片描述
注意

  • 出现频率前K高的元素
  • 按照任意顺序返回
  • 数据保证答案唯一
个人实现
  • 这道题没有说数据是有序的,并不能从顺序进行考虑。
  • 最直白的做法, 统计每一个元素出现的次数,然后使用出现的次数进行排序,然后返回前k高地元素,也就是返回阈值之前的所有的元素。
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>  counts;
        for(auto x : nums)  counts[x] ++;
        vector<pair<int,int>>   ct;
        for(auto item : counts) ct.push_back({item.first,item.second});
        sort(ct.begin(),ct.end(),[](auto a,auto b){
            return a.second > b.second;
        });
        vector<int> res;
        for(int i = 0;i < k;i ++)   res.push_back(ct[i].first);
        return res;
       
    }
};
  • 纯硬做,直接模拟思路,完全照搬!
    在这里插入图片描述
参考实现
  • 前半部分思路是一样的,就是要统计每一个元素的出现的次数,然后形成一个key-value键值对,然后使用计数排序,实现前k个频率最高的元素的计算。
  • 具体代码如下
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>  counts;
        for(auto x : nums)  counts[x] ++;
        int m = nums.size();
        vector<int>   ct(m + 1,0);
        // 实现计数排序
        for(auto [k,v]:counts)  ct[v] ++;
        // 遍历前k个元素,计算一个边界次数
        int edg = m,s = 0;
        while(s < k)   s+= ct[edg --];
        // 遍历获取的满足条件的k
        vector<int> res;
        for(auto [k,v]:counts)  {
            if(v > edg)   res.push_back(k);
        }
        return res;
    }
};

遍历map的好方法

  • 使用[a,b]然后加上auto实现
for(auto [k,v] : map)

总结

  • 大概测了一下,发现自己做一道题,加上修改的总结的时间是超过了50分钟的,有点吓人,一天得花多少时间是用来做算法题。还是得快一点。
  • 可以,今天的效率蛮快的,在十一点就完成了算法题的内容,下面再补充一下关于设计模式的相关知识,然后下午就看一下我们的项目了。加油,冲 !
  • 剑走偏锋呀,感觉自己的路子不对,很多东西都没有专门走过,所以就会有很多问题,现在得转换一下思路,项目的代码我看的不是很懂,那就要从不是很懂的地方一点点开始看,一点点开始弄。现在欠缺了太多东西,后续还要增加每天一样的知识补充。其实很多东西,都是要花时间去弄的,现在就是知道MySQL的基础的东西,但是对于高可用的东西,并不了解。然后Java的多线程编程也不知道,感觉还是得花大时间。
  • 现在应该专心去弄什么?有点乱,感觉有点自暴自弃,觉得完蛋了,但是其实那几个项目并不难,跟着往后做就行了。加油吧。如果有不懂的,就去找SSM中学过的,然后就是哪里不行,补充哪里。
  • 我得调整一下自己的计划,现在欠缺的是项目还有简历,得想办法结合项目,把简历整理出来,后续再根据简历上的东西进行一点点补充。
  • 看项目有点吃力,是因为我从来没有跟着一个东西,从头到尾敲过一个项目,所以看的很吃力。
  • 晚上有点摆烂了,学了一天了,太累了,晚上注意力难以集中!!
  • 明天加油吧!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/776687.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

封锁-封锁模式(共享锁、排他锁)、封锁协议(两阶段封锁协议)

一、引言 1、封锁技术是目前大多数商用DBMS采用的并发控制技术&#xff0c;封锁技术通过在数据库对象上维护锁来实现并发事务非串行调度的冲突可串行化 2、基于锁的并发控制的基本思想是&#xff1a; 当一个事务对需要访问的数据库对象&#xff0c;例如关系、元组等进行操作…

RocketMQ-订阅一致及解决方案

背景 这里借用Rocketmq官方的一句话来描述订阅关系一致: 订阅关系一致指的是同一个消费者分组Group ID下&#xff0c;所有Consumer实例所订阅的Topic和Tag必须完全一致。如果订阅关系不一致&#xff0c;可能导致消息消费逻辑混乱&#xff0c;消息被重复消费或遗漏。 具体的问题…

BS结构的毕业设计题目管理系统-计算机毕业设计源码92342

目 录 摘要 1 绪论 1.1 研究背景 1.2目的及意义 1.3论文结构与章节安排 2 毕业设计题目管理系统设计分析 2.1 可行性分析 2.1.1 技术可行性分析 2.1.2 经济可行性分析 2.1.3 法律可行性分析 2.2 系统功能分析 2.2.1 功能性分析 2.2.2 非功能性分析 2.3 系统用例分…

3D打印推动透气钢革命

在科技日新月异的今天&#xff0c;3D打印技术如同一股强劲的潮流&#xff0c;正悄然改变着制造业。从简单的塑料玩具到复杂的工业部件&#xff0c;再到高精尖的医疗器械&#xff0c;3D打印技术凭借其独特的优势&#xff0c;不断拓宽着应用的边界。今天&#xff0c;我们一起深度…

Linux-DNS

DNS域名解析服务 1.DNS介绍 DNS 是域名系统 (Domain Name System) 的缩写&#xff0c;是因特网的一项核心服务&#xff0c;它作为可以将域名和IP地址相互映射的一个分布式数据库&#xff0c;能够使人更方便的访问互联网&#xff0c;而不用去记住能够被机器直接读取的IP数串。…

MySQL/SqlServer 跨服务器 增删改查(CRUD) 的一种方法

前言&#xff1a;主要是利用SqlServer 的链接服务器功能 1.准备一台 SqlServer Server&#xff0c;服务如下图&#xff1a; 这台服务器专门用于 链接服务器 IP&#xff1a;10.x.x.3 和数据源服务器&#xff08;10.x.x.5&#xff09; 在一个局域网 1.1 版本 是 2017 2.在 10.…

算法体系-26 第二十六节:第26节:单调栈结构 (5节)

一 单调栈知识讲解 1.1描述 一个数组里面想的到每个位置与他最近的左边和右边比他小的最近的信息 1.2 分析 通过单调栈的特点&#xff0c;for遍历数组中的每个数&#xff0c;当前数来的时候对比单调栈中的数进行每个数的左右判断完满足条件的进行更新到当前i种的 int[][] re…

MySQL索引教程(01):创建索引

文章目录 MySQL 创建索引索引介绍MySQL CREATE INDEX 语法MySQL 索引类型MySQL CREATE INDEX 实例结论 MySQL 创建索引 对于一个具有大量数据行的表&#xff0c;如果你根据某个查询条件检索数据时很慢&#xff0c;可能是因为你没有在检索条件相关的列上创建索引。 索引类似于…

平价猫粮新选择!福派斯鲜肉猫粮,让猫咪享受美味大餐!

福派斯鲜肉猫粮&#xff0c;作为一款备受铲屎官们青睐的猫粮品牌&#xff0c;凭借其卓越的品质和高性价比&#xff0c;为众多猫主带来了健康与美味的双重享受。接下来&#xff0c;我们将从多个维度对这款猫粮进行解析&#xff0c;让各位铲屎官更加全面地了解它的魅力所在。 1️…

查看电脑显卡(NVIDIA)应该匹配什么版本的CUDA Toolkit

被串行计算逼到要吐时&#xff0c;决定重拾CUDa了&#xff0c;想想那光速般的处理感觉&#xff08;夸张了&#xff09;不要太爽&#xff0c;记下我的闯关记录。正好我的电脑配了NVIDIA独显&#xff0c;GTX1650&#xff0c;有菜可以炒呀&#xff0c;没有英伟达的要绕道了。回到正…

详细分析SQL语句中的硬解析、软解析、软软解析基本知识

目录 前言1. 基本知识2. Demo 前言 从实战中探索 图为全局搜索且在高并发下&#xff0c;会引发硬解析&#xff0c;导致CPU崩溃 1. 基本知识 解析 (parsing) 是数据库在处理 SQL 语句时必不可少的一步&#xff0c;它将 SQL 语句转换为数据库可以执行的低级指令 硬解析 (Hard…

昇思25天学习打卡营第18天|Pix2Pix实现图像转换

Pix2Pix概述 Pix2Pix是基于条件生成对抗网络实现的一种深度学习图像转换模型。Pix2Pix是将cGAN应用于有监督的图像到图像翻译&#xff0c;包括生成器和判别器。 基础原理 cGAN的生成器是将输入图片作为指导信息&#xff0c;由输入图像不断尝试生成用于迷惑判别器的“假”图像…

c++ 附赠课程的知识点记录

&#xff08;1&#xff09; 静态变量的赋值 再一个例子&#xff1a; &#xff08;2&#xff09; 一般在定义类的赋值运算符函数时&#xff0c; operator ( const A& a ) 函数&#xff0c;应避免自赋值的情况&#xff0c;就是把对象 a 又赋值给 对象a 如同 a a 这样的情况…

类和对象深入理解

目录 static成员概念静态成员变量面试题补充代码1代码2代码3如何访问private中的成员变量 静态成员函数静态成员函数没有this指针 特性 友元友元函数友元类 内部类特性1特性2 匿名对象拷贝对象时的一些编译器优化 感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接…

C++ | Leetcode C++题解之第217题存在重复元素

题目&#xff1a; 题解&#xff1a; class Solution { public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> s;for (int x: nums) {if (s.find(x) ! s.end()) {return true;}s.insert(x);}return false;} };

【PB案例学习笔记】-27制作一个控制任务栏显示与隐藏的小程序

写在前面 这是PB案例学习笔记系列文章的第27篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…

视频参考帧和重构帧复用

1、 视频编码中的参考帧和重构帧 从下图的编码框架可以看出&#xff0c;每编码一帧需要先使用当前帧CU(n)减去当前帧的参考帧CU&#xff08;n&#xff09;得到残差。同时&#xff0c;需要将当前帧的重构帧CU*&#xff08;n&#xff09;输出&#xff0c;然后再读取重构帧进行预测…

Pandas数据可视化详解:大案例解析(第27天)

系列文章目录 Pandas数据可视化解决不显示中文和负号问题matplotlib数据可视化seaborn数据可视化pyecharts数据可视化优衣库数据分析案例 文章目录 系列文章目录前言1. Pandas数据可视化1.1 案例解析&#xff1a;代码实现 2. 解决不显示中文和负号问题3. matplotlib数据可视化…

HTTP代理服务器:深度解析与应用

“随着互联网的飞速发展&#xff0c;HTTP代理服务器在网络通信中扮演着越来越重要的角色。它们作为客户端和服务器之间的中介&#xff0c;不仅优化了网络性能&#xff0c;还提供了强大的安全性和隐私保护功能。” 一、HTTP代理服务器的概念与作用 HTTP代理服务器是一种能够接…

Qt扫盲-QRect矩形描述类

QRect矩形描述总结 一、概述二、常用函数1. 移动类2. 属性函数3. 判断4. 比较计算 三、渲染三、坐标 一、概述 QRect类使用整数精度在平面中定义一个矩形。在绘图的时候经常使用&#xff0c;作为一个二维的参数描述类。 一个矩形主要有两个重要属性&#xff0c;一个是坐标&am…