[C++ Code] Divide sugar, divide biscuits, swing sequence, greedy algorithm–Code Random Record

• The essence of greed is to select the local optimum at each stage to achieve the global optimum. Simulate manually by yourself. If the simulation is feasible, you can try the greedy strategy. If it is not feasible, you may need dynamic programming. The greedy algorithm is generally divided into the following four steps:
  • Break the problem into several sub-problems
  • Find a suitable greedy strategy
  • Find the optimal solution for each subproblem
  • Stack local optimal solutions into global optimal solutions

Title: Distributing Cookies

• Let’s say you’re a great parent and want to give your kids some cookies. However, no more than one cookie can be given to each child. For each child i, there is an appetite value g[i], which is the minimum size of biscuits that can satisfy the child’s appetite; and each biscuit j, all have a size s[j]. If s[j] >= g[i], we can assign this cookie j to the child i and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum value.

• class Solution {<!-- -->
  public:
      int findContentChildren(vector<int> & amp; g, vector<int> & amp; s) {<!-- -->
          int g_p=g.size()-1,s_p=s.size()-1;
          sort(g.begin(),g.end());
          sort(s.begin(),s.end());
          int count = 0;
          while(s_p>-1 & amp; & amp; g_p>-1){<!-- -->
              if(g[g_p]<=s[s_p]){<!-- -->
                  g_p--;
                  s_p--;
                  count + + ;
              }else{<!-- -->
                  g_p--;
              }
          }
          return count;
      }
  };
  

• To satisfy more children, don’t waste cookie sizes. Large-sized biscuits can satisfy both children with large appetites and children with small appetites, so priority should be given to those with large appetites. You can try to use the greedy strategy and sort the cookie array and child array first. Then traverse the children array from back to front, use large cookies to satisfy those with big appetites first, and count the number of satisfied children.

• class Solution {<!-- -->
  public:
      int findContentChildren(vector<int> & amp; g, vector<int> & amp; s) {<!-- -->
          sort(g.begin(),g.end());
          sort(s.begin(),s.end());
          int index=s.size()-1,res=0;
          for(int i=g.size()-1;i>=0;i--){<!-- -->
              if(index<0){<!-- -->
                  break;
              }
              if(g[i]<=s[index]){<!-- -->
                  index--;
                  res++;
              }
          }
          return res;
      }
  };
  

• Time complexity: O(nlogn); Space complexity: O(1).

• It can be seen from the code that I use an index to control the traversal of the cookie array. Traversing the cookies does not create a for loop, but uses self-decrement, which is also a common technique.

Topic: Swinging Sequence

• If the difference between consecutive numbers alternates strictly between positive and negative numbers, the sequence of numbers is called a wobble sequence . **The first difference (if present) may be positive or negative. Sequences with only one element or two unequal elements are also considered wobble sequences. Subsequence can be obtained by deleting some (or not) elements from the original sequence, leaving the remaining elements in their original order. Given an integer array nums, return the length of the longest subsequence in nums that is the wobble sequence.

• class Solution {<!-- -->
  public:
      int wiggleMaxLength(vector<int> & amp; nums) {<!-- -->
          if(nums.size()<2){<!-- -->
              return nums.size();
          }
          int curdiff=0;
          int prediff=0;
          int count=1;
          for(int i=0;i<nums.size()-1;i + + ){<!-- -->
              curdiff=nums[i + 1]-nums[i];
              if((prediff<=0 & amp; & amp;curdiff>0)||(prediff>=0 & amp; & amp;curdiff<0)){<!-- -->
                  count + + ;
                  prediff=curdiff;//Note here, prediff is only updated when the swing changes
              }
          }
          return count;
      }
  };
  

• The essence of the abnormal situation in this question is to consider flat slopes. There are two types of flat slopes, one is a flat slope between the top and bottom, and the other is a monotonous flat slope, as shown in the picture:

  • 

• Time complexity: O(n); Space complexity: O(1)

Topic: Maximum sum of subarrays

• Given an integer array nums, please find a continuous subarray with the maximum sum (the subarray contains at least one element) and return its maximum sum. Subarray is a contiguous portion of an array.

