The article directories

      • 738. Monotonically increasing numbers
        • Greedy method
      • 763. Divide letter intervals
      • 56. Consolidated intervals

738. Monotonically increasing numbers

Given a non-negative integer N, find the largest integer less than or equal to N (greedy requirement), and the integer whose digits are monotonically increasing (hard requirement).

(An integer is said to be monotonically increasing if and only if the numbers x and y on each of the adjacent digits satisfy that x <= y.)

Example 1: Input: N = 10 Output: 9

Example 2: Input: N = 1234 Output: 1234

Example 3: Input: N = 332 Output: 299

Note: N is an integer in the range [0, 10^9].

Greedy method

They want the most monotonically increasing integer less than or equal to N, so let’s take a two-digit number.

For example, if strNum[i-1] > strNum[I] is not monotonically increasing, we want strNum[i-1] — and strNum[I] to be 9, so that the integer is 89, which is the largest monotonically increasing integer less than 98.

If you think clearly about this point, the problem will be easy to solve.

StrNum [i-1] > strNum[I], strNum[i-1] -, strNum[I] = 9, strNum[I] = 9, strNum[I] = 9

Global optimality: Obtain the largest monotonically increasing integer less than or equal to N.

But in this case, local optimality leads to global optimality, and we also need other conditions, namely, the order of traversal, and the place where the marker starts to change to 9.

Do I go back or do I go back to front?

StrNum [i-1] = strNum[i-1] = strNum[i-2] = strNum[i-1] = strNum[i-1] = strNum[i-2]

This is a bit abstract. For example, the number 332, if you go backwards and forwards, becomes 329, and 2 is less than 3 in the first place, the real result should be 299.

So going backwards and forwards changes what you’ve already walked through!

Then the result obtained from the last comparison can be reused by traversing from the back to the front. The value change of traversing 332 from the back to the front is 332 -> 329 -> 299

After determining the order of traversal, the local optimal can be derived globally at this time, and there is no counter example, try greedy.

class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] charArray = (N + "").toCharArray(); // int becomes String int flag = chararray. length; // If the first loop is not enteredifBlock, the second loop does not need to be executedfor(int i = charArray.length - 1; i >= 1; I --) {// use I I -1, so from [1,length-1]if(charArray[i-1] > charArray[I]) {// The value must be less than or equal to. CharArray [i-1]--; charArray[i-1]--; }}for (int i = flag; i < charArray.length; i++) {
            charArray[i] = '9';
        }
        returnInteger.parseInt(new String(charArray)); }}Copy the code

763. Divide letter intervals

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

Example: input: S = “ababcbacadefegdehijhklij” output: [9,7,8]

Explanation: The results were “ababcbaca”, “defegde”, “hijhklij”. Each letter appears in at most one fragment. Like “ababcbacadefegde”, “hijhklij” is incorrectly divided because of the small number of fragments.

Tip 1: the length of S is between [1, 500]. Tip 2: S contains only lowercase letters’ a ‘through’ z ‘.

The traversal process is equivalent to finding the boundary of each letter. “If you find the farthest boundary of all letters traversed before, it means that this boundary is the partition point”. All of the letters have been in front of us, as far as we can get.

It can be divided into the following two steps:

1. Count the last position of each character; 2, iterate through the character from the beginning, and update the farthest subscript of the character, if the longest subscript of the character is found and the current subscript is equal, then find the segmentation point.

class Solution { public List<Integer> partitionLabels(String S) { List<Integer> result=new ArrayList<>(); // Store the length insideif (S==null || S.length()<=1) return result;
        char[] charArray=S.toCharArray();
        int[] hash=new int[27];
        
