网站移动端适配怎么做,金乡县网站开发,北京广告设计公司排名前十强,网站建设销售顾问开场白文章目录 引言正文贪心——45 跳跃游戏II个人实现参考实现 划分字母区间个人实现参考实现 数组中的第K个最大元素个人实现参考做法 前K个高频元素个人实现参考实现 总结 引言
今天就开始的蛮早的#xff0c;现在是九点多#xff0c;刚好开始做算法#xff0c;今天有希望能够… 文章目录 引言正文贪心——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(vectorint nums) {vectorint 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(vectorint nums) {vectorint f(nums.size() 1,0);for(int i 1,j 0;i nums.size();i ){while(j nums[j] i) j ; // 不断将j向后移动保证当前跳数范围包括了对应if[i] f[j] 1;// 更新每一个节点所属的最少跳数段落信息维护对应的数组}return f[nums.size() - 1];}
};确实很巧妙学到了这个跳数这里应该不会再出问题了
这个可以看看之前的做的跳跃游戏原始版本题目链接
那道题也是使用类似方法主要是通过最远距离和i之间的关系判定能否到达最远距离中间会不会出现断链的情况。
划分字母区间
题目链接
注意
同一个字母最多出现在一个片段中每一个字母只能用一次片段数最多的情况所有划分结果顺序拼接最终仍然是s小写英文字母组成长度最小是1 保证每一个片段的字母是彼此不同的而且要保证最终的片段数尽可能多
个人实现
这里有一个约束就是每一个字母只能在一个片段出现不能横跨两个片段这个怎么实现这个题也是类似横跨区间的问题保证一个字母出现的第一个索引和最后一个索引都是在同一个片段内部不然就不满足约束条件所以需要记录所有的字母的出现的两个位置。然后就是怎么合理的安排区间的问题。是否需要进行二次遍历保证区间的相互包含从而实现最多的划分。这里的时间复杂度目测是O(n),我需要遍历两次
class Solution {
public:vectorint partitionLabels(string s) {vectorint res;// 更新记录每一个元素出现的最早的位置和vectorpairint,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);}coutword[s[0] - a].firstendl;coutword[s[0] - a].secondendl;// 再次遍历计算区间的长度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:vectorint partitionLabels(string s) {vectorint res;// 更新记录每一个元素出现的最早的位置和vectorint word(27,0);for(int i 0;i s.size();i ){word[s[i] - a] max(i, word[s[i] - a]);}coutword[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(vectorint nums, int k) {queueint 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(vectorint 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(vectorint nums, int k) {return quickSort(nums,0,nums.size() - 1,k-1);}
};这是一个模板题只能说是超过了我的知识范围所以还是得不断补充完善。
前K个高频元素
题目链接 注意
出现频率前K高的元素按照任意顺序返回数据保证答案唯一
个人实现
这道题没有说数据是有序的并不能从顺序进行考虑。最直白的做法 统计每一个元素出现的次数然后使用出现的次数进行排序然后返回前k高地元素也就是返回阈值之前的所有的元素。
class Solution {
public:vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int counts;for(auto x : nums) counts[x] ;vectorpairint,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;});vectorint res;for(int i 0;i k;i ) res.push_back(ct[i].first);return res;}
};纯硬做直接模拟思路完全照搬
参考实现
前半部分思路是一样的就是要统计每一个元素的出现的次数然后形成一个key-value键值对然后使用计数排序实现前k个频率最高的元素的计算。具体代码如下
class Solution {
public:vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int counts;for(auto x : nums) counts[x] ;int m nums.size();vectorint ct(m 1,0);// 实现计数排序for(auto [k,v]:counts) ct[v] ;// 遍历前k个元素计算一个边界次数int edg m,s 0;while(s k) s ct[edg --];// 遍历获取的满足条件的kvectorint 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中学过的然后就是哪里不行补充哪里。我得调整一下自己的计划现在欠缺的是项目还有简历得想办法结合项目把简历整理出来后续再根据简历上的东西进行一点点补充。看项目有点吃力是因为我从来没有跟着一个东西从头到尾敲过一个项目所以看的很吃力。晚上有点摆烂了学了一天了太累了晚上注意力难以集中明天加油吧