• The idea of a brute force solution is to set the starting position in the first level of for, and the second level of for loop traverses the array to find the maximum value.

  • class Solution {<!-- -->
    public:
        int maxSubArray(vector<int> & amp; nums) {<!-- -->
            int res = INT32_MIN;
            int count;
            for(int i=0;i<nums.size();i + + ){<!-- -->
                count=0;
                for(int j=i;j<nums.size();j + + ){<!-- -->
                    count + = nums[j];
                    res = count>res?count:res;
                }
            }
            return res;
        }
    };//time out
    class Solution {<!-- -->
    public:
        int maxSubArray(vector<int> & amp; nums) {<!-- -->
            int res = INT32_MIN;
            int count;
            for(int i=0;i<nums.size();i + + ){<!-- -->
                if(nums[i]<=0){<!-- -->
                    continue;
                }
                count=0;
                for(int j=i;j<nums.size();j + + ){<!-- -->
                    count + = nums[j];
                    res = count>res?count:res;
                }
            }
            if(res==INT32_MIN){<!-- -->
                res=nums[0];
                for(int i=1;i<nums.size();i + + ){<!-- -->
                    res= res>nums[i]?res:nums[i];
                }
            }
            return res;
        }
    };
    

• Local optimum: Give up immediately when the current “continuous sum” is a negative number and recalculate the “continuous sum” from the next element, because the “continuous sum” of negative numbers plus the next element will only get smaller and smaller. Global optimal: choose the largest “continuous sum”. From a code perspective: Traverse nums and accumulate count from the beginning. If count becomes negative once added to nums[i], then count should be accumulated from 0 starting from nums[i + 1] because it has become negative. The count will only drag down the sum. This is equivalent to constantly adjusting the starting position of the maximum suborder and interval in the brute force solution.

• class Solution {<!-- -->
  public:
      int maxSubArray(vector<int> & amp; nums) {<!-- -->
          int res=INT32_MIN;
          int count=0;
          for(int i=0;i<nums.size();i + + ){<!-- -->
              count + =nums[i];
              if(count>res){<!-- -->
                  res=count;
              }
              if(count<=0){<!-- -->
                  count=0;
              }
          }
          return res;
      }
  };
  

• Time complexity: O(n); Space complexity: O(1)

Topic: The best time to buy and sell stocks II

• You are given an integer array prices, where prices[i] represents the price of a certain stock on day i. On each day, you can decide whether to buy and/or sell stocks. You may hold maximum of one stock at any time. You can also buy and sell same day. Returns the max profit you can make.

• Choose a low one to buy, then choose a high one to sell, then choose a low one to buy…the cycle repeats. Local optimal: collect daily positive profits, global optimal: find the maximum profit.

• class Solution {<!-- -->
  public:
      int maxProfit(vector<int> & amp; prices) {<!-- -->
          int res=0;
          for(int i=0;i<prices.size()-1;i + + ){<!-- -->
              res + = (prices[i + 1]-prices[i]) > 0?(prices[i + 1]-prices[i]):0;
          }
          return res;
      }
  };
  

Title: Jumping Game

• Given an array of non-negative integers, you are initially at the first position of the array. Each element in the array represents the maximum length you can jump at that position. Determine whether you can reach the last position.

• It is not necessary to specify how many steps to jump at a time. Take the maximum number of jump steps each time. This is the coverage range that can be jumped. Within this range, no matter how you jump, you can definitely jump over. **Then this question turns into whether the jump coverage can cover the end point! **Take the maximum number of jump steps for each move (get the maximum coverage), and update the maximum coverage every time you move one unit.

• The local optimal solution of the greedy algorithm: take the maximum number of jump steps each time (take the maximum coverage), the overall optimal solution: finally get the overall maximum coverage and see if you can reach the end point.

• class Solution {<!-- -->
  public:
      bool canJump(vector<int> & amp; nums) {<!-- -->
          int cover=0;
          if(nums.size()<=1)
              return true;
          for(int i=0;i<=cover;i + + ){<!-- -->
              cover=max(i + nums[i],cover);
              if(cover>=nums.size()-1){<!-- -->
                  return true;
              }
          }
          return false;
      }
  };
  

• Don’t stick to how many steps you jump each time, but look at the coverage. You can definitely jump within the coverage, regardless of how you jump.

Title: Jumping Game II

