Leetcode brush problem – greedy

Ensure that each operation is locally optimal and that the resulting result is globally optimal

1. Distribution of biscuits

The title

Let’s say you’re a great parent and you 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 a cookie to satisfy a child’s appetite; And every cookie J has a size S [J]. If s[j] >= g[I], we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number.

Train of thought

A classic greedy algorithm

Proof: Suppose that in a certain choice, greedy strategy chooses to allocate the MTH biscuit to the child with the smallest satisfaction degree, and the MTH biscuit is the smallest biscuit that can satisfy the child; Suppose there is an optimal strategy to allocate the NTH cookie to the child, and M

var findContentChildren = function(g, s) {
  g.sort((a, b) = > a - b);
  s.sort((a, b) = > a - b);

  let gi = 0, si = 0;
  
  while(gi < g.length && si < s.length) {
    if (g[gi] <= s[si]) {
      gi++;
    }
    si++;
  }

  return gi;
};
Copy the code

2. Unoverlapping interval

The title

Given a set of intervals, find the minimum number of intervals to remove so that the remaining intervals do not overlap.

Note:

You can assume that the end of an interval is always greater than its beginning. The boundaries of the intervals [1,2] and [2,3] “touch” each other, but do not overlap each other.

Train of thought

• Calculate the maximum number of non-overlapping intervals that can be formed, and subtract the number of non-overlapping intervals from the total number of intervals
• How do I figure out the maximum number of non-overlapping intervals? Greedy: Select the interval with the smallest ending each time, because the smaller the end of the selected interval, the larger the space left for the following interval, and the larger the number of intervals that can be selected later

var eraseOverlapIntervals = function(intervals) {
  intervals.sort((a, b) = > a[1] - b[1]);
  let count = 1;
  let end = intervals[0] [1];

  for (let i = 1; i < intervals.length; i++) {
    const item = intervals[i];
    if (item[0] < end) {
      continue;
    }
    count++;
    end = item[1];
  }

  return intervals.length - count;
};
Copy the code

3. Detonate the balloon with the minimum number of arrows

The title

There are many spherical balloons in two dimensions. For each balloon, the input provided is the start and end coordinates of the balloon diameter in the horizontal direction. Since it’s horizontal, the y-coordinate doesn’t matter, so it’s enough to know where the x-coordinate starts and ends. The start coordinate is always less than the end coordinate.

A bow and arrow can be shot completely vertically from different points along the X-axis. Shoot an arrow at coordinate X. If there is a balloon whose diameter starts and ends at coordinates xstart, xend, and xstart ≤ x ≤ xend, the balloon will be detonated. There is no limit to the number of bows and arrows that can be fired. Once a bow is fired, it can go indefinitely. We want to find the minimum number of arrows needed to detonate all the balloons.

Give you an array of points, where points [I] = [xstart,xend] returns the minimum number of arrows that must be fired to detonate all the balloons.

Train of thought

Variation on problem two

var findMinArrowShots = function(points) {
  points.sort((a, b) = > a[1] - b[1]);

  let count = 1;
  let minEnd = points[0] [1];

  for (let i = 1; i < points.length; i++) {
    const item = points[i];

    if (item[0] <= minEnd) {
      continue;
    }

    count++;
    minEnd = item[1];
  }

  return count;
};
Copy the code

4. Rebuild the queue based on height

The title

Suppose you have an out-of-order group of people standing in a queue, and the array people represents the attributes of some people in the queue (not necessarily in order). Each people[I] = [hi, ki] means that the ith person is hi, and there are exactly ki people in front of them who are hi or higher.

You reconstruct and return the queue represented by the input array people. The returned queue should be formatted as an array queue, where Queue [j] = [hj, kj] is the property of the JTH person in the queue (queue[0] is the person at the front of the queue).

Train of thought

The height is in descending order, the K value is in ascending order, and then inserted into the KTH position in the queue in the ordered order

var reconstructQueue = function(people) {
  people.sort((a, b) = > a[0] === b[0]? a[1] - b[1] : b[0] - a[0])
  const resArr = [];

  for (let i = 0; i < people.length; i++) {
    const item = people[i];
    resArr.splice(item[1].0, item);
  }

  return resArr;
};
Copy the code

5. Letter interval

The title

The string S consists of lowercase letters. We want to divide the string into as many fragments as possible, with the same letter appearing in at most one fragment. Returns a list representing the length of each string fragment.

