每日一练——Day 13

àì夳堔傛蜴生んèń 2023-09-27 17:11 13阅读 0赞

> **前言：**
> 
> 小亭子正在努力的学习编程，接下来将开启编程题的练习~~
> 
> 分享的文章都是学习的笔记和感悟，如有不妥之处希望大佬们批评指正~~
> 
> 同时如果本文对你有帮助的话，**烦请点赞关注支持一波, 感激不尽~~**

## 第一题 ##

### 题目描述： ###

> [刷题点这里][Link 1]![88841e76141644419d85f18e1e3cc5ce.png][]
> 
> ### 描述 ###
> 
> 在命令行输入如下命令：
> 
> 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

### 解题分析： ###

> 整体思路：
> 
> 本题通过以空格和双引号为间隔，统计参数个数。对于双引号，通过添加flag，保证双引号中的空格被输出
> 
> 注意：
> 
> 1、先输出的是个数
> 
> 2、遇到""空格原样输出
> 
> 3、没有""遇到空格就换行  
> 4、遇到 "(前括号) 后，先往后移动一位，再判断下一位字符是该输出，还是遇到了 " （后括号）
> 
> 5、预设一个标记flag= 1 ，遇到双引号的前一半,flag = 0,在遇到后一半,异或运算后 flag= 1,此时双引号结束

### 代码实现： ###

import java.util.Scanner;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String str  = in.nextLine();
            int count = 0;
            //统计个数
            for (int i = 0 ; i < str.length(); i++ ) {
                //
                if (str.charAt(i) == '"') {
                    do {
                        i++;            //注意:此处i需要先往后移动一位
                    } while (str.charAt(i) != '"');
    
                }
                if (str.charAt(i) == ' ') {
                    count ++;
                }
    
            }
            System.out.println(count + 1);  //因为count统计的是空格数,参数个数等于空格数+1
            /*
            遇到双引号的前一半,flag = 0,在遇到后一半,异或运算后 flag= 1,此时双引号结束
            */
            int flag = 1;
            for (int i = 0 ; i < str.length(); i++ ) {
                if (str.charAt(i) == '"') {
                    flag ^= 1;
                }
                //除了双引号和特殊空格以外的字符都要打印
                if (str.charAt(i) != ' ' && str.charAt(i) != '"') {
                    System.out.print(str.charAt(i));
                }
                //双引号中的空格需要打印
                if (str.charAt(i) == ' ' && flag == 0) {
                    System.out.print(str.charAt(i));
                }
                双引号外碰到空格，需要换行
                if (str.charAt(i) == ' ' && flag == 1) {
                    System.out.println();
                }
            }
    
        }
    }

## 第二题 ##

### 题目描述： ###

> [刷题点这里][Link 2]![64ca15affaad43eaab8f5a0bc8cb42aa.png][]
> 
> ### 描述 ###
> 
> 小易来到了一条石板路前，每块石板上从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

### 解题分析： ###

> 【此题用到了[动态规划][Link 3]，我会准备专门的文章去讲解这类题的解法，[关注我][Link 4]一起手撕动态规划~~[关注我][Link 4]】
> 
> 题目的意思是从N开始，最少需要累加几步可以变成指定的数字M，每次累加的值为当前值的一个约数
> 
> ![d1cd360c27a14b8eb8a9b0be6cb60bc9.png][]
> 
> 【解题思路】：  
> 将1 - M个石板看做一个结果数组step，每个step\[i\]储存着从起点到这一步最小的步数，其中0为不能到达。 从起点开始对step进行遍历，先求i的所有约数（即从step\[i\]能走的步数），然后更新那几个能到达的位置的最小步数。如果不能到达则更新为此时位置的最小步数 + 1，如果是能到达的就更新为min（已记录的最小步数，此处的最小步数 + 1）），遍历一遍后得到结果。
> 
> 一：动归五部曲分析题目:
> 
> 1、step数组的含义:
> 
> step\[i\]储存着从起点到这一步最小的步数
> 
> 2、确定递推公式  
> step\[i+j\]=Math.min(step\[i+j\],step\[i\]+1)  
> 或 step\[i+j\]=step\[i\]+1;  
> 
> 
> 3、dp数组如何初始化
> 
> step\[i\]=Integer.MAX\_VALUE; 初始化为最大值，方便后续更新
> 
> 4、确定遍历顺序
> 
> 从前往后顺序遍历， for(int i=n;i<m;i++)
> 
> 5、举例推导dp数组
> 
> 如图上图所示的蓝色框里的n，（这里我就不单独写出来了）
> 
> 二、注意：
> 
> 1.约数的求解方法：
> 
> eg：12的约数
> 
> 12 % i = 0 ，i 就是12的一个约数
> 
>     for(int i=2;i*i<=num;i++){
>         if(num%i==0){
>                 list.add(i);
>             if(num/i!=i){
>                 list.add(num/i);
>                     }
>             }
>     }
> 
> i 从 2 开始，是因为题目要求除了1和本身的约数
> 
> i \*i <= num，是因为大于 根号下 num的数 ，都不可能被num整除
> 
> 2.数组step存的是i位置最少需要跳跃的步数,
> 
> 有两种情况:
> 
> 当step\[i+j\]!=Integer.MAX\_VALUE时,有不同的走法,取最小值更新step
> 
> 达到step\[i+j\]==Integer.MAX\_VALUE)时,再原来的最小步数上再走一步
> 
>     if(i+j<=m && step[i+j]!=Integer.MAX_VALUE){
>                         step[i+j]=Math.min(step[i+j],step[i]+1);
>                     }else if(i+j<=m){
>                         step[i+j]=step[i]+1;
>                     }

### 代码实现： ###

import java.util.Scanner;
    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();
            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; i++) {
                //当步数等于最大值的时候说明没有走这一步,直接跳过
                if (step[i] == Integer.MAX_VALUE) {
                    continue;
                }
                
     // 求i的约数
                List<Integer> list = div(i);
                //遍历每个踩到的点的约数
                for (int j : list) {
    //j代表此时我们一步可以条几个台阶
    
                    if (i + j <= m && step[i + j] != Integer.MAX_VALUE) {
         //在跳到i+j位置的步数和跳到i的步数加1,之间取最小值,存到step数组中
                        step[i + j] = Math.min(step[i + j], step[i] + 1);
                    } else if (i + j <= m) {
                        
                        step[i + j] = step[i] + 1;
                    }
                }
            }
    
    
            if (step[m] == Integer.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(step[m]);
            }
        } 
    
        //求约数的方法
        public static List <Integer> div(int num) {
            List<Integer> list = new ArrayList<>();
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    list.add(i);
                    if (num / i != i) {
                        list.add(num / i);
                    }
                }
            } 
            return list;
    
        }
    }

[Link 1]: https://www.nowcoder.com/practice/668603dc307e4ef4bb07bcd0615ea677?tpId=37&&tqId=21%20297&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
[88841e76141644419d85f18e1e3cc5ce.png]: https://img-blog.csdnimg.cn/88841e76141644419d85f18e1e3cc5ce.png
[Link 2]: https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8?tpId=85&&tqId=29%20852&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
[64ca15affaad43eaab8f5a0bc8cb42aa.png]: https://img-blog.csdnimg.cn/64ca15affaad43eaab8f5a0bc8cb42aa.png
[Link 3]: http://t.csdn.cn/8J6mQ
[Link 4]: https://blog.csdn.net/qq_48584557?type=blog
[d1cd360c27a14b8eb8a9b0be6cb60bc9.png]: https://img-blog.csdnimg.cn/d1cd360c27a14b8eb8a9b0be6cb60bc9.png