题目链接

刷题链接：https://www.nowcoder.com/exam/oj/ta?tpId=37
参考博客：http://www.amoscloud.com/?cat=56

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

方法1：用Java的Scanner 类的特性

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         String word = "";
  8.         while (scan.hasNext()) {
  9.             word = scan.next();
  10.         }
  11.         System.out.println(word.length());
  12.     }
  13. }

HJ2 计算某字符出现次数

描述
写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
数据范围： [1,1000]

输入描述：
第一行输入一个由字母和数字以及空格组成的字符串，第二行输入一个字符。

输出描述：
输出字符串中含有该字符的个数。（不区分大小写字母）

代码：

  1. import java.util.*;
  3. public class Main{
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while(scan.hasNext()) {
  8.             char[] arr = scan.nextLine().toLowerCase().toCharArray();
  9.             String str = scan.nextLine().toLowerCase();
  10.             int count = 0;
  12.             for(int i = 0; i < arr.length; i++){
  13.                 if(arr[i] == str.charAt(0)){
  14.                     count++;
  15.                 }
  16.             }
  17.             System.out.println(count);
  18.         }
  19.     }
  20. }

HJ3 明明的随机数

描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数（ N≤1000 ），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据(用于不同的调查)，希望大家能正确处理)。

注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。
当没有新的输入时，说明输入结束。
数据范围：n在[1, 1000] ，输入的数字大小满足 [1, 500]

输入描述：
注意：输入可能有多组数据(用于不同的调查)。每组数据都包括多行，第一行先输入随机整数的个数 N ，接下来的 N 行再输入相应个数的整数。具体格式请看下面的”示例”。

输出描述：
返回多行，处理后的结果

方法1：桶排序。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             int n = scan.nextInt();
  9.             boolean[] map = new boolean[501];
  11.             for (int i = 0; i < n; i++) {
  12.                 int num = scan.nextInt();
  13.                 map[num] = true;
  14.             }
  16.             for (int i = 1; i < 501; i++) {
  17.                 if (map[i]) {
  18.                     System.out.println(i);
  19.                 }
  20.             }
  21.         }
  22.     }
  23. }

HJ4 固定长度分割字符串

描述
•连续输入字符串，请按长度为8拆分每个输入字符串并进行输出；
•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
（注：本题有多组输入）

输入描述：
连续输入字符串(输入多次,每个字符串长度小于等于100)

输出描述：
依次输出所有分割后的长度为8的新字符串

方法1：补全法。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             String str = scan.nextLine();
  10.             // 1. 长度不是8的整数倍，统一补足8个0
  11.             if (str.length() % 8 != 0) {
  12.                 str = str + "00000000";
  13.             }
  15.             // 2. 固定长度截取，并打印
  16.             while (str.length() >= 8) {
  17.                 System.out.println(str.substring(0, 8));
  18.                 str = str.substring(8);
  19.             }
  20.         }
  21.     }
  22. }

HJ5 进制转换

描述：写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

数据范围：保证结果在int范围内
注意本题有多组输入

输入描述：
输入一个十六进制的数值字符串。注意：一个用例会同时有多组输入数据，请参考帖子https://www.nowcoder.com/discuss/276 处理多组输入的问题。

输出描述：
输出该数值的十进制字符串。不同组的测试用例用\n隔开。

方法1：手动转换

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             String hex = scan.nextLine().substring(2);
  9.             int num = 0;
  10.             int len = hex.length();
  12.             for (int i = len - 1; i >= 0; i--) {
  13.                 int temp = hexToNum(hex.charAt(i));
  14.                 num += temp * Math.pow(16, len - 1 - i);
  15.             }
  16.             System.out.println(num);
  17.         }
  18.     }
  20.     private static int hexToNum(char c) {
  21.         switch (c) {
  22.             case 'A':
  23.                 return 10;
  24.             case 'B':
  25.                 return 11;
  26.             case 'C':
  27.                 return 12;
  28.             case 'D':
  29.                 return 13;
  30.             case 'E':
  31.                 return 14;
  32.             case 'F':
  33.                 return 15;
  34.             default:
  35.                 return Integer.parseInt(String.valueOf(c));
  36.         }
  37.     }
  38. }

方法2：使用API

  1. import java.util.*;
  3. public class Main {
  4.     // 方法2：使用Java的API
  5.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             String str = scan.nextLine();
  9.             int num = Integer.parseInt(str.substring(2), 16);
  10.             System.out.println(num);
  11.         }
  12.     }
  13. }

HJ6 质数因子

描述：
输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

输入描述：
输入一个整数

输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

方法1：循环相除法。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             int num = scan.nextInt();
  9.             StringBuilder sb = new StringBuilder();
  11.             for (int i = 2; i <= Math.sqrt(num); i++) {
  12.                 while (num % i == 0) {
  13.                     sb.append(i);
  14.                     sb.append(" ");
  15.                     num = num / i;
  16.                 }
  17.             }
  19.             // num 最后有两种可能：1或某个质数
  20.             if (num != 1) {
  21.                 sb.append(num);
  22.                 sb.append(" ");
  23.             }
  25.             System.out.println(sb);
  26.         }
  27.     }
  28. }

HJ8 合并表记录

描述
数据表记录包含表索引index和数值value（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照index值升序进行输出。

方法1：Jdk8的流式编程

  1. import java.util.*;
  2. import java.util.stream.Collectors;
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  8.         while (sc.hasNext()) {
  9.             int num = sc.nextInt();
  10.             Map<Integer, Integer> map = new HashMap<>();
  12.             for (int i = 0; i < num; i++) {
  13.                 int key=sc.nextInt();
  14.                 int value=sc.nextInt();
  16.                 // 有key 就相加，没有key 就put
  17.                 map.put(key, map.getOrDefault(key, 0) + value);
  18.             }
  20.             // 这一句用到好多jdk8的新语法啊
  21.             List<Map.Entry<Integer, Integer>> collect = map.entrySet().stream().sorted(
  22.                     ((o1, o2) -> {
  23.                         return o1.getKey() - o2.getKey();
  24.                     })
  25.             ).collect(Collectors.toList());
  27.             for (Map.Entry<Integer, Integer> entry :
  28.                     collect) {
  29.                 System.out.println(entry.getKey() + " " + entry.getValue() );
  30.             }
  31.         }
  32.     }
  33. }

方法2：哈希表和有序表

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         HashMap<Integer, Integer> map = new HashMap<>();
  7.         int num = scan.nextInt();
  9.         while (scan.hasNext()) {
  10.             for (int i = 0; i < num; i++) {
  11.                 int key = scan.nextInt();
  12.                 int value = scan.nextInt();
  14.                 if (!map.containsKey(key)) {
  15.                     map.put(key, value);
  16.                 } else {
  17.                     map.put(key, map.get(key) + value);
  18.                 }
  19.             }
  21.             // 把map的keySet 排序
  22.             TreeSet<Integer> treeSet = new TreeSet<>(map.keySet());
  23.             for (Integer key : treeSet) {
  24.                 System.out.println(key + " " + map.get(key));
  25.             }
  26.         }
  27.     }
  28. }

HJ9 整数逆序不含重复数字

描述
输入一个 int 型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。
保证输入的整数最后一位不是 0 。

输入描述：
输入一个int型整数

输出描述：
按照从右向左的阅读顺序，返回一个不含重复数字的新的整数

示例1
输入：9876673
输出：37689

方法1：求余加哈希表。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while(scan.hasNext()){
  8.             int num = scan.nextInt();
  9.             boolean[] arr = new boolean[10];
  10.             StringBuilder sb = new StringBuilder();
  12.             // 数组相当于一个哈希表，用来判断某个数字是否出现过
  13.             while(num != 0){
  14.                 int remainder = num % 10;
  16.                 if(arr[remainder] == false){
  17.                     sb.append(remainder);
  18.                     arr[remainder] = true;
  19.                 }
  20.                 num = num / 10;
  21.             }
  22.             System.out.println(sb);
  23.         }
  24.     }
  25. }

HJ10 统计字符种类

描述：编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次。
例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。

输入描述：输入一行没有空格的字符串。

输出描述：输出字符串中范围在(0~127，包括0和127)字符的种数。

示例1
输入：abcb
输出：3

