Day2--每日一练

• 🍁 个人主页：爱编程的Tom
• 💫 本篇博文收录专栏：每日一练-算法篇
• 👉 目前其它专栏：c系列小游戏     c语言系列--万物的开始_  Java专栏等              
• 🎉 欢迎 👍点赞✍评论⭐收藏💖三连支持一下博主🤞
• 🧨现在的沉淀就是对未来的铺垫🎨 

前言

今天的题目开始上难度了，我只能说，多练习多练习，任重而道远……

今日题目：1.牛牛的快递问题 （1kg以内20，超出每kg1元,不足按1kg算，加急5元）

                  2.最短花费爬楼梯问题---动态规划

                  3.两个字符串在一个字符数组之间的最小距离 -- 贪心算法

题目一 

题目描述：牛牛正在寄快递，他了解到快递在 1kg 以内的按起步价 20 元计算，超出部分按每 kg 1元计算，不足 1kg 部分按 1kg计算。如果加急的话要额外付五元，请问牛牛总共要支付多少快递费
输入描述：
第一行输入一个单精度浮点数 a 和一个字符 b ，a 表示牛牛要寄的快递的重量，b表示牛牛是否选择加急，‘y’ 表示加急 ，‘n’ 表示不加急。
输出描述：
输出牛牛总共要支付的快递费用

先开始尝试用if循环语句，发现只通过83.33%的测试用例，代码如下：

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double a = scanner.nextDouble();
        char b = scanner.next().charAt(0);
        System.out.println(offer(a,b));

    }
    public static int offer(double a, char b) {
        int ret = 20;

        if (a <= 1 && b == 'y') {
            if (a == 0) {
                return 0;
            }else {
                int m = ret + 5;
                return m;
            }
        } else if (a > 1 && b == 'y') {
            int n = ret+((int)a)+5;
            return n;
        }else if(a <= 1 && b == 'n') {
            if (a == 0) {
                return 0;
            }else {
                int c = ret;
                return c;
            }
        }else {
            int p = ret + (int) a;
            return p;
        }
    }

 后来发现问题出现在（int)a这里，而且设置较多的临时变量，导致代码繁琐，后面更换思路

重写代码如下：（完美通过测试用例）

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double a = scanner.nextDouble();
        char b = scanner.next().charAt(0);
        System.out.println(offer1(a,b));
    }
    public static int offer1(double a, char b) {
        int ret = 0;
        if (a <= 1) {
            ret = 20;
        }else {
            ret = 20 + (int) a;
        }
        if (b == 'y') {
            ret += 5;
        }
        return ret;
    }

题目二 

题目描述：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯

请你计算并返回达到楼梯顶部的最低花费。

解决思路：一看此题，典型的动态规划问题，我们需要找到该题的状态转移方程，由题可知，通过最后逆向思维来看，我们可以由i-1到达顶楼，也可由i-2到顶楼，此时我们使用一个dp数组来存储到达该阶梯所需要花费的费用，cost数组表示由该阶梯到达顶楼的花费，最后再把二者相加。

我们需要两者之间的最小值，即可得;

状态转移方程：dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

代码如下：（通过全部测试用例）

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] cost = new int[n];
        int[] dp = new int[n+1];

        for (int i = 0; i < n; i++) {
            cost[i] = sc.nextInt();
        }
        for (int i = 2; i <= n ; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        System.out.println(dp[n]);
    }

题目三 

题目描述：给定一个字符串数组strs，再给定两个字符串str1和str2，返回strs中str1与str2的最小距离，如果str1或str2为null，或不在strs中，返回-1。 

初看此题，没有头绪，想过用暴力法解决，但双重for循环会导致题目超时，此时换一种解题思路，可以使用两个变量来标记str1和str2的相对位置，通过一次遍历，得出结果。

解题思路：通过设置两个变量prev1，prev2来标记str1和str2的初始位置，我们可以设置为-1，通过for循环，找到str1的第一次位置，同时向该位置的左边寻找str2，即prev2是否不为-1，此时更新ret(设置为最小距离的变量)的值为i-prev2,并更新prev1的值。另一半也是如此，找到str2的值，向左寻找str1即prev1不为-1的位置，更新ret的值为i-prev1;同时将prev2指向当前已经找到的str2的值，最后在输出ret即可。

代码如下:(代码通过全部测试用例，注：此处初始化ret为最大值的小技巧，取最小值不影响结果）

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str1 = sc.next();
        String str2 = sc.next();
        int prev1 = -1;
        int prev2 = -1;
        int ret = 0x3f3f3f3f;
        String[] ch = new String[n];
        for (int i = 0; i < n; i++) {
            ch[i] = sc.next();
            if (ch[i].equals(str1)) {
                if (prev2 != -1) {
                    ret = Math.min(ret,(i-prev2));

                }
                prev1 = i ;
            }else if (ch[i].equals(str2)){
                if (prev1 != -1) {
                    ret = Math.min(ret,(i-prev1));
                }
                prev2 = i;
            }
        }
        System.out.println(ret == 0x3f3f3f3f ? -1 : ret);
    }