【Java牛客刷题第四期】——想让自己算法大幅度提升，这一期你一定不要错过

题目描述:
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入描述:
输入包含多组数据。

每组数据包含两个字符串s,t，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。


输出描述:
对应每组输入，输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就输出0，每个结果占一行。
示例1
输入
abcde a3
aaaaaa aa
输出
0
3

链接：牛客链接

解题思路;
题目简单描述下，就是在S串中，T串整体出现了多少次。

代码如下:

import java.util.Scanner;

/**
 *
 *减花布条
 **/
public class Demo5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            String t = sc.nextLine();
            System.out.println(cut(s,t));
        }
    }
    public static int cut(String s,String t) {
        int i = s.indexOf(t);//返回t首次出现再s中的位置
        if(i == -1) {
            return 0;
        }
        return 1 + cut(s.substring(i + t.length()),t);
    }
}

题目描述:
NowCoder每天要给许多客户写电子邮件。正如你所知，如果一封邮件中包含多个收件人，收件人姓名之间会用一个逗号和空格隔开；如果收件人姓名也包含空格或逗号，则姓名需要用双引号包含。.现在给你一组收件人姓名，请你帮他生成相应的收件人列表。

输入描述:
输入包含多组数据。

每组数据的第一行是一个整数n (1≤n≤128)，表示后面有n个姓名。

紧接着n行，每一行包含一个收件人的姓名。姓名长度不超过16个字符。


输出描述:
对应每一组输入，输出一行收件人列表。
示例1
输入
3
Joe
Quan, William
Letendre,Bruce
2
Leon
Kewell
输出
Joe, "Quan, William", "Letendre,Bruce"
Leon, Kewell

链接：牛客链接

解题思路:
基础的字符串处理问题,题干非常清晰

先接受到一个数字,代表接下来是多少数据逐个接收每个名字,如果名字中没有','或者' '则直接初出,否者在改名字前后拼接"'\"再输出除最后一个名字外,每个名字之后都有一个","注意用例处理完换行

代码如下:

import java.util.Scanner;

/**
 * 牛客 收件人列表
 */
public class Demo6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            sc.nextLine();//改行代码非常关键,将数字所在行之后的内容接收完
            for (int i = 0; i < n; i++) {
                String name = sc.nextLine();
                if(name.contains(",") || name.contains(" ") ) {
                    System.out.print("\"" + name + "\"");
                }else{
                    System.out.print(name);
                }
                //收件人姓名之间用 逗号 和 空格 分开 注意:最后一个位置是没有的
                if(i != n-1) {
                    System.out.print(", ");
                }
            }
            System.out.println();
        }
    }
}

题目描述：
给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。

注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1\le s\le 150≤s≤150 
进阶：时间复杂度：O(n^3)\O(n 3 ) ，空间复杂度：O(n)\O(n) 

输入描述：
输入两个只包含小写字母的字符串

输出描述：
输出一个整数，代表最大公共子串的长度

示例1
输入：
asdfas
werasdfaswer
复制
输出：
6

链接：牛客链接

在之前的刷题笔记当中，这道题也出现过，想了解更多DP题目请点击：【Java刷题特辑第二章】
如果对DP问题解题思路，不够清楚，不知道从何下手请点击：算法篇之动态规划

解题思路：

代码如下：

public class Demo5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            System.out.println(func(str1,str2));
        }
    }
    public static int func(String str1,String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        char[] A = str1.toCharArray();//字符串转字符串数组
        char[] B = str2.toCharArray();
        int max = 0;
        int[][] dp = new int[len1 + 1][len2 +1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if(A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(max < dp[i][j]) {
                    max = dp[i][j];
                }
            }
        }
        return max;
    }
}

题目描述：
我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

输入描述:
输入包含多组数据。

每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。

输出描述:
对应每组输入，输出最长公共子序列的长度。
示例1
输入
abcfbc abfcab
programming contest
abcd mnp
输出
4
2
0

链接：牛客链接

解题思路：

首先，这道题题目要求的是求最长公共子序列（子串可以不连续），而上一道题求公共子串（子串连续），切勿混淆
注意：这道题和上一道题，区别在于 本题 子串不连续，所以我们应该考虑两种情况（思路和上一道题类似）

代码如下：

import java.util.Scanner;

