刷题_13：参数解析 and 跳石板

青旅半醒 2023-09-29 23:43 19阅读 0赞

### 一.参数解析 ###

**题目链接：**

> [参数解析][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≤s≤1000  
> 进阶：时间复杂度：O(n) ，空间复杂度：O(n)**

**输入描述：**

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

**输出描述：**

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

**示例1：**

> **输入：  
> xcopy /s c:\\ d:\\e  
> 输出：  
> 4  
> xcopy  
> /s  
> c:\\  
> d:\\e**

**个人总结：**

> **关于这道题我只能说细节很多，首先我们设置一个标志位，用来判断我们是否进入了 “” 内部，进入了则对空格进行拼接，没有进入则将字符串加入链表并清空，详细的可以自己看代码。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            //因为要先输出参数个数再输出各个参数 所以得用个链表储存结果
            List<String> res = new ArrayList<>();
            char[] chs = s.toCharArray();
            //没有遇到引号时 标志位设置为false
            boolean flag = false;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < chs.length; i++) {
        
                if (chs[i] == '"' && flag == false) {
        
                    flag = true;
                } else if (chs[i] == '"' && flag == true) {
        
                    flag = false;
                } else if (chs[i] == ' ' && flag == true) {
        
                    sb.append(chs[i]);
                } else if (chs[i] == ' ') {
        
                    res.add(sb.toString());
                    sb = new StringBuilder();
                } else {
        
                    sb.append(chs[i]);
                }
            }
            res.add(sb.toString());
            System.out.println(res.size());
            for (String str : res) {
        
                System.out.println(str);
            }
        }
    }

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

### 二.跳石板 ###

**题目链接：**

> [跳石板][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**

**个人总结：**

> **动态规划题，我们定义一个dp\[i\]：表示到达i所需的最小步数，遍历到第i个时，我们找出它所有的约数(约数即为当前点i可以向前跳的步数)，我们假设约数为j，则状态转移方程为`dp[i + j] = Math.min(dp[i + j], dp[i] + 1);`  
> 代码部分解释：  
> `if (dp[i] == max) { continue; }`：dp\[i\] == max则表示dp\[i\]不可到达，直接跳过即可。  
> `for (int j = 2; (j * j) <= i; j++)`：j \* j <= m，减少运算次数的同时，达到了遍历所有约数的要求，比较巧妙。**

**代码实现：**

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();
            //dp[i]：到达i所需的最小步数
            int[] dp = new int[m + 1];
            int max = Integer.MAX_VALUE;
            for (int i = 0; i <= m; i++) {
        
                dp[i] = max;
            }
            dp[n] = 0;
            for (int i = n; i <= m; i++) {
        
                if (dp[i] == max) {
        
                    continue;
                }
                for (int j = 2; (j * j) <= i; j++) {
        
                    if (i % j == 0) {
        
                        if (i + j <= m) {
        
                            dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                        }
                        if (i + i / j <= m) {
        
                            dp[i + i / j] = Math.min(dp[i + i / j], dp[i] + 1);
                        }
                    }
                }
            }
            System.out.println(dp[m] == max ? -1 : dp[m]);
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/668603dc307e4ef4bb07bcd0615ea677
[Link 2]: https://www.nowcoder.com/questionTerminal/4284c8f466814870bae7799a07d49ec8