Parameter analysis and stone jumping board

️ Argument parsing ️

Topic details

Enter the following command at the command line ：

xcopy /s c:\ d:\e,

The parameters are as follows ：

• Parameters 1： Command word xcopy

• Parameters 2： character string /s

• Parameters 3： character string c:\

• Parameters 4:  character string d:\e

Please write a parameter resolver , Implementation of the command line to resolve the various parameters .

Parsing rules ：

1. The parameter separator is a space 2. For using "" Included parameters , If there is a space in the middle , Cannot resolve to more than one parameter . For example, on the command line, type xcopy /s "C:\program files" "d:" when , Parameter is still 4 individual , The first 3 Arguments should be strings C:\program files, instead of C:\program, Pay attention to the output parameters , Need to put "" Get rid of , There is no nesting of quotation marks .3. Parameters are indefinite in length

4. Input is guaranteed by use cases , There will be no input that does not meet the requirements

Data range ： String length ：1≤

s

≤1000

Advanced ： Time complexity ：O*(

n) , Spatial complexity ：O

(*n)

Input description ：

Enter a line of string , There can be spaces

Output description ：

Number of output parameters , The decomposed parameters , Each parameter has an exclusive line

Example 1

Input ：

xcopy /s c:\\ d:\\e


Output ：

4
xcopy
/s
c:\\
d:\\e


Topic link ：

Argument parsing

Their thinking

The basic idea ：

  simulation

Their thinking ：

The meaning of this question is very clear , Just give us a string , String has many parameter commands , We need to separate these parameters and find the number of parameters .

Each parameter is separated by a space , However, some parameters contain spaces , However, the blank space in this part is

"

Wrap it up. .

So we can decide whether we are

"

Divide spaces into two categories , One is in

"

Space outside , The other is in

"

Space inside , about

"

Space outside , Its number determines the number of parameters , Therefore, when we calculate the number of parameters, we are essentially calculating the number of spaces , The number of final parameters is

The number of spaces outside quotation marks +1

.

Then this problem can be divided into two problems , For the sake of

"

The number of spaces outside and the parsing parameters .

The first question is , seek

"

The number of spaces outside , It's simple , We traverse the string , If we traverse to

"

, We will not carry out the technology of blank space , Until I meet another one

"

, This eliminates

"

Spaces within are counted , The rest of the space , Just count normally .

The second question is , Output all the parameters , In fact, this idea is basically the same as the first question , We also traverse , Encountered non space non

"

Characters are output directly without line breaks , encounter

"

The outer space will output carriage return , If you encounter

"

了 , Output directly without line breaks

"

Everything after , Until we meet again

"

.

In general, there are three situations when traversing ：

• situation 1: The traversal characters are
  "
  as well as
  ""
  In the character ,  encounter
  "
  , There has been no line feed output " After all characters until encountered again
  "

• situation 2: The traversal characters are
  "
  Space outside , Output carriage return

• situation 3: The traversal character is neither a space nor
  "
  , Output all characters before spaces directly without line breaks

Source code

import java.util.*;

public class Main{
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 String str = sc.nextLine();
 
 // The first part , Calculate the number of parameter strings , That is to calculate the number of effective spaces
 char[] cs = str.toCharArray();
 int ans = 0;
 int n = cs.length;
 for (int i = 0; i < n; i++) {
 // situation 1： with &quot; String ,&quot;&quot; The string inside is a whole , It's a parameter , Including spaces
 if (cs[i] == '&quot;') {
 // Skip calculation &quot; The space inside
 i++;
 while (i < n && cs[i] != '&quot;') {
 i++;
 }
 } else if (cs[i] == ' ') {
 ans++;
 }
 }
 // The final number of parameters is the number of valid split spaces +1
 ans++;
 System.out.println(ans);
 // The second part , Output specific parameters
 int i = 0;
 while (i < n) {
 // situation 1: The traversal characters are &quot; as well as &quot;&quot; In the character ,  encounter &quot;, There has been no line feed output &quot; After all characters until encountered again &quot;
 // situation 2: The traversal characters are &quot; Space outside , Output carriage return
 // situation 3: The traversal character is neither a space nor &quot;, Directly output all characters before spaces
 if (cs[i] == '&quot;') {
 // Output directly without line breaks &quot;&quot; All the characters in it
 i++;
 while (i < n && cs[i] != '&quot;') {
 System.out.print(cs[i++]);
 }
 i++;
 } else if (cs[i] == ' ') {
 // encounter &quot; Output carriage return in outer space
 System.out.println();
 i++;
 } else {
 // encounter &quot; The outside is not &quot; And non spaces , Direct output without line breaks
 while (i < n && cs[i] != ' ') {
 System.out.print(cs[i++]);
 } 
 }
 }
 }
}