var partitionLabels = function (s) {
  const letterArr = initArr(s);
  letterArr.sort((a, b) = > a[0] - b[0]);
  let index = 0;

  for (let i = 0; i < letterArr.length; i++) {
    if (letterArr[i][0]! = = -1) {
      index = i;
      break; }}let begin = letterArr[index][0];
  let end = letterArr[index][1];
  const res = [];

  for (let i = index + 1; i < letterArr.length; i++) {
    const item = letterArr[i];
    if (item[0] < end) {
      end = Math.max(end, item[1]);
    } else {
      res.push(end - begin + 1);
      begin = item[0];
      end = item[1];
    }
  }

  res.push(end - begin + 1);

  return res;
};

function initArr(s) {
  const letterArr = new Array(26);
  for (let i = 0; i < 26; i++) {
    letterArr[i] = [-1, -1];
  }
  const lettera = 'a'.charCodeAt();
  const sArr = s.split(' ');
  for (let i = 0; i < s.length; i++) {
    const code = sArr[i].charCodeAt() - lettera;
    if (letterArr[code][0] = = = -1) {
      letterArr[code][0] = i;
    }
    letterArr[code][1] = i;
  }

  return letterArr;
}
Copy the code

6,Problems and flowers

The title

Suppose you have a very long flower bed, and one part of the plot is planted with flowers, but the other part is not. However, flowers cannot grow in adjacent plots. They compete for water and both die.

Flowerbed gives you an array of integers representing a flowerbed, consisting of zeros and ones, where 0 indicates no flowers and 1 indicates flowers. Another number, n, can I plant n flowers without breaking the planting rules? Returns true if yes, false if no.

var canPlaceFlowers = function(flowerbed, n) {
  if (n === 0) return true; 

  for (let i = 0, len = flowerbed.length; i < len; i++) {
    if (flowerbed[i] === 1) { // If = 1, jump 2 Spaces
      i += 1;
    } else {
      // is equal to 0 and can grow flowers
      if ((i + 1 === len) || (i + 1 < len && flowerbed[i + 1= = =0)) {
        n--;
        if (n === 0) return true;
        i += 1;
      } else {
        // if = 0, you can't plant flowers
        i += 2; }}}return n === 0;
};
Copy the code

7,Judgment subsequence

Given the strings s and t, determine whether S is a subsequence of t.

A subsequence of strings is a new string formed by deleting some (or none) characters from the original string without changing the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not).

var isSubsequence = function(s, t) {
  const m = s.length, n = t.length;
  let i = 0, j = 0;

  while(i < m && j < n) {
    if (s[i] === t[j]) {
      i++;
    }
    j++;
  }

  return i === m;
};
Copy the code

Eight,Nondecreasing sequence(important)

Given an array of integers of length n, determine whether the array can become a non-decrement array with at most one element changed.

We define a nondecreasing sequence like this: for any I in the array (0 <= I <= n-2), nums[I] <= nums[I + 1].

var checkPossibility = function(nums) {
  const n = nums.length;
  let count = 0;

  for (let i = 0; i < n; i++) {
    const x = nums[i], y = nums[i + 1];
    if (x > y) {
      count++;
      if (count > 1) return false;
      if (i > 0 && y < nums[i - 1]) {
        nums[i + 1] = x; }}}return true;
};
Copy the code

9,The best time to buy and sell stocks II

Given an array prices, prices[I] is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

var maxProfit = function(prices) {
  let sum = 0;

  for (let i = 0; i < prices.length; i++) {
    if (i + 1 && prices[i + 1] > prices[i]) {
      sum += (prices[i + 1] - prices[i]); }}return sum;
};
Copy the code

10,Maximum suborder sum

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Train of thought

Dynamic programming: f(I) represents the maximum sum of a contiguous subarray ending with the element I

f(i) = Math.max(f(i-1) + x, x);
Copy the code

var maxSubArray = function(nums) {
  let res = nums[0];
  let arr = new Array(a); arr[0] = nums[0];

  for (let i = 1; i < nums.length; i++) {
    arr[i] = Math.max(arr[i - 1] + nums[i], nums[i]);
    res = Math.max(res, arr[i]);
  }

  return res;
};
Copy the code

11,The best time to buy and sell stocks

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

var maxProfit = function(prices) {
  let res = 0;
  let minArr = new Array(prices.length).fill(10001);
  minArr[0] = prices[0];

  for(let i = 1; i < prices.length; i++) {
    minArr[i] = Math.min(minArr[i - 1], prices[i]);
  }

  for (let i = 0; i < prices.length; i++) {
    res = Math.max(prices[i] - minArr[i], res);
  }

  return res;
};
Copy the code