参数解析与跳石板

️参数解析️

题目详情

在命令行输入如下命令：

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


题目链接：

参数解析

解题思路

基本思路：

 模拟

解题思路：

这道题的意思很明确，就是给我们一个字符串，字符串有很多的参数命令，我们需要将这些参数给分离出来并需要求参数的个数。

每个参数都是使用空格分开的，但是由于有部分的参数本身就含有空格，不过这部分的空格它被

"

包起来了。

所以我们可以根据是否在

"

中将空格分为两类，一种是在

"

外的空格，另外一种就是在

"

内的空格，对于

"

外的空格，它的数量决定了参数的数量，因此我们计算参数数量时本质上就是计算空格的数量，最终参数的个数为

引号外空格数量+1

。

那么这道题可以拆分成两个问题，分别为求

"

外的空格数量与解析参数。

第一个问题，求

"

外的空格数量，很简单，我们遍历字符串，如果我们遍历到

"

，我们就不进行空格的技术，直到再次遇到一个

"

，这样就排除了

"

内的空格被计数，那剩下的空格，就正常地计数即可。

第二个问题，输出所有的参数，其实这个思路与第一题思路基本一致，我们也是遍历，遇到非空格非

"

字符就直接不换行输出，遇到

"

外空格就输出回车，如果遇到

"

了，直接不换行输出

"

后的所有内容，直到再次遇到

"

。

总的来说就是遍历的时候会遇到三种情况：

• 情况1:遍历的字符为
  "
  以及
  ""
  内的字符, 遇到
  "
  ，一直无换行输出"后所有字符直到再次遇到
  "

• 情况2:遍历的字符为
  "
  外的空格，输出回车

• 情况3:遍历的字符既不是空格也不是
  "
  ，直接不换行输出空格前所有字符

源代码

import java.util.*;

public class Main{
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 String str = sc.nextLine();
 
 //第一部分，计算参数字符串的个数,也就是计算有效空格的数量
 char[] cs = str.toCharArray();
 int ans = 0;
 int n = cs.length;
 for (int i = 0; i < n; i++) {
 //情况1：带有&quot;的字符串，&quot;&quot;里面的字符串为一整体，是一个参数，包括空格也算
 if (cs[i] == '&quot;') {
 //跳过计算&quot;里面的空格
 i++;
 while (i < n && cs[i] != '&quot;') {
 i++;
 }
 } else if (cs[i] == ' ') {
 ans++;
 }
 }
 //最终参数个数为有效分割空格数+1
 ans++;
 System.out.println(ans);
 //第二部分，输出具体参数
 int i = 0;
 while (i < n) {
 //情况1:遍历的字符为&quot;以及&quot;&quot;内的字符, 遇到&quot;，一直无换行输出&quot;后所有字符直到再次遇到&quot;
 //情况2:遍历的字符为&quot;外的空格，输出回车
 //情况3:遍历的字符既不是空格也不是&quot;，直接输出空格前所有字符
 if (cs[i] == '&quot;') {
 //直接不换行输出&quot;&quot;里面所有字符
 i++;
 while (i < n && cs[i] != '&quot;') {
 System.out.print(cs[i++]);
 }
 i++;
 } else if (cs[i] == ' ') {
 //遇到&quot;外空格输出回车
 System.out.println();
 i++;
 } else {
 //遇到&quot;外的非&quot;与非空格,直接无换行输出
 while (i < n && cs[i] != ' ') {
 System.out.print(cs[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

示例1

输入：

4 24


输出：

5


题目链接：

跳石板

解题思路

基本思路：

 动态规划

习题分析：

简单说，就是这位小易站在一块编号为

k

的石板上，它只能跳

k

的约数步（不包含

1

和

k

），题目会给我们一个起点编号与终点编号，我们要求这位小易从起点跳到终点的最小步数，很明显每跳到一块石块上的步数是取决于从哪一块石块跳过来时已经花费的步数，我们考虑动态规划，毕竟动态规划才会需要利用“上一次”的数据。

解题思路：

前面我们已经分析了，该题应该使用动态规划，下面我们来进行分析与推理：

不妨设起点编号为

，终点编号为

。

状态定义：

 定义

为跳到石块

时的最小步数。

确定初始状态：

 

，其他未经过的石块统一标记为

。

状态转移方程：

 不妨设从第

块石板跳到第

块石板,

的一个约数为

，则

，由于

与

的值不唯一，我们取所有情况的最小步数，即

，当然还有一种特殊情况，那就是第

块石块是第一次被经过，此时的

，遇到这种情况

。

由于我们需要使用到某个数的约数，所以我们可以提前写一个求约数的方法，将一个数的所有约数全部放到一个集合中。

我们遍历的石板的终点编号为

，所以我们的答案就是

，如果

，我们就对

状态进行修改与赋值，否则我们没有必要去对

进行赋值，因为对求

没有帮助，所以我们的动态规划数组的空间为

大小的一维数组。

源代码

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();
 //排除n==m的情况
 if (n == m) {
 System.out.println(0);
 return;
 }
 //状态定义：定义f[i]为跳到第i块石板时的最小步数。
 //确定初始状态：f[n] = 0
 //状态转移方程：不妨设从第j块石板跳到第i块石板,j的一个约数为a，则i=j+a，
 //由于j与a的值不唯一，我们取所有情况的最小步数，即f[i]=f[j+a]=min(f[j])+1
 //如果值为f[i]=0，表示为起点，我们使用-1表示不会经过第i块石板
 int[] f = new int[m+1];
 Arrays.fill(f,-1);
 f[n] = 0;
 for (int j = n; j <= m; j++) {
 //f[j] = 0 表示起点 f[j]=-1表示不会经过第j块石板
 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);
 }
 //找约数
 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;
 }
}


总结

本题为动态规划求最值问题，解决该题的关键就是正确合理地定义状态，确定出初始情况和推导状态转移方程。