【Java版oj】day21小易的升级之路、找出字符串中第一个只出现一次的字符

忘是亡心i 2024-03-24 13:22 30阅读 0赞

**目录**

一、小易的升级之路

（1）原题再现

（2）问题分析

（3）完整代码

二、找出字符串中第一个只出现一次的字符

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、小易的升级之路 ##
> 
> ### （1）原题再现 ###
> 
> [小易的升级之路\_\_牛客网][Link 1]
> 
> 小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3...bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?
> 
> **输入描述:**
> 
> 对于每组数据,第一行是两个整数n(1≤n<100000)表示怪物的数量和a表示小易的初始能力值. 然后输入n行，每行整数,b1,b2...bn(1≤bi≤n)表示每个怪物的防御力
> 
> **输出描述:**
> 
> 对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值
> 
> **示例1**
> 
> 输入
> 
> 3 50
> 
> 50 105 200
> 
> 5 20
> 
> 30 20 15 40 100
> 
> 输出
> 
> 110
> 
> 205
> 
> ### （2）问题分析 ###
> 
> 这题很简单只需要找出两个数的最大公因数，根据题意分情况讨论即可。找出两数中较小的数，从最小的数开始每次减一，大数和小数同时能整除一个数，即跳出循环，找到最大公因数。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     
>     /*
>      * 小易的升级之路
>      */
>     
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNextInt()) {
>                 int monsterNum = sc.nextInt();
>                 int cur = sc.nextInt();
>                 for (int i = 0; i < monsterNum; i++) {
>                     int energe = sc.nextInt();
>                     if (energe <= cur) {
>                         cur += energe;
>                     } else {
>                         cur += largerest(cur, energe);
>                     }
>                 }
>                 System.out.println(cur);
>             }
>         }
>         public static int largerest(int a, int b) {
>             int large = Math.max(a, b);
>             int small = Math.min(a, b);
>             int i = 0;
>             for (i = small; i >= 1; i--) {
>                 if (large % i == 0 && small % i == 0) {
>                     break;
>                 }
>             }
>             return i;
>         }
>     }
> 
> ![7e25d4e078084b899c0dad88790b7762.png][]

> ## 二、找出字符串中第一个只出现一次的字符 ##
> 
> ### （1）原题再现 ###
> 
> [找出字符串中第一个只出现一次的字符\_牛客题霸\_牛客网][Link 2]
> 
> **描述**
> 
> 找出字符串中第一个只出现一次的字符
> 
> **输入描述：**
> 
> 输入一个非空字符串
> 
> **输出描述：**
> 
> 输出第一个只出现一次的字符，如果不存在输出-1
> 
> **示例1**
> 
> 输入：
> 
> asdfasdfo
> 
> 输出：
> 
> o
> 
> ### （2）问题分析 ###
> 
> 定义两个链表，一个用来存放key关键字，一个用来存放value值。key表示每个不一样的字符，value表示该字符出现的次数。**如果字符不在链表中，代表第一次出现，count（粗出现的次数为1）。****如果字符在链表中出现，我们需要取出对应位置的value即count，count+1。**
> 
> **可能有人要问为什么不直接用Map集合呢，键值对直接就有key、value啊？**
> 
>  **因为题目要求是输出第一个只出现一次的字符**，如果我们使用Map的话，他是有序的，内部会自动帮我们把字符按照字典序排序，而我们输入的字符串是无序的，如此一来就找不到谁是第一个只出现一次的字符。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     /*
>      * 找出字符串中第一个只出现一次字符
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner (System.in);
>             String str = sc.nextLine();
>     
>             List<Character>key = new LinkedList<>();
>             List<Integer>value = new LinkedList<>();
>             for (int i = 0; i < str.length(); i++) {
>                 int count = 1;
>                 if (!key.contains(str.charAt(i))) {
>                     key.add(str.charAt(i));
>                     value.add(count);
>                 } else {
>                     int index = key.indexOf(str.charAt(i));
>                     count = value.get(index) + 1;
>                     value.set(index, count);
>                 }
>             }
>     
>             if (!value.contains(1)) {
>                 System.out.println(-1);
>             } else {
>                 for (int i = 0; i < key.size(); i++) {
>                     if (value.get(i) == 1) {
>                         System.out.println(key.get(i));
>                         break;
>                     }
>                 }
>             }
>         }
>     }
> 
> ![40627158fe8c44c6bf8a81fe4a2945e0.png][]

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

![50ea647f766340d98b7520dec4f09ebf.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/fe6c73cb899c4fe1bdd773f8d3b42c3d?toCommentId=15633488
[7e25d4e078084b899c0dad88790b7762.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/392890b7d3584a5da5d0531fa25930b9.png
[Link 2]: https://www.nowcoder.com/practice/e896d0f82f1246a3aa7b232ce38029d4?tpId=37&&tqId=21282&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
[40627158fe8c44c6bf8a81fe4a2945e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/070196b13d0441f2b450dd801012c4ab.png
[50ea647f766340d98b7520dec4f09ebf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/b0b4f18dd4194a148e66339f41b146dd.png