// 牛客 最长公共子序列
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.next();
            String str2 = sc.next();
            System.out.println(func(str1,str2));
        }
    }

    public static int func(String str1,String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] DP = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1 ; i++) {
            for (int j = 1; j <= len2 ; j++) {
                // 如果 arr[i-1] == arr[j-1]
                if(str1.charAt(i-1) == str2.charAt(j-1)) {
                    DP[i][j] = DP[i-1][j-1] + 1;
                }else {
                    // 如果不相等，在 dp[i-1][j] 和 dp[i][j-1 中取最大值
                    DP[i][j] = Math.max(DP[i-1][j],DP[i][j-1]);
                }
            }
        }
        return DP[len1][len2];
    }
}

这里我发现了个 牛客上的 bug 不知道咋回事


如果 最长公共子序列这道题 控制台输入是 sc.nextLine（） 代码通不过 ？？？

题目描述：
今年公司年会的奖品特别给力，但获奖的规矩却很奇葩：

输入描述:
输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）

输出描述:
对应每一组数据，以“xx.xx%”的格式输出发生无人获奖的概率。
示例1
输入
2
输出
50.00%

链接：牛客链接

解题思路：

解这道题之前，我们需要明白 什么时候才算都不获奖？全部都不获奖的概率如何计算？对于 什么时候才算都 不获奖，当然是所有人都拿到了别人的名字，没有拿到自己的名字

全部都不获奖的概率 必定是由 n个人都拿错的情况种数 除 n个人都拿出的所有排列情况数

推导：

假设a的名字没有被a拿到，其他n - 1个人都有可能拿到，即有n - 1种情况。假设b拿到了a的名字，那么对于b的名字有两种情况

最终得出公式n人都不获奖的概率h(n) = (n - 1) * (f(n - 1) + f(n - 2)) / (n!).

错排问题举例：

用A、B、C……表示写着ｎ位友人名字的信封，a、b、c……表示ｎ份相应的写好的信纸。把错装的总数为记作D(n)。假设把ａ错装进Ｂ里了，包含着这个错误的一切错装法分两类：

总之在ａ装入B的错误之下，共有错装法D(n－2)＋D(n－1)种。

a装入C，装入D……的n－2种错误之下，同样都有D(n－1)＋D(n－2)种错装法，因此D(n)＝(n－1)[D(n－1)＋D(n－2)] --------------->D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地，D(1) = 0, D(2) = 1.

所以这道题的总体思路：

错排的递推公式是：D(n) = (n - 1) [D(n - 2) + D(n - 1)]，也就是第n项为n - 1倍的前两项和。通过这个递推公式可以得到在总数为n的时候，错排的可能性一共有多少种。那么要求错排的概率，我们还需要另一个数值，就是当总数为n的时候，所有的排列组合一共有多少种，那么根据排列组合，肯定是使用
的公式来求，也就是n的阶乘。所以结果很简单，就是用公式求出第n项的错排种类，和n的阶乘，然后两者一除，就是概率了。

代码如下：

import java.util.Scanner;

public class Demo3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // p(无人获奖) = 都没获奖的情况/n个人抽取的情况
        // 无一人获奖的 情况 D（n）

        long[] a = new long[21]; //错排特殊情况  D[1] = 0 D[2] =1
        a[0] = a[1] = 0;
        a[2] = 1;

        long[] b = new long[21]; // 阶乘
        b[0] = b[1] = 1;
        b[2] = 2;
        // 算N错排数据和阶乘
        for (int i = 3; i <= 20 ; i++) {
            a[i] = (i-1)*(a[i-1] + a[i-2]);
            b[i] = b[i-1] * i;
        }
        while (sc.hasNext()) {
            int n  = sc.nextInt();
            System.out.printf("%.2f%%\n",100.0*a[n]/b[n]);
        }

    }
}

题目描述：
NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？即没有人收到属于自己的邮件。

输入描述:
输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。

输出描述:
对应每一组数据，输出一个正整数，表示无人收到自己邮件的种数。
示例1
输入
2
3
输出
1
2

链接：牛客链接

解题思路：

这道题和上一道思路一模一样，也是典型的错排问题，这道题，根据题目意思，要求我们去求，所有人收到错误的邮件的情况，如何推导，这里不在赘述

代码如下：

import java.util.Scanner;

// 牛客 发邮件 错排问题
public class Demo4 {
    public static void main(String[] args) {
        //错排情况
        long[] D = new long[21];
        D[0] = D[1] = 0;
        D[2] = 1;
        for (int i = 3; i <= 20 ; i++) {
            D[i] = (i-1) * (D[i-1] + D[i-2]);
        }

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(D[n]);
        }
    }
}