方法1：桶排序

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             String str = scan.nextLine();
  9.             int count = getCount(str);
  10.             System.out.println(count);
  11.         }
  12.     }
  14.     // 桶排序
  15.     public static int getCount(String str) {
  16.         int count = 0;
  17.         boolean[] flag = new boolean[128];
  19.         for (int i = 0; i < str.length(); i++) {
  20.             char c = str.charAt(i);
  21.             if (!flag[c]) {
  22.                 flag[c] = true;
  23.                 count++;
  24.             }
  25.         }
  26.         return count;
  27.     }
  28. }

HJ11 数字颠倒

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         String str = scan.nextLine();
  7.         StringBuilder sb = new StringBuilder(str);
  8.         sb.reverse();
  9.         System.out.println(sb);
  10.     }
  11. }

HJ12 字符串反转

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             String str = scan.nextLine();
  10.             // 将字符串变成char数组再倒序输出
  11.             char[] chars = str.toCharArray();
  12.             for (int i = chars.length - 1; i >= 0; i--) {
  13.                 System.out.print(chars[i]);
  14.             }
  15.             System.out.println();
  16.         }
  17.     }
  18. }

HJ13 句子逆序

描述：将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”
所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符
数据范围：输入的字符串长度满足 【1,1000】
注意本题有多组输入

输入描述：输入一个英文语句，每个单词用空格隔开。保证输入只包含空格和字母。

输出描述：得到逆序的句子

示例1
输入：I am a boy
输出：boy a am I

方法1：字符串用空格分隔

  1. import java.util.*;
  3. public class Main{
  4.     // 方法2：分割逆序拼接
  5.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  8.         while (scan.hasNext()) {
  9.             String str = scan.nextLine();
  10.             String[] arr = str.split(" ");
  11.             StringBuilder sb = new StringBuilder();
  13.             for (int i = arr.length - 1; i >= 0; i--) {
  14.                 sb.append(arr[i]).append(" ");
  15.             }
  16.             System.out.println(sb);
  17.         }
  18.     }
  19. }

方法2：两次逆序。

  1. import java.util.*;
  3. public class Main {
  4.     // 方法1：两次反转
  5.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  8.         while (scan.hasNext()) {
  9.             String str = scan.nextLine();
  10.             char[] arr = str.toCharArray();
  11.             int len = arr.length;
  13.             int start = 0;
  14.             for (int i = 0; i <= len; i++) {
  15.                 // 第一次反转，对单词进行反转
  16.                 if (i == len || arr[i] == ' ') {
  17.                     reverse(arr, start, i - 1);
  18.                     start = i + 1;
  19.                 }
  20.             }
  22.             // 第二次反转，对整个字符串进行反转
  23.             reverse(arr, 0, len - 1);
  24.             System.out.println(new String(arr));
  25.         }
  26.     }
  28.     // 对数组[start, end]这段区间进行反转
  29.     public static void reverse(char[] arr, int start, int end) {
  30.         while (start < end) {
  31.             char temp = arr[start];
  32.             arr[start] = arr[end];
  33.             arr[end] = temp;
  34.             start++;
  35.             end--;
  36.         }
  37.     }
  38. }

HJ14 字符串排序

描述
给定 n 个字符串，请对 n 个字符串按照字典序排列。

数据范围： ，字符串长度满足
输入描述：
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。
输出描述：
数据输出n行，输出结果为按照字典序排列的字符串。

方法1：手写快速排序，定义比较规则

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         String count = scan.nextLine();
  7.         int len = Integer.parseInt(count);
  8.         String[] arr = new String[len];
  10.         for (int i = 0; i < len; i++) {
  11.             arr[i] = scan.nextLine();
  12.         }
  14.         quickSort(arr, 0, arr.length - 1);
  16.         for (String str : arr) {
  17.             System.out.println(str);
  18.         }
  19.     }
  21.     private static void quickSort(String[] arr, int low, int high) {
  22.         if (low < high) {
  23.             int pos = partition(arr, low, high);
  24.             quickSort(arr, low, pos - 1);
  25.             quickSort(arr, pos + 1, high);
  26.         }
  27.     }
  29.     private static int partition(String[] arr, int low, int high) {
  30.         String pivot = arr[low];
  31.         int lt = low;
  32.         int gt = high;
  34.         for (int i = low + 1; i <= gt; i++) {
  35.             int compare = compareTo(arr[i], pivot);
  36.             if (compare < 0) {
  37.                 swap(arr, i, lt);
  38.                 lt++;
  39.             } else {
  40.                 swap(arr, i, gt);
  41.                 gt--;
  42.                 i--;
  43.             }
  44.         }
  45.         return lt;
  46.     }
  48.     // 定义两个字符串的排序规则
  49.     private static int compareTo(String a, String b) {
  50.         int i = 0;
  51.         char[] arr1 = a.toCharArray();
  52.         char[] arr2 = b.toCharArray();
  54.         // 逐个比较
  55.         while (i < arr1.length && i < arr2.length) {
  56.             if (arr1[i] == arr2[i]) {
  57.                 i++;
  58.             } else if (arr1[i] < arr2[i]) {
  59.                 return -1;
  60.             } else {
  61.                 return 1;
  62.             }
  63.         }
  65.         // 长度一样，说明两个字符串一样
  66.         if (arr1.length == arr2.length) {
  67.             return 0;
  68.         }
  70.         // a短，返回-1；b短，返回1
  71.         if (i == arr1.length) {
  72.             return -1;
  73.         } else {
  74.             return 1;
  75.         }
  76.     }
  78.     private static void swap(String[] arr, int i, int j) {
  79.         String temp = arr[i];
  80.         arr[i] = arr[j];
  81.         arr[j] = temp;
  82.     }
  83. }

方法2：使用API

  1. import java.util.*;
  3. public class Main {
  4.     // 方法2：使用API
  5.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  7.         String count = scan.nextLine();
  8.         int len = Integer.parseInt(count);
  9.         String[] arr = new String[len];
  11.         for (int i = 0; i < len; i++) {
  12.             arr[i] = scan.nextLine();
  13.         }
  15.         Arrays.sort(arr);
  17.         for (String str : arr) {
  18.             System.out.println(str);
  19.         }
  20.     }
  21. }

HJ15 求二进制中1的个数

描述：输入一个 int 型的正整数，计算出该 int 型数据在内存中存储时 1 的个数。

输入描述：输入一个整数（int类型）

输出描述：这个数转换成2进制后，输出1的个数

示例1
输入：5
输出：2

方法1：减一消除法。
用&运算会很巧妙，num & (num - 1)，会把num二进制表示中最右侧的1 给消除掉， 每次消除一次就记录次数，直到num变成0，就会得到有多少个1.

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             int num = scan.nextInt();
  9.             int count = 0;
  11.             while (num != 0) {
  12.                 count++;
  13.                 num = num & (num - 1);
  14.             }
  15.             System.out.println(count);
  16.         }
  17.     }
  18. }

HJ16 购物单

HJ17 坐标移动

方法1：正则加哈希

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         Map<Character, Integer> map = new HashMap<>();
  8.         while (scan.hasNext()) {
  9.             String str = scan.nextLine();
  10.             String[] arr = str.split(";");
  11.             String regex = "[ADWS]\\d{1}\\d?";
  12.             int x = 0;
  13.             int y = 0;
  15.             for (int i = 0; i < arr.length; i++) {
  16.                 if (arr[i].matches(regex)) {
  17.                     map.put(arr[i].charAt(0), map.getOrDefault(arr[i].charAt(0), 0) + Integer.parseInt(arr[i].substring(1)));
  18.                 }
  19.             }
  20.             x = x - map.get('A') + map.get('D');
  21.             y = y - map.get('S') + map.get('W');
  22.             System.out.println(x + "," + y);
  23.             map.clear();
  24.         }
  25.         scan.close();
  26.     }
  27. }