summary

This is a simple traversal simulation problem , We just need to distinguish between situations , Make different treatment for each situation .

️ Jumping stone slab ️

Topic details

Xiao Yi came to a stone road , From... On each slate 1 Next to the number ：1、2、3....... This flagstone road can only move forward according to special rules ： For Xiaoyi, the current number is K Of   slate , Xiaoyi can only jump forward at a time K A divisor of ( Not included 1 and K) Step , Jump to K+X(X by K A non 1 And itself ) The location of .  Xiaoyi is currently in the position of No N Stone slab , He wants to jump to the right number M Go to the slate , Xiao Yi wants to know how many jumps it takes to get to . for example ：N = 4,M = 24：4->6->8->12->18->24 So Xiaoyi needs to jump at least 5 Time , You can start from 4 Flagstone No. 1 jumps to 24 No. stone slab

Input description ：

Enter as one line , There are two integers N,M, Space off . (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

Output description ：

Output the minimum number of steps that Xiaoyi needs to jump , If the output cannot be reached -1

Example 1

Input ：

4 24


Output ：

5


Topic link ：

Jumping stone slab

Their thinking

The basic idea ：

  Dynamic programming

Exercise analysis ：

In short , This is Xiaoyi standing on a block numbered

k

On the slate of , It can only jump

k

Approximate steps of （ It doesn't contain

1

and

k

）, The title will give us a starting number and an ending number , We ask this Xiaoyi to jump from the starting point to the end of the minimum number of steps , Obviously, the number of steps to jump on a stone depends on the number of steps taken when jumping from which stone , We consider dynamic programming , After all, dynamic planning is needed “ Last time ” The data of .

Their thinking ：

We have analyzed , This problem should use dynamic programming , Now let's analyze and reason ：

You may wish to set the starting point number as

, The end point number is

.

State definition ：

  Definition

For jumping on stones

Minimum number of steps at .

Determine the initial state ：

 

, Other stones that have not passed through are uniformly marked as

.

State transition equation ：

  You might as well start from

A stone slab jumps to the

A slate ,

A divisor of is

, be

, because

And

The value of is not unique , We take the minimum number of steps in all cases , namely

, Of course, there is a special case , That's number one

This stone was passed for the first time , At this time

, In this case

.

Because we need to use the divisor of a certain number , So we can write a method of finding the divisor in advance , Put all divisors of a number into a set .

The end number of the slate we traverse is

, So our answer is

, If

, We're right

State modification and assignment , Otherwise, we don't have to be right

Assign a value , Because to ask

No help , So the space of our dynamic programming array is

One dimensional array of sizes .

Source code

import java.util.*;

public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 int n = sc.nextInt();
 int m = sc.nextInt();
 // exclude n==m The situation of
 if (n == m) {
 System.out.println(0);
 return;
 }
 // State definition ： Definition f[i] To jump to the i The minimum number of steps for a stone slab .
 // Determine the initial state ：f[n] = 0
 // State transition equation ： You might as well start from j A stone slab jumps to the i A slate ,j A divisor of is a, be i=j+a,
 // because j And a The value of is not unique , We take the minimum number of steps in all cases , namely f[i]=f[j+a]=min(f[j])+1
 // If the value is f[i]=0, Expressed as the starting point , We use -1 It means that it will not pass through i A slate
 int[] f = new int[m+1];
 Arrays.fill(f,-1);
 f[n] = 0;
 for (int j = n; j <= m; j++) {
 //f[j] = 0  The starting point  f[j]=-1 It means that it will not pass through j A slate
 if (f[j] == -1) {
 continue;
 }
 List<Integer> list = find(j);
 for (int a : list) {
 if (j + a <= m) {
 if (f[j + a] == -1) {
 f[j + a] = f[j] + 1;
 } else {
 f[j + a] = (f[j] + 1) < f[j + a] ? (f[j] + 1) : f[j + a];
 }
 }
 }
 }
 int ans = f[m];
 System.out.println(ans);
 }
 // Find a divisor
 private static List<Integer> find(int n) {
 List<Integer> list = new ArrayList<>();
 for (int i = 2; i * i <= n; i++) {
 if (n % i == 0) {
 list.add(i);
 if (n / i != i) {
 list.add(n / i);
 }
 }
 }
 return list;
 }
}


summary

This topic is dynamic programming to find the most value problem , The key to solve this problem is to define the state correctly and reasonably , Determine the initial situation and derive the state transition equation .