Greed in three or two ways

1. Distribution of biscuits

Description:

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:

You may assume the greed factor is always positive. 
You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

Analysis:

The biscuit given to a child should be as small as possible and satisfy the child, so that the large biscuit can be brought to the more satisfied child. Because the youngest child is the easiest to be satisfied, satisfy the youngest child first. The greedy strategy chooses to allocate the mth biscuit to the child with the lowest degree of satisfaction, and the mth biscuit is the smallest biscuit to satisfy the child. Assuming that there is an optimal strategy, the child is assigned the nth biscuit, and m < n. We can find that after this round of allocation, there must be a bigger biscuit left after greedy strategy allocation than the optimal strategy. Therefore, in the subsequent allocation, greedy strategy can certainly satisfy more children. That is to say, there is no better strategy than greedy strategy, that is, greedy strategy is the best strategy.

JAVA CODE:

public class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0;
        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
            }
            j++;
        }
        return i;
    }
}

Source of title: 455. Assign Cookies

2. Reorganizing the queue according to height and serial number

Description:

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:

The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Analysis:

In order to ensure that the insertion operation does not affect the follow-up operation, the taller students should do the insertion operation first, otherwise the smaller students'original correct insertion of the first position may become the i+1 position. Height h decreases, number k increases, and then a student is inserted into position I of the queue. At the same time, we use the added feature of the specified idx of list.

JAVA CODE:

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if (people.length < 1 || null == people || people[0].length < 1){
            return new int[0][0];
        }
        //h descending order, k ascending order; taller students should do insertion first
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return (o1[0] == o2[0] ? o1[1]-o2[1]: o2[0] - o1[0]);
            }
        });
        List<int[]> list = new ArrayList<>();
        for (int[] arr : people){
            list.add(arr[1], arr);
        }
        return list.toArray(new int[list.size()][]);
    }
}

Source of title: 406. Queue Reconstruction by Height

3. Throwing darts to pierce balloons

Description:

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Analysis:

The balloon is placed on a horizontal axis, which can overlap. The dart is projected vertically to the coordinate axis, so that the balloon on the path is punctured. Solve the minimum number of darts thrown so that all balloons are punctured. That is to say, to calculate the number of non-overlapping intervals.

JAVA CODE:

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length < 1){
            return 0;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int num = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++){
            if (points[i][0] <= end ){
                continue;
            }
            num++;
            end = points[i][1];
        }
        return num;
    }
}

Source of title: 452. Minimum Number of Arrows to Burst Balloons

4. Number of non-overlapping intervals

Description:

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Note:

  1. You may assume the interval's end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Analysis:

First, the number of non-overlapping intervals that can be formed at most is calculated, and then the number of non-overlapping intervals is subtracted from the total number of intervals. In each selection, the end of the interval is the most important. The smaller the end of the selected interval, the larger the space left behind, and the larger the number of intervals that can be selected later. Sort by the end of the interval, and select the interval with the smallest end and no overlap with the previous interval.

JAVA CODE:

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length < 1){
            return 0;
        }
        //Sort by right endpoint
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
       // quickSot(intervals, 0, intervals.length-1);
        int cnt = 1;
        int right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++){
            if (intervals[i][0]< right){
                continue;
            }
            right = intervals[i][1];
            cnt++;
        }
        return intervals.length - cnt; 
    }
    private static void quickSot(int[][] arr, int low, int high){
        if (arr.length < 1 || low >= high){
            return;
        }
        int i = low;
        int j = high;
        int right = arr[low][1];
        while (i<j){
            //Find the first position larger than right from left to right
            while (i<j && right < arr[i][1]){
                i++;
            }
            //Find the first location less than right from right to left
            while (i<j && right >= arr[j][1]){
                j--;
            }
            if (i<j){
                int tmpL = arr[i][0];
                int tmpR = arr[i][1];
                arr[i][0] = arr[j][0];
                arr[i][1] = arr[j][1];
                arr[j][0] = tmpL;
                arr[j][1] = tmpR;
            }
        }

        int tmpL = arr[i][0];
        int tmpR = arr[i][1];
        arr[i][0] = arr[low][0];
        arr[i][1] = arr[low][1];
        arr[low][0] = tmpL;
        arr[low][1] = tmpR;
        quickSot(arr, low, i-1);
        quickSot(arr, i+1, high);

    }
}

5. Modify at most one number to a non-decreasing array

Description:

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Analysis:

When nums[i] < nums[i-1] occurs, it is necessary to consider which number of arrays should be modified so that the previous number of arrays before I can be made into non-decreasing arrays without affecting subsequent operations. Priority should be given to nums[i - 1] = nums[i], because if nums[i] = nums[i - 1] is modified, the number of nums[i] will increase, which may be larger than nums[i + 1], thus affecting subsequent operations. Another special case is that nums[i] < nums[i - 2]. Modifying nums[i - 1] = nums[i] does not make an array nondecreasing, but only nums[i] = nums[i - 1].

JAVA CODE:

class Solution {
    public boolean checkPossibility(int[] nums) {
        if(nums.length < 1){
            return false;
        }
        int cnt = 0;
        for (int i = 1; i < nums.length && cnt < 2; i++){
            if (nums[i] >= nums[i-1]){
                continue;
            }
            cnt++;
            if (i-2 >= 0 && nums[i-2] > nums[i] ){
                nums[i] = nums[i-1];
            } else {
                nums[i-1] = nums[i];
            }

        }
        return cnt <= 1;
    }
}

6. Find the maximum sum of subarrays

Description:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

JAVA CODE:

class Solution {
    public int maxSubArray(int[] nums) {
        if (null == nums || nums.length < 1){
            return 0;
        }
        int preS = nums[0];
        int maxS = preS;
        for (int i = 1; i < nums.length; i++){
            preS = (preS > 0 ? preS + nums[i] : nums[i]);
            maxS = Math.max(preS, maxS);
        }
        return maxS;
    }
}

7. Separating strings to bring the same characters together

Description:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

  1. S will have length in range [1, 500].
  2. S will consist of lowercase letters ('a' to 'z') only.

Analysis:

Splitting the string into char [], saving the last position of each character with int [], and comparing the last position of each character from scratch using loops, such as last Idx in ababcbacadefegdehijhklij, and then finding the last position IDX of all characters from start a to last a, if IDX > last Idx Then update lastIdx=idx, and finally save the interval length of this [first Idx, last Idx] as the length of the scoring string.

JAVA CODE:

public class Solution {

  public List<Integer> partitionLabels(String S) {
    List<Integer> list = new ArrayList<>();
    if (null == S || S.length() < 1){
      return list;
    }
    //Store the last position of each letter
    int[] arr = new int[26];
    int len = S.length();
    for (int i = 0; i < len; i++){
      arr[char2Idx(S.charAt(i))] = i;
    }
    int firstIdx = 0;
    while (firstIdx < len){
      int lastIdx = firstIdx;
      for (int i = firstIdx; i < len && i <= lastIdx; i++){
        int idx = arr[char2Idx(S.charAt(i))];
        if (idx > lastIdx){
          lastIdx = idx;
        }
      }
      list.add(lastIdx - firstIdx + 1);
      firstIdx = lastIdx + 1;
    }
    return list;
  }

  private static int char2Idx(char c){
    return c - 'a';
  }

}

In addition, I found a summary of the topic Bank of the blog to share here: https://www.cnblogs.com/grandyang/category/625406.html

Tags: Java less REST

Posted on Fri, 13 Sep 2019 01:12:14 -0700 by quikone