方法2：正则表达式

  1. import java.util.*;
  3. public class Main {
  4.     // 方法2：正则表达式
  5.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  8.         while (scan.hasNext()) {
  9.             String str = scan.nextLine();
  10.             String[] arr = str.split(";");
  11.             String regex = "[WASD][0-9]{1,2}";
  12.             int x = 0;
  13.             int y = 0;
  15.             for (int i = 0; i < arr.length; i++) {
  16.                 // 1. 正则表达式匹配合法的字符串
  17.                 if (!arr[i].matches(regex)) {
  18.                     continue;
  19.                 }
  21.                 // 2. 截取字符串中后面的数值部分，
  22.                 int digit = Integer.parseInt(arr[i].substring(1));
  24.                 // 3. 根据移动方向，改变坐标值
  25.                 switch (arr[i].charAt(0)) {
  26.                     case 'W':
  27.                         y += digit;
  28.                         break;
  29.                     case 'S':
  30.                         y -= digit;
  31.                         break;
  32.                     case 'A':
  33.                         x -= digit;
  34.                         break;
  35.                     case 'D':
  36.                         x += digit;
  37.                         break;
  38.                 }
  39.             }
  40.             System.out.println(x + "," + y);
  41.         }
  42.     }
  43. }

HJ19 简单错误记录

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  7.         Map<String, Integer> map = new LinkedHashMap<>();
  8.         String tstr = null;
  10.         while (scan.hasNext()) {
  11.             tstr = scan.nextLine();
  12.             String[] str = tstr.split("\\s+");
  13.             String fname = str[0].substring(str[0].lastIndexOf("\\") + 1);
  14.             fname = fname.substring(Math.max(fname.length() - 16, 0)) + " " + str[1];  //max 最快推荐 ？：也可以 if太麻烦
  16.             Integer tmp = map.get(fname);  //get==null较快写法
  17.             if (tmp == null) {
  18.                 map.put(fname, 1);
  19.             } else {
  20.                 map.put(fname, tmp + 1);
  21.             }
  22.         }
  23.         int count = 0;
  24.         for (Map.Entry<String, Integer> it : map.entrySet()) {
  25.             if (map.size() - count <= 8) {
  26.                 System.out.println(it.getKey() + " " + it.getValue());
  27.             }
  28.             count++;
  29.         }
  30.     }
  31. }

HJ20 密码验证合格程序

方法1：手动检查

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         StringBuilder sb = new StringBuilder();
  7.         String str = null;
  9.         while (scan.hasNext()) {
  10.             str = scan.nextLine();
  11.             char[] arr = str.toCharArray();
  12.             boolean[] flag = new boolean[4];
  14.             // 1. 长度没有超过8位
  15.             if (arr.length < 9) {
  16.                 sb.append("NG").append("\n");
  17.                 continue;
  18.             }
  20.             // 2. 至少有3种不同类型的符号
  21.             for (int i = 0; i < arr.length; i++) {
  22.                 if ('A' <= arr[i] && arr[i] <= 'Z') {
  23.                     flag[0] = true;
  24.                 } else if ('a' <= arr[i] && arr[i] <= 'z') {
  25.                     flag[1] = true;
  26.                 } else if ('0' <= arr[i] && arr[i] <= '9') {
  27.                     flag[2] = true;
  28.                 } else {
  29.                     flag[3] = true;
  30.                 }
  31.             }
  32.             int count = 0;
  33.             for (int i = 0; i < 4; i++) {
  34.                 if (flag[i]) {
  35.                     count++;
  36.                 }
  37.             }
  39.             // 3. 不能有长度大于2的包含公共元素的子串重复
  40.             boolean sign = true;
  41.             for (int i = 0; i < arr.length - 5; i++) {
  42.                 for (int j = i + 3; j < arr.length - 2; j++) {
  43.                     if (arr[i] == arr[j] && arr[i + 1] == arr[j + 1] && arr[i + 2] == arr[j + 2]) {
  44.                         sign = false;
  45.                     }
  46.                 }
  47.             }
  49.             if (count >= 3 && sign) {
  50.                 sb.append("OK").append("\n");
  51.             } else {
  52.                 sb.append("NG").append("\n");
  53.             }
  54.         }
  55.         System.out.println(sb);
  56.     }
  57. }

方法2：正则表达式匹配

  1. import java.util.*;
  2. import java.util.regex.*;
  4. public class Main {
  5.     public static void main(String[] arg) {
  6.         Scanner scan = new Scanner(System.in);
  8.         while (scan.hasNext()) {
  9.             String str = scan.next();
  11.             if (str.length() <= 8) {
  12.                 System.out.println("NG");
  13.                 continue;
  14.             }
  15.             if (!getMatch(str)) {
  16.                 System.out.println("NG");
  17.                 continue;
  18.             }
  19.             if (hasDuplicatedString(str, 0, 3)) {
  20.                 System.out.println("NG");
  21.                 continue;
  22.             }
  23.             System.out.println("OK");
  24.         }
  25.     }
  27.     // 2. 包括大小写字母.数字.其它符号，至少三种
  28.     private static boolean getMatch(String str) {
  29.         int count = 0;
  30.         String[] regex = {"[a-z]", "[A-Z]", "[0-9]", "[^a-zA-Z0-9]"};
  32.         for (int i = 0; i < regex.length; i++) {
  33.             Pattern pattern = Pattern.compile(regex[i]);
  34.             Matcher matcher = pattern.matcher(str);
  35.             if (matcher.find()) {
  36.                 count++;
  37.             }
  38.         }
  39.         return count >= 3;
  40.     }
  42.     // 3. 校验是否有重复子串
  43.     private static boolean hasDuplicatedString(String str, int left, int right) {
  44.         if (right >= str.length()) {
  45.             return false;
  46.         }
  48.         if (str.substring(right).contains(str.substring(left, right))) {
  49.             return true;
  50.         } else {
  51.             return hasDuplicatedString(str, left + 1, right + 1);
  52.         }
  53.     }
  54. }

HJ21 简单密码

方法1：直接按照规则进行变换

  1. import java.util.*;
  3. public class Main {
  5.     // 方法1：直接按照规则变换
  6.     public static void main(String[] args) {
  7.         Scanner scan = new Scanner(System.in);
  8.         String str;
  10.         while (scan.hasNext()) {
  11.             str = scan.next();
  12.             StringBuilder sb = new StringBuilder();
  14.             for (int i = 0; i < str.length(); i++) {
  15.                 char c = str.charAt(i);
  17.                 if (c >= 'A' && c < 'Z') {
  18.                     c = (char) (c - 'A' + 'b');
  19.                 } else if (c == 'Z') {
  20.                     c = 'a';
  21.                 } else if (c >= 'a' && c <= 'c') {
  22.                     c = '2';
  23.                 } else if (c >= 'd' && c <= 'f') {
  24.                     c = '3';
  25.                 } else if (c >= 'g' && c <= 'i') {
  26.                     c = '4';
  27.                 } else if (c >= 'j' && c <= 'l') {
  28.                     c = '5';
  29.                 } else if (c >= 'm' && c <= 'o') {
  30.                     c = '6';
  31.                 } else if (c >= 'p' && c <= 's') {
  32.                     c = '7';
  33.                 } else if (c >= 't' && c <= 'v') {
  34.                     c = '8';
  35.                 } else if (c >= 'w' && c <= 'z') {
  36.                     c = '9';
  37.                 }
  38.                 sb.append(c);
  39.             }
  40.             System.out.println(sb);
  41.         }
  42.     }
  43. }

方法2：哈希表

  1. import java.util.*;
  3. public class Main {
  5.     // 定义map容器，存储按键对应数字字符
  6.     private static Map<String, String> map = new HashMap<>();
  8.     // 静态初始化map
  9.     static {
  10.         map.put("1", "1");
  11.         map.put("abc", "2");
  12.         map.put("def", "3");
  13.         map.put("ghi", "4");
  14.         map.put("jkl", "5");
  15.         map.put("mno", "6");
  16.         map.put("pqrs", "7");
  17.         map.put("tuv", "8");
  18.         map.put("wxyz", "9");
  19.         map.put("0", "0");
  20.     }
  22.     public static void main(String[] args) {
  23.         Scanner scan = new Scanner(System.in);
  24.         while (scan.hasNext()) {
  25.             String str = scan.nextLine();
  26.             char[] arr = str.toCharArray();
  27.             StringBuilder sb = new StringBuilder();
  29.             for (char c : arr) {
  30.                 if (c >= '0' && c <= '9') {
  31.                     sb.append(c);
  32.                 } else if (c >= 'A' && c <= 'Y') {  // 如果是A~Y的大写字母则需要将其+32位转换成小写再向后移1位
  33.                     char newChar = (char) (c + 32 + 1);
  34.                     sb.append(newChar);
  35.                 } else if (c == 'Z') {              // 如果是Z，则加密成a
  36.                     sb.append("a");
  37.                 } else {
  38.                     Set<String> keys = map.keySet();
  39.                     for (String key : keys) {
  40.                         if (key.contains(String.valueOf(c)))
  41.                             sb.append(map.get(key));
  42.                     }
  43.                 }
  44.             }
  45.             System.out.print(sb.toString());
  46.         }
  47.     }
  48. }


