2022年5月31日大约 44 分钟约 13260 字
牛客网-华为机试
HJ1 字符串最后一个单词的长度
描述
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于 5000。（注：字符串末尾不以空格为结尾）
输入描述
输入一行，代表要计算的字符串，非空，长度小于 5000。
输出描述
输出一个整数，表示输入字符串最后一个单词的长度。
示例 1
输入：
hello nowcoder输出：
8说明：
最后一个单词为nowcoder，长度为8代码
- 方法一: 系统函数
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String[] s = str.split(" "); //正则表达式实用性更强( str.split("\\s+"))
int length = s[s.length - 1].length();
System.out.println(length);
}
}- 方法二: 反过来打印
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int length = str.length();
int count = 0;
for (int i = length - 1; i >= 0; i--) {
if (str.charAt(i)==' ') { // 或者 if (str.substring(i, i + 1).equals(" ")) {
break;
}
count++;
}
System.out.println(count);
}
}HJ2 计算某字符出现次数
描述
写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
数据范围： 1 \le n \le 1000 \1≤n≤1000
输入描述
第一行输入一个由字母和数字以及空格组成的字符串，第二行输入一个字符。
输出描述
输出输入字符串中含有该字符的个数。（不区分大小写字母）
示例 1
输入：
ABCabc
A输出：
2代码
- 一、
/**
* 二：计算某字符出现的次数
* 1.接收输入的第一个字符串，并转换为小写。（完整字符串str1）
* 2.接收输入的第二个字符串，并转换为小写。（单个字符str2）
* 3.将str1中的str2字符串全部替换为 “”
* 4.用str1.length-str2.length = 出现次数
*/
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
// 完整字符串
String str1 = input.nextLine().toLowerCase();
// 单个字符串
String str2 = input.nextLine().toLowerCase();
// 完整字符的长度-单个字符长度 = 出现的次数
int num = str1.length() - str1.replaceAll(str2,"").length();
System.out.println(num);
}
}- 二、
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
String character = scanner.nextLine();
Pattern compile = Pattern.compile(character, Pattern.CASE_INSENSITIVE);
Matcher matcher = compile.matcher(string);
int count = 0;
while (matcher.find()) {
count++;
}
System.out.println(count);
}
}HJ3 明明的随机数
描述
明明生成了 NN个 1 到 500 之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。
数据范围： 1 \le n \le 1000 \1≤n≤1000 ，输入的数字大小满足 1 \le val \le 500 \1≤val≤500
输入描述
第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数，代表明明生成的随机数。 具体格式可以参考下面的"示例"。
输出描述
输出多行，表示输入数据处理后的结果
示例 1
输入：
3
2
2
1输出：
1
2说明：
输入解释：
第一个数字是3，也即这个小样例的N=3，说明用计算机生成了3个1到500之间的随机整数，接下来每行一个随机数字，共3行，也即这3个随机数字为：
2
2
1
所以样例的输出为：
1
2代码
一、
题目有两个要求：
- 去重
- 排序
import java.util.*;
public class Test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//获取个数
int num = sc.nextInt();
//创建TreeSet进行去重排序
TreeSet set = new TreeSet();
//输入
for(int i =0 ; i < num ;i++){
set.add(sc.nextInt());
}
//输出
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}二、
主要的思路就是空间换时间，还有利用数组的下标。
- 创建一个 1001 个数字的数组，在输入一个 1-1000 的数字时将改数组对应下标的值改为 1。
- 然后再从小到大循环数组中值为 1 的下标输出，因为下标本身有序的因此就不用排序。
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int num = scanner.nextInt();
int[] arr = new int[1001];
for (int i = 0; i < num; i++) {
int n = scanner.nextInt();
arr[n] = 1;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i] == 1) {
System.out.println(i);
}
}
}
}HJ4 字符串分隔
描述
•输入一个字符串，请按长度为 8 拆分每个输入字符串并进行输出；
•长度不是 8 整数倍的字符串请在后面补数字 0，空字符串不处理。
输入描述
连续输入字符串(每个字符串长度小于等于 100)
输出描述
依次输出所有分割后的长度为 8 的新字符串
示例 1
输入：
abc输出：
abc00000代码
一、
思路
- 需要输入字符串，用到 Scanner 和 hasNext()。 （1）建立 Scanner sc = new Scanner(System.in); （2）判断有无输入用 sc.hasNext().接收字符串使用 sc.nextLine().
- 一次性接受全部的字符串，对 8 取余，获知需要补 0 的位数。使用 StringBuilder 中的 append()函数进行字符串修改，别忘了 toString()。 字符串缓冲区的建立：StringBuilder sb = new StringBuilder();
- 输出时，截取前 8 位进行输出，并更新字符串。用到 str.substring()函数： （1）str.substring(i)意为截取从字符索引第 i 位到末尾的字符串。 （2）str.substring(i,j)意为截取索引第 i 位到第（j-1）位字符串。包含 i，不包含 j。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String str = sc.nextLine();
StringBuilder sb = new StringBuilder();//牢记字符串缓冲区的建立语法
sb.append(str);//字符串缓冲区的加入
int size = str.length();
int addZero = 8 - size%8;//addzero的可能值包括8
while((addZero > 0)&&(addZero<8)){//注意边界调节，避免addzero=8
sb.append("0");//使用‘’或“”都可
addZero--;
}
String str1 = sb.toString();
while(str1.length()>0){
System.out.println(str1.substring(0,8));
str1 = str1.substring(8);
}
}
}
}二、
/**
*1.输入字符串大于8时，递归截取前8位输入，直至小于8位时进入循环补0
*2.字符串小于8时直接跳到循环补0操作，补满至8位时打印输出
*3.正好等于8位或为空字符串时，直接打印输出
*/
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String s=in.nextLine();
while(s.length()>8){
System.out.println(s.substring(0,8));
s=s.substring(8);
}
while(s.length()<8&&s.length()>0){
s+="0";
}
System.out.println(s);
}
}
}三、
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str;
while (sc.hasNext()) {
str = sc.nextLine();
while (str.length() > 8) {
System.out.println(str.substring(0, 8));
str = str.substring(8);
}
str = str + "00000000";
System.out.println(str.substring(0, 8));
}
}
}HJ5 进制转换
描述
写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。
数据范围：保证结果在 1 \le n \le 2^{31}-1 \1≤n≤231−1
输入描述
输入一个十六进制的数值字符串。
输出描述
输出该数值的十进制字符串。不同组的测试用例用\n 隔开。
示例 1
输入：
0xAA输出：
170代码
一、python3 解法
while True:
try:
print(int(input(),16))
except:
breakwhile True:
try:
number = input()
n = len(number)
dic = {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'A':10,'B':11,'C':12,'D':13,'E':14,'F':15}
final = 0
for i in range(2,n):
final += dic[number[i]]*(16**(n-i-1))
print(final)
except:
break二、Java
- substring(int a,int b)方法可以截断字符串，当只有一个参数时，截取范围是[a,length-1],当有两个参数时，截取范围是[a,b-1]。
- Integer.parseInt(String s,int a)方法可以转换进制，将字符串转换为“a”进制，只有一个参数 s 时，转换为 10 进制。
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
String s = sc.nextLine();
System.out.println(Integer.parseInt(s.substring(2,s.length()),16));
}
}
}import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String str = in.nextLine();
String s1 = str.substring(2);
int a = Integer.valueOf(s1,16);
System.out.println(a);
}
}
}HJ8 合并表记录
描述
数据表记录包含表索引 index 和数值 value（int 范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照 index 值升序进行输出。
提示:
0 <= index <= 11111111
1 <= value <= 100000
输入描述
先输入键值对的个数 n（1 <= n <= 500） 接下来 n 行每行输入成对的 index 和 value 值，以空格隔开
输出描述
输出合并后的键值对（多行）
示例 1
输入：
4
0 1
0 2
1 2
3 4输出：
0 3
1 2
3 4示例 2
输入：
3
0 1
0 2
8 9输出：
0 3
8 9代码
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
TreeMap<Integer, Integer> map = new TreeMap<>(); // 输出结果要求有序！
while(sc.hasNextInt()){
int n = sc.nextInt();
for(int i = 0; i < n; ++i){
int a = sc.nextInt();
int b = sc.nextInt();
map.put(a,map.getOrDefault(a,0) + b);
}
}
for (Integer i : map.keySet()) {
System.out.println(i + " " + map.get(i));
}
}
}import java.util.*;
public class Main {
public static void main(String agv[]) {
Scanner scanner = new Scanner(System.in);
int tableSize = scanner.nextInt();
Map<Integer, Integer> table = new HashMap<>(tableSize);
for (int i = 0; i < tableSize; i++) {
int key = scanner.nextInt();
int value = scanner.nextInt();
if (table.containsKey(key)) {
table.put(key, table.get(key) + value);
} else {
table.put(key, value);
}
}
for (Integer key : table.keySet()) {
System.out.println( key + " " + table.get(key));
}
}
}HJ14 字符串排序
描述
给定 n 个字符串，请对 n 个字符串按照字典序排列。
数据范围： 1 \le n \le 1000 \1≤n≤1000 ，字符串长度满足 1 \le len \le 100 \1≤len≤100
输入描述
输入第一行为一个正整数 n(1≤n≤1000),下面 n 行为 n 个字符串(字符串长度≤100),字符串中只含有大小写字母。
输出描述
数据输出 n 行，输出结果为按照字典序排列的字符串。
示例 1
输入：
9
cap
to
cat
card
two
too
up
boat
boot输出：
boat
boot
cap
card
cat
to
too
two
up只需要按字典排列字符串，可以调用 Arrays.sort API，也可以使用 PriorityQueue，还可以自己实现 Comparator，三种方法测试了一下用时相差不大。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
withPriorityQueue();
}
// 方法一: 调用API Arrays.sort
public static void withArraysAPI() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] ss = new String[n];
for (int i = 0; i < n; i++) {
ss[i] = br.readLine();
}
br.close();
Arrays.sort(ss);
for(int i = 0; i < n; i++) {
System.out.println(ss[i]);
}
}
// 方法二: 使用PriorityQueue
public static void withPriorityQueue() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<String> pq = new PriorityQueue<>();
String s = "";
while ((s = br.readLine()) != null) {
pq.offer(s);
}
br.close();
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
// 方法三: 使用list并自己实现Comparator, 比较能体现算法的思路
public static void withComparator() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<String> list = new ArrayList<>();
String s = "";
while ((s = br.readLine()) != null) {
list.add(s);
}
br.close();
list.sort(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
int i = 0;
while (i < s1.length() && i < s2.length()) {
if (s1.charAt(i) != s2.charAt(i)) {
return (s1.charAt(i) > s2.charAt(i))? 1: -1;
}
i++;
}
if (s1.length() == s2.length()) {
return 0;
} else {
return (s1.length() > s2.length())? 1: -1;
}
}
});
for(int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}HJ20 密码验证合格程序
描述
密码要求:
1.长度超过 8 位
2.包括大小写字母.数字.其它符号,以上四种至少三种
3.不能有长度大于 2 的包含公共元素的子串重复 （注：其他符号不含空格或换行）
数据范围：输入的字符串长度满足 1 \le n \le 100 \1≤n≤100
输入描述
一组字符串。
输出描述
如果符合要求输出：OK，否则输出 NG
示例 1
输入：
021Abc9000
021Abc9Abc1
021ABC9000
021$bc9000复制
输出：
OK
NG
NG
OK题目主要信息
1、检验输入的密码是否合格
2、密码要求如下
长度超过 8 位
密码要求:
1.长度超过 8 位
2.包括大小写字母.数字.其它符号,以上四种至少三种
3.不能有长度大于 2 的不含公共元素的子串重复 （注：其他符号不含空格或换行）
方法一：暴力
具体方法
按照密码的要求，依次遍历验证即可。
1、首先验证长度是否大于 8，不满足直接输出 NG 并继续 2、验证是否包含三种以上的字符 3、验证是否存在重复子串，并且长度大于等于 3 这里主要给出第三步的详解，前两步的直接遍历求解即可。 第三步可以使用类似窗口的方法，因为要求最长重复子串不能大于 2，所以就把窗口的大小设置为 3。
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s;
while((s = bf.readLine())!=null){
//1.长度超过8位
if(s.length() <= 8){
System.out.println("NG");
continue;
}
//2.包括大小写字母.数字.其它符号,以上四种至少三种
int count[] = new int[4];//记录出现个数
for(int i=0;i<s.length();i++){
if(s.charAt(i) >= 'A'&& s.charAt(i)<='Z' ){
count[0] = 1;
}else if(s.charAt(i) >= 'a'&& s.charAt(i)<='z' ){
count[1] = 1;
}else if(s.charAt(i) >= '0'&& s.charAt(i)<='9' ){
count[2] = 1;
}else {
count[3] = 1;
}
}
if(count[0]+count[1]+count[2]+count[3]<3){
System.out.println("NG");
continue;
}
//3.不能有长度大于2的不含公共元素的子串重复 （注：其他符号不含空格或换行）
if(getString(s,0,3)){
System.out.println("NG");
continue;
} else {
System.out.println("OK");
}
}
}
//检测是否存在长度大于3的重复子串
static boolean getString(String str,int l,int r) {
if (r >= str.length()) {
return false;
}
if (str.substring(r).contains(str.substring(l, r))) {
return true;
} else {
return getString(str, l + 1, r + 1);
}
}
}复杂度分析
- 时间复杂度：O(n2)O(n^2)O(n2)，n 为单次密码长度，验证重复子串两层循环遍历字符串
- 空间复杂度：O(1)O(1)O(1)，字符串 s 属于必要空间
方法二：正则表达式
具体做法
匹配小写字母、大写字母、数字、其他字符，还是匹配串中前后连续三个一样的字符，我们都可以用正则表达式。只要把正则表达式写出来即可
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s;
while ((s = bf.readLine())!=null) {
// 长度check, 相同长度超2的子串重复check
if (s.length() <= 8 ) {
System.out.println("NG");
continue;
}
// 大小写字母.数字.其它符号check
String[] regexes = {"\\d", "[a-z]", "[A-Z]", "[^\\da-zA-Z]"};
int types = 0;
for (String re : regexes) {
Pattern p = Pattern.compile(re);
Matcher m = p.matcher(s);
if (m.find()) {
types += 1;
}
}
if(types<3){
System.out.println("NG");
continue;
}
//匹配串前后连续3个字符一样的
//public String replaceAll(String replacement)
//替换模式与给定替换字符串相匹配的输入中存在长度大于2的不含公共元素的子串重复 删除一个重复字串长度显然变短了 这时输入NG
if(s.replaceAll("(.{3,})(?=.{3,}\\1)", "").length() < s.length()){
System.out.println("NG");
continue;
}
System.out.println("OK");
}
}
}复杂度分析
- 时间复杂度：O(n)O(n)O(n)，正则表达式匹配复杂度为 O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)，常数级空间，字符串 s 属于必要空间
HJ23 删除字符串中出现次数最少的字符
描述
实现删除字符串中出现次数最少的字符，若出现次数最少的字符有多个，则把出现次数最少的字符都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
数据范围：输入的字符串长度满足 1 \le n \le 20 \1≤n≤20 ，保证输入的字符串中仅出现小写字母
输入描述
字符串只包含小写英文字母, 不考虑非法输入，输入的字符串长度小于等于 20 个字节。
输出描述
删除字符串中出现次数最少的字符后的字符串。
示例 1
输入：
aabcddd输出：
aaddd1.哈希表，时间 O(N)，空间 O(1)
public String delete(String str) {
// Map记录每个字母的次数
Map<Character, Integer> map = new HashMap<>();
for (char ch : str.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// 快速找出最少次数
int min = Integer.MAX_VALUE;
for (int times : map.values()) {
min = Math.min(min, times);
}
StringBuilder res = new StringBuilder();
for (char ch : str.toCharArray()) {
if (map.get(ch) != min) {
res.append(ch);
}
}
return res.toString();
}
public static void main(String[] args) {
Main solution = new Main();
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str = in.nextLine();
String res = solution.delete(str);
System.out.println(res);
}
}2
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String s = scanner.nextLine();
char[] chars = s.toCharArray();
//统计每个字母的数量
HashMap<Character, Integer> map = new HashMap<>();
for (char aChar : chars) {
map.put(aChar, (map.getOrDefault(aChar, 0) + 1));
}
//找到数量最少的字符数量
Collection<Integer> values = map.values();
Integer min = Collections.min(values);
//用空字符串替换该字母
for (Character character : map.keySet()) {
if (map.get(character) == min){
s = s.replaceAll(String.valueOf(character), "");
}
}
System.out.println(s);
}
}
}题目主要意思
1、删除一个字符串中出现次数最少的字符，若多个字符出现次数一样，都删除。
2、字符串需要保持原来的顺序
3、字符串只包含小写字母
4、多行输入输出
方法一：暴力法
具体做法
- 直接遍历字符串，将字符串存入到数组中，将字符串转成 ASCII 格式的，也就是都在 128 个 ASCII 里，设置一个 26 大小的数组即可，因为题目里说了只包含小写字母。
- 遍历字符串后将字符对应的 ASCII 的个数存入对应的数组中。
- 遍历数组找到最小的个数
- 遍历数组，如果当前字符出现的个数等于最小个数，则被替换掉。
Java 代码
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str ;
while ((str = bf.readLine()) != null && !str.equals("")) {
char []chars = str.toCharArray();
// 题目所给出的都是小写字母 共计26个 a~z
int[] temp = new int[26];
for (int i = 0; i < chars.length; i++) {
//找到当前字符在数组中的位置 比如97对应的是a的ASCII码，
int index = chars[i] - 97;
temp[index] = temp[index] + 1;
}
//找到次数最少的个数
int min = Integer.MAX_VALUE;
for (int i = 0; i < 26; i++) {
// 跳过
if (temp[i] != 0) {
min = Math.min(min,temp[i]);
}
}
// 开始删除最小
for (int i = 0; i < 26; i++) {
if (temp[i] == min) {
char ch = (char) ('a' + i);
str = str.replace(ch + "", "");
}
}
System.out.println(str);
}
}
}复杂度分析
- 时间复杂度：O(n)O(n)O(n),需要遍历字符串和数组。
- 空间复杂度：O(n)O(n)O(n),临时数组 temp。
方法二：借助 HashMap 来存储
具体做法
遍历字符串，将字符存入 HashMap 中，在遍历 HashMap 找到最小的 values，在遍历一遍 HashMap 把不等于最小 values 的记录，最后输出。
举例说明：aabcddd
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
public class Main {
public static String delete(String str) {
// Map记录每个字母的次数
HashMap<Character, Integer> map = new HashMap<>();
for (char ch : str.toCharArray()) {
//将每个字符存入其中
map.put(ch, map.getOrDefault(ch, 1) + 1);
}
// 快速找出最少次数
int min = Integer.MAX_VALUE;
for (int times : map.values()) {
min = Math.min(min, times);
}
//最后输出的值
StringBuilder result = new StringBuilder();
for (char ch : str.toCharArray()) {
if (map.get(ch) != min) {
result.append(ch);
}
}
return result.toString();
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s;
while ((s = bf.readLine())!=null) {
System.out.println(delete(s));
}
}
}复杂度分析
- 时间复杂度：O(n),需要多次遍历字符串和 Map，但都不存在嵌套遍历。
- 空间复杂度：O(n),借助了 Map 存储
HJ25 数据分类处理
描述
信息社会，有海量的数据需要分析处理，比如公安局分析身份证号码、 QQ 用户、手机号码、银行帐号等信息及活动记录。
采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。
数据范围：1 \le I,R \le 100 \1≤I,R≤100 ，输入的整数大小满足 0 \le val \le 2^{31}-1\0≤val≤231−1
输入描述
一组输入整数序列 I 和一组规则整数序列 R，I 和 R 序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为 0~(2^31) -1，序列个数不限
输出描述
从 R 依次中取出 R，对 I 进行处理，找到满足条件的 I：
I 整数对应的数字需要连续包含 R 对应的数字。比如 R 为 23，I 为 231，那么 I 包含了 R，条件满足 。
按 R 从小到大的顺序:
(1)先输出 R；
(2)再输出满足条件的 I 的个数；
(3)然后输出满足条件的 I 在 I 序列中的位置索引(从 0 开始)；
(4)最后再输出 I。
附加条件：
(1)R 需要从小到大排序。相同的 R 只需要输出索引小的以及满足条件的 I，索引大的需要过滤掉
(2)如果没有满足条件的 I，对应的 R 不用输出
(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)
序列 I：15,123,456,786,453,46,7,5,3,665,453456,745,456,786,453,123（第一个 15 表明后续有 15 个整数）
序列 R：5,6,3,6,3,0（第一个 5 表明后续有 5 个整数）
输出：30, 3,6,0,123,3,453,7,3,9,453456,13,453,14,123,6,7,1,456,2,786,4,46,8,665,9,453456,11,456,12,786
说明：
30----后续有 30 个整数
3----从小到大排序，第一个 R 为 0，但没有满足条件的 I，不输出 0，而下一个 R 是 3
6--- 存在 6 个包含 3 的 I
0--- 123 所在的原序号为 0
123--- 123 包含 3，满足条件
示例 1
输入：
15 123 456 786 453 46 7 5 3 665 453456 745 456 786 453 123
5 6 3 6 3 0输出：
30 3 6 0 123 3 453 7 3 9 453456 13 453 14 123 6 7 1 456 2 786 4 46 8 665 9 453456 11 456 12 786说明：
将序列R：5,6,3,6,3,0（第一个5表明后续有5个整数）排序去重后，可得0,3,6。
序列I没有包含0的元素。
序列I中包含3的元素有：I[0]的值为123、I[3]的值为453、I[7]的值为3、I[9]的值为453456、I[13]的值为453、I[14]的值为123。
序列I中包含6的元素有：I[1]的值为456、I[2]的值为786、I[4]的值为46、I[8]的值为665、I[9]的值为453456、I[11]的值为456、I[12]的值为786。
最后按题目要求的格式进行输出即可。题目主要信息
1、 一组输入整数序列 I 和一组规则整数序列 R，I 和 R 序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为 0~(2^31) -1，序列个数不限
2、 从 R 依次中取出 R[i]，对 I 进行处理，找到满足条件的 I
3、按 R[i]从小到大的顺序:
(1)先输出 R[i]；
(2)再输出满足条件的 I 的个数；
(3)然后输出满足条件的 I 在 I 序列中的位置索引(从 0 开始)；
(4)最后再输出 I。
4、附加条件：
(1)R[i]需要从小到大排序。相同的 R[i]只需要输出索引小的以及满足条件的 I，索引大的需要过滤掉
(2)如果没有满足条件的 I，对应的 R[i]不用输出
(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)
方法一：直接暴力求解
具体方法
遍历每个 R[i]，并遍历每个 I[i]是否符合要求，符合的话就记录。
Java 代码
import java.io.*;
import java.util.*;
public class Main {//数据分类处理
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
if (str.equals("")) continue;
//需要过了的I
String[] I = str.split(" ");
// R
String[] temp = br.readLine().split(" ");
long[] R = new long[Integer.parseInt(temp[0])];
for (int i = 0; i < R.length; i++) R[i] = Long.parseLong(temp[i+1]);
//先对R进行排序 然后在依次遍历
Arrays.sort(R);
//最终的结果记录
StringBuilder result = new StringBuilder();
int count = 0;
for (int i = 0; i < R.length; i++) {
//当R中的值相等的时候 只保留第一个出现的
if (i > 0 && R[i] == R[i-1]) continue;
//需要进行匹配的字符
String pattern = R[i] + "";
int num = 0;
StringBuilder index = new StringBuilder();
for (int j = 1; j < I.length; j++) {
//说明出现了 找到位置
if (I[j].indexOf(pattern) != -1) {
num++;
index.append(" ").append(j-1).append(" ").append(I[j]);
}
}
//说明存在跟此时R[i]匹配的I
if (num > 0){
result.append(" ").append(R[i]).append(" ").append(num).append(index);
count += num*2+2;
}
}
System.out.println(count + result.toString());
}
}
}复杂度分析
- 时间复杂度：O(nm+mlogm)O(nm+mlogm)O(n**m+mlogm)，需要两层 for 循环遍历，一层遍历 R 一层遍历 I，另外就是进行了排序的操作。
- 空间复杂度：O(1)O(1)O(1) ,都是常数级别变量
方法二：借助 Map
具体做法
在每一轮遍历 I 的过程中，将当前 I[i]存入到 Map 中，并以 key 和 value 的形式，其中 key 是当前元素的下标，value 为当前元素的值。
最终在遍历 Map,将结果存入到最终的 result 结果中。
Java 代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int num = sc.nextInt();
//读取I
String[] array = new String[num];
for (int i =0; i<num; i++) {
array[i] = String.valueOf(sc.nextInt());
}
//读取R
int rnum = sc.nextInt();
Set<Integer> set = new TreeSet<>();
for (int i =0; i<rnum; i++) {
set.add(sc.nextInt());
}
StringBuilder result = new StringBuilder();
int count = 0;//记录符合的个数
//遍历 R
for (int i : set) {
int j = 0;//记录I的每个元素的index
Map<Integer, String> map = new TreeMap<>();
//在I中寻找符合要求的I[i]
for (String str : array) {
if (str.contains(String.valueOf(i))){
map.put(j, str);
}
j++;
}
//如果Map非空 则存入result中
if (!map.isEmpty()) {
if (count > 0) {
result.append(" ");
}
result.append(i).append(" ").append(map.size());
count +=2;//多两个数组
for (Map.Entry<Integer, String> entry : map.entrySet()) {
count+=2;
result.append(" ").append(entry.getKey()).append(" ").append(entry.getValue());
};
}
}
if (count > 0) {
StringBuilder result2 = new StringBuilder();
result2.append(count).append(" ").append(result.toString());
System.out.println(result2.toString());
}
}
}
}复杂度分析
- 时间复杂度：O(nm+mlog2m)O(nm+mlog2m)O(n**m+mlo**g2m)，需要两层 for 循环遍历，一层遍历 R 一层遍历 I，另外就是进行了排序的操作。
- 空间复杂度：O(n)O(n)O(n)，辅助空间为哈希表的长度.
方法三
import java.util.*;
public class Main{
public static void main(String[] args){
/*
根据题解可知：整数序列I 和 规则整数序列R
1、是根据R中元素到I序列中进行匹配查询并将I序列中出现的R[i]的索引(index)和I[i]的值进行记录
2、定义集合用于记录待查找条件R[i]和R[i]出现的次数(count),最后将第一步得到的集合放进来即可，此处也可使用StringBuffer
*/
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int In = scanner.nextInt(); //整数序列I的个数
String[] I_arr = new String[In];
for(int i=0;i<In;i++){
I_arr[i]= String.valueOf(scanner.nextInt());
}
int Rn = scanner.nextInt();//规则整数序列R的个数
Set<Integer> R_set = new TreeSet<>();//使用TreeSet进行排序和去重
for(int i = 0; i<Rn; i++){
R_set.add(scanner.nextInt());
}
List<Integer> I_list = new ArrayList<>();//用于存储整数序列I
List<Integer> R_list = new ArrayList<>();//用于存储规则整数序列R
for(int item : R_set){
int count = 0;//统计R中元素在I中出现的次数
for(int i =0; i<I_arr.length; i++){
if(I_arr[i].contains(String.valueOf(item))){
count++;
I_list.add(i);
I_list.add(Integer.valueOf(I_arr[i]));
}
}
if(count>0){
R_list.add(item);
R_list.add(count);
R_list.addAll(I_list);
}
I_list.clear();
}
System.out.print(R_list.size()+" ");
for(Integer i:R_list){
System.out.print(i+" ");
}
System.out.println();
}
}
}HJ27 查找兄弟单词
描述
定义一个单词的“兄弟单词”为：交换该单词字母顺序（注：可以交换任意次），而不添加、删除、修改原有的字母就能生成的单词。
兄弟单词要求和原来的单词不同。例如： ab 和 ba 是兄弟单词。 ab 和 ab 则不是兄弟单词。
现在给定你 n 个单词，另外再给你一个单词 x ，让你寻找 x 的兄弟单词里，按字典序排列后的第 k 个单词是什么？
注意：字典中可能有重复单词。
数据范围：1 \le n \le 1000 \1≤n≤1000 ，输入的字符串长度满足 1 \le len(str) \le 10 \1≤len(str)≤10 ， 1 \le k < n \1≤k<n
输入描述
输入只有一行。 先输入字典中单词的个数 n，再输入 n 个单词作为字典单词。 然后输入一个单词 x 最后后输入一个整数 k
输出描述
第一行输出查找到 x 的兄弟单词的个数 m 第二行输出查找到的按照字典顺序排序后的第 k 个兄弟单词，没有符合第 k 个的话则不用输出。
示例 1
输入：
3 abc bca cab abc 1复制
输出：
2
bca复制
示例 2
输入：
6 cab ad abcd cba abc bca abc 1输出：
3
bca说明：
abc的兄弟单词有cab cba bca，所以输出3
经字典序排列后，变为bca cab cba，所以第1个字典序兄弟单词为bca代码
import java.util.*;
/**
* 功能描述: <br>
* @Param: 输入：
* 6 cab ad abcd cba abc bca abc 1
* 复制
* 输出：
* 3
* bca
* 复制
* 说明：
* abc的兄弟单词有cab cba bca，所以输出3
* 经字典序排列后，变为bca cab cba，所以第1个字典序兄弟单词为bca
* @Return:
* @Author: guokun
* @Date: 2021/10/13 14:18
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()){
String[] ss = scanner.nextLine().split(" ");
Integer a = Integer.parseInt(ss[0]);
String x = ss[ss.length-2];
Integer k = Integer.parseInt(ss[ss.length-1]);
List<String> list = new ArrayList<>();
for (int i = 1; i <=a ; i++) {
if (isBrother(x,ss[i])){
list.add(ss[i]);
}
}
int size = list.size();
System.out.println(size);
if (size>=k){
Collections.sort(list);
System.out.println(list.get(k-1));
}
}
}
public static boolean isBrother(String x,String y){
if (x.length()!=y.length()||y.equals(x)){
return false;
}
char[] s = x.toCharArray();
char[] j= y.toCharArray();
Arrays.sort(s);
Arrays.sort(j);
return new String(s).equals(new String(j));
}
}1、对 n 个单词升序排序
2、第 n 个单词和 x 相等 和 长度不一致的跳过
3、对第 n 个单词 和 x 的每个字符升序排序，并比较是否相等，如果相等则为兄弟单词。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int num = in.nextInt();
List<String> datas = new ArrayList();
for(int i = 0 ; i < num ; i++){
datas.add(in.next());
}
String x = in.next();
char[] xs = x.toCharArray();//取反
int index = in.nextInt();
Collections.sort(datas);
int count = 0;
String k = "";
for(String str : datas){
if(x.equals(str) || x.length() != str.length()){
continue; //字符串一样 和 长度不一样的跳过
}
char[] strs = str.toCharArray();
Arrays.sort(xs);
Arrays.sort(strs);
if(!Arrays.equals(strs,xs)){
continue;//升序排序不相等，跳过
}
count += 1; // 满足条件的累加
if (count == index) {
k = str;//第K个兄弟单词
}
}
System.out.println(count);
System.out.println(k);
}
}
}HJ28 素数伴侣
描述
题目描述 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如 2 和 5、6 和 13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有 4 个正整数：2，5，6，13，如果将 5 和 6 分为一组中只能得到一组“素数伴侣”，而将 2 和 5、6 和 13 编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
输出:
输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
数据范围： 1 \le n \le 100 \1≤n≤100 ，输入的数据大小满足 2 \le val \le 30000 \2≤val≤30000
输入描述
输入说明 1 输入一个正偶数 n 2 输入 n 个整数
输出描述
求得的“最佳方案”组成“素数伴侣”的对数。
示例 1
输入：
4
2 5 6 13输出：
2示例 2
输入：
2
3 6输出：
0题意整理
- 输入 N（N 为偶数）个正整数，从其中挑选出若干对组成“素数伴侣”。
- 问怎么挑选，可以使得“素数伴侣”的对数最多。
- 如果两个正整数的和为素数，则这两个正整数称之为“素数伴侣”。
方法一（匈牙利算法）
1.解题思路
- 首先定义两个 list 容器，分别存储输入整数中的奇数和偶数。
- 然后利用匈牙利算法找到“素数伴侣”对数最多时的配对数。匈牙利算法的核心思想是先到先得，能让就让。
- 最后输出“素数伴侣”最多时的对数。
图解展示（匈牙利算法）： 
举例说明：如图所示，首先 A1 和 B2 配对（先到先得），然后轮到 A2，A2 也可以和 B2 配对，这时候 B2 发现 A1 还可以和 B4 配对，所以放弃了 A1，选择和 A2 组成伴侣（能让就让）。接着 A3 直接和 B1 配对（先到先得）。最后 A4 尝试与 B4 配对，但是这样 A1 就只能与 B2 配对，而 A2 就找不到伴侣了，一层层递归下来，发现不可行，所以 A4 不能与 B4 配对。
2.代码实现
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
static int max=0;
public static void main(String[] args){
//标准输入
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
//输入正偶数
int n=sc.nextInt();
//用于记录输入的n个整数
int[] arr=new int[n];
//用于存储所有的奇数
ArrayList<Integer> odds=new ArrayList<>();
//用于存储所有的偶数
ArrayList<Integer> evens=new ArrayList<>();
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
//将奇数添加到odds
if(arr[i]%2==1){
odds.add(arr[i]);
}
//将偶数添加到evens
if(arr[i]%2==0){
evens.add(arr[i]);
}
}
//下标对应已经匹配的偶数的下标，值对应这个偶数的伴侣
int[] matcheven=new int[evens.size()];
//记录伴侣的对数
int count=0;
for(int j=0;j<odds.size();j++){
//用于标记对应的偶数是否查找过
boolean[] v=new boolean[evens.size()];
//如果匹配上，则计数加1
if(find(odds.get(j),matcheven,evens,v)){
count++;
}
}
System.out.println(count);
}
}
//判断奇数x能否找到伴侣
private static boolean find(int x,int[] matcheven,ArrayList<Integer> evens,boolean[] v){
for(int i=0;i<evens.size();i++){
//该位置偶数没被访问过，并且能与x组成素数伴侣
if(isPrime(x+evens.get(i))&&v[i]==false){
v[i]=true;
/*如果i位置偶数还没有伴侣，则与x组成伴侣，如果已经有伴侣，并且这个伴侣能重新找到新伴侣，
则把原来伴侣让给别人，自己与x组成伴侣*/
if(matcheven[i]==0||find(matcheven[i],matcheven,evens,v)){
matcheven[i]=x;
return true;
}
}
}
return false;
}
//判断x是否是素数
private static boolean isPrime(int x){
if(x==1) return false;
//如果能被2到根号x整除，则一定不是素数
for(int i=2;i<=(int)Math.sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
}3.复杂度分析
- 时间复杂度：假设输入的奇数的数目为 p，输入的偶数的数目为 q，则 find 函数的时间复杂度为 O(q2)O(q^2)O(q2) ，因为循环内还嵌套了一个递归，虽然还有一个判断是否是素数的函数，但是题目中输入的数据范围在 1-100 之间，所以这个判断素数的函数的时间复杂度为 O( 1)O(1)O(1)。最坏情况下，奇数和偶数的数目相等，均为 n/2n/2n/2，此时 find 函数的复杂度为 O(n2)O(n^2)O(n2) ，需要对所有的奇数执行 find，所以时间复杂度为 O(n3)O(n^3)O(n3)。
- 空间复杂度：需要额外大小为 p 和 q 的 list 容器分别存储对应的奇数和偶数，p、q 均不大于 n，所以空间复杂度为 O(n)O(n)O( n)。
方法二（利用 io 流）
1.解题思路
思路和方法一基本一致，不同的是通过 io 流操作来处理输入的数据。
2.代码实现
import java.io.*;
import java.util.ArrayList;
public class Main{
static int max=0;
public static void main(String[] args) throws Exception{
//io输入
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s;
while((s=br.readLine())!=null){
//输入正偶数n
int n=Integer.parseInt(s);
//输入n个整数
String[] arr=br.readLine().split(" ");
//用于存储所有的奇数
ArrayList<Integer> odds=new ArrayList<>();
//用于存储所有的偶数
ArrayList<Integer> evens=new ArrayList<>();
for(int i=0;i<n;i++){
int num=Integer.parseInt(arr[i]);
//将奇数添加到odds
if(num%2==1){
odds.add(num);
}
//将偶数添加到evens
if(num%2==0){
evens.add(num);
}
}
//下标对应已经匹配的偶数的下标，值对应这个偶数的伴侣
int[] matcheven=new int[evens.size()];
//记录伴侣的对数
int count=0;
for(int j=0;j<odds.size();j++){
//用于标记对应的偶数是否查找过
boolean[] v=new boolean[evens.size()];
//如果匹配上，则计数加1
if(find(odds.get(j),matcheven,evens,v)){
count++;
}
}
System.out.println(count);
}
}
//判断奇数x能否找到伴侣
private static boolean find(int x,int[] matcheven,ArrayList<Integer> evens,boolean[] v){
for(int i=0;i<evens.size();i++){
//该位置偶数没被访问过，并且能与x组成素数伴侣
if(isPrime(x+evens.get(i))&&v[i]==false){
v[i]=true;
/*如果i位置偶数还没有伴侣，则与x组成伴侣，如果已经有伴侣，并且这个伴侣能重新找到新伴侣，
则把原来伴侣让给别人，自己与x组成伴侣*/
if(matcheven[i]==0||find(matcheven[i],matcheven,evens,v)){
matcheven[i]=x;
return true;
}
}
}
return false;
}
//判断x是否是素数
private static boolean isPrime(int x){
if(x==1) return false;
//如果能被2到根号x整除，则一定不是素数
for(int i=2;i<=(int)Math.sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
}3.复杂度分析
- 时间复杂度：假设输入的奇数的数目为 p，输入的偶数的数目为 q，则 find 函数的时间复杂度为 O(q2)O(q^2)O(q2) ，因为循环内还嵌套了一个递归，虽然还有一个判断是否是素数的函数，但是题目中输入的数据范围在 1-100 之间，所以这个判断素数的函数的时间复杂度为 O( 1)O(1)O(1)。最坏情况下，奇数和偶数的数目相等，均为 n/2n/2n/2，此时 find 函数的复杂度为 O(n2)O(n^2)O(n2) ，需要对所有的奇数执行 find，所以时间复杂度为 O(n3)O(n^3)O(n3)。
- 空间复杂度：需要额外大小为 p 和 q 的 list 容器分别存储对应的奇数和偶数，p、q 均不大于 n，所以空间复杂度为 O(n)O(n)O( n)。
HJ33 整数与 IP 地址间的转换
描述
原理：ip 地址的每段可以看成是一个 0-255 的整数，把每段拆分成一个二进制形式组合起来，然后把这个二进制数转变成 一个长整数。 举例：一个 ip 地址为 10.0.3.193 每段数字 相对应的二进制数 10 00001010 0 00000000 3 00000011 193 11000001
组合起来即为：00001010 00000000 00000011 11000001,转换为 10 进制数就是：167773121，即该 IP 地址转换后的数字就是它了。
数据范围：保证输入的是合法的 IP 序列
输入描述
输入 1 输入 IP 地址 2 输入 10 进制型的 IP 地址
输出描述
输出 1 输出转换成 10 进制的 IP 地址 2 输出转换后的 IP 地址
示例 1
输入：
10.0.3.193
167969729输出：
167773121
10.3.3.193题目主要信息
1、将 ip 地址转化为长整数
2、将长整数转换为 ip 地址
方法一:通过二进制进行转换
具体方法
在问题中有两个转换过程，一个是将 ip 地址转换为长整数，一个是将长整数转换为 ip 地址，通过题目中的转换过程进行转换。 对于 ip 地址转换成长整数： 1、将 ip 地址切割成四段数字 2、每段数字用 8 位 2 二进制数字表示 3、将四段二进制数字组合 4、将二进制数字转换成长整数 对于长整数转换成 ip 地址则步骤相反 1、将长整数转换成 32 位二进制数字 2、将 32 位二进制数字进行切割 3、将每段的二进制数字转换为十进制数字 4、形成 ip 地址
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String s = sc.next();
if(s.contains(".")){
System.out.println(ip2num(s));
}else{
System.out.println(num2ip(Long.parseLong(s)));
}
}
}
public static long ip2num(String ip){
String[] iip = ip.split("\\.");
StringBuilder sb = new StringBuilder();
for(int i=0; i<4; i++){
int num = Integer.parseInt(iip[i]); // 拆分
String num2 = Integer.toBinaryString(num); //转换为二进制
while(num2.length()<8){
num2 = "0" + num2; // 拼接
}
sb.append(num2);
}
return Long.parseLong(sb.toString(), 2); // 转化为10进制
}
public static String num2ip(long num){
String num2 = Long.toBinaryString(num); //转换为2进制
while(num2.length()<32){
num2 = "0" + num2;
}
String[] ans = new String[4];
for(int i=0; i<4; i++){
String s = num2.substring(8*i, 8*i+8); //拆分
s = Integer.toString(Integer.parseInt(s, 2)); //转化为10进制
ans[i] = s;
}
return String.join(".", ans); //拼接
}
}复杂度分析
- 时间复杂度：O(1)O(1)O(1)，均为常数级别的转换
- 空间复杂度：O(1)O(1)O(1)
方法二：直接转换（10 进制和 256 进制）
具体方法
在第一种方法中，我们通过二进制进行转换，但是仔细分析之后，我们发现，二进制在转换过程中并没有起到作用，再进行重新分析，我们可以发现，ip 地址实际上是 256 进制下的四位数字，所以我们可以直接进行转换，将 10 进制转化为 256 进制。
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String s = sc.next();
if(s.contains(".")){
System.out.println(ip2num(s));
}else{
System.out.println(num2ip(Long.parseLong(s)));
}
}
}
public static long ip2num(String ip){
String[] iip = ip.split("\\.");
Long ans = (long)0;
for(int i = 0; i<4; i++){
ans = ans * 256 + Long.parseLong(iip[i]);
}
return ans;
}
public static String num2ip(long num){
String[] ans = new String[4];
for(int i=3; i>=0; i--){
ans[i] = Long.toString(num % 256);
num = num / 256;
}
return String.join(".", ans);
}
}复杂度分析
- 时间复杂度：O(1)O(1)O(1)，均为常数级别的转换
- 空间复杂度：O(1)O(1)O(1)
HJ41 称砝码
描述
现有 n 种砝码，重量互不相等，分别为 m1,m2,m3……mn ； 每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
注：
称重重量包括 0
数据范围：每组输入数据满足 1 \le n \le 10 \1≤n≤10 ， 1 \le m_i \le 2000 \1≤m**i≤2000 ， 1 \le x_i \le 10 \1≤x**i≤10
输入描述
对于每组测试数据： 第一行：n --- 砝码的种数(范围[1,10]) 第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000]) 第三行：x1 x2 x3 …… xn --- 每种砝码对应的数量(范围[1,10])
输出描述
利用给定的砝码可以称出的不同的重量数
示例 1
输入：
2
1 2
2 1输出：
5说明：
可以表示出0，1，2，3，4五种重量。hashset 去重，三层循环，遍历砝码，遍历砝码个数，遍历当前 set 的结果
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) { // 注意 while 处理多个 case
HashSet<Integer> set = new HashSet<>();//存放所有可能的结果，不用担心重复问题
set.add(0);//初始化为0
int n = in.nextInt();//个数
int[] w = new int[n];
int[] nums = new int[n];
for(int i=0;i<n;i++){
w[i] = in.nextInt();//砝码的重量
}
for(int i=0;i<n;i++){
nums[i] = in.nextInt();//砝码个数
}
for(int i=0;i<n;i++){//遍历砝码
ArrayList<Integer> list = new ArrayList<>(set);//取当前所有的结果
for(int j=1;j<=nums[i];j++){//遍历个数
for(int k=0;k<list.size();k++){
set.add(list.get(k) + w[i] * j);
}
}
}
System.out.println(set.size());
}
}
}HJ60 查找组成一个偶数最接近的两个素数
描述
任意一个偶数（大于 2）都可以由 2 个素数组成，组成偶数的 2 个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。
数据范围：输入的数据满足 4 \le n \le 1000 \4≤n≤1000
输入描述
输入一个大于 2 的偶数
输出描述
从小到大输出两个素数
示例 1
输入：
20输出：
7
13示例 2
输入：
4输出：
2
2穷举优化
解题思路：
采取从中间向两边枚举的方式，这样贪心的控制住两素数之差距离最小的这个限制
算法流程：
- 对于每个数字，从最接近的两个中位数开始处理判断是否素数
- 如果两个组成偶数的数字都是素数，因为是从最接近的两个数开始枚举，因此一旦都是素数则输出并返回，得到结果
Java 版本代码如下：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()){
int num = scanner.nextInt();
solution(num);
}
}
private static void solution(int num) {
//如num=10, 遍历:5,6,7,8
// 从最接近的两个中位数开始处理判断
for(int i = num / 2; i < num - 1; i++) {
if(isPrime(i) && isPrime(num - i)) {
System.out.println((num - i) + "\n" + i);
return;
}
}
}
// 判断是否素数
private static boolean isPrime(int num) {
for(int i = 2; i <= Math.sqrt(num); i++) {
if(num % i == 0) {
return false;
}
}
return true;
}
}HJ68 成绩排序
描述
给定一些同学的信息（名字，成绩）序列，请你将他们的信息按照成绩从高到低或从低到高的排列,相同成绩
都按先录入排列在前的规则处理。
例示： jack 70 peter 96 Tom 70 smith 67
从高到低 成绩 peter 96 jack 70 Tom 70 smith 67
从低到高
smith 67
jack 70
Tom 70
peter 96
注：0 代表从高到低，1 代表从低到高
数据范围：人数：1\le n \le 200\1≤n≤200
进阶：时间复杂度：O(nlogn)*O*(nlogn) ，空间复杂度：O(n)*O*(n)
输入描述
第一行输入要排序的人的个数 n，第二行输入一个整数表示排序的方式，之后 n 行分别输入他们的名字和成绩，以一个空格隔开
输出描述
按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开
示例 1
输入：
3
0
fang 90
yang 50
ning 70输出：
fang 90
ning 70
yang 50示例 2
输入：
3
1
fang 90
yang 50
ning 70输出：
yang 50
ning 70
fang 90算法流程：
- 通过一个二维数组，每一行包括姓名编号，成绩，将输入的姓名用编号代替，第二列保存成绩
- 自定义排序
- 倒序，按第二列的成绩降序排列,如果相等的话，返回 0，顺序不变，因为默认编号是升序的，符合题意
- 升序则 按成绩升序排序
- 最后根据已经排序后的数组，顺序输出结果
代码
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
HashMap<Integer,String> map = new HashMap<>();
while(sc.hasNextLine()){
// 学生成绩数
int n = Integer.parseInt(sc.nextLine());
//1是升序，0是降序
int flag = Integer.parseInt(sc.nextLine());
// 每一行包括姓名编号，成绩
int[][] score = new int[n][2];
for(int i=0;i<n;i++){
String[] nameAndScore = sc.nextLine().split(" ");
// 学生用编号代替
score[i][0] = i;
score[i][1] = Integer.parseInt(nameAndScore[1]);
map.put(i,nameAndScore[0]);
}
// 自定义排序
Arrays.sort(score,(o1,o2) ->{
// 倒序，按第二列的成绩降序排列,如果相等的话，返回0，顺序不变，因为默认编号是升序的，符合题意
if(flag==0){
return o2[1] - o1[1];
}else{
// 按成绩升序排序
return o1[1] - o2[1];
}
});
// 根据已经排序后的数组，顺序输出结果
for(int i=0;i<n;i++){
System.out.println(map.get(score[i][0]) + " " + score[i][1]);
}
}
}
}HJ101 输入整型数组和排序标识，对其元素按照升序或降序进行排序
描述
输入整型数组和排序标识，对其元素按照升序或降序进行排序
数据范围： 1 \le n \le 1000 \1≤n≤1000 ，元素大小满足 0 \le val \le 100000 \0≤val≤100000
输入描述
第一行输入数组元素个数 第二行输入待排序的数组，每个数用空格隔开 第三行输入一个整数 0 或 1。0 代表升序排序，1 代表降序排序
输出描述
输出排好序的数字
示例 1
输入：
8
1 2 4 9 3 55 64 25
0输出：
1 2 3 4 9 25 55 64示例 2
输入：
5
1 2 3 4 5
1输出：
5 4 3 2 1Scanner 有多次输入，且存在输入数字组成数组的情况 建议使用 while(sc.hasNext()) 判断是否存在下次输入，并按业务录入数字组成数组
Arrays.sort 方法可以对 Integer 数组 按 Comparator 自定义比较器执行排序，注意参数 o1,o2, 左-右（o1-o2）是升序排序; 右-左（o2-o1）是降序排序;
题解源代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//有多次输入，且存在输入数字组成数组的情况
while(sc.hasNext()){
//第一行输入数组元素个数
int arrCount = sc.nextInt();
//第二行输入待排序的数组，每个数用空格隔开
Integer[] arr = new Integer[arrCount];
//录入 arrCount 个 数字，组成数组
for(int i=0;i<arrCount;i++){
arr[i] = sc.nextInt();
}
//第三行输入一个整数0或1。0代表升序排序，1代表降序排序
int flagSort = sc.nextInt();
if(flagSort==0){
Arrays.sort(arr,new Comparator<Integer>(){
public int compare(Integer o1 ,Integer o2){
return o1-o2;
}
});
}
if(flagSort==1){
Arrays.sort(arr,new Comparator<Integer>(){
public int compare(Integer o1 ,Integer o2){
return o2-o1;
}
});
}
for(Integer m : arr){
System.out.print(m + " ");
}
break;
}
System.out.println();
}
}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[] arr = new int[n];//创建数组
for (int i = 0; i < n; i++) {//数组填入
arr[i] = sc.nextInt();
}
int flag = sc.nextInt();//接收排序标识
Arrays.sort(arr);//数组排序
if (flag == 0) {//正序输出
for(int i =0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
else {//逆序输出
for(int i = arr.length - 1; i >= 0; i--){
System.out.print(arr[i] + " ");
}
}
}
}
}HJ106 字符逆序
描述
将一个字符串 str 的内容颠倒过来，并输出。
数据范围：1 \le len(str) \le 10000\1≤len(str)≤10000
输入描述
输入一个字符串，可以有空格
输出描述
输出逆序的字符串
示例 1
输入：
I am a student输出：
tneduts a ma I示例 2
输入：
nowcoder输出：
redocwon代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
String input = scan.nextLine();
StringBuilder res = new StringBuilder(input);
System.out.println(res.reverse());
}
}HJ108 求最小公倍数
描述
正整数 A 和正整数 B 的最小公倍数是指 能被 A 和 B 整除的最小的正整数值，设计一个算法，求输入 A 和 B 的最小公倍数。
数据范围：1 \le a,b \le 100000 \1≤a,b≤100000
输入描述
输入两个正整数 A 和 B。
输出描述
输出 A 和 B 的最小公倍数。
示例 1
输入：
5 7输出：
35示例 2
输入：
2 4输出：
4代码
a，b 的最大公约数为 gcd（a，b），最小公倍数的公式为： }.svg)
此题说是正数，所以绝对值无所谓了。我们可以发现题目带了‘递归’的标签，那么就用递归来实现 gcd，既是面向题目编程，又方便了自己，一举两得。
gcd 的算法是根据 Euclidean algorithm 来的，拿维基百科的例子来说：
计算a = 1071 和b = 462 的最大公约数的过程如下：从 1071 中不断减去 462 直到小于 462（可以减 2 次，即商q0 = 2），余数是 147：
1071 = 2 × 462 + 147.
然后从 462 中不断减去 147 直到小于 147（可以减 3 次，即q1 = 3），余数是 21：
462 = 3 × 147 + 21.
再从 147 中不断减去 21 直到小于 21（可以减 7 次，即q2 = 7），没有余数：
147 = 7 × 21 + 0.
此时，余数是 0，所以 1071 和 462 的最大公约数是 21。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
int a = sc.nextInt();
int b = sc.nextInt();
for(int i = Math.min(a,b); i > 0; i--){
if(a%i == 0 && b%i == 0){
System.out.println(a*b/i);
break;
}
}
}
}
}import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int a = in.nextInt();
int b = in.nextInt();
int lcm = a*b / gcd(a,b);
System.out.println(lcm);
}
}
public static int gcd(int a, int b) {
if (b==0) return a;
return gcd(b,a%b);
}
}