牛客网-华为机试
牛客网-华为机试
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:
break
while 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
输出:
aaddd
1.哈希表,时间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(q2)*O*(*q*2),因为循环内还嵌套了一个递归,虽然还有一个判断是否是素数的函数,但是题目中输入的数据范围在1-100之间,所以这个判断素数的函数的时间复杂度为O(1)O(1)*O*(1)。最坏情况下,奇数和偶数的数目相等,均为n/2n/2*n*/2,此时find函数的复杂度为O(n2)O(n2)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(q2)*O*(*q*2),因为循环内还嵌套了一个递归,虽然还有一个判断是否是素数的函数,但是题目中输入的数据范围在1-100之间,所以这个判断素数的函数的时间复杂度为O(1)O(1)*O*(1)。最坏情况下,奇数和偶数的数目相等,均为n/2n/2*n*/2,此时find函数的复杂度为O(n2)O(n2)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 1
Scanner有多次输入,且存在输入数字组成数组的情况 建议使用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),最小公倍数的公式为: 此题说是正数,所以绝对值无所谓了。我们可以发现题目带了‘递归’的标签,那么就用递归来实现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);
}
}