HJ22 汽水瓶问题

描述
某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。
小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。
数据范围：输入的正整数满足 1 \le n \le 100 \1≤n≤100

注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。
输入描述：
输入文件最多包含 10 组测试数据，每个数据占一行，仅包含一个正整数 n（ 1<=n<=100 ），表示小张手上的空汽水瓶数。n=0 表示输入结束，你的程序不应当处理这一行。

输出描述：
对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。

递归问题
根据题意可得：
拿出2个瓶子、再向老板借1个空瓶，换来一瓶水，喝完后把空瓶还给老板，也就是说用2个空瓶可以喝到1瓶水，所以可以总结递推公式：f(n) = f(n - 2) + 1；也可以直接推理出 n / 2 就是结果。

方法1：递归

  1. import java.util.*;
  3. public class Main {
  4.     // 方法1：递归
  5.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             int n = scan.nextInt();
  9.             if (n == 0) {
  10.                 return;
  11.             }
  12.             int m = drink(n);
  13.             System.out.println(m);
  14.         }
  15.     }
  17.     public static int drink(int n) {
  18.         if (n == 1) {
  19.             return 0;
  20.         }
  21.         if (n == 2) {
  22.             return 1;
  23.         }
  24.         return drink(n - 2) + 1;
  25.     }
  26. }

方法2：直接计算。

  1. import java.util.*;
  3. public class Main {
  4.     // 方法2：直接计算结果
  5.     public static void main(String[] args) {
  6.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             int n = scan.nextInt();
  9.             if (n == 0) {
  10.                 return;
  11.             }
  12.             System.out.println(n / 2);
  13.         }
  14.     }
  15. }


HJ23 删除字符串中出现次数最少的字符

方法1：哈希表。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while(scan.hasNext()){
  7.             String str = scan.nextLine();
  9.             // 1. 数组做哈希表，统计每个字符出现的次数
  10.             int[] arr = new int[26];
  11.             for (int i = 0; i < str.length(); i++) {
  12.                 int index = str.charAt(i) - 'a';
  13.                 arr[index]++;
  14.             }
  16.             // 2. 找到出现次数最小的次数
  17.             int min = Integer.MAX_VALUE;
  18.             for (int i = 0; i < 26; i++) {
  19.                 if (arr[i] != 0 && arr[i] < min) {
  20.                     min = arr[i];
  21.                 }
  22.             }
  24.             // 3. 再次遍历字符串，过滤出现次数最少的字符
  25.             StringBuilder sb = new StringBuilder();
  26.             for (int i = 0; i < str.length(); i++) {
  27.                 int index = str.charAt(i) - 'a';
  28.                 if (arr[index] != min) {
  29.                     sb.append(str.charAt(i));
  30.                 }
  31.             }
  32.             System.out.println(sb);
  33.         }
  34.     }
  35. }


HJ26 字符串排序

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String str = scan.nextLine();
  9.             // 1. 筛选出字母添加到list集合中，大小写紧挨着
  10.             List<Character> list = new ArrayList<>();
  11.             for (int i = 'A'; i <= 'Z'; i++) {
  12.                 for (int j = 0; j < str.length(); j++) {
  13.                     char c = str.charAt(j);
  14.                     if (c == i || c == i + 32) {    // 该字母的大写或小写
  15.                         list.add(c);
  16.                     }
  17.                 }
  18.             }
  19.             // 2. 遍历字符串，找到非字母字符，插入到list 集合对应位置
  20.             for (int i = 0; i < str.length(); i++) {
  21.                 char c = str.charAt(i);
  22.                 if (! Character.isLetter(c)) {
  23.                     list.add(i, c);
  24.                 }
  25.             }
  27.             // 3. list集合转字符串
  28.             StringBuilder sb = new StringBuilder(str.length());
  29.             for(Character c : list){
  30.                 sb.append(c);
  31.             }
  32.             System.out.println(sb);
  33.         }
  34.     }
  35. }

HJ27 查找兄弟单词

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             // 1. 前期处理，读取各项数据
  8.             int N = scan.nextInt();
  10.             String[] str = new String[N];
  11.             for (int i = 0; i < N; i++) {   // 输入n个单词作为字典单词
  12.                 str[i] = scan.next();
  13.             }
  15.             String findStr = scan.next();   // 输入一个待查单词
  16.             int count = scan.nextInt();     // 输入待查单词的 指定序号
  18.             // 2. 查找兄弟单词
  19.             ArrayList<String> list = new ArrayList<>();
  20.             for (int i = 0; i < N; i++) {
  21.                 // 长度相等，且字面值不相等
  22.                 if ((str[i].length() == findStr.length()) && (!str[i].equals(findStr))) {
  23.                     if (checkBorther(findStr, str[i])) {
  24.                         list.add(str[i]);
  25.                     }
  26.                 }
  27.             }
  29.             // 3. 输出
  30.             Collections.sort(list);
  31.             System.out.println(list.size());
  32.             if (list.size() >= count) {
  33.                 System.out.println(list.get(count - 1));
  34.             }
  35.         }
  36.     }
  38.     // 判断两个字符串是否是兄弟单词
  39.     public static boolean checkBorther(String str1, String str2) {
  40.         // 桶排序思想
  41.         int[] flag = new int[26];
  42.         char[] ch1 = str1.toCharArray();
  43.         char[] ch2 = str2.toCharArray();
  45.         for (int i = 0; i < ch1.length; i++) {
  46.             flag[ch1[i] - 'a']++;
  47.             flag[ch2[i] - 'a']--;
  48.         }
  49.         for (int i = 0; i < 26; i++) {
  50.             if (flag[i] != 0) {
  51.                 return false;
  52.             }
  53.         }
  54.         return true;
  55.     }
  56. }


HJ28 素数伴侣

方法1：匈牙利配对法

  1. import java.util.*;
  3. public class Main {
  4.     // 方法1：
  5.     public static void main(String[] args) throws Exception {
  6.         Scanner scan = new Scanner(System.in);
  7.         while (scan.hasNext()) {
  8.             // 1. 读取数据
  9.             int count = scan.nextInt();
  11.             int[] arr = new int[count];
  12.             for (int i = 0; i < count; i++) {
  13.                 arr[i] = scan.nextInt();
  14.             }
  16.             // 2. 元素奇偶分开
  17.             ArrayList<Integer> evens = new ArrayList<>();
  18.             ArrayList<Integer> odds = new ArrayList<>();
  19.             for (int i = 0; i < count; i++) {
  20.                 if (arr[i] % 2 == 1) {
  21.                     odds.add(arr[i]);
  22.                 } else {
  23.                     evens.add(arr[i]);
  24.                 }
  25.             }
  27.             // 3. 奇偶配对 匈牙利配对法
  28.             int result = 0;
  30.             // 记录偶数配对的奇数伴侣的index(基1)
  31.             int[] eventPairs = new int[evens.size() ];
  33.             for (int i = 0; i < odds.size(); i++) {
  34.                 boolean[] used = new boolean[evens.size()];
  35.                 if (findPair(i, odds, evens, eventPairs, used)) {
  36.                     result++;
  37.                 }
  38.             }
  39.             System.out.println(result);
  40.         }
  41.     }
  43.     public static boolean findPair(int oddIndex, ArrayList<Integer> odds, ArrayList<Integer> evens, int[] eventPairs, boolean[] used) {
  44.         for (int i = 0; i < evens.size(); i++) {
  45.             // 该偶数没有被使用过，且符合匹配规则
  46.             if (!used[i] && isPrime(odds.get(oddIndex) + evens.get(i) )) {
  47.                 used[i] = true;
  48.                 if (eventPairs[i] == 0 || findPair(eventPairs[i] - 1, odds, evens, eventPairs, used)) {
  49.                     eventPairs[i] = oddIndex + 1;
  50.                     return true;
  51.                 }
  52.             }
  53.         }
  54.         return false;
  55.     }
  57.     // 判断是否为素数
  58.     public static boolean isPrime(int num) {
  59.         // 1. 特殊情况 2，3
  60.         if (num <= 3) {
  61.             return num > 1;
  62.         }
  63.         // 2. 只有每个6X-1 和 6X+1可能为质数
  64.         if (num % 6 != 1 && num % 6 != 5) {
  65.             return false;
  66.         }
  68.         double sqrt = Math.sqrt(num);
  69.         // 判断每个 6X-1 和 6X+1
  70.         for (int i = 5; i < sqrt; i += 6) {
  71.             if (num % i == 0 || num % (i + 2) == 0) {
  72.                 return false;
  73.             }
  74.         }
  75.         return true;
  76.     }
  77. }