• Given a 0-indexed integer array nums of length n. The initial position is nums[0]. Each element nums[i] represents the maximum length to jump forward from index i. In other words, if you are at nums[i], you can jump to any nums[i + j]: 0 <= j <= nums[i ] ; i + j < n. Returns the minimum number of hops to reach nums[n – 1]. Generated test cases can reach nums[n - 1].

• Greedy idea, local optimal: walk as much as possible within the current movable distance. If the end point has not been reached, add one to the number of steps. Overall optimal: take as many steps as possible in one step to achieve the minimum number of steps. **When actually solving the problem, you must start from the coverage area. No matter how you jump, you must be able to jump within the coverage area. Increase the coverage area with the minimum number of steps. Once the coverage area covers the end point, you will get the minimum number of steps. ! **If the mobile subscript reaches the maximum coverage distance of the current step and has not yet reached the end point, then you must take another step to increase the coverage until the coverage reaches the end point.

• When the moving subscript reaches the farthest distance subscript currently covered, the number of steps will be increased by one to increase the coverage distance. The last number of steps is the minimum number of steps.

• If the subscript of the current farthest distance covered is not the end point of the set, the number of steps will be increased by one, and you need to continue walking. If the subscript of the farthest distance currently covered is the end point of the collection, the number of steps does not need to be increased by one, because you cannot go further.

• class Solution {<!-- -->
  public:
      int jump(vector<int> & amp; nums) {<!-- -->
          if(nums.size()<=1)
              return 0;
          int max_len=0;//The maximum distance currently covered
          int count = 0;
          int next_len=0;//The next step covers the farthest distance subscript
          for(int i=0;i<nums.size();i + + ){<!-- -->
              next_len=max(nums[i] + i,next_len);//Update the next step to cover the farthest distance subscript
              if(i==max_len){<!-- --> // Encounter the longest distance subscript currently covered
                  count + + ;
                  max_len=next_len;
                  if(next_len>=nums.size()-1)
                      break;
              }
          }
          return count;
      }
  };
  

• Time complexity: O(n); Space complexity: O(1). The key to understanding this question is: Increase the maximum coverage area with the smallest number of steps until the coverage area covers the end point. The minimum number of steps within this range can definitely be jumped, regardless of how it is jumped. , don’t worry about whether to jump one unit or two units in one step.

Title: Maximizing array sum after K times inversion

• Given an integer array nums and an integer k, modify the array as follows: select an index i and replace nums[i] with -nums[i ]. Repeat this process exactly k times. The same subscript i can be selected multiple times. After modifying the array in this way, return the array’s maximum possible sum .

• Greedy idea, local optimal: let the negative number with a large absolute value become a positive number, the current value reaches the maximum, and the overall optimal: the sum of the entire array reaches the maximum. Then if all the negative numbers are converted into positive numbers, K is still greater than 0. The problem at this time is an ordered sequence of positive integers. How to convert K times of positive and negative numbers to maximize the array sum.

• Then the steps to solve this problem are:

  • Step 1: Sort the array from large to small according to the absolute size. Note that the array should be sorted according to the absolute size
  • Step 2: Traverse from front to back. When encountering a negative number, change it to a positive number. At the same time, K–
  • Step 3: If K is still greater than 0, then repeatedly transform the element with the smallest value to use up K
  • Step 4: Sum

• class Solution {<!-- -->
  public:
      static bool cmp(int a,int b){<!-- -->
          return abs(a)>abs(b);
      }
      int largestSumAfterKNegations(vector<int> & amp; nums, int k) {<!-- -->
          sort(nums.begin(),nums.end(),cmp);
          for(int i=0;i<nums.size();i + + ){<!-- -->
              if(k>0 & amp; & amp; nums[i]<0){<!-- -->
                  nums[i] = -nums[i];
                  k--;
              }
          }
          if(k%2==1) nums[nums.size()-1] = -nums[nums.size()-1];
          int res=0;
          for(int item:nums){<!-- -->
              res + =item;
          }
          return res;
      }
  };
  

Topic: Gas Station

