Java题目训练——参数解析和跳石板

叁歲伎倆 2023-09-30 20:49 9阅读 0赞

**目录**

一、参数解析

二、跳石板

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

### 一、参数解析 ###

题目描述：

> 在命令行输入如下命令：
> 
> 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)

输入描述：

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

输出描述：

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

示例

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

**题目解析：**

> 首先计算共有几个参数，通过循环遍历完成，记得双引号中的所有内容算一个参数，然后是所有参数的输出操作，需要设置一个flag标记是在引号内还是引号外，每次遇到双引号时改变flag的标记值，在引号外时遇到空格要跳过，在引号内的所有内容直接输出。

public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String s = in.nextLine();
    
            int count = 0;
            for(int i = 0;i < s.length();i++){
                if(s.charAt(i) == '"'){
                    i++;
                    while(s.charAt(i) != '"'){
                        i++;
                    }
                }
                if(s.charAt(i) == ' '){
                    count++;
                }
            }
            System.out.println(count+1);
    
            int flag = 0;
            for(int i = 0;i < s.length();i++){
                if(flag == 0&&s.charAt(i) == '"'){
                    flag = 1;
                    continue;
                }
                if(flag == 1&&s.charAt(i) == '"'){
                    flag = 0;
                    continue;
                }
                if(flag == 0){
                    if(s.charAt(i) != ' '){
                        System.out.print(s.charAt(i));
                    }else{
                        System.out.println();
                    }
                }else{
                    System.out.print(s.charAt(i));
                }
            }
        }
    }

### 二、跳石板 ###

题目描述：

> 小易来到了一条石板路前，每块石板上从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

示例

> 输入：4 24
> 
> 输出：5

**题目解析：**

> 本题采取回溯法，先新建一个M + 1大小的数组step\[M + 1\]，并且将其初始值全部赋一个很大的值（这里赋了整型的最大值），接下来从step\[N\]开始，因为从其开始所以使step\[N\] = 0，循环遍历至step\[M + 1\]处，遍历时如果到达某一点时他的值还是Integer.MAX\_VALUE，说明该点是无法到达的，直接继续看下一点；如果该点可到达，新建一个数组list存储该点的所有约数，遍历所有约数的可能，其中分为两种情况，第一种是如果加上该约数到达的点没有到达终点并且之前到达过，需要比较之前的值和现在更新的值哪个更小并更新为更小值；第二种是如果加上该约数到达的点没有到达终点并且之前没有到达过，该点值等于未加约数点的值再加1。
> 
> 最后在step\[M\]点是步数最小值，如果是Integer.MAX\_VALUE，说明该点无法到达。
> 
> 需要注意的是，在求约数集合时我们需要通过一些判定条件来减少时间复杂度，否则解题时会超出时间限制。

import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
    
            int[] step = new int[m + 1];
            for(int i = 0;i < m + 1;i++){
                step[i] = Integer.MAX_VALUE;
            }
    
            step[n] = 0;
            for(int i = n;i < m + 1;i++){
                //无法到达的点
                if(step[i] == Integer.MAX_VALUE){
                    continue;
                }
                List<Integer> list = div(i);
                for(int j : list){
                    //没有到达终点并且之前到达过
                    if(i + j < m + 1&&step[i + j] != Integer.MAX_VALUE){
                        step[i + j] = Math.min(step[i + j],step[i] + 1);
                    }
                    //没有到达终点但之前没到达过
                    else if(i + j < m + 1){
                        step[i + j] = step[i] + 1;
                    }
                }
            }
    
            if(step[m] != Integer.MAX_VALUE){
                System.out.println(step[m]);
            }else{
                System.out.println(-1);
            }
        }
    
        public static List<Integer> div(int n){//返回约数合集，需要减小时间复杂度
            List<Integer> list = new ArrayList<Integer>();
            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;
        }
    }

如有建议或想法，欢迎一起讨论学习~