【Java版oj】day33剪花布条、客似云来

喜欢ヅ旅行 2024-03-23 11:20 58阅读 0赞

**目录**

一、剪花布条

（1）原题再现

（2）问题分析

（3）完整代码

二、客似云来

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、剪花布条 ##
> 
> ### （1）原题再现 ###
> 
> [剪花布条\_\_牛客网][Link 1]  
> 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
> 
> **输入描述:**
> 
> 输入包含多组数据。
> 
> 每组数据包含两个字符串s,t，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。
> 
> **输出描述:**
> 
> 对应每组输入，输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就输出0，每个结果占一行。
> 
> 示例1
> 
> 输入
> 
> abcde a3
> 
> aaaaaa aa
> 
> 输出
> 
> 0
> 
> 3
> 
> ### （2）问题分析 ###
> 
> 这道题可以用快慢指针，如果快慢指针指向的字符串中包含目标字符串，则将计数+1，然后改变快慢指针的位置，前面寻找过的部分不再寻找。如果不包含目标字符串，就将慢指针往后移动。
> 
> ### （3）完整代码 ###
> 
>     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(); //小饰条
>                 int fast = 0, slow = 0; //快慢指针
>                 int count = 0;
>                 for (int i = 0; i < str1.length(); i++) {
>                     if (str1.substring(slow, fast + 1).contains(str2)) {
>                         count++;
>                         slow = fast +
>                                1; //开始新的寻找，往后继续寻找,前面找过的部分不要
>                         fast++;
>                     } else {
>                         fast++;//往后继续寻找
>                     }
>                 }
>                 System.out.println(count);
>             }
>         }
>     }
> 
> ![1d3ebc26b3054e46860940c49a5ddaf2.png][]

> ## 二、客似云来 ##
> 
> ### （1）原题再现 ###
> 
> [客似云来\_\_牛客网][Link 2]
> 
> NowCoder开了一家早餐店，这家店的客人都有个奇怪的癖好：他们只要来这家店吃过一次早餐，就会每天都过来；并且，所有人在这家店吃了两天早餐后，接下来每天都会带一位新朋友一起来品尝。  
> 于是，这家店的客人从最初一个人发展成浩浩荡荡成百上千人：1、1、2、3、5……  
> 现在，NowCoder想请你帮忙统计一下，某一段时间范围那他总共卖出多少份早餐（假设每位客人只吃一份早餐）。
> 
> **输入描述:**
> 
> 测试数据包括多组。
> 
> 每组数据包含两个整数from和to(1≤from≤to≤80)，分别代表开店的第from天和第to天。
> 
> **输出描述:**
> 
> 对应每一组输入，输出从from到to这些天里（包含from和to两天），需要做多少份早餐。
> 
> ### （2）问题分析 ###
> 
> 这道题就是斐波那契求和，有两个注意点。
> 
> 第一点不能超过数据范围，所以我们使用long类型。
> 
> 第二点不能超过运行时间，运行时间很小，肯定不能用递归。所以用一个数组直接保存所有需要的斐波那契数。因为是循环输入，如果我们每次在循环里面都建立一个数组，最后总时间就会发生超时错误。所有我们在输入循环外面建一个数组即可。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     /*
>     *斐波那契凤尾
>     */
>     public class Main {
>         public static long[] fibs = new long[100001];
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>     
>             //生成fib
>             fibs[0] = 1;
>             fibs[1] = 1;
>             int flag = 0;
>             for (int i = 2; i < fibs.length; i++) {
>                 long ret = fibs[i - 1] + fibs[i - 2];
>                 fibs[i] = ret % 1000000;
>                 if (flag == 0 && ret >= 1000000) flag = i;
>             }
>     
>             while (sc.hasNextInt()) {
>                 int n = sc.nextInt();
>                 if (n < flag) System.out.println(fibs[n]);
>                 else System.out.printf("%06d\n", fibs[n]);
>             }
>         }
>     }
> 
> ![4bdeeb56839f44f1a37f811090bb0334.png][]

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

![a7ff6ee58ab244cd9ebcc6ee953df6ec.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/1046cd038f7a4b04b2b77b415973de1c
[1d3ebc26b3054e46860940c49a5ddaf2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c0bdf10a59c0494a8a3c0dffefe2974d.png
[Link 2]: https://www.nowcoder.com/questionTerminal/3549ff22ae2c4da4890e9ad0ccb6150d
[4bdeeb56839f44f1a37f811090bb0334.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/dca81645cd704b568b8399e559c1c178.png
[a7ff6ee58ab244cd9ebcc6ee953df6ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/84a9037b9fe64f2a81ef6d5d2baca28a.png