HJ29 字符串加解密

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             System.out.println(encode(scan.nextLine()));
  8.             System.out.println(decode(scan.nextLine()));
  9.         }
  10.     }
  12.     // 加密函数
  13.     private static String encode(String code) {
  14.         char[] arr = code.toCharArray();
  16.         for (int i = 0; i < arr.length; i++) {
  17.             if (arr[i] >= 'a' && arr[i] < 'z')
  18.                 arr[i] = (char) (arr[i] - 'a' + 'A' + 1);
  19.             else if (arr[i] == 'z')
  20.                 arr[i] = 'A';
  21.             else if (arr[i] >= 'A' && arr[i] < 'Z')
  22.                 arr[i] = (char) (arr[i] - 'A' + 'a' + 1);
  23.             else if (arr[i] == 'Z')
  24.                 arr[i] = 'a';
  25.             else if (arr[i] >= '0' && arr[i] < '9')
  26.                 arr[i] = (char) (arr[i] + 1);
  27.             else if (arr[i] == '9')
  28.                 arr[i] = '0';
  29.         }
  30.         return String.valueOf(arr);
  31.     }
  33.     // 解密函数
  34.     private static String decode(String password) {
  35.         char[] arr = password.toCharArray();
  37.         for (int i = 0; i < arr.length; i++) {
  38.             if (arr[i] > 'a' && arr[i] <= 'z')
  39.                 arr[i] = (char) (arr[i] - 'a' + 'A' - 1);
  40.             else if (arr[i] == 'a')
  41.                 arr[i] = 'Z';
  42.             else if (arr[i] > 'A' && arr[i] <= 'Z')
  43.                 arr[i] = (char) (arr[i] - 'A' + 'a' - 1);
  44.             else if (arr[i] == 'A')
  45.                 arr[i] = 'z';
  46.             else if (arr[i] > '0' && arr[i] <= '9')
  47.                 arr[i] = (char) (arr[i] - 1);
  48.             else if (arr[i] == '0')
  49.                 arr[i] = '9';
  50.         }
  51.         return String.valueOf(arr);
  52.     }
  53. }

HJ31 单词倒排

方法1：正则表达式分割

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String str = scan.nextLine();
  8.             String res = reverse(str);
  9.             System.out.println(res);
  10.         }
  11.     }
  13.     public static String reverse(String str) {
  14.         // 正则表达式匹配非字母的字符
  15.         String[] arr = str.split("[^A-Za-z]");
  16.         StringBuilder sb = new StringBuilder();
  18.         // 逆序添加
  19.         for (int i = arr.length - 1; i >= 0; i--) {
  20.             sb.append(arr[i]).append(" ");
  21.         }
  22.         return sb.toString().trim();
  23.     }
  24. }

HJ33 整数与IP地址间的转换

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String str = scan.next();
  8.             String res;
  10.             if (str.contains(".")) {
  11.                 res = ip2num(str);
  12.             } else {
  13.                 res = num2ip(str);
  14.             }
  15.             System.out.println(res);
  16.         }
  17.     }
  19.     // IP转数字，注意进制转化
  20.     private static String ip2num(String str) {
  21.         String[] arr = str.split("\\.");
  22.         long result = 0;
  24.         for (int i = 0; i < 4; i++) {
  25.             result = result * 256 + Integer.parseInt(arr[i]);
  26.             System.out.println(result);
  27.         }
  28.         return "" + result;
  29.     }
  31.     // 数字转IP，注意字符串拼接顺序
  32.     private static String num2ip(String str) {
  33.         long ipv4 = Long.parseLong(str);
  34.         String res = "";
  36.         for (int i = 0; i < 4; i++) {
  37.             int num = (int) (ipv4 % 256);
  38.             res = num + "." + res;
  39.             ipv4 /= 256;
  40.         }
  41.         return res.substring(0, res.length() - 1);
  42.     }
  43. }

HJ34 图片整理

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int bucket[] = new int[128];
  8.             String str = scan.next();
  10.             // 1. 字符映射数组的下标
  11.             for (int i = 0; i < str.length(); i++) {
  12.                 char c = str.charAt(i);
  13.                 bucket[c]++;
  14.             }
  16.             // 2. 打印
  17.             for (int i = 48; i < bucket.length; i++) {  //  从'0'开始输出
  18.                 if (bucket[i] != 0) {
  19.                     for (int j = 0; j < bucket[i]; j++) {
  20.                         System.out.print((char) i);
  21.                     }
  22.                 }
  23.             }
  24.             System.out.println();
  25.         }
  26.     }
  27. }

HJ35 三角矩阵

方法1：总结出数列规律。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  8.             StringBuilder sb = new StringBuilder();
  10.             for (int row = 1; row <= n; row++) {
  12.                 // 1. 按行处理，元素为 (j * j + j) / 2
  13.                 for (int j = 1; j < n - (row - 1); j++) {
  14.                     int num = (j + row - 1);
  15.                     int value = (num * num + num) / 2 - (row - 1);
  16.                     sb.append(value).append(" ");
  17.                 }
  19.                 // 2. 添加每行末尾的元素
  20.                 int end = (n * n + n) / 2 - (row - 1);
  21.                 sb.append(end).append("\n");
  22.             }
  23.             System.out.println(sb);
  24.         }
  25.     }
  26. }

HJ36 字符串加密

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String key = scan.next().toLowerCase();
  8.             String s = scan.next();
  9.             ArrayList<Character> list = new ArrayList<>();
  11.             // 如果list中不存在就放入
  12.             for (int i = 0; i < key.length(); i++) {
  13.                 if (!list.contains(key.charAt(i))) {
  14.                     list.add(key.charAt(i));
  15.                 }
  16.             }
  18.             // 将A-Z放入到list中
  19.             for (int i = 97; i <= 122; i++) {
  20.                 char c = (char) i;
  21.                 if (!list.contains(c)) {
  22.                     list.add(c);
  23.                 }
  24.             }
  26.             Map<Character, Character> map = new HashMap<>();
  27.             int begin = 97;
  28.             for (int i = 0; i < list.size(); i++) {
  29.                 map.put((char) (begin + i), list.get(i));
  30.             }
  32.             StringBuilder sb = new StringBuilder();
  33.             for (int i = 0; i < s.length(); i++) {
  34.                 char c = s.charAt(i);
  35.                 Character character = map.get(c);
  36.                 if (s.charAt(i) >= 97 && s.charAt(i) <= 122) {
  37.                     sb.append(character);
  38.                 } else {
  39.                     sb.append(Character.toUpperCase(character));
  40.                 }
  41.             }
  42.             System.out.println(sb.toString());
  43.         }
  44.     }
  45. }

HJ37 数兔子

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  8.             System.out.println(countRabbit(n));
  9.         }
  10.     }
  12.     public static int countRabbit(int n) {
  13.         if (n == 1 || n == 2) {
  14.             return 1;
  15.         }
  16.         return countRabbit(n - 1) + countRabbit(n - 2);
  17.     }
  18. }

HJ38 小球落地反弹总路程

如图所示：假设从地面弹起到高度h，这样计算简单，最后再减去h就可以了。
image.png

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int h = scan.nextInt();
  8.             double temp = h;
  9.             double sum = 0;
  11.             // 1. 假设小球从地上弹起到初始高度h，再落下来计算
  12.             for (int i = 0; i < 5; i++) {
  13.                 sum += temp * 2;
  14.                 temp = temp / 2;
  15.             }
  17.             // 2. 减掉第一次假设弹上来的高度h
  18.             sum -= h;
  20.             System.out.printf("%.6f\n", sum);
  21.             System.out.printf("%.6f\n", temp);
  22.         }
  23.     }
  24. }

