牛客网-华为机试

xlc520大约 44 分钟约 13191 字

牛客网-华为机试

HJ1 字符串最后一个单词的长度

描述

计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）

示例1

输入：

hello nowcoder

输出：

说明：

最后一个单词为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.接收输入的第一个字符串，并转换为小写。（完整字符串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

输入：

输出：

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，空字符串不处理。

示例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

代码：

一、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

输入：

输出：

0 3
1 2
3 4

示例2

输入：

输出：

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),字符串中只含有大小写字母。

示例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

示例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个的话则不用输出。

示例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);
    }
}
}

题目描述若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如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
3 6

输出：

题意整理。

输入N（N为偶数）个正整数，从其中挑选出若干对组成“素数伴侣”。
问怎么挑选，可以使得“素数伴侣”的对数最多。
如果两个正整数的和为素数，则这两个正整数称之为“素数伴侣”。

方法一（匈牙利算法）

1.解题思路

首先定义两个list容器，分别存储输入整数中的奇数和偶数。
然后利用匈牙利算法找到“素数伴侣”对数最多时的配对数。匈牙利算法的核心思想是先到先得，能让就让。
最后输出“素数伴侣”最多时的对数。

图解展示（匈牙利算法）： alt

举例说明：如图所示，首先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*(*q*2)，因为循环内还嵌套了一个递归，虽然还有一个判断是否是素数的函数，但是题目中输入的数据范围在1-100之间，所以这个判断素数的函数的时间复杂度为O(1)O(1)*O*(1)。最坏情况下，奇数和偶数的数目相等，均为n/2n/2*n*/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*(*q*2)，因为循环内还嵌套了一个递归，虽然还有一个判断是否是素数的函数，但是题目中输入的数据范围在1-100之间，所以这个判断素数的函数的时间复杂度为O(1)O(1)*O*(1)。最坏情况下，奇数和偶数的数目相等，均为n/2n/2*n*/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

输出：

说明：

可以表示出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

输入：

输出：

7
13

示例2

输入：

输出：

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

输出：

示例2

输入：

2 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);
    }
}