        for(int i=0; i<S.length(); i++)hash[charArray[i]-'a']=i; // If a letter appears after another letter, the following I overwrites the preceding one, sohashInt right=0; int right=0; int right=0; int left=0;for(int i=0; i<S.length(); i++){ right=Math.max(right,hash[charArray[i]-'a']); // Select a larger oneif(I == right){result.add(right-left+1); left=right+1; Left = I +1}}returnresult; }}Copy the code

56. Consolidated intervals

Given a set of intervals, merge all overlapping intervals.

Example 1: input: intervals = [[1, 3], [2, 6], [8, 10], [15, 17]] output: [[1, 6], [8, 10], [15, 17]] : interval [1, 3] and [2, 6] overlap, merge them into [1, 6].

Example 2: input: intervals = [[1, 4], [4, 5]] output: [[1, 5]] : interval [1, 4] and [4, 5] can be seen as overlapping range. Note: The input type was changed on 15 April 2019. Reset the default code definition to get the new method signature.

[I][0] <= the life of an infant [I][1]

So I sort by the left boundary. After sorting, local optimal: take the largest right boundary for each merge, so that more intervals can be merged. Global optimal: merge all overlapping intervals.

The C++ function push_back() is equivalent to list.add() : the function adds a new element to the end of the vector, next to the current last element. Push_back () adds an element to the end of the vector.

The C++ back() function is equivalent to the list.get(list.size()-1) function: returns a reference to the last element in the current vector.

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length<=1) returnintervals; List<int[]> result=new ArrayList<>(); Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {returno1[0] - o2[0]; }}); boolean isFinished=false; / / not completefor(int i=1; i<intervals.length; i++){ int start=intervals[i-1][0]; int end=intervals[i-1][1];while(I < intervals. Length && intervals [I] [0] < = end) {/ / is also calculate overlap, also want to merge the end = math.h Max (end, intervals [I] [1]). // Take the first element and the second element as the larger end, then I ++, and the third element [I][0] comparisonif (i==intervals.length-1) isFinished=true;
                i++;
            }
            result.add(new int[]{start,end});
        }
        if(! isFinished){ result.add(new int[]{intervals[intervals.length-1][0],intervals[intervals.length-1][1]}); }returnresult.toArray(new int[result.size()][]); // result.size() {enjoy.length}}Copy the code

To simplify the

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length<=1) returnintervals; List<int[]> result=new ArrayList<>(); Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {returno1[0] - o2[0]; }}); result.add(new int[]{intervals[0][0],intervals[0][1]}); // Put the first one in firstfor(int i=1; i<intervals.length; i++){ // int start=intervals[i-1][0]; // int end=intervals[i-1][1]; //while// End = Math. Max (end, end [I][1]); // End = Math. // I ++; // I ++; // I ++; // } // result.add(new int[]{start,end}); int[] lastElement = result.get(result.size()-1);if(lastElement [1] > = intervals [I] [0]) {/ / than and equal to calculate overlap, will merge / / reset the element to the end of the list cannot be modified, can only be deleted first, after the new, Int start=lastElement[0]; result.remove(result.size()-1); Result.add (new int[]{start, math.max (lastElement[1], enjoyment.string [I][1])}); Math.max = math.max;else{ result.add(intervals[i]); }}returnresult.toArray(new int[result.size()][]); // result.size() {enjoy.length}}Copy the code

is

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length<=1) returnintervals; List<int[]> result=new ArrayList<>(); Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {returno1[0] - o2[0]; }}); result.add(new int[]{intervals[0][0],intervals[0][1]}); // Put the first one in firstfor(int i=1; i<intervals.length; i++){ int[] lastElement = result.get(result.size()-1);if(lastElement [1] > = intervals [I] [0]) {/ / than and equal to calculate overlap, will merge / / reset the element to the end of the list cannot be modified, can only be deleted first, after the new, Int start=lastElement[0]; result.remove(result.size()-1); Result.add (new int[]{start, math.max (lastElement[1], enjoyment.string [I][1])}); Math.max = math.max;else{ result.add(intervals[i]); }}returnresult.toArray(new int[result.size()][]); // result.size() {enjoy.length}}Copy the code