题目描述：
Web系统通常会频繁地访问数据库，如果每次访问都创建新连接，性能会很差。为了提高性能，架构师决定复用已经创建的连接。当收到请求，并且连接池中没有剩余可用的连接时，系统会创建一个新连接，当请求处理完成时该连接会被放入连接池中，供后续请求使用。现在提供你处理请求的日志，请你分析一下连接池最多需要创建多少个连接。

输入描述:
输入包含多组数据，每组数据第一行包含一个正整数n（1≤n≤1000），表示请求的数量。

紧接着n行，每行包含一个请求编号id（A、B、C……、Z）和 *** 作（connect或disconnect）。

输出描述:
对应每一组数据，输出连接池最多需要创建多少个连接。
示例1
输入
6
A connect
A disconnect
B connect
C connect
B disconnect
C disconnect
输出
2

链接：牛客链接

解题思路：

循环接收每组用例，对于每组用例进行如下 *** 作

依次获取每个状态，如果该状态是connect，则将其id插入到set中，否则删除该id获取从刚开始到目前set中的最大值输出结果

代码如下：

import java.util.*;
// 牛客 数据库连接池
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n  = sc.nextInt();
            int max = 0;
            // 每一行有 n条 记录
            Set s = new HashSet<>();
            while ( n != 0) {
                String id,record;
                id = sc.next();
                record = sc.next();
                // 如果是改记录是链接，将其id插入到set中，否则删除
                if(record.equals("connect")) {
                    s.add(id);
                }else {
                    s.remove(id);
                }
                max = Math.max(max,s.size());
                n--;
            }
            System.out.println(max);
        }
    }
}

题目描述：
工作中，每当要部署一台新机器的时候，就意味着有一堆目录需要创建。例如要创建目录“/usr/local/bin”，就需要此次创建“/usr”、“/usr/local”以及“/usr/local/bin”。好在，Linux下mkdir提供了强大的“-p”选项，只要一条命令“mkdir -p /usr/local/bin”就能自动创建需要的上级目录。现在给你一些需要创建的文件夹目录，请你帮忙生成相应的“mkdir -p”命令。

输入描述:
输入包含多组数据。

每组数据第一行为一个正整数n(1≤n≤1024)。

紧接着n行，每行包含一个待创建的目录名，目录名仅由数字和字母组成，长度不超过200个字符。

输出描述:
对应每一组数据，输出相应的、按照字典顺序排序的“mkdir -p”命令。

每组数据之后输出一个空行作为分隔。
示例1
输入
3
/a
/a/b
/a/b/c
3
/usr/local/bin
/usr/bin
/usr/local/share/bin
输出
mkdir -p /a/b/c
mkdir -p /usr/bin
mkdir -p /usr/local/bin
mkdir -p /usr/local/share/bin

链接：牛客链接

解题思路：

循环接收获取每组用例，对于每组用例进行如下 *** 作：

对该组用例按照字典顺序排序将该数组用例中相等的或者前一个是后一个子串的路径剔除输入结果并换行

注意：
如果目录结构为如下：/ab 为 二级目录 /a/b为三级目录，我们需要判断 /ab的结尾是不是‘/’

/a
/ab
/a/b

代码如下：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            // 接收 n 条路径
            String[] path = new String[n];
            for (int i = 0; i < n; i++) {
                path[i] = sc.next();
            }
            // 对 path中的 n条路径进行排序
            Arrays.sort(path);
            // 将数组中：相等的元素一级前一个是后一个淄川的字符串剔除
            // 注意：此处采用标记法删除
            boolean[] flag = new boolean[n];
            for (int i = 0; i < n - 1; i++) {
                // 相同目录
                if(path[i].equals(path[i+1])) {
                    flag[i] = true;//剔除
                }else if(path[i].length() < path[i+1].length() &&
                path[i+1].contains(path[i]) && path[i+1].charAt(path[i].length())=='/') {
                    flag[i] = true;//剔除
                }
            }
            //输出
            for (int i = 0; i < n; i++) {
                if(!flag[i]) {
                    System.out.println("mkdir -p " +path[i]);
                }
            }
            //给空行
            System.out.println();
        }
    }
}

“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”

如果有错误❌,欢迎指正哟😋

🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