潍坊网站建设建站,怎么让网站绑定域名,网站建设风险是什么意思,开滦建设集团网站455. 分发饼干
题目 随想录 本质#xff1a; 对于每个孩子#xff0c;使用可以满足该孩子的最小的饼干。所以对孩子胃口和饼干进行sort排序#xff0c;依次将大的饼干满足给孩子。 贪心策略#xff1a; 想一下局部最优#xff0c;想一下全局最优#xff0c;如果局部最优…455. 分发饼干
题目 随想录 本质 对于每个孩子使用可以满足该孩子的最小的饼干。所以对孩子胃口和饼干进行sort排序依次将大的饼干满足给孩子。 贪心策略 想一下局部最优想一下全局最优如果局部最优可以推出全局最优就可以考虑贪心。
局部最优对每个孩子使用满足该孩子胃口的最小的饼干全局最优尽可能满足更多的孩子
技巧 这里没有使用两个for循环而是采用了index自减的方式。 class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int indexs.size()-1;int result0;for(int jg.size()-1;j0;j--){if(index0s[index]g[j])//这里index必须0{index--;result;}}return result;}
};也可以小饼干先喂饱小胃口 错误的 从小到大喂的话是根据饼干来的如果按照孩子来for循环则同时孩子胃口在增大饼干也在增大eg: [10,9,8,7] [5,6,7,8] 正确输出是2但是这里输出了0因为不是找到第一个饼干该饼干可以满足最小的孩子胃口。所以从小到大喂应该for循环遍历饼干。而从大到小喂饱就应该遍历孩子找到第一个孩子可以满足饼干大小的然后依次往后遍历。
//错误的
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index0;int result0;for(int j0;jg.size();j){if(indexs.size()s[index]g[j]){index;result;}} return result;}
};正确的从小到大喂 不用设置result,最后的index就是孩子的数量 class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index0;for(int j0;js.size();j){if(indexg.size()s[j]g[index]){index;}} return index;}
};376. 摆动序列
题目 随想录 方法一贪心 用图形的思路即波峰
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size()1) return nums.size();int curdif0;int predif0;int result1;for(int i0;inums.size()-1;i){curdifnums[i1]-nums[i];if((curdif0predif0)||(curdif0predif0)){result;predifcurdif;} }return result; }
};方法二动态规划 待学。。。
53. 最大子数组和
题目 方法一贪心 本题关键是贪心贪在哪局部最优当前面序列累加为负数时就直接清空sum从头开始累加这里就是体现了贪。 全局最优选取最大的连续和 对比暴力法利用连续何是否为负数不断调整开始的位置每次记录最大和调整结束的位置。 我看的随想录思路写的 class Solution {
public:int maxSubArray(vectorint nums) {int maxINT_MIN;int sum0;int j;for(j0;jnums.size();j){ if(nums[j]0)break;else {if(nums[j]max)maxnums[j];}}if(jnums.size())maxnums[j];for(int ij;inums.size();i){sumnums[i];if(sum0){ if(summax)maxsum;}else sum0; //因为这里用的是else 所以当样例全为负数时就不可行了。对比随想录随想录是这里用了两个if而不是当sum为正数时才赋值给max,所以包含了负数我写的这种没有包含负数所以在上面判断了全部都是负数的情况也就是从第一个不为负数的值开始计数}return max;}
};
随想录 class Solution {
public:int maxSubArray(vectorint nums) {int maxINT_MIN;int sum0;for(int i0;inums.size();i){sumnums[i];//这里的逻辑要细品为何不用else 因为时两种不同的情况并且不是互斥的所以不用elseif(summax)maxsum;if(sum0) sum0;}return max;}
};
方法二暴力法
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) { // 设置起始位置count 0;for (int j i; j nums.size(); j) { // 每次从起始位置i开始遍历寻找最大值count nums[j];result count result ? count : result;}}return result;}
};方法三动态规划
122. 买卖股票的最佳时机 II
题目 方法一贪心
误区
想的是差值最大差值对应的元素是不同的错误原因这里不是不能重复而是买入卖出所以是可以重复的当天买当天卖也是可以的。 注意只有一只股票只不过这只股票是在不断变化的 分解的思维将整体的利润分解为每天的利润。eg:将0~3天的利润prices[3]-prices[0]转化为(prices[3]-prices[2])(prices[2]-prices[1])(prices[1]-prices[0]),
随想录拾取正区间的值就是很巧妙的将整体的最优解转化成了找局部的最优解如何转化呢就是根据【分解的思维】并且这种不是说跳着找到下一个比当前值大的因为这种是聚焦到一天即计算出当前天和之后哪一天卖出利润最大相当于是每次在这n天中找了两天而正确的思路是同时计算利用局部最优推出全局最优局部最优就是相邻两天的最大而全局最优就是将所有相邻中的正数都拾取。 官方题解思路: 由于股票的购买没有限制因此整个问题等价于寻找 x个不相交的区间 (l_i,r_i] 使得如下的等式最大化.这也是我思路不清晰的原因。 评论区的思路 把所有的上坡都用sum累加收集。
贪心算法偏向的是题解的算法而不是数据结构算法 看了随想录思路写的 class Solution {
public:int maxProfit(vectorint prices) {vectorint v(prices.size(),0);for(int i1;iprices.size();i){v[i]prices[i]-prices[i-1];}int sum0;for(int i0;iv.size();i){if(v[i]0)sumv[i];}return sum;}
};
随想录只需要一次for循环 class Solution {
public:int maxProfit(vectorint prices) {int sum0;for(int i1;iprices.size();i){summax((prices[i]-prices[i-1]),0);}return sum;}
};
方法二动态规划
55. 跳跃游戏
题目 要看官方题解去理解。。。。 max(inums[i],cover)使用的是inums[i]而不是用从0累加这里也很巧妙 当icover就说明跳不到了所以在for循环里写的是icover 这里有一点很关键就是为什么要更新最大范围即通过最大范围来判断是否会跳到最后一格 因为本题不是纠结如何跳而是关注能不能跳到。如3 1 2 2 1 1从0开始跳跳到其最大范围3如果33说明是可以跳到3这个位置的然后在这个基础上继续往后跳注意”这个基础上“因为每跳到一个地方就说明一定可以然后再更新最大的覆盖范围这样一直往前直到最大范围超过了最后一个下标 根据官方题解如何判断位置x可不可以到达y只要xnums[x]y则说明可以到达推广到每一个x即对于每一个可以到达的位置x 说明x都满足了其上一个的nums[x0]x0,这里的上一个就是任意一个可以到达位置x0 所以对于每一个可以到达的x它使得x1,x2…xnums[i]都可以到达 反思 我自己一直纠结怎么走而不是判断是否走到没有搞清楚最大步数与贪心之间的关系 随想录 class Solution {
public:bool canJump(vectorint nums) {if(nums.size()1) return true;int covernums[0];for(int i1;icover;i) //使用的是cover{covermax(inums[i],cover);if(covernums.size()-1)return true; }return false;}
};官方题解 class Solution {
public:bool canJump(vectorint nums) {if(nums.size()1) return true;int covernums[0];for(int i1;inums.size();i){if(icover){covermax(inums[i],cover);if(covernums.size()-1)return true; }}return false;}
};
45. 跳跃游戏 II
题目
在该下标可以跳跃的最大长度 困惑的点贪心贪在哪每次是跳最大的还是最小的但是又有很多种组合。
如果是最大的一直跳跳到最后停止的地方的下标大于等于最后一个下标就说明可以如果不行则倒着减一个再继续跳直到第一个起始位置只跳一步
以最小的步数增加覆盖范围覆盖范围一旦大于了nums.size()则就说明是最大的
懂了懂了就是从iinums[i]之间的所有位置i都能到达只不过i可以走一步走两步…最大可以走inums[i]步所以就在iinums[i]中找到最大的数也就是下一次的跳跃起点。 例如对于数组 [2,3,1,2,4,2,3]初始位置是下标 0从下标 0 出发最远可到达下标 2。下标 0 可到达的位置中下标 1 的值是 3从下标 1 出发可以达到更远的位置因此第一步到达下标 1。
从下标 1 出发最远可到达下标 4。下标 1 可到达的位置中下标 4 的值是 4 从下标 4 出发可以达到更远的位置因此第二步到达下标 4。
因此可以用maxPox记录下一个最远可达的下标位置然后step
贪心贪在哪每跳一次下一次的增加都是最大的即保证了step一次跳的最远。 这里每跳一步尽可能的多走体现了贪心思想 不管怎么跳i~inums[i]之间的位置是都能跳到的以最小的步数增加覆盖范围当移动下标走到了最大覆盖范围的边界时就step
我的错误点将最大步数nums[i]和maxPos没有搞清楚实际上是一个东西 错误:
//错误
class Solution {
public:int jump(vectorint nums) {int maxPos0;int maxStep0;int step0;for(int i0;inums.size();){maxStep0;for(int ji;jinums[i]jnums.size();j){// maxStepmax(maxStep,nums[j]);if(maxStepnums[j]){maxPosj;maxStepnums[j];}} step;imaxPos;}return step;}
};看的这个大神的解析解析 这里是用start和end来控制区间的 可以看出for循环实际上是从头到尾遍历了一遍nums所以可以合成一个遍历 这里的区间是左闭右开[start,end)
class Solution {
public:int jump(vectorint nums) {int maxPos0;int start0;int end1;//因为是[ ),所以end为1int step0;while(endnums.size()){maxPos0;for(int jstart;jend;j){maxPosmax(maxPos,jnums[j]);} startend;endmaxPos1; step;}return step;}
};合成一个遍历 随想录方法一
class Solution {
public:int jump(vectorint nums) {int maxPos0;int end0;int step0;//这里jnums.size()for(int j0;jnums.size();j){maxPosmax(maxPos,jnums[j]);if(jend) {//需要判断j是否覆盖到了最后一个位置nums.size()-1if(jnums.size()-1){endmaxPos; step;if(endnums.size()-1) break;//看后面的下一步是否到了最后一个位置}else break;}}return step;}
};随想录方法二 这里的区间相当于是左闭右闭[j,end] 每次j都会走到end 关于jnusm.szie()-1就停下来可以看随想录的方法二解析。
class Solution {
public:int jump(vectorint nums) {int maxPos0;int end0; //[ ]所以end从0开始int step0;//因为end是从0开始的在起始位置时startend所以step就加了1相当于跳了一步了所以这里jnums.size()-1,相当于最后一步不用跳了因为在起始位置就加了1了跳到倒数第二个位置就好了因为题目说了一定可以跳到重点所以倒数第二个位置不为0for(int j0;jnums.size()-1;j){maxPosmax(maxPos,jnums[j]);//j相当于是起点end记录每次跳跃的区间终点当起点和终点重合之后也就是该区间的最大的跳跃值已经比较完毕然后去更新下一次的endif(jend) {endmaxPos; step;}}return step;}
};1005. K 次取反后最大化的数组和
题目 我的误区 刚开始想的是将所有的都sort一下从小到大排列然后找出前k个变成正数想把数组中的数字尽可能多的变成正数 忽略了一个条件就是一个负数可以被一直±±。忽略了k与负数的个数比较然后又想到下面这个 k负数个数时且数组中有0时就将多余的k弄到0身上如果没有0且k为奇数则弄到最小的那个负数身上k为偶数时就k负数个数就直接从小到大将k个负数弄成正数如果K还大于0那么反复转变数值最小的元素将K用完
正确思路 随想录 按照绝对值大小从大到小排列最后进行消耗k的是绝对值最小的元素不管该数原来是正数还是负数还是0 按照绝对值从大到小进行排列并从前往后进行遍历见到负数就变正数并k– 然后检查k是否消耗完了如果没有消耗完则在绝对值最小的数字上nums[nums.size()-1]不断±±直到k消耗完 贪心 局部最优负数变为正数当前数字最大 全局最优整个的和最大 如果将所有负数都变为正数了k还没有消耗完则此时问题变为了一个正数的序列如何改变正负来使整体的和最大。又一次用到了贪心 局部最优: 找到绝对值最小的数字变为负数反转消耗剩余的k使得当前的相对值最大1反转为-15反转为-5-1大于-5 全局最优整个的和最大
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); for(int i0;inums.size();i){if(nums[i]0k0) //这里k0必须加上因为最多就是将k个负数变为正数{nums[i]*-1;k--;} }if(k0){while(k--)nums[nums.size()-1]*-1;}int sum0;for(int j0;jnums.size();j){sumnums[j];}return sum;}
};
134. 加油站
题目 方法一暴力法 模拟环 for循环适合模拟从头到尾的遍历而while循环适合模拟环形遍历要善于使用while 错误点
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int sum0;for(int j0;jgas.size();j){int ij;//(1)while(i!j) //这里是肯定进不来的因为i一定等于j在1处{sumgas[i];sum-cost[i];i;ii%gas.size();}if(sum0ij)return i;}return -1;}
};
暴力法【随想录】 暴力法模拟一圈对while循环使用要熟练
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {for (int i 0; i cost.size(); i) {int rest gas[i] - cost[i]; // 记录剩余油量int index (i 1) % cost.size();while (rest 0 index ! i) { // 模拟以i为起点行驶一圈rest gas[index] - cost[index];index (index 1) % cost.size();}// 如果以i为起点跑一圈剩余油量0返回该起始位置if (rest 0 index i) return i;}return -1;};随想录:贪心方法二 思路 整个的大思路破解口是如果整个的gas-cost剩余量0说明一定可以走完一圈的如果小于0说明从任意一点出发都不可能走完一圈。同理推广到局部的数组如果在[i,j)内的剩余量0,说明在[i,j]内的任意一点出发都不可能走完一圈所以返回的起始点start从j1开始。 这里必须将整个的剩余油量sum和每个小区间的剩余油量ans分开。 局部最优 当前累加rest[j]的和curSum一旦小于0起始位置至少要是j1因为从j开始一定不行。 全局最优 找到可以跑一圈的起始位置。 随想录可以换一个思路首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。 同理推到局部相当于是一个小数组 i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置起始位置从i1算起再从0计算curSum。 class Solution {public:int canCompleteCircuit(vectorint gas, vectorint cost) {int ans0;int start0;int sum0;// for(int i0;igas.size();i)// {// ansgas[i]-cost[i];// }// if(ans0) return -1;//这里使用一个for循环即可for(int i0;igas.size();i){ansgas[i]-cost[i];sumgas[i]-cost[i];if(ans0){//i;starti1;ans0;}}if(sum0) return -1;return start;}};随想录贪心方法一没懂为什么要从后往前填平min? 贪心一
135. 分发糖果。。。。。。
题目
860.柠檬水找零
题目 三种情况
5元直接接收10元用5元找零20元用510或者5*3找零需要讨论的就是这一种情况
误区
题意要弄清楚不能进行排序刚开始还用sum其实不准确应该单独分开然后思路更加清晰
涉及的贪心 遇到20的情况应该先利用105的组合而不是5*3的组合因为5元可以找零10和20 更加玩万能否则就会有测试样例过不去
class Solution {
public:bool lemonadeChange(vectorint bills) { // sort(bills.begin(),bills.end()); 不能排序int five0;int ten0;// int twenty0; 可以不用写20for(int i0;ibills.size();i){if(bills[i]5){five;}else if(bills[i]10){if(five0){five--;ten;}else return false;}else if(bills[i]20){if(five1ten1){five--;ten--;}else if(five3){fivefive-3;}else return false;}}return true;}
};406. 根据身高重建队列
题目 思路: 【随想录】 两个维度技巧确定一边然后贪心另一边 本题也是两个维度和分糖果那道题差不多也是先确定一个维度的排序再去确定另一个维度的排序。 如果按照后面的k排序排出的结果没有啥用所以先对身高进行从大到小的排序再根据k进行插入排序注意插入排序就是只看k的大小就好因为是在身高从大到小的顺序上进行的所以前面的排序不会干扰后面的排序。 贪心 局部最优按照身高从大到小进行排序并按照k的大小进行插入排序使people满足了队列的属性 全局最优使整个people满足队列的属性
class Solution {
public:static bool cmp(vectorinta,vectorintb){if(a[0]b[0]){return true;}else if(a[0]b[0]){return a[1]b[1];}return false;}vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(),people.end(),cmp);vectorvectorint result;for(int i0;ipeople.size();i){int pospeople[i][1];result.insert(result.begin()pos,people[i]);}return result;}
};使用vector和list的不同之处 vector的底层是使用的listvector每次插入元素当大于capacity时就会扩容到两倍因此会效率不高使用list会效率高
list版本
class Solution {
public:static bool cmp(vectorinta,vectorintb){if(a[0]b[0]){return a[1]b[1];}return a[0]b[0];}vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(),people.end(),cmp);listvectorint result;for(int i0;ipeople.size();i){listvectorint::iterator itresult.begin();int kpeople[i][1];while(k--){it;}result.insert(it,people[i]);}return vectorvectorint(result.begin(),result.end());}
};452. 用最少数量的箭引爆气球
题目 思路 【随想录】 按起点排序或者终点排序都可以这里用起点从小到大进行每次就检查前一个的终点和后一个的起点是否重叠如果不重叠就新射一箭result,如果重叠了就更新最小有边界因为每次都是比较上一个的有边界 新学习到的画图题目是需要知道个数模拟时不需要真的去移除而是像之前换零钱一样直接计数即可
class Solution {
public:// static bool cmp(vectorinta,vectorintb)// {// if(a[1]b[1])// return a[0]b[0];// return a[1]b[1];// }static bool cmp(vectorinta,vectorintb){return a[0]b[0];}int findMinArrowShots(vectorvectorint points) {sort(points.begin(),points.end(),cmp);int result1;for(int i1;ipoints.size();i){//没有重叠if(points[i][0]points[i-1][1]){result;}else {//更新最小的有边界画图可以看出points[i][1]min(points[i-1][1],points[i][1]);}}return result;}
};435. 无重叠区间
题目 贪心法则
如果是右边界从小到大进行排列则从前往后遍历贪心体现在尽量右边界越小越好这样会给后面的元素留下更多的空间如果是按照左边界从小到大进行排列则从后往前遍历贪心体现在尽量左边界越大越好这样会给前面的元素留下更多的空间。
这里用的是有边界从小到大进行排列从前向后进行遍历。 技巧 贪心中的逆向思维求一个最小值可以用总数减去它相反的最大值 因此这里将找最少的可去区间变成了找最多的不重叠的区间再用总数减去最多的不重叠区间。
class Solution {
public:static bool cmp(vectorinta,vectorintb){return a[1]b[1];}int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),cmp);int sum1;int endintervals[0][1];for(int i1;iintervals.size();i){//这里不是intervals[i][0]intervals[i-1][1];直接用end记录上一个的最后一个边界这里的上一个不是i-1,而是符合不交叉条件的上一个 注意这里还是//这里使用的切割点就是endif(intervals[i][0]end){sum; endintervals[i][1];}}return intervals.size()-sum;}
};763. 划分字母区间
题目 就是统计每一个字符最后出现的位置用哈希然后再遍历字符串设置一个start和end表示分割的区间当遍历i区间最大值时则是分割点。如下图第一个区间的最大值是8当遍历到8时说明前面区间最大值已经到头了所以找到了第一个分割点。
class Solution {
public:vectorint partitionLabels(string s) {vectorintresult;unordered_mapchar,int mp;for(int i0;is.size();i){mp[s[i]]i;}int end0;int start0;for(int i0;is.size();i){endmax(end,mp[s[i]]);if(endi){result.push_back(end-start1);starti1;}}return result;}
};随想录 字母哈希可以直接用a[27]来映射
class Solution {
public:vectorint partitionLabels(string s) {vectorintresult;int hash[27]{0};for(int i0;is.size();i){hash[s[i]-a]i;}int end0;int start0;for(int i0;is.size();i){endmax(end,hash[s[i]-a]);if(endi){result.push_back(end-start1);starti1;}}return result;}
};随想录补充 根据打气球和无重叠区间的思路来解找到每一个字符的开始和结束区间然后再根据左边界从小到大进行排列从左向右遍历目标是找到不重叠的区间判断条件当下一个的左边界大于前面的最大有边界时就说明是找到了不重叠的区间也就是分割点了。
class Solution {
public:static bool cmp(vectorint a, vectorint b) {return a[0] b[0];}// 记录每个字母出现的区间vectorvectorint countLabels(string s) {vectorvectorint hash(26, vectorint(2, INT_MIN));vectorvectorint hash_filter;for (int i 0; i s.size(); i) {if (hash[s[i] - a][0] INT_MIN) {hash[s[i] - a][0] i;}hash[s[i] - a][1] i;}// 去除字符串中未出现的字母所占用区间for (int i 0; i hash.size(); i) {if (hash[i][0] ! INT_MIN) {hash_filter.push_back(hash[i]);}}return hash_filter;}vectorint partitionLabels(string s) {vectorint res;// 这一步得到的 hash 即为无重叠区间题意中的输入样例格式区间列表// 只不过现在我们要求的是区间分割点vectorvectorint hash countLabels(s);// 按照左边界从小到大排序sort(hash.begin(), hash.end(), cmp);// 记录最大右边界int rightBoard hash[0][1];int leftBoard 0;for (int i 1; i hash.size(); i) {// 由于字符串一定能分割因此,// 一旦下一区间左边界大于当前右边界即可认为出现分割点if (hash[i][0] rightBoard) {res.push_back(rightBoard - leftBoard 1);leftBoard hash[i][0];}rightBoard max(rightBoard, hash[i][1]);}// 最右端res.push_back(rightBoard - leftBoard 1);return res;}
};56. 合并区间
题目 我的根据上一道题目的随想录补充的思路写的当出现不重叠的区间时就加入到result中然后用right不断地记录最大的右边界。 这里和随想录的解析有点不一样需要再看一下随想录的解析 随想录解析以及最后一个区间何时加入 class Solution {
public:static bool cmp(vectorinta,vectorintb){return a[0]b[0];}vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),cmp);int leftintervals[0][0];int rightintervals[0][1];vectorvectorint result;for(int i1;iintervals.size();i){if(intervals[i][0]right){result.push_back({left,right});leftintervals[i][0];} rightmax(right,intervals[i][1]);}//最后一个区间result.push_back({left,right});return result;}
};
738. 单调递增的数字
题目 方法一暴力法 自己写的超时 class Solution {
public:bool judge(int a){int tINT_MAX;int b0;while(a){ba%10; //3 2 1aa/10; //12 1 0if(tb) return false;tb; }return true;}int monotoneIncreasingDigits(int n) {if(judge(n))return n;while(n--){if(judge(n)){return n;}}return 0;}
};随想录 思路从后往前遍历当遇到前一个字符s[i-1]比当前字符s[i]大时就将前一个字符减去一s[i-1]–,将当前字符变为9,s[i]‘9’.eg 98则变成了89. 使用flag记录第一个需要改变的位置然后从该位置起将字符改为9. 直接将flag赋值为s.size()如果s直接是递增整数就不用改9了 单个数字字符0-9两位的就不行了因为0-9才有ascii码直接–可以得到小一个的数但是其他不能保证
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);}
};
我写的看的思路
class Solution {
public:int monotoneIncreasingDigits(int n) {string sto_string(n);int flag0;for(int is.size()-1;i1;i--){if(s[i-1]s[i]){s[i-1]to_string((s[i-1]-0)-1)[0];flagi;}}if(flag!0){for(int iflag;is.size();i)s[i]9;}return atoi(s.c_str());}
};
714. 买卖股票的最佳时机含手续费
题目 方法一贪心 看了官方解 思路 每次买入的时候交手续费 buy表示你手上的股票买入的最低价格初始化为price[0]free 当前的price[i]freebuy时说明遇到了一个比现在手上股票还低的股票这个时候应该与其用现在手上的buy买股票还不如用当前的price[i]free买,所以将buy更新为buyprice[i]free; 如果当前股票price[i]buy说明可以卖出并获得price[i]-buy的收益但是该结果不一定是最优的因为后面可能会出现比price[i]还高的价格所以可以看成是当前我用price[i]买了一只股票即将buy更新为price[i]-free后面如果出现了新的高的价格即price[i1]price[i]时就会累加收益price[i1]-buy (buyprice[i]),相当于是price[i1]-price[i] 其余的情况当price[i]在[buy-free,buy]之间表示当前股票没有低到让我们去买也没有高到让我们去卖就什么也不做
class Solution {
public:int maxProfit(vectorint prices, int fee) {int buyprices[0]fee;int result0;for(int i1;iprices.size();i){if(prices[i]feebuy) buyprices[i]fee;else if(prices[i]buy) {//注意这里是else !!!因为第一个if已经改变了buy的值resultprices[i]-buy;//buyprices[i]fee;buyprices[i];//因为只需要减一次fee,eg相当于下一次直接是累加result后为price[i1]price[i];}}return result;}
};方法二动态规划 待学。。。
968. 监控二叉树
题目 随想录思路 题目破解口摄像头不能安装到叶子节点上。 因此从下往上进行遍历每一个结点有三种状态: 0: 没有被覆盖 1有摄像头 2被覆盖了 使用后序遍历从下向上进行根据左右子树的状态确定当前结点的状态
如果左右子树中都被覆盖了if(left 2right 2)说明他们的父节点没有被覆盖从下往上进行的返回0如果左右子树中有一个没被覆盖或者都没被覆盖if(left 0||right 0)说明他们的父节点该安装摄像头了所以就result将其返回1如果左右子树全有一个有摄像头if(left 1||right 1)说明父节点一定被覆盖了返回2最后还要判断头结点是否被覆盖如果没有则给头结点安装摄像头result
随想录解析
/*** 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:int result0;int postOrder(TreeNode* root){if(rootNULL) return 2;int leftpostOrder(root-left);int rightpostOrder(root-right);if(left0||right0) {result;return 1;}if(left2right2){return 0;}if(left1||right1){return 2;}return -1;}int minCameraCover(TreeNode* root) {if(postOrder(root)0)result;return result;}
};难点 贪心的思路如何遍历状态的推导
