目录

 一、参数解析

（1）原题再现

（2）问题分析

（3）完整代码

 二、跳石板

（1）原题再现

（2）问题分析

（3）完整代码

 一、参数解析

（1）原题再现

参数解析_牛客题霸_牛客网

描述

在命令行输入如下命令：

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

各个参数如下：

参数1：命令字xcopy

参数2：字符串/s

参数3：字符串c:\\

参数4: 字符串d:\\e

请编写一个参数解析程序，实现将命令行各个参数解析出来。

解析规则：

1.参数分隔符为空格
2.对于用""包含起来的参数，如果中间有空格，不能解析为多个参数。比如在命令行输入xcopy /s "C:\\program files" "d:\"时，参数仍然是4个，第3个参数应该是字符串C:\\program files，而不是C:\\program，注意输出参数时，需要将""去掉，引号不存在嵌套情况。
3.参数不定长

4.输入由用例保证，不会出现不符合要求的输入

数据范围：字符串长度：1\le s\le 1000\1≤s≤1000 

进阶：时间复杂度：O(n)\O(n) ，空间复杂度：O(n)\O(n) 

输入描述：

输入一行字符串，可以有空格

输出描述：

输出参数个数，分解后的参数，每个参数都独占一行

示例1

输入：

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

输出：

4

xcopy

/s

c:\\

d:\\e

（2）问题分析

       本题我们可以使用一个快慢指针法。对指针等于空格和引号分别作出判断。

       首先考虑没有引号的情况：快指针先在前走，慢指针在原地，当快指针遇到空格时，划分一个字符串。然后改变快慢指针的指向，注意不要把快慢指针指向同一个字符，不方便对有引号的情况进行分割，要一前一后，初始值无所谓。开始下一个字符串的划分。

       其次考虑给定字符串有引号的情况：同样运用快慢指针，在后的慢指针遇到第一个引号，只有当在前的快指针遇到第二个引号时，才进行分割。注意的是，因为快慢指针一前一后，所以快指针不会遇到第一个引号的。

       分情况讨论：当慢指针没有遇到引号时，快指针跟空格进行判断；当慢指针遇到引号时，快指针跟引号进行判断。

       在运行时，我还遇到了一个奇怪的问题，就是字符串的输出格式与题目要求不同，按照上诉思想进行分割时，有些情况分割的字符串两端会出现空格，我们可以使用trim()方法除去两端空格。

（3）完整代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();String ans;int slow = 0;int fast = 0;int count = 0;Listres = new LinkedList<>();while (fast < str.length()) {if (str.charAt(slow) != '"') {while (fast < str.length() && str.charAt(fast) != ' ') {fast++;}ans = str.substring(slow, fast).trim();res.add(ans);count++;slow = fast + 1;fast = slow + 1;} else {while (fast < str.length() && str.charAt(fast) != '"') {fast++;}ans = str.substring(slow + 1, fast ).trim();res.add(ans);count++;slow = fast + 1;fast = slow + 1;}}System.out.println(count);for (int i = 0; i < res.size(); i++) {System.out.println(res.get(i));}}
}

 二、跳石板

（1）原题再现

跳石板_牛客题霸_牛客网

描述

        小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......
        这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

输入描述：

输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

输出描述：

输出小易最少需要跳跃的步数,如果不能到达输出-1

示例1

输入：

4 24

输出：

5

2

（2）问题分析

        本题本质上是一道动态规划。首先我们定义一个状态数组minSteps[]，里面用来保存到达i所用的最小步数。所有数组值初始化默认为Integer.MAX_VALUE，如果到最后遍历完还是Integer.MAX_VALUE，就表示到不了这个点。

        初始状态时i=n时，就是小易当前所在的石板编号，定义他的初始状态就是0，不需要跳步，本身就在这个位置。状态方程：

minSteps[i + list.get(j)] = Math.min(minSteps[i + list.get(j)], minSteps[i] + 1);

        表示的是到编号i+i编号的因子list.get(j)的这块石板的步数，由两种情况，一种是这个位置上次所记录的最小步数；另一种是这次从石板跳一步步长为list.get(i)的步数（i位置所记录的最小步数+1）。这两者之间取最小值，记录下来。

        具体的每一步可以看代码，我写了详细的解析。

        本题还有一个注意点：就是运行超时的问题。所以我们在求一个数的因子时，不要使用n，而是Math.sqrt(n) n的平方根。一个数都是由他的较大的因数和较小的因数的乘积组成。所以我们只需遍历一半就可以了。

        需要格外小心的是，可能这两个因数一样大，就像7*7=49，我们只需要加入链表一次就可以了。

（3）完整代码

import java.util.*;//注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();System.out.println(leastStep(n, m));}
//动态规划求最小步数public static int leastStep(int n, int m) {if (m == n) {return 0;} else {//minSteps[i]表示到达i所用的最小步数，所有数组值初始化默认为Integer.MAX_VALUE，如果到最后遍历完还是Integer.MAX_VALUE，就表示到不了这个点。int []minSteps = new int[m + 1];for (int i = 0; i < minSteps.length; i++) {minSteps[i] = Integer.MAX_VALUE;}// Arrays.fill(minSteps,Integer.MAX_VALUE);minSteps[n] = 0; //初始状态，从n到达石板n的最小步数为0for (int i = n; i < m+1  ; i++) {if (minSteps[i] == Integer.MAX_VALUE) { //一次都没有到达过就跳过这次循环continue;}List  list = new ArrayList<>();approximate(list, i);//求当前编号为i石板的因子for (int j = 0; j < list.size(); j++) {if (i + list.get(j) <= m) { //从编号i的石板往后跳list.get(j)步,判断是否越界minSteps[i + list.get(j)] = Math.min(minSteps[i + list.get(j)], minSteps[i] + 1);}}}if (minSteps[m] == Integer.MAX_VALUE) {return -1;} else {return minSteps[m];}}}public static Listapproximate(List list, int n) {for (int i = 2; i <= Math.sqrt(n); i++) {if (n % i == 0) {//较小的因子list.add(i);}//判断较大的因子是不是和较小的因子一样大，如果是就不要加进链表if (n % (n/i) ==0 && n / i != i) {list.add(n / i);}}return list;}
}