Catalog

Sort subsequence

Find the longest consecutive number string in the string

---

These two programming problems are of average difficulty , But you must read the question carefully and understand the meaning of the question , Doing the first question “ Sort subsequence ” when , I have never understood the meaning of non increasing or non decreasing sorting , I have been unable to start because of this problem , Finally, I learned that , Non recursive, i.e arr[i] <= arr[i+1] , Non incremental sort arr[i] >= arr[i+1] ; When doing the second question , I also misunderstood the meaning of the title , What I understand is that it's not just a continuous string of numbers , It has to be incremental , Maybe I thought more about programming at that time , I didn't read the questions carefully .

Sort subsequence

Topic link ： Sort subsequence

Input description

The first line of input is an integer n(1 < n < 10^5), The second line includes n It's an integer A_i（1 < A_i < 10^9） Represents an array A Every number in

Output description

Output an integer indicating that Niuniu can A At least how many segments

for example  

Input

6

1 2 3 2 2 1

Output

2

Their thinking  

① Defining variables count To record the number of subsequences that can be divided into , Traverse the array starting with the first element , Judge in turn ;

② If arr[i] < arr[i+1], Enter the non increasing sequence to judge , Until the array traversal is completed or arr[i] > arr[i+1] when , Traversal stops ,count++;

③ If arr[i] > arr[i+1], Enter the non decreasing sequence to judge , Until the array traversal is completed or arr[i] < arr[i+1] when , Traversal stops ,count++;

④ If arr[i] == arr[i+1], No judgment , direct i++ Just traverse the next position .

A special case ： If the input sequence is 5 5 5 5 5, When five identical data , At this time, only the fourth step will be carried out , Two or three steps will not enter judgment , At this point, it shows that the array space is larger than the actual stored data 1 The benefits of , At this time, the elements stored in the array are 5 5 5 5 5 0, This ensures that the array is not out of bounds , It also ensures the accuracy of the code .

Specific code implementation

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // The array memory is larger than the actual data stored +1, In case the array goes out of bounds 
        int[] arr = new int[n+1];
        for(int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        int count = 0;
        int i = 0;
        while(i < n) {
            if(arr[i] < arr[i+1]) {
                while(i<n && arr[i] <= arr[i+1]) {
                    i++;
                }
                count++;
                i++;
            }else if(arr[i] == arr[i+1]) {
                i++;
            }else {
                while(i<n && arr[i] >= arr[i+1]) {
                    i++;
                }
                count++;
                i++;
            }
        }
        System.out.println(count);
    }
}

Find the longest consecutive number string in the string

Topic link ： Find the longest consecutive number string in the string

Their thinking  

Find the longest continuous number string in the string by counting

① Define three variables ,count,max,end.

count Used to record the length of each continuous digital string

max Used to record the longest continuous number string in the string

end Used to record the subscript of the last number in the longest continuous number string .

② Traversal string , When characters are encountered , take count Set as 0; When you encounter the first number ,count Start counting , Until the next character appears ; Compare count And max, If count > max, Make max = count.

for example ： When the first number string is counted , here

When the second segment of string statistics is finished

At this point, the traversal of the string has ended , according to max and end Directly output the longest string , The specific code is as follows  

  Specific code implementation

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        int max = 0;
        int end = 0;
        int count = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                count++;
                if(max < count) {
                    max = count;
                    end = i;
                }
            }else {
                count = 0;
            }
        }
        for(int i = end-max+1; i <= end; i++) {
            System.out.print(str.charAt(i));
        }
    } 
}