网站推广的案例天津网站app建设

当前位置： 首页 > news >正文

网站推广的案例,天津网站app建设,小程序上线需要多少钱,哪个网站找做软件下载✨感谢您阅读本篇文章#xff0c;文章内容是个人学习笔记的整理#xff0c;如果哪里有误的话还请您指正噢✨ ✨ 个人主页#xff1a;余辉zmh–CSDN博客 ✨ 文章所属专栏#xff1a;贪心算法篇–CSDN博客 文章目录 前言例题1.买卖股票的最佳时机2.买卖股票的最佳时机23.k次取… ✨感谢您阅读本篇文章文章内容是个人学习笔记的整理如果哪里有误的话还请您指正噢✨ ✨ 个人主页余辉zmh–CSDN博客 ✨ 文章所属专栏贪心算法篇–CSDN博客 文章目录 前言例题1.买卖股票的最佳时机2.买卖股票的最佳时机23.k次取反后的最大化数组和4.按身高排序5.优势洗牌6.最长回文串7.增减字符串匹配8.分发饼干 前言 本篇文章是对贪心算法练习题的讲解有关贪心算法的讲解可以看本系列的第一篇文章这里就不再重复讲解直接继续讲解例题。 例题 1.买卖股票的最佳时机 题目 算法原理 本道题的贪心策略很简单既然要求获取最高的利润而且本道题限制只能买卖一次那么就在整个股票价格中选择最低点买入最高点卖出即可这样就能保证利润最大化。 设置两个变量一个用来标记最低的买价一个用来标记当前利润遍历整个股票价格现将当前价格减去最低的买价更新利润然后更新当前价格是否是最低价。遍历完整个股票价格后当前利润就是最大的利润。 代码实现 int maxProfit(vectorint prices){//minnum表示最低的买价ret表示最高的利润int minnum INT_MAX, ret INT_MIN;for(auto x : prices){ret max(ret, x - minnum);minnum min(minnum, x);}if(ret0){return 0;}return ret; }2.买卖股票的最佳时机2 题目 算法原理 本道题和上一道题不同的是不再局限于只能买卖一次可以无限次买卖只要保证最后的利润是最大的即可。 首先需要明白什么时候买卖才能有利润不亏损那就是下一个价格比当前价格低也就是升序排列所以在上升趋势段买卖才会有利润但是在上升趋势段的什么时候买卖才能最大利润那肯定就是上升趋势段的最低点和最高点买入和卖出。因此找到所有升序段的利润然后相加就是整体的最大利润。这就是本道题的贪心策略。 这里有两种解法第一种就是找到一个升序段标记最低点和最高点的价格然后直接两个端点相减就是当前整个升序段的利润和第二种就是只要下一个的价格大于当前价格就买入和卖出。比如说当前有连续三天的价格都是上升趋势第一种方式就是在第一天买入第三天卖出只找开始和结尾。而第二种方式则是第一天买入第二天卖出然后第二天再买入第三天卖出将整个升序段的利润拆分成每一天利润最后每一天的利润和还是整个升序段的利润和。 代码实现 //方法一 int maxProfit(vectorint prices){//使用双指针找到上升趋势的最低点和最高点进行买卖int ret 0;for (int buy 0; buy prices.size(); buy){//卖指针从买指针位置开始找int sell buy;//找到上身趋势的最高点while(sell1prices.size()prices[sell]prices[sell1]){sell;}//在当前位置买卖ret prices[sell] - prices[buy];//更新买指针指向当前位置buy sell;}return ret; } //方法二 int maxProfit(vectorint prices){//在上升趋势段一天一天地买卖获取利润int ret 0;for (int i 0; i prices.size(); i){//如果下一个值大于当前值就直接买卖if(i1prices.size()prices[i1]prices[i]){ret prices[i 1] - prices[i];}}return ret; }3.k次取反后的最大化数组和 题目 算法原理 本道题的题意要求挑选数组中的一个数变化为相反数总共需要变化k次最后使变化后的数组和最大。注意一个数可以变化多次没有次数限制。 既然题意要求变化后的数组和最大那么每次变化都挑选最小的数变化不就行了吗这样就能对数组和的影响减小。但是数组中有正数和负数之分因此两种情况要分类讨论如果是负数的话负数的相反数是正数可以使数组和变大因此负数只需变化一次即可如果是正数的话还要继续分情况讨论如果当前剩余的k次为偶数正数变化两次后还是正数所以变化偶数次后还是当前数相当于不变对数组和无影响直接结束如果当前剩余的k次为奇数只需让最小的正数变化一次为负数这样对数组和的影响最小然后剩余偶数次变化偶数次后相当于不变直接结束即可。这就是本道题的贪心策略。 这里我是用小根堆数据结构来实现每次直接获取堆顶元素然后判断正负负数就变化一次变化后存放到堆中正数再判断剩余次数的奇偶如果是偶数直接结束相当于变化偶数次不变如果是奇数当前正数因为是最小的正数所以变化一次剩余偶数次同理直接结束。最后返回变化后的元素和 代码实现 struct Greater{bool operator()(const int p1,const int p2){return p1 p2;} }; int largestSumAfterKNegations(vectorint nums, int k){//建立一个小根堆priority_queueint, vectorint, Greater heap(nums.begin(), nums.end());while(k0){//获取堆顶元素int t heap.top();heap.pop();//如果堆顶元素是负数修改为正数if(t0){heap.push(-t);k–;}//如果堆顶元素是正数先判断当前剩余次数else{//如果次数为奇数修改最小的正数为负数次数减一剩余次数就是偶数//下一个正数进行偶数次的变换,相当于不变直接结束if(k%21){heap.push(-t);k 0;}//如果剩余偶数次当前正数变化完所有次数相当于不变直接结束else{heap.push(t);k 0;}}}int ret 0;while(!heap.empty()){retheap.top();heap.pop();}return ret; }4.按身高排序 题目 算法原理 本道题其实并不是贪心算法题但是本道题使用的策略会在下一道贪心算法题中用到因此可以先用这道题练习一下。 本道题就是一道简单的排序问题一个数组存放的是名字一个数组存放的是身高两个数组通过下标可以一一对应名字和身高然后就是按照身高排序返回排序后的名字。这里就存在了一个细节问题如果直接对身高这个数组排序排完序后名字数组没有变就会导致不能再通过下标一一对应名字和身高最后返回的名字顺序也就是错误的。 本道题有多种解法第一种就是可以使用二元数组重新创建一个数组数组里面存放的是键值对pairstring,int使每个名字一一对应各自的身高。然后将数组按照身高排序最后遍历数组返回名字即可。第二种就是可以借助哈希表建立名字和身高的映射关系其实和第一种同理只不过数据存储方式不一样实现过程还是相同的。 上面两种方式都可以实现但这里重点要介绍的还是第三种方式直接对下标进行排序建立一个新数组存放的是每一个下标然后通过Lambda表达式自定义排序规则[]是捕获列表用于排序时可以访问的外部变量这里排序的外部变量就是身高数组()内是参数列表对应下标数组中需要排序的两个下标{}内是函数体也就是排序规则的实现按照下标对应的身高数组中的身高进行排序。这样自定义排序规则就可以实现下标按照身高排序不改变原有的名字和身高数组最后再遍历排序好的下标数组通过下标就可以找到名字返回即可。 代码实现 vectorstring sortPeople(vectorstring names, vectorint heights){//建立一个下标数组int n names.size();vectorint index(n);for (int i 0; i n; i){index[i] i;}//对下标数组进行排序sort(index.begin(), index.end(), {return heights[i] heights[j]; });//提取结果vectorstring ret;for(auto i : index){ret.push_back(names[i]);}return ret; }5.优势洗牌 题目 算法原理 代码实现 vectorint advantageCount(vectorint nums1, vectorint nums2){int n nums1.size(), m nums2.size();//给数组2创建一个下标数组vectorint index(m);for (int i 0; i m; i){index[i] i;}// 数组1直接排序数组2通过下标数组排序,排升序sort(nums1.begin(), nums1.end());sort(index.begin(), index.end(), {return nums2[i] nums2[j]; });//创建一个结果数组用来存放数组1按题意要求的排序vectorint ret(n);//两个指针用来指向下标数组的前后位置int left 0, right m - 1;for (int i 0; i ; i){//如果第一个数组的值大于第二个数组的当前值左指针指向下标数组中的位置就是结果数组中存放的下标if(nums1[i]nums2[index[left]]){ret[index[left]] nums1[i];}//如果小于等于存放到右指针指向的下标位置else{ret[index[right–]] nums1[i];}}return ret; }6.最长回文串 题目 算法原理 本道题的贪心策略比较简单构成回文串时尽可能多地选取字符先统计所有字符的个数有奇数个也有偶数个如果当前字符是偶数个n那么回文串中一定包含所有的当前字符n个比如字符a有4个回文串就是aa|aa左右两侧平均分如果当前字符是奇数个n那么回文串中一定包含当前字符的n-1个比如字符b有5个回文串就是bb|bb当统计完所有字符后如果最后回文串的长度小于原字符串的长度说明存在奇数个字符随便选一个奇数个的字符放到中间|位置回文串的长度再加一。 代码实现 int longestPalindrome(string s){//建立哈希表统计字符的个数unordered_mapchar, int hash;for(auto ch : s){hash[ch];}int ret 0;for(auto [ch,count] : hash){//不管个数是奇数还是偶数都是先除以2再乘以2ret count / 2 * 2;}//如果最后回文串的长度小于原字符串的长度说明存在奇数个的字符回文串长度再1if(rets.size()){ret;}return ret; }7.增减字符串匹配 题目 算法原理 本道题的贪心策略原字符串的长度为n从0到n挑选数字填充数组对应字符串中的每个字符遇到’I’选择0到n中剩余的最小的数因为下一个不管位置是字符’I’还是字符’D’挑选的值都会比当前最小的数大这样就能满足字符’I’的要求下一个比当前的大遇到’D’选择0到n中剩余的最大的数因为下一个不管位置时字符’I’还是字符’D’挑选的值都会比当前最大的数小这样就能满足字符’D’的要求下一个比当前的小当遍历完所有的字符后剩下的一个值填充到数组最后。 代码实现 vectorint diStringMatch(string s){//贪心策略遇到I选择最小的数遇到D选择最大的数int n s.size();//两个指针表示0到n的数字left表示最小的数right表示最大的数int left 0, right n;vectorint ret(n 1);for (int i 0; i n; i){if(s[i]I){ret[i] left;}else{ret[i] right–;}}//最后一个位置用剩下的一个值填充ret[n] left;return ret; }8.分发饼干 题目 算法原理 本道题的贪心策略其实和上面优势洗牌一样同样借助了田忌赛马的原理只不过本道题比较简单要求统计的是最多能满足的个数不用按照数组的格式一一对应返回所以贪心策略就可以简单化还是先将两个数组排序然后一一比较如果两个数能比过也就是数组s的值大于数组g的值就直接比较下一对满足个数加一如果比不过也就是数组s的值小于数组g的值不用再和数组g中最大的值比较去拖累最大的值因为即使和最大的比较也比过题意要求返回的是满足个数所以直接跳过当前数组s的值用下一个比即可。 相较于优势洗牌那道题本道题还是比较简单的。 代码实现 int findContentChildren(vectorint g, vectorint s){//贪心策略先将两个数组排序在能满足当前胃口的情况下选择较小的饼干sort(g.begin(),g.end());sort(s.begin(), s.end());int ret 0;for (int i 0, j 0; i g.size() j s.size(); ){//如果当前饼干能满足当前胃口值直接选择当前饼干if(s[j]g[i]){ret;i;j;}//否则跳过当前饼干else{j;}}return ret; }以上就是关于贪心算法练习题第二部分的讲解如果哪里有错的话可以在评论区指正也欢迎大家一起讨论学习如果对你的学习有帮助的话点点赞关注支持一下吧