ftp 迁移 网站,丽水企业网站开发企业,建设产品信息网站,网站建设个人网银目录 专栏导读一、题目描述二、输入描述三、输出描述四、输入示例1、输入#xff1a;2、输出3、说明 五、解题思路1、核心思想#xff1a;2、核心算法是构建一个map#xff1a; 六、Java算法源码七、效果展示1、输入2、输出3、说明4、没有移除后再次拼接的情况#xff0c;改… 目录 专栏导读一、题目描述二、输入描述三、输出描述四、输入示例1、输入2、输出3、说明 五、解题思路1、核心思想2、核心算法是构建一个map 六、Java算法源码七、效果展示1、输入2、输出3、说明4、没有移除后再次拼接的情况改造一下 华为OD机试 2023B卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题A卷B卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
单词接龙的规则是
可用于接龙的单词首字母必须要与前一个单词的尾字母相同当存在多个首字母相同的单词时取长度最长的单词如果长度也相等则取字典序最小的单词已经参与接龙的单词不能重复使用。
现给定一组全部由小写字母组成单词数组并指定其中的一个单词作为起始单词进行单词接龙请输出最长的单词串单词串是单词拼接而成中间没有空格。
二、输入描述
输入的第一行为一个非负整数表示起始单词在数组中的索引K0 K N 输入的第二行为一个非负整数表示单词的个数N接下来的N行分别表示单词数组中的单词。
备注
单词个数N的取值范围为[1, 20]单个单词的长度的取值范围为[1, 30]
三、输出描述
输出一个字符串表示最终拼接的单词串。
四、输入示例
1、输入
0 6 word dd da dc dword d
2、输出
worddwordda
3、说明
先确定起始单词word再接以d开头的且长度最长的单词dword剩余以d开头且长度最长的有dd、da、dc则取字典序最小的da所以最后输出worddwordda。
五、解题思路
1、核心思想
可用于接龙的单词首字母必须要与前一个单词的尾字母相同当存在多个首字母相同的单词时取长度最长的单词如果长度也相等则取字典序最小的单词已经参与接龙的单词不能重复使用。
2、核心算法是构建一个map
key每个字符串的第一个字符value以key开头的字符串并按字符串长度、字典顺序排序
如果接龙字符串builder的末字符在map中存在表示有以builder末字符开头的字符串继续循环获取以“末字符”开头的字符串集合获取排序后的第一个添加到接龙字符串builder在map中移除已经加入接龙的字符串如果此开头的字符串还有其他字符串再加入map否则移除获取接龙字符串builder末字符进行下次判断输出接龙字符串builder
六、Java算法源码
package com.guor.od;import java.util.*;public class OdTest03 {/*** 单词接龙* 核心思想** 1. 可用于接龙的单词首字母必须要与前一个单词的尾字母相同* 2. 当存在多个首字母相同的单词时取长度最长的单词* 3. 如果长度也相等则取字典序最小的单词* 4. 已经参与接龙的单词不能重复使用。*/public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 起始单词在数组中的索引Kint K Integer.parseInt(scanner.nextLine());// 单词的个数Nint N Integer.parseInt(scanner.nextLine());// 接下来的N行分别表示单词数组中的单词ListString wordList new ArrayList();for (int i 0; i N; i) {wordList.add(scanner.nextLine());}// 获取第一个单词String first wordList.get(K);// 已经参与接龙的单词不能重复使用故移除wordList.remove(K);// 最终拼接的单词串StringBuilder builder new StringBuilder();builder.append(first);/*** key每个字符串的第一个字符* value以key开头的字符串并按字符串长度排序*/MapString,ListString listMap getListMap(wordList);System.out.println(listMap);// 获取接龙字符串的最后一个字符作为待接龙字符串的第一个字符String last builder.substring(builder.length() - 1);// 如果接龙字符串builder的末字符在map中存在表示有以builder末字符开头的字符串继续循环while (listMap.containsKey(last)) {// 获取以“末字符”开头的字符串集合ListString tempList listMap.get(last);// 获取排序后的第一个String firstWord tempList.get(0);// 添加到接龙字符串builderbuilder.append(firstWord);// 在map中移除已经加入接龙的字符串tempList.remove(firstWord);// 如果此开头的字符串还有其他字符串再加入map否则移除if(tempList.size()0){listMap.put(last, tempList);}else {listMap.remove(last);}// 获取接龙字符串builder末字符进行下次判断last builder.substring(builder.length() - 1);}// 输出接龙字符串builderSystem.out.println(builder);}/*** key每个字符串的第一个字符* value以key开头的字符串并按字符串长度排序*/public static MapString,ListString getListMap(ListString wordList) {MapString,ListString listMap new HashMap();for(String word : wordList){String first String.valueOf(word.charAt(0));ListString list null;if(listMap.containsKey(first)){list listMap.get(first);list.add(word);sortList(list);}else{list new ArrayList();list.add(word);}listMap.put(first,list);}return listMap;}/*** 排序规则* 1. 当存在多个首字母相同的单词时取长度最长的单词* 2. 如果长度也相等则取字典序最小的单词*/private static void sortList(ListString wordList){wordList.sort(new ComparatorString() {Overridepublic int compare(String o1, String o2) {if(o1.length()o2.length()){return -1;}else if(o1.length()o2.length()){return 1;}else{// 字典排序return o1.compareTo(o2);}}});}
}七、效果展示
1、输入
0 11 nezha love loves learn learning java j2ee javas appl goj gpj
2、输出
nezhaappllearninggojjavas
3、说明
构建一个mapkey每个字符串的第一个字符value以key开头的字符串并按照字符串长度、字典顺序排序
{a[appl], g[goj, gpj], j[javas, j2ee, java], l[learning, learn, loves, love]}
以第1个字符串开头nezhaa开头的只有appl拼接appl拼接为nezhaappl以l开头的有[learning, learn, loves, love]取第1个字符串learning拼接为nezhaappllearning以g开头的有[goj, gpj]取第一个字符串goj拼接为nezhaappllearninggoj以j开头的有[javas, j2ee, java]取第一个字符串javas拼接位nezhaappllearninggojjavas
4、没有移除后再次拼接的情况改造一下
0 11 nezha love loves learn learning java j2ee javasj appl goj gpj
输出
{a[appl], g[goj, gpj], j[javasj, j2ee, java], l[learning, learn, loves, love]} nezhaappllearninggojjavasjj2ee 下一篇华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分 考生抽中题】
本文收录于华为OD机试JAVA真题A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
