牛客网-华为机试

xlc5202022年5月31日
大约 43 分钟约 13000 字

牛客网-华为机试

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

二、

主要的思路就是空间换时间,还有利用数组的下标。

  1. 创建一个1001个数字的数组,在输入一个1-1000的数字时将改数组对应下标的值改为1。
  2. 然后再从小到大循环数组中值为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

代码:

一、

思路

  1. 需要输入字符串,用到Scanner和hasNext()。 (1)建立 Scanner sc = new Scanner(System.inopen in new window); (2)判断有无输入用sc.hasNext().接收字符串使用sc.nextLine().
  2. 一次性接受全部的字符串,对8取余,获知需要补0的位数。使用StringBuilder中的append()函数进行字符串修改,别忘了toString()。 字符串缓冲区的建立:StringBuilder sb = new StringBuilder();
  3. 输出时,截取前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。

alt

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、多行输入输出

方法一:暴力法

具体做法

  1. 直接遍历字符串,将字符串存入到数组中,将字符串转成ASCII格式的,也就是都在128个ASCII里,设置一个26大小的数组即可,因为题目里说了只包含小写字母。
  2. 遍历字符串后将字符对应的ASCII的个数存入对应的数组中。
  3. 遍历数组找到最小的个数
  4. 遍历数组,如果当前字符出现的个数等于最小个数,则被替换掉。

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

alt

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容器,分别存储输入整数中的奇数和偶数。
  • 然后利用匈牙利算法找到“素数伴侣”对数最多时的配对数。匈牙利算法的核心思想是先到先得,能让就让。
  • 最后输出“素数伴侣”最多时的对数。

图解展示(匈牙利算法): 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(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进制。

alt

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