【Java版oj】day13参数解析、跳石板

た入场券 2024-03-25 21:44 38阅读 0赞

**目录**

一、参数解析

（1）原题再现

（2）问题分析

（3）完整代码

二、跳石板

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、参数解析 ##
> 
> ### （1）原题再现 ###
> 
> [参数解析\_牛客题霸\_牛客网][Link 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;
>             List<String>res = 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));
>             }
>         }
>     }
> 
> ![67134525e56240318f673bb55dbefa53.png][]

> ## 二、跳石板 ##
> 
> ### （1）原题再现 ###
> 
> [跳石板\_牛客题霸\_牛客网][Link 2]
> 
> **描述**
> 
> 小易来到了一条石板路前，每块石板上从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的最小步数为0
>                 for (int i = n; i < m+1  ; i++) {
>                     if (minSteps[i] == Integer.MAX_VALUE) { //一次都没有到达过就跳过这次循环
>                         continue;
>                     }
>     
>                     List <Integer> 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 List<Integer>approximate(List<Integer> 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;
>         }
>     }
> 
> ![7ed678979e984a40a97210c4e0c72062.png][]

--------------------

![070c0e8db08941f8bbc35e6f3ef2556a.png][]

[Link 1]: https://www.nowcoder.com/practice/668603dc307e4ef4bb07bcd0615ea677
[67134525e56240318f673bb55dbefa53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/af81061ce60d4177ac9803d68157d70e.png
[Link 2]: https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8
[7ed678979e984a40a97210c4e0c72062.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/029de65df22d458fa5f189e31b562d77.png
[070c0e8db08941f8bbc35e6f3ef2556a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/37f0d5131f40420daba46dadfda3b69d.png