HJ40 统计四种字符个数

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String str = scan.nextLine();
  8.             int letters = 0;
  9.             int spaces = 0;
  10.             int digits = 0;
  11.             int others = 0;
  13.             for (int i = 0; i < str.length(); i++) {
  14.                 char c = str.charAt(i);
  15.                 if (Character.isLetter(c)) {
  16.                     letters++;
  17.                 } else if (Character.isDigit(c)) {
  18.                     digits++;
  19.                 } else if (Character.isSpaceChar(c)) {
  20.                     spaces++;
  21.                 } else {
  22.                     others++;
  23.                 }
  24.             }
  26.             System.out.println(letters);
  27.             System.out.println(spaces);
  28.             System.out.println(digits);
  29.             System.out.println(others);
  30.         }
  31.     }
  32. }

HJ41 砝码可称量的重量

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  8.             int[] weight = new int[n];
  9.             int[] nums = new int[n];
  11.             for (int i = 0; i < n; i++) {
  12.                 weight[i] = scan.nextInt();
  13.             }
  14.             for (int i = 0; i < n; i++) {
  15.                 nums[i] = scan.nextInt();
  16.             }
  17.             int count = fama(n, weight, nums);
  18.             System.out.println(count);
  19.         }
  20.         scan.close();
  21.     }
  23.     public static int fama(int n, int[] weight, int[] nums) {
  24.         // 1. 先往set中添加第一个砝码可称量出来的重量
  25.         Set<Integer> set = new HashSet<>();
  26.         for (int i = 0; i <= nums[0]; i++) {
  27.             set.add(weight[0] * i);
  28.         }
  30.         // 2. 遍历其他砝码，得到当前这个型号的砝码可称量的重量，添加到set中
  31.         for (int i = 1; i < n; i++) {
  32.             List<Integer> list = new ArrayList<>(set);
  34.             for (int j = 0; j <= nums[i]; j++) {
  36.                 // 遍历上一刻的集合，把新的重量添加进去
  37.                 for (int k = 0; k < list.size(); k++) {
  38.                     int newWeight = weight[i] * j;
  39.                     set.add(list.get(k) + newWeight);
  40.                 }
  41.             }
  42.         }
  43.         return set.size();
  44.     }
  45. }

HJ43 迷宫问题

描述：定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
本题含有多组数据，输入的内容只包含0~1

输入描述：输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解，不考虑有多解的情况，即迷宫只有一条通道。

输出描述：
左上角到右下角的最短路径，格式如样例所示。

迷宫的例子

  1. int[][] maze = {
  2.     {0, 1, 0, 0, 0},
  3.     {0, 1, 1, 1, 0},
  4.     {0, 0, 0, 0, 0},
  5.     {0, 1, 1, 1, 0},
  6.     {0, 0, 0, 1, 0}
  7. };

image.png

方法1：回溯算法。
思考：下图就是代码的运行轨迹，要多在脑海中想象。
华为迷宫问题DFS路径探索Snipaste.png

这是在某个位置，当四个方向上遍历结束时，打印当前path里面存储的路径结点。

  1. 当前坐标：[3 ,4]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)-->(2,4)-->(3,4)-->(4,4)
  2. 当前坐标：[0 ,2]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)-->(2,4)-->(3,4)-->(1,4)-->(0,4)-->(0,3)-->(0,2)
  3. 当前坐标：[0 ,3]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)-->(2,4)-->(3,4)-->(1,4)-->(0,4)-->(0,3)
  4. 当前坐标：[0 ,4]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)-->(2,4)-->(3,4)-->(1,4)-->(0,4)
  5. 当前坐标：[1 ,4]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)-->(2,4)-->(3,4)-->(1,4)
  6. 当前坐标：[2 ,4]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)-->(2,4)-->(3,4)
  7. 当前坐标：[2 ,3]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)-->(2,4)
  8. 当前坐标：[2 ,2]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)-->(2,3)
  9. 当前坐标：[2 ,1]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(2,2)
  10. 当前坐标：[4 ,2]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(3,0)-->(4,0)-->(4,1)-->(4,2)
  11. 当前坐标：[4 ,1]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(3,0)-->(4,0)-->(4,1)
  12. 当前坐标：[4 ,0]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(3,0)-->(4,0)
  13. 当前坐标：[3 ,0]  (0,0)-->(1,0)-->(2,0)-->(2,1)-->(3,0)
  14. 当前坐标：[2 ,0]  (0,0)-->(1,0)-->(2,0)-->(2,1)
  15. 当前坐标：[1 ,0]  (0,0)-->(1,0)-->(2,0)
  16. 当前坐标：[0 ,0]  (0,0)-->(1,0)
  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  8.             int m = scan.nextInt();
  10.             // 1. 创建迷宫数组，从控制台读取数据并初始化数组
  11.             int[][] maze = new int[n][m];
  12.             for (int i = 0; i < n; i++) {
  13.                 for (int j = 0; j < m; j++) {
  14.                     maze[i][j] = scan.nextInt();
  15.                 }
  16.             }
  18.             // 2. 创建两个list，分别存储一条路径和所有路径
  19.             ArrayList<int[]> path = new ArrayList<>();
  20.             ArrayList<ArrayList<int[]>> ret = new ArrayList<>();
  22.             // 3. DFS，深度优先搜索
  23.             dfsMazePath(maze, 0, 0, path, ret);
  25.             // 4. 找到结果集中最短的路径
  26.             int minIndex = 0;
  27.             for (int i = 0; i < ret.size(); i++) {
  28.                 if (ret.get(i).size() < ret.get(minIndex).size()) {
  29.                     minIndex = i;
  30.                 }
  31.             }
  33.             // 5. 按题目要求打印路径
  34.             path = ret.get(minIndex);
  35.             for (int i = 0; i < path.size(); i++) {
  36.                 int[] arr = path.get(i);
  37.                 System.out.println("(" + arr[0] + "," + arr[1] + ")");
  38.             }
  39.         }
  40.     }
  42.     public static void dfsMazePath(int[][] maze, int i, int j, ArrayList<int[]> path, ArrayList<ArrayList<int[]>> ret) {
  43.         // 1. 递归的终止条件：边界
  44.         if (i < 0 || i > maze.length - 1 || j < 0 || j > maze[0].length - 1) {
  45.             return;
  46.         }
  47.         // 2. 递归的终止条件：当前路径不可走，返回
  48.         if (maze[i][j] == 1) {
  49.             return;
  50.         }
  51.         // 3. 递归的终止条件：到达迷宫的终点
  52.         if (i == maze.length - 1 && j == maze[0].length - 1) {
  53.             int[] last = {i, j};
  54.             path.add(last);
  55.             ret.add(new ArrayList<>(path));
  56.             return;
  57.         }
  59.         // 4. 当前路径可走，添加到path中，并把坐标设置为不可访问
  60.         int[] cur = {i, j};
  61.         path.add(cur);
  62.         maze[i][j] = 1;
  64.         // 5. 向四个方向进行探索
  65.         dfsMazePath(maze, i, j + 1, path, ret);   // 右
  66.         dfsMazePath(maze, i + 1, j, path, ret);   // 下
  67.         dfsMazePath(maze, i, j - 1, path, ret);   // 左
  68.         dfsMazePath(maze, i - 1, j, path, ret);   // 上
  70.         // // 这段代码主要是用来查看DFS遍历的轨迹
  71.         // System.out.print("当前坐标：" + "[" + i + " ," + j + "]  ");
  72.         // for (int k = 0; k < path.size(); k++) {
  73.         //     int[] tmp = path.get(k);
  74.         //     System.out.print("(" + tmp[0] + "," + tmp[1] + ")");
  75.         //     if (k != path.size() - 1) {
  76.         //         System.out.print("-->");
  77.         //     }
  78.         // }
  79.         // System.out.println();
  81.         // 6. 回溯。path中移除最后一个坐标，并把当前坐标恢复成可访问
  82.         path.remove(path.size() - 1);
  83.         maze[i][j] = 0;
  84.     }
  85. }

HJ52 编辑距离

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String str1 = scan.nextLine();
  8.             String str2 = scan.nextLine();
  9.             int m = str1.length();
  10.             int n = str2.length();
  12.             // 1. 创建dp数组，并初始化边缘状态
  13.             int[][] dp = new int[m + 1][n + 1];
  14.             dp[0][0] = 0;
  15.             for (int i = 1; i < dp.length; i++) {
  16.                 dp[i][0] = i;
  17.             }
  18.             for (int i = 1; i < dp[0].length; i++) {
  19.                 dp[0][i] = i;
  20.             }
  22.             // 2. 填充dp数组
  23.             for (int i = 1; i < dp.length; i++) {
  24.                 for (int j = 1; j < dp[0].length; j++) {
  25.                     if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
  26.                         dp[i][j] = dp[i - 1][j - 1];
  27.                     } else {
  28.                         int insertCost = dp[i][j - 1] + 1;
  29.                         int deleteCost = dp[i - 1][j] + 1;
  30.                         int replaceCost = dp[i - 1][j - 1] + 1;
  32.                         dp[i][j] = Math.min(insertCost, Math.min(deleteCost, replaceCost));
  33.                     }
  34.                 }
  35.             }
  36.             System.out.println(dp[m][n]);
  37.         }
  38.     }
  39. }

HJ53 杨辉三角的变形

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNextInt()) {
  7.             int num = scan.nextInt();
  9.             if (num == 1 || num == 2) {
  10.                 System.out.println(-1);
  11.             } else if (num % 4 == 1 || num % 4 == 3) {
  12.                 System.out.println(2);
  13.             } else if (num % 4 == 0) {
  14.                 System.out.println(3);
  15.             } else if (num % 4 == 2) {
  16.                 System.out.println(4);
  17.             }
  18.         }
  19.     }
  20. }

HJ54 表达式求值

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  7.         String s = scan.nextLine();
  8.         s = s.replace("{", "(");
  9.         s = s.replace("[", "(");
  10.         s = s.replace("}", ")");
  11.         s = s.replace("]", ")");
  13.         System.out.println(slove(s));
  14.     }
  16.     public static int slove(String s) {
  17.         int len = s.length();
  18.         char[] arr = s.toCharArray();
  19.         int index = 0;
  20.         char sign = '+';
  21.         int number = 0;
  22.         Stack<Integer> stack = new Stack<>();
  24.         // 遍历字符串
  25.         for (int i = 0; i < len; i++) {
  26.             char ch = arr[i];
  28.             // 1. 当前字符是空格，跳过
  29.             if (ch == ' ') {
  30.                 continue;
  31.             }
  33.             // 2. 当前字符是数字，拼接数字
  34.             if (Character.isDigit(ch)) {
  35.                 number = number * 10 + ch - '0';
  36.             }
  38.             // 3. 当前字符是小括号
  39.             if (ch == '(') {
  40.                 int j = i + 1;
  41.                 int count = 1;
  43.                 while (count > 0) {
  44.                     if (arr[j] == ')') {
  45.                         count--;
  46.                     }
  47.                     if (arr[j] == '(') {
  48.                         count++;
  49.                     }
  50.                     j++;
  51.                 }
  53.                 // 递归，解小括号中的表达式
  54.                 number = slove(s.substring(i + 1, j - 1));
  55.                 i = j - 1;
  56.             }
  58.             // 4. 遇到符号，将数字处理后放进栈
  59.             if (!Character.isDigit(ch) || i == len - 1) {
  60.                 if (sign == '+') {
  61.                     stack.push(number);
  62.                 } else if (sign == '-') {
  63.                     stack.push(-1 * number);
  64.                 } else if (sign == '*') {
  65.                     stack.push(stack.pop() * number);
  66.                 } else if (sign == '/') {
  67.                     stack.push(stack.pop() / number);
  68.                 }
  70.                 sign = ch;
  71.                 number = 0;
  72.             }
  73.         }
  75.         // 5. 栈中数字求和得到结果
  76.         int ans = 0;
  77.         while (!stack.isEmpty()) {
  78.             ans += stack.pop();
  79.         }
  80.         return ans;
  81.     }
  82. }

HJ55 挑7

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  8.             int count = 0;
  10.             for (int i = 1; i <= n; i++) {
  11.                 if (i % 7 == 0) {
  12.                     count++;
  13.                 } else {
  14.                     String s = String.valueOf(i);
  15.                     if (s.contains("7")) {
  16.                         count++;
  17.                     }
  18.                 }
  19.             }
  20.             System.out.println(count);
  21.         }
  22.     }
  23. }

HJ56 完全数计算

  1. import java.util.*;
  3. public class Main {
  5.     // 参考：https://blog.nowcoder.net/n/9d96f4ca947f493b8c7632cddfd9cb24
  6.     public static void main(String[] args) {
  7.         Scanner scan = new Scanner(System.in);
  8.         while (scan.hasNext()) {
  9.             int num = scan.nextInt();
  10.             int count = 0;
  12.             for (int i = 2; i <= num; i++) {
  13.                 if (isPerfect(i)) {
  14.                     count++;
  15.                 }
  16.             }
  17.             System.out.println(count);
  18.         }
  19.     }
  21.     public static boolean isPerfect(int n) {
  22.         // 每个数都有因子 1
  23.         int sum = 1;
  25.         // 数学原理：一对因子总会分布在这个数的根号两边，或者就是这平方根值。
  26.         for (int i = 2; i * i <= n; i++) {
  27.             // 如果能被整除
  28.             if (n % i == 0) {
  29.                 int quotient = n / i;            // 整除得到的商
  31.                 if (quotient == i) {             // 商和除数一样
  32.                     sum = sum + i;
  33.                 } else {
  34.                     sum = sum + i + quotient;    // 不为平方根时，加上两个因子
  35.                 }
  36.             }
  37.         }
  38.         return sum == n;
  39.     }
  40. }

HJ60 查找组成一个偶数最接近的两个素数

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  9.             // 最接近的素数，就从数的中间开始
  10.             for (int i = n / 2; i >= 2; i--) {
  11.                 if (isPrime(i) && isPrime(n - i)) {
  12.                     System.out.println(i);
  13.                     System.out.println(n - i);
  14.                     break;
  15.                 }
  16.             }
  17.         }
  18.     }
  20.     public static boolean isPrime(int n) {
  21.         // 素数 除了1和它本身的数，都不能被整除,所以要从2 开始到小于n
  22.         for (int i = 2; i < n; i++) {
  23.             if (n % i == 0) {
  24.                 return false;
  25.             }
  26.         }
  27.         return true;
  28.     }
  29. }

HJ62 二进制中1的个数

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  8.             int count = 0;
  10.             while (n != 0) {
  11.                 n = n & (n - 1);
  12.                 count++;
  13.             }
  14.             System.out.println(count);
  15.         }
  16.     }
  17. }

HJ63 DNA序列

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String str = scan.nextLine();
  8.             int n = scan.nextInt();
  9.             double len = 0.0;
  10.             String result = "";
  12.             for (int i = 0; i < str.length() - n + 1; i++) {
  13.                 String aim = str.substring(i, i + n);
  14.                 String res = aim.replaceAll("[^CG]", "");
  15.                 double cur = (double) res.length() / (double) n;
  17.                 if (cur > len) {
  18.                     len = cur;
  19.                     result = aim;
  20.                 }
  21.             }
  22.             System.out.println(result);
  23.         }
  24.     }
  25. }

HJ65 最长公共子串

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String s1 = scan.nextLine();
  8.             String s2 = scan.nextLine();
  10.             // 题目要求特殊：输出在较短串中最先出现的那个
  11.             String temp = "";
  12.             if (s1.length() > s2.length()) {
  13.                 temp = s1;
  14.                 s1 = s2;
  15.                 s2 = temp;
  16.             }
  18.             System.out.println(lcs(s1, s2));
  19.         }
  20.     }
  22.     // 动态规划
  23.     public static String lcs(String str1, String str2) {
  24.         int m = str1.length();
  25.         int n = str2.length();
  27.         // 1. 创建dp数组
  28.         // dp[i][j] 表示以str1第i个字符结尾，同时在str2中第j 个字符结尾时的公共子串长度
  29.         int[][] dp = new int[m + 1][n + 1];
  30.         int maxLen = 0;
  31.         int end = 0;
  33.         // 2. 填充dp数组
  34.         for (int i = 1; i <= m; i++) {
  35.             for (int j = 1; j <= n; j++) {
  36.                 // 3. 从头开始比较两个字符串，
  37.                 // 如果当前两个字符相同，长度就在上一个基础上加1
  38.                 // 如果不相同，公共子串就断开了，dp[i][j] = 0，因为初始化默认是0，所以不用重新赋值
  39.                 if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
  40.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  42.                     // 4. 更新记录最大的长度
  43.                     if (dp[i][j] > maxLen) {
  44.                         maxLen = dp[i][j];
  46.                         // end 记录最长公共子串尾部字符的索引坐标
  47.                         end = i - 1;
  48.                     }
  49.                 }
  51.             }
  52.         }
  53.         // 5. 截取最长公共子串，[end - maxLen + 1, end + 1)
  54.         return str1.substring(end - maxLen + 1, end + 1);
  55.     }
  56. }