• There are n gas stations on a ring road, and the ith gas station has gas[i] liters of gasoline. You have a car with unlimited fuel tank capacity. Driving from the i gas station to the i + 1 gas station requires gasoline cost[i] l. You start at one of the gas stations and start with an empty tank. Given two integer arrays gas and cost, if you can drive around the ring in order, return the number of the gas station at the time of departure, otherwise return - 1. If a solution exists, it is guaranteed that it is unique.

• The method of violence is obviously

  O

  (

  n

  2

  )

  O(n^2)

  O(n2), traverse each gas station as the starting point, and simulate a circle. If you run a lap without cutting off the fuel in the middle, and the final fuel level is greater than or equal to 0, it means that the starting point is OK. The for loop is suitable for simulating traversal from beginning to end, while the while loop is suitable for simulating circular traversal. You must be good at using while.

• class Solution {<!-- -->
  public:
      int canCompleteCircuit(vector<int> & amp; gas, vector<int> & amp; cost) {<!-- -->
          for(int i=0;i<cost.size();i + + ){<!-- -->
              int rest = gas[i]-cost[i];
              int index=(i + 1)%cost.size();
              while(rest>0 & amp; & amp;index!=i){<!-- -->// Simulate driving a circle starting from i (if rest==0, then the answer is not unique)
                  rest + = gas[index]-cost[index];
                  index=(index + 1)%cost.size();
              }
              // If you run a circle with i as the starting point and the remaining fuel level >= 0, return to the starting position
              if(rest>=0 & amp; & amp; index==i)
                  return i;
          }
          return -1;
      }
  };//time out
  

• Make a greedy selection directly from the global situation, the situation is as follows:

  • Situation 1: If the total gas is less than the total cost, then no matter where you start, you will not be able to run a lap.
  • Case 2: rest[i] = gas[i]-cost[i] is the remaining fuel for the day. i starts from 0 and accumulates to the last stop. If there is no negative number in the accumulation, it means that starting from 0, the fuel is not exhausted. If so, then 0 is the starting point.
  • Case 3: If the accumulated minimum value is a negative number, the car will start from a non-0 node, from back to front,see which node can fill in the negative number, the node that can fill in the negative number is the starting node< /strong>.

• class Solution {<!-- -->
  public:
      int canCompleteCircuit(vector<int> & amp; gas, vector<int> & amp; cost) {<!-- -->
          int cursum=0;
          int min=INT_MAX;// Starting from the starting point, the minimum amount of fuel in the tank
          for(int i=0;i<gas.size();i + + ){<!-- -->
              int rest = gas[i]-cost[i];
              cursum + = rest;
              if(cursum<min){<!-- -->
                  min=cursum;
              }
          }
          if(cursum<0) return -1;
          if(min>=0) return 0;
          for(int i=gas.size()-1;i>=0;i--){<!-- -->
              int rest=gas[i]-cost[i];
              min + = rest;
              if(min>=0){<!-- -->
                  return i;
              }
          }
          return -1;
      }
  };
  

• First of all, if the total fuel amount minus the total consumption is greater than or equal to zero, then you can definitely complete a lap, which means that the sum of the remaining fuel amounts rest[i] of the gas stations at each station must be greater than or equal to zero. i starts from 0 and accumulates rest[i], and the sum is recorded as curSum. Once curSum is less than zero, it means that the interval [0, i] cannot be used as the starting position, because if any position is selected as the starting point in this interval, the oil will be cut off at i. , then the starting position is calculated from i + 1, and curSum is calculated from 0.

• Then local optimality: Once the sum curSum of the current accumulated rest[i] is less than 0, the starting position must be at least i + 1, because starting from before i will not work. Global Optimum: Find a starting positionthat allows you to run a lap.

• class Solution {<!-- -->
  public:
      int canCompleteCircuit(vector<int> & amp; gas, vector<int> & amp; cost) {<!-- -->
          int cursum=0;
          int tosum =0;
          int start=0;
          for(int i=0;i<gas.size();i + + ){<!-- -->
              cursum + =gas[i]-cost[i];
              tosum + =gas[i]-cost[i];
              if(cursum<0){<!-- --> // Once the current accumulated rest[i] and curSum are less than 0
                  start=i + 1;//The starting position is updated to i + 1
                  cursum=0;// curSum starts from 0
              }
          }
          if(tosum<0) return -1;
          return start;
      }
  };
  

• Time complexity: O(n); Space complexity: O(1)