住房和城乡建设报名网站,江门网站制作方案,专业网站建设顾问,2023年房地产市场分析贪心算法相关题简单题目455.分发饼干1005.K次取反后最大化的数组和860.柠檬水找零序列问题376.摆动序列法一#xff1a;贪心法法二#xff1a;动态规划单调递增的数字简化版本有点难度53.最大子序和贪心算法动态规划134.加油站968.监控二叉树两个维度权衡问题分发糖果406.根据…
贪心算法相关题简单题目455.分发饼干1005.K次取反后最大化的数组和860.柠檬水找零序列问题376.摆动序列法一贪心法法二动态规划单调递增的数字简化版本有点难度53.最大子序和贪心算法动态规划134.加油站968.监控二叉树两个维度权衡问题分发糖果406.根据身高重建队列贪心解决股票问题122.买卖股票的最佳时机II贪心法动规法区间问题55.跳跃游戏贪心法45.跳跃游戏II动态规划452.用最少数量的箭引爆气球435.无重叠区间736.划分字母区间56.合并区间补充改版自弓箭数量那题贪心简单题目
455.分发饼干
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int count0,i0,j0;while(ig.size()js.size()){if(s[j]g[i]) {count;i;}j;}return count;}
};1005.K次取反后最大化的数组和
class Solution {
public:static bool cmp(int a,int b){return abs(a)abs(b);}int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(),nums.end(),cmp);int sum0;for(int i 0;inums.size();i){if(nums[i]0k0){nums[i] -nums[i];k--;}}if(k%21) nums[nums.size()-1]*-1;for(int i 0;inums.size();i){sumnums[i];}return sum;}
};860.柠檬水找零
class Solution {
public:bool lemonadeChange(vectorint bills) {mapint,int map1;for(int i 0;ibills.size();i){if(bills[i]5)map1[5];if(bills[i]10){map1[5]--;map1[10];if(map1[5]0) return false;}if(bills[i]20){if(map1[10]){map1[5]--;map1[10]--;}else{map1[5]-3;}map1[20];if(map1[5]0||map1[10]0) return false;}} return true; }
};序列问题
376.摆动序列
法一贪心法
局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值 整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
我们根据正常理解可以总结出我们需要统计波动的数量定义prediff(nums[i]-nums[i-1])和curdiff(nums[i1]-nums[i]),则波动需要满足的条件是prediff0curdiff0) || (prediff0curdiff0)。 但是这样会忽略平坡的情况平坡分两种 一是上下坡中有平坡对于这种情况我们只统计一个波动就好默认统计prediff0的情况就是平坡在前上下坡在后统计这一波动这对应的也是代码随想录中提到的删除平坡中左面的元素。 二是单调坡中有平坡这对应的是我们应该修改对于prediff的更新因为单调坡中的拐点使用上面的条件确实会被统计两次。 最后考虑两个数以及数组两端的情况默认最右面有一个峰值res1起步两个数的话无法判断写死摆动序列为2.
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size()2) {if(nums[0]!nums[1]) return nums.size();if(nums[0]nums[1]) return 1;}int prediff0,curdiff0,res1;for(int i 0;inums.size()-1;i){curdiffnums[i1]-nums[i];if(prediff0curdiff0||prediff0curdiff0){res;prediffcurdiff;}}return res;}
};法二动态规划
dp数组含义
dp[i][0]:表示考虑前i个数第i个数作为山峰的摆动子序列最长长度dp[i][1]:表示考虑前i个数第i个数作为山谷的摆动子序列最长长度
递推表达式 dp[i][0] max(dp[i][0],dp[j][1]1) 其中0ji其nums[j]nums[i]表示将nums[i]接到某个山谷后面作为山峰的最长长度。 dp[i][1] max(dp[i][1],dp[j][0]1) 其中0ji其nums[j]nums[i]表示将nums[i]接到某个山峰后面作为山谷的最长长度
class Solution {
public:int dp[1010][2];int wiggleMaxLength(vectorint nums) {memset(dp,0,sizeof(dp));dp[0][0]dp[0][1] 1;for(int i 1;inums.size();i){dp[i][0] dp[i][1] 1;for(int j 0;ji;j)if(nums[i]nums[j]) dp[i][0] max(dp[i][0],dp[j][1]1);for(int j0;ji;j)if(nums[i]nums[j]) dp[i][1] max(dp[i][1],dp[j][0]1);}return max(dp[nums.size()-1][0],dp[nums.size()-1][1]);}
};单调递增的数字
class Solution {
public:int monotoneIncreasingDigits(int n) {if (n 10) return n;string str ;while (n) {char c n % 10 0;str c;n n / 10;}reverse(str.begin(), str.end());for(int i 1;istr.size();i){if(str[i]str[i-1]){str[i-1]-1;for(int ji;jstr.size();j){str[j]9;}for(int ki-2;k0;k--){if(str[k]str[k1]){str[k]-1;str[k1]9;}}}}int num 0;for (int i 0; i str.size(); i) {num num*10str[i] - 0;}return num;}
};简化版本
从后往前遍历如果出现strNum[i - 1] strNum[i]的情况则strNum[i - 1]–然后一直用一个flag记录i的位置以便于之后将i之后所有卫生纸上的数字
class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值为了防止第二个for循环在flag没有被赋值的情况下执行int flag strNum.size();for (int i strNum.size() - 1; i 0; i--) {if (strNum[i - 1] strNum[i] ) {flag i;strNum[i - 1]--;}}for (int i flag; i strNum.size(); i) {strNum[i] 9;}return stoi(strNum);}
};有点难度
53.最大子序和
贪心算法
class Solution {
public:int maxSubArray(vectorint nums) {int count0,resINT32_MIN;for(int i 0;inums.size();i){countnums[i];res countres?count:res;if(count0) count0;}return res;}
};动态规划
这道题写动规的时候dp的含义直接设置成了前i个连续子数组的最大和没有再设置res去保存最大值导致dp[i]在更新的时候到底是最大值还是只是和的时候出现了两层表示意义。比如123-76dp[3] 6但dp[3]按照原有含义没有办法直接nums[4]。
class Solution {
public:int dp[100010];int maxSubArray(vectorint nums) {memset(dp,0,sizeof(dp));int res nums[0];dp[0] nums[0];for(int i 1;inums.size();i){dp[i] max(dp[i-1]nums[i],nums[i]);if(dp[i]res) resdp[i];}return res;}
};134.加油站
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int min_gas 0,sum_gas0;for(int i 0;igas.size();i){sum_gassum_gasgas[i]-cost[i];if(sum_gasmin_gas) min_gassum_gas;}if(sum_gas0) return -1;else{sum_gas0;for(int igas.size()-1;i0;i--){sum_gasgas[i]-cost[i];if(sum_gas-min_gas){return i;}}}return -1;}
};968.监控二叉树
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 0:表示该节点没有被覆盖// 1:表示该节点有摄像头// 2:表示该节点被覆盖int ans;int traversal(TreeNode* cur){if(curnullptr) return 2;int left traversal(cur-left);int right traversal(cur-right);if(left0||right0) {ans;return 1;}if(left1||right1){return 2;}if(left2||right2){return 0;}return -1;}int minCameraCover(TreeNode* root) {int root_num traversal(root);if(root_num0) ans;return ans;}
};两个维度权衡问题
分发糖果
class Solution {
public:int candy(vectorint ratings) {vectorint candy(ratings.size(),1);for(int i1;iratings.size();i){if(ratings[i]ratings[i-1]){candy[i] candy[i-1]1;}}for(int iratings.size()-1;i0;i--){if(ratings[i-1]ratings[i]){candy[i-1]max(candy[i]1,candy[i-1]);}}int ans0;for(int i 0;icandy.size();i){anscandy[i];}return ans; }
};406.根据身高重建队列
现根据身高从大到小排列再根据k一个一个插入。
class Solution {
public:static bool cmp(vectorint a,vectorint b){if(a[0]b[0]) return a[1]b[1];else return a[0]b[0];}vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(),people.end(),cmp);vectorvectorint que;for(int i 0;ipeople.size();i){int position people[i][1];que.insert(que.begin()position,people[i]);}return que;}
};贪心解决股票问题
122.买卖股票的最佳时机II
贪心法
class Solution {
public:int maxProfit(vectorint prices) {int sum0;for(int i 1;iprices.size();i){if(prices[i]-prices[i-1]0){sumprices[i]-prices[i-1];}}return sum;}
};动规法
class Solution {
public:int dp[30010];int maxProfit(vectorint prices) {memset(dp,0,sizeof(dp));int sum0;for(int i 1;iprices.size();i){dp[i]dp[i-1] max(prices[i]-prices[i-1],0);}return dp[prices.size()-1];}
};区间问题
区间问题总结除了两个跳跃游戏。我们一共左了四个区间的贪心算法题。用最少弓箭射爆气球五重叠区间的个数划分字母区间和合并区间。用最少的弓箭射爆气球实际上我们要找的是重叠区间的个数而射爆气球这道题认为[1,2],[2,3]不属于重叠区间这需要注意。我们按照左边界排序后只需要遍历interval中每一个右边界每次更新重叠区间的右端点rmin(points[i][1],r)r \text {min}(\text{points}[i][1],r)rmin(points[i][1],r)然后处理每个interval左边界和r的关系就好。无重叠区间的个数实际上总区间个数减去重叠区间个数所以看清楚条件[1,2],[2,3]属不属于重叠情况确立等号是否成立。划分字母区间这道题有点难度需要统计每个字符出现的最远位置下标然后处理。合并区间按左边界排序后然后从左到右遍历看是否是重叠的然后更新合并区间的左边界右边界。
55.跳跃游戏
贪心法
class Solution {
public:bool canJump(vectorint nums) {int step0;if(nums.size()1) return true;for(int i 0;istep;i){stepmax(inums[i],step);if(stepnums.size()-1) return true;}return false;}
};45.跳跃游戏II
动态规划
class Solution {
public://我的思路是dp数组表示到第i个格子需要的最短次数//dp数组更新的递推公式是从j0个格子开始找int dp[10100];int jump(vectorint nums) {memset(dp, 10010, sizeof(dp));if (nums.size() 1) return 0;else dp[0] 0;for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (j nums[j] i) {dp[i] min(dp[j] 1, dp[i]);break;}}}return dp[nums.size() - 1];}
};452.用最少数量的箭引爆气球
class Solution {
public:static bool cmp(vectorint a, vectorint b){if(a[0]b[0]) return a[1]b[1];else return a[0]b[0];}int findMinArrowShots(vectorvectorint points) {sort(points.begin(),points.end(),cmp);int lpoints[0][0],rpoints[0][1];int ans1;for(int i 1;ipoints.size();i){l points[i][0];r min(points[i][1],r);if(lr){rpoints[i][1];ans;}}return ans;}
};435.无重叠区间
class Solution {
public://无重叠区间的个数等于总区间个数减去重叠区间个数static bool cmp(vectorint a,vectorint b){if(a[1]b[1]) return a[0]b[0];else return a[1]b[1];}int eraseOverlapIntervals(vectorvectorint intervals) {//这里需要记一下按右边界排序要从左向右找//按左边界排序要从右向左找sort(intervals.begin(),intervals.end(),cmp);int lintervals[0][0],rintervals[0][1];int ans1;for(int i 1;iintervals.size();i){if(intervals[i][0]r){ans;rintervals[i][1];}}return intervals.size()-ans;}
};736.划分字母区间
这道题不用回溯不是所有的划分字母区间都要回溯这道题主要在于统计之前遍历过所有字母的最远边界如果当前下标到达了这个最远边界说明到达了字符串的分割点。
class Solution {
public://贪心法mapchar,int mp;vectorint ans;vectorint partitionLabels(string s) {for(int i 0;is.size();i){mp[s[i]] i;}int split0,split1-1;for(int i 0;is.size();i){if(mp[s[i]]split) splitmp[s[i]];if(isplit){ans.push_back(split-split1);split1 split;} }return ans;}
};56.合并区间
通过做这道题我先是按照解上面题的常规套路按照右边界排序后来发现很多bug这道合并区间的题如果从左到右遍历一定是先按左边界排列。
class Solution {
public:static bool cmp(vectorinta, vectorintb){if(a[0]b[0]) return a[1]b[1];else return a[0]b[0];}vectorvectorint res;vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),cmp);int l intervals[0][0];int r intervals[0][1];for(int i 1;iintervals.size();i){if(intervals[i][0]r){r max(intervals[i][1],r);}else{res.push_back({l,r});l intervals[i][0];r intervals[i][1];}}res.push_back({l,r});return res;}
};补充改版自弓箭数量那题
class Solution {
public://无重叠区间的个数等于总区间个数减去重叠区间个数static bool cmp(vectorint a, vectorint b){if(a[0]b[0]) return a[1]b[1];else return a[0]b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),cmp);int lintervals[0][0],rintervals[0][1];int ans1;for(int i 1;iintervals.size();i){l intervals[i][0];r min(intervals[i][1],r);if(lr){ //加个等号认为等于的情况不属于交叉区间rintervals[i][1];ans;}}return intervals.size()-ans;}
};贪心
要从覆盖范围出发不管怎么跳覆盖范围一定是可以跳到的以最小的步数增加覆盖范围覆盖范围一旦覆盖了重点得到的就是最小步数。
class Solution {
public:int jump(vectorint nums) {if(nums.size()1) return 0;int curmaxindex 0; // 当前覆盖最远距离下标当前位置为i的话能走到的最远距离就是inums[i]。int nextmaxindex 0; // 记录走的最大步数int step 0; // 下一步覆盖最远距离下标for(int i 0;icurmaxindex;i){nextmaxindex max(nums[i]i,nextmaxindex); // 更新下一步能走到的最远距离if(icurmaxindex){ // 如果i已经走到了当前能走到的最大距离if(curmaxindexnums.size()-1){step; // 那么我们一定要走下一步了但下一步的落脚点在哪儿不用管// 不要误认为下一步落脚点一定是curdistance这个没关系curmaxindexnextmaxindex; // 更新当前覆盖最远距离下标if(nextmaxindexnums.size()-1) break; // 下一步的覆盖范围已经可以达到终点结束循环}}}return step;}
};