HJ67 24点

这个题有点意思，原来还是用DFS来做的，有想过打印出一个完整的算式，但做了半天没做出来，以后再看看吧。

  1. import java.util.*;
  3. public class Main {
  5.     // 全局变量
  6.     static boolean flag = false;
  8.     public static void main(String[] args) {
  9.         Scanner scan = new Scanner(System.in);
  10.         while (scan.hasNext()) {
  11.             String[] s = scan.nextLine().split(" ");
  12.             int[] arr = new int[4];
  13.             boolean[] visit = new boolean[4];
  14.             for (int i = 0; i < 4; i++) {
  15.                 arr[i] = Integer.parseInt(s[i]);
  16.             }
  18.             dfs(arr, 0, 0, visit);
  19.             System.out.println(flag);
  20.         }
  21.     }
  23.     private static boolean dfs(int[] arr, int count, float num, boolean[] visit) {
  24.         if (count == 4 && num == 24) {
  25.             flag = true;
  26.             return true;
  27.         }
  29.         for (int i = 0; i < 4; i++) {
  30.             if (visit[i] == false) {
  31.                 visit[i] = true;
  33.                 if (dfs(arr, count + 1, num + arr[i], visit) ||
  34.                         dfs(arr, count + 1, num - arr[i], visit) ||
  35.                         dfs(arr, count + 1, num * arr[i], visit) ||
  36.                         dfs(arr, count + 1, num / arr[i], visit)) {
  37.                     return true;
  38.                 }
  40.                 visit[i] = false;
  41.             }
  42.         }
  43.         return false;
  44.     }
  45. }

HJ72 百钱买百鸡问题

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         // 鸡翁值5， 一百块最多买20只  鸡翁买x只
  6.         // 鸡母值3， 一百块最多买33只  鸡母买y只
  7.         // 鸡雏三值1， 一百块最多买300只 鸡雏买z只
  8.         Scanner scan = new Scanner(System.in);
  10.         // 买x鸡翁，y只鸡母，z只鸡雏
  11.         // 5x + 3y + z/3 = 100       ==>  15x + 9y + z = 300
  12.         // x + y + z = 100  加上面式子 ==>  14x + 8y = 200  ==> 7x + 4y = 100  ==>  y = (100 - 7x)/4
  13.         while (scan.hasNextInt()) {
  14.             int n = scan.nextInt();
  16.             for (int x = 0; x <= 14; x++) {
  17.                 if ((100 - 7 * x) % 4 == 0) {
  18.                     int y = (100 - 7 * x) / 4;
  19.                     int z = 100 - x - y;
  20.                     System.out.println(x + " " + y + " " + z);
  21.                 }
  22.             }
  23.         }
  24.     }
  25. }

HJ76 尼科彻斯定理

  1. import java.util.Scanner;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNextInt()) {
  7.             int num = scan.nextInt();
  8.             long sum = (long) Math.pow(num, 3);
  9.             int a1 = (int) sum / num - (num - 1);
  10.             StringBuilder sb = new StringBuilder();
  11.             sb.append(a1);
  13.             for (int i = 1; i < num; i++) {
  14.                 a1 = a1 + 2;
  15.                 sb.append("+");
  16.                 sb.append(a1);
  17.             }
  18.             System.out.println(sb);
  19.         }
  20.     }
  21. }

HJ77 火车进站

题目没看懂，代码也只是大概看了下。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             int n = scan.nextInt();
  9.             // 未进站的火车
  10.             Queue<Integer> queue = new LinkedList<>();
  12.             // 已进站的火车
  13.             Stack<Integer> stack = new Stack<>();
  15.             for (int i = 0; i < n; i++) {
  16.                 queue.offer(scan.nextInt());
  17.             }
  19.             List<String> outQueueList = new ArrayList<>();
  21.             // 获取所有出站队列保存到outQueueList
  22.             processOutQueue(queue, stack, "", outQueueList);
  24.             // 排序后输出
  25.             Collections.sort(outQueueList);
  26.             for (String str : outQueueList) {
  27.                 System.out.println(str);
  28.             }
  30.         }
  31.     }
  33.     private static void processOutQueue(Queue<Integer> queue, Stack<Integer> stack, String outQueue, List<String> list) {
  34.         // 1. 递归的终止条件：如果队列和栈都为空，则保存出站信息
  35.         if (queue.isEmpty() && stack.isEmpty()) {
  36.             list.add(outQueue.trim());
  37.             return;
  38.         }
  40.         // 2. 出栈
  41.         if (!stack.isEmpty()) {
  42.             // 先克隆
  43.             Queue<Integer> tempQueue = new LinkedList<>(queue);
  44.             Stack<Integer> tempStack = (Stack<Integer>) stack.clone();
  45.             String tempOutQueue = outQueue + (tempStack.pop() + " ");
  47.             processOutQueue(tempQueue, tempStack, tempOutQueue, list);
  48.         }
  50.         // 3. 队列入队
  51.         if (!queue.isEmpty()) {
  52.             // 先克隆
  53.             Queue<Integer> tempQueue = new LinkedList<>(queue);
  54.             Stack<Integer> tempStack = (Stack<Integer>) stack.clone();
  55.             tempStack.push(tempQueue.poll());
  57.             processOutQueue(tempQueue, tempStack, outQueue, list);
  58.         }
  59.     }
  60. }

HJ84 统计大写字母个数

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String str = scan.nextLine();
  9.             // 使用正则表达式特别方便，这句代码意思是把所有非大写字母替换为空 
  10.             String res = str.replaceAll("[^A-Z]", "");
  11.             System.out.println(res.length());
  12.         }
  13.     }
  14. }

HJ86 二进制中最长连续1

  1. import java.util.Scanner;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNextInt()) {
  7.             int num = scan.nextInt();
  8.             int maxLen = 0;
  9.             int count = 0;
  11.             while (num != 0) {
  12.                 // 1. 当前二进制数字末尾是1，和1做&运算，会得到1
  13.                 if ((num & 1) == 1) {
  14.                     count++;
  15.                     maxLen = Math.max(maxLen, count);
  16.                 } else {
  17.                     // 2. 当前二进制是0，就把cont重新设置为0
  18.                     count = 0;
  19.                 }
  20.                 // 3. 无符号右移
  21.                 num >>>= 1;
  22.             }
  23.             System.out.println(maxLen);
  24.         }
  25.     }
  26. }

HJ92 连续最长的数字串

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         while (sc.hasNextLine()) {
  7.             String str = sc.nextLine();
  8.             int len = str.length();
  9.             int[] dp = new int[len + 1];
  10.             int maxLen = 0;
  12.             for (int i = 1; i <= len; i++) {
  13.                 char c = str.charAt(i - 1);
  14.                 if (c >= '0' && c <= '9') {
  15.                     dp[i] = dp[i - 1] + 1;
  16.                     maxLen = Math.max(maxLen, dp[i]);
  17.                 }
  18.             }
  20.             for (int i = 1; i <= len; i++) {
  21.                 if (dp[i] == maxLen) {
  22.                     System.out.print(str.substring(i - maxLen, i));
  23.                 }
  24.             }
  25.             System.out.println("," + maxLen);
  26.         }
  27.     }
  28. }

HJ96 数字首尾加符号

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         while (scan.hasNext()) {
  7.             String input = scan.next();
  8.             String str = input.replaceAll("([0-9]+)", "*$1*");
  9.             System.out.println(str);
  10.         }
  11.     }
  12. }