devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

华为机考-java牛客网/力扣 部分刷题记录_输入处理(重要):hj5.进制转换

作者：你好赵伟 | 2024-05-23 08:22:43

赞

踩

输入处理(重要):hj5.进制转换

【刷题题型】

1. 入门题（5题）

(1) 输入处理（重要）：HJ5.进制转换

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         String s = in.nextLine();
  7.         if(s.contains("0x")){
  8.             s = s.substring(2);
  9.         }
  10.         Integer n = Integer.parseInt(s,16);
  11.         System.out.println(n.toString());
  12.     }
  13. }
  14. /*
  15. 16转10
  16. Integer.parseInt(string,16);
  17. 10转2
  18. Integer.toBinaryString(num);
  19. 10转8
  20. Integer.toOctalString(num);
  21. 10转16
  22. Integer.toHexString(num);
  23. */
  24.     public static void main(String[] args){
  25.         Scanner in = new Scanner(System.in);
  26.         String s = in.next();
  27.         System.out.println(Integer.parseInt(s.substring(2),16));
  28.     }

(2) 排列组合：(牛客搜索)NC61.两数之和

  1. import java.util.*;
  2.  
  3.  
  4. public class Solution {
  5.     /**
  6.      * 
  7.      * @param numbers int整型一维数组 
  8.      * @param target int整型 
  9.      * @return int整型一维数组
  10.      */
  11.     public int[] twoSum (int[] numbers, int target) {
  12.         // write code here
  13.         Map<Integer,Integer> map = new HashMap();
  14.         int[] num = new int[2];
  15.         for(int i = 0; i < numbers.length; i++){
  16.             Integer sum = target - numbers[i];
  17.             if(map.containsKey(sum)){
  18.                 num[0] = map.get(sum);
  19.                 num[1] = i+1;
  20.                 break;
  21.             } else {
  22.                 map.put(numbers[i],i+1);
  23.             }
  24.         }
  25.         return num;
  26.     }
  27. }

(3) 快速排序：HJ3.明明的随机数 Arrays.sort();

  1. import java.util.*;
  2. public class Main{
  3.     public static void main(String[] args){
  4.         Scanner in = new Scanner(System.in);
  5.         int n = in.nextInt();
  6.         int[] m= new int[n];
  7.         for(int i = 0; i < n; i++){
  8.             m[i] = in.nextInt();
  9.         }
  10.         in.close();
  11.         Arrays.sort(m);
  12.         System.out.println(m[0]);
  13.         for(int i = 1; i < n; i++){
  14.             if(m[i] != m[i-1]){
  15.                 System.out.println(m[i]);
  16.             }
  17.         }
  18.     }
  19. }

(4) 哈希表：HJ10.字符个数统计

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         String s = in.next();
  7.         Set<String> set = new HashSet();
  8.         for(int i = 0; i < s.length(); i++){
  9.             String str = s.substring(i,i+1);
  10.             set.add(str);
  11.         }
  12.         System.out.println(set.size());
  13.     }
  14. }

(5) 递归：NC68.跳台阶

  1. public class Solution {
  2.     public int jumpFloor(int target) {
  3.         if(target == 1 || target == 0){
  4.             return 1;
  5.         }
  6.         if(target == 2){
  7.             return 2;
  8.         }
  9.         return jumpFloor(target - 1) + jumpFloor(target - 2);
  10.     }
  11. } 
  12. import java.util.*;
  13. public class Solution {
  14.     Map<Integer,Integer> map = new HashMap();
  15.     public int jumpFloor(int target) {
  16.         if(target == 1 || target == 0){
  17.             return 1;
  18.         }
  19.         if(target == 2){
  20.             return 2;
  21.         }
  22.         if(map.containsKey(target)){
  23.             return map.get(target);
  24.         } else{
  25.             map.put(target,jumpFloor(target - 1) + jumpFloor(target - 2));
  26.             return map.get(target);
  27.         }
  28.     }
  29. }

2.字符串操作（6题）（带*题目与第一第二道题目难度相近，以下题目基本覆盖大部分知识点）

(1) HJ17.坐标移动

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args) {
  5.         Scanner in = new Scanner(System.in);
  6.         String s = in.nextLine();
  7.         in.close();
  8.         String[] str = s.split(";");
  9.         int[] n = new int[2];
  10.         java.util.regex.Pattern pattern = java.util.regex.Pattern.compile("[0-9]*");
  11.         for(String s1 : str){
  12.             if(s1.length() <= 3 && s1.length() >= 2 && pattern.matcher(s1.substring(1)).matches()){
  13.                 String s2 = s1.substring(0,1);
  14.                 Integer s4 = Integer.parseInt(s1.substring(1));
  15.                 if("A".equals(s2)){
  16.                     n[0] = n[0] - s4;
  17.                 }else if("D".equals(s2)){
  18.                      n[0] = n[0] + s4;
  19.                 }else if("W".equals(s2)){
  20.                     n[1] = n[1] + s4;
  21.                 }else if("S".equals(s2)){
  22.                     n[1] = n[1] - s4;
  23.                 }
  24.             } 
  25.         }
  26.         System.out.println(n[0]+","+n[1]);
  27.     }
  28. }

正则表达式：

(2) HJ20.密码验证合格程序

  1. import java.util.*;
  2. import java.util.regex.*;
  3.  
  4. public class Main{
  5.     public static void main(String[] args){
  6.         Scanner in = new Scanner(System.in);
  7.         while(in.hasNext()){
  8.             String s = in.next();
  9.             if(s.length() <= 8){
  10.                 System.out.println("NG");
  11.                 continue;
  12.             }
  13.             if(getMatch(s)){
  14.                 System.out.println("NG");
  15.                 continue;
  16.             }
  17.             if(getString(s,0,3)){
  18.                 System.out.println("NG");
  19.                 continue;
  20.             }
  21.             System.out.println("OK");
  22.         }
  23.     }
  24.     
  25.     private static boolean getString(String str,int l,int r){
  26.         if(r >= str.length()){
  27.             return false;
  28.         }
  29.         if(str.substring(r).contains(str.substring(l,r))){
  30.             return true;
  31.         } else {
  32.             return getString(str,l+1,r+1);
  33.         }
  34.     }
  35.     
  36.     private static boolean getMatch(String str){
  37.         int count = 0;
  38.         Pattern p1 = Pattern.compile("[A-Z]");
  39.         if(p1.matcher(str).find()){
  40.             count++;
  41.         }
  42.         Pattern p2 = Pattern.compile("[a-z]");
  43.         if(p2.matcher(str).find()){
  44.             count++;
  45.         }
  46.         Pattern p3 = Pattern.compile("[0-9]");
  47.         if(p3.matcher(str).find()){
  48.             count++;
  49.         }
  50.         Pattern p4 = Pattern.compile("[^a-zA-Z0-9]");
  51.         if(p4.matcher(str).find()){
  52.             count++;
  53.         }
  54.         if(count >= 3){
  55.             return false;
  56.         }
  57.         return true;
  58.     }
  59. }

(3) *HJ23.删除字符串中出现次数最少的字符

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         String s = in.next();
  7.         in.close();
  8.         Map<Character,Integer> map = new HashMap();
  9.         StringBuffer str = new StringBuffer();
  10.         for(char c : s.toCharArray()){
  11.             map.put(c,map.getOrDefault(c,1)+1);
  12.         }
  13.         int min = Integer.MAX_VALUE;
  14.         for(int e : map.values()){
  15.             min = Math.min(min,e);
  16.         }
  17.         for(char c : s.toCharArray()){
  18.             if(map.get(c) != min){
  19.                 str.append(c);
  20.             }
  21.         }
  22.         System.out.println(str);
  23.     }
  24. }

(4) *HJ33.整数与IP地址间的转换

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         while(in.hasNext()){
  7.             String s = in.next();
  8.             if(s.contains(".")){
  9.                 System.out.println(toNumber(s));
  10.             }else {
  11.                  System.out.println(toIp(s));
  12.             }
  13.         }
  14.     }
  15.     
  16.     private static String toIp(String str){
  17.         Long num = Long.parseLong(str);
  18.         String res = Long.toBinaryString(num);
  19.         StringBuffer sf = new StringBuffer();
  20.         if(res.length() != 32){
  21.             for(int i = 0; i < 32 - res.length(); i++ ){
  22.                 sf.append("0");
  23.             }
  24.         }
  25.         sf.append(res);
  26.         String s = sf.toString();
  27.         StringBuffer sf1 = new StringBuffer();
  28.         return toIp2(s,0,8,sf1);
  29.     }
  30.     
  31.     private static String toIp2(String str,int l,int r, StringBuffer sf1){
  32.         String s = str.substring(l,r);
  33.         Long num = Long.parseLong(s,2);
  34.         if(r == str.length()){
  35.             sf1.append(num);
  36.         }else {
  37.             sf1.append(num + ".");
  38.             toIp2(str,r,r+8,sf1);
  39.         }
  40.         return sf1.toString();
  41.     }
  42.     
  43.     private static Long toNumber(String str){
  44.         String[] s = str.split("\\.");
  45.         StringBuffer sf = new StringBuffer();
  46.         for(String s1 : s){
  47.             Long num = Long.parseLong(s1);
  48.             String res = Long.toBinaryString(num);
  49.             if(res.length() < 8){
  50.                 for(int i = 0; i < 8 - res.length(); i++){
  51.                     sf.append("0");
  52.                 }
  53.             }
  54.             sf.append(res);
  55.         }
  56.         return Long.parseLong(sf.toString(),2);
  57.     }
  58. }

(5) HJ101.输入整型数组和排序标识

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         while(in.hasNext()){
  7.             int n = in.nextInt();
  8.             int[] nums = new int[n];
  9.             for(int i = 0; i < n; i++){
  10.                 nums[i] = in.nextInt();
  11.             }
  12.             int flag = in.nextInt();
  13.             Arrays.sort(nums);
  14.             if(flag == 0){
  15.                 for(int i = 0; i < n; i++){
  16.                     System.out.print(nums[i] + " ");
  17.                 }
  18.                 System.out.println();
  19.             } else {
  20.                 for(int i = n - 1; i >= 0; i--){
  21.                     System.out.print(nums[i] + " ");
  22.                 }
  23.                 System.out.println();
  24.             }
  25.         }
  26.     }
  27. }

(6) *HJ106.字符串逆序

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         String s = in.nextLine();
  7.         String[] str = s.split(" ");
  8.         for(int i = 0; i < str.length; i++){
  9.             if(str[i].length() > 1){
  10.                 StringBuffer sf = new StringBuffer();
  11.                 sf.append(str[i]);
  12.                 str[i] = sf.reverse().toString();
  13.             }
  14.         }
  15.         for(int i = str.length -1; i >= 0 ; i--){
  16.             System.out.print(str[i] + " ");
  17.         }
  18.     }
  19. }

3. 排序（5题）

(1) HJ8.合并表记录

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         while(in.hasNext()){
  7.             int n = in.nextInt();
  8.             TreeMap<Integer,Integer> map = new TreeMap();
  9.             for(int i = 0; i < n; i++){
  10.                 int a = in.nextInt();
  11.                 int b = in.nextInt();
  12.                 map.put(a,map.getOrDefault(a,0) + b);
  13.             }
  14.             map.forEach((key,value) -> {
  15.                 System.out.println(key+" "+value);
  16.             });
  17.         }
  18.     }
  19. }

(2) *HJ14.字符串排序

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         List<String> list = new ArrayList();
  7.         while(in.hasNext()){
  8.             int n = in.nextInt();
  9.             for(int i = 0; i < n; i++){
  10.                 list.add(in.next());
  11.             }
  12.             Collections.sort(list);
  13.             for(String s : list){
  14.                 System.out.println(s);
  15.             }
  16.         }
  17.     }
  18. }

(3) HJ27.查找兄弟单词

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         String[] s = in.nextLine().split(" ");
  7.         int n = Integer.parseInt(s[0]);
  8.         String x = s[s.length - 2];
  9.         int k = Integer.parseInt(s[s.length - 1]);
  10.         List<String> list = new ArrayList();
  11.         for(String str : s){
  12.             if(isBrother(str,x)){
  13.                 list.add(str);
  14.             }
  15.         }
  16.         int size = list.size();
  17.         System.out.println(size);
  18.         if(size >= k){
  19.             Collections.sort(list);
  20.             System.out.println(list.get(k - 1));
  21.         }
  22.     }
  23.     
  24.     private static boolean isBrother(String str,String x){
  25.         if(str.equals(x) || str.length() != x.length()){
  26.             return false;
  27.         }
  28.         char[] c = str.toCharArray();
  29.         char[] ch = x.toCharArray();
  30.         Arrays.sort(c);
  31.         Arrays.sort(ch);
  32.         return String.valueOf(c).equals(String.valueOf(ch));
  33.     }
  34. }

(4) *NC37.合并区间

  1. import java.util.*;
  2. /**
  3.  * Definition for an interval.
  4.  * public class Interval {
  5.  *     int start;
  6.  *     int end;
  7.  *     Interval() { start = 0; end = 0; }
  8.  *     Interval(int s, int e) { start = s; end = e; }
  9.  * }
  10.  */
  11. public class Solution {
  12.     public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
  13.         ArrayList<Interval> res = new ArrayList();
  14.         int size = intervals.size();
  15.         if(size == 0){
  16.             return res;
  17.         }
  18.         Collections.sort(intervals,new Comparator<Interval>(){
  19.             public int compare(Interval o1, Interval o2){
  20.                 if(o1.start != o2.start){
  21.                     // 头升序
  22.                     return o1.start - o2.start;
  23.                 } else {
  24.                     // 尾升序
  25.                     return o1.end - o2.end;
  26.                 }
  27.             }
  28.         });
  29.         res.add(intervals.get(0));
  30.         int count = 0;
  31.         for(int i = 1; i < size; i++){
  32.             Interval o1 = intervals.get(i);
  33.             Interval o2 = res.get(count);
  34.             if(o1.start <= o2.end){
  35.                 if(o2.end < o1.end){
  36.                     o2.end = o1.end;
  37.                 }
  38.             } else{
  39.                 res.add(o1);
  40.                 count++;
  41.             }
  42.         }
  43.         return res;
  44.     }
  45. }

(5) *HJ68.成绩排序

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         while(in.hasNext()){
  7.             int n = in.nextInt();
  8.             int flag = in.nextInt();
  9.             String[] names = new String[n];
  10.             int[] grades = new int[n];
  11.             for(int i = 0; i < n; i++){
  12.                 names[i] = in.next();
  13.                 grades[i] = Integer.parseInt(in.next());
  14.             }
  15.             if(flag == 0){
  16.                 for(int i = 0; i<n; i++){
  17.                     for(int j = 0; j < n-1-i; j++){
  18.                         if(grades[j] < grades[j+1]){
  19.                             int g = grades[j];
  20.                             grades[j] = grades[j+1];
  21.                             grades[j+1] = g;
  22.                             String name = names[j];
  23.                             names[j] = names[j+1];
  24.                             names[j+1] = name;
  25.                         }
  26.                     }
  27.                 }
  28.             }else {
  29.                for(int i = 0; i<n; i++){
  30.                     for(int j = 0; j < n-1-i; j++){
  31.                         if(grades[j] > grades[j+1]){
  32.                             int g = grades[j];
  33.                             grades[j] = grades[j+1];
  34.                             grades[j+1] = g;
  35.                             String name = names[j];
  36.                             names[j] = names[j+1];
  37.                             names[j+1] = name;
  38.                         }
  39.                     }
  40.                 }
  41.             }
  42.             for(int i = 0; i< n; i++){
  43.                 System.out.println(names[i] + " " + grades[i]);
  44.             }
  45.         }
  46.     }
  47. }

4.栈（2题）

(1) NC52.括号序列

  1. import java.util.*;
  2.  
  3.  
  4. public class Solution {
  5.     /**
  6.      * 
  7.      * @param s string字符串 
  8.      * @return bool布尔型
  9.      */
  10.     public boolean isValid (String s) {
  11.         // write code here
  12.         if(s.length() < 2){
  13.             return false;
  14.         }
  15.         Stack<Character> st = new Stack();
  16.         for(int i = 0; i < s.length(); i++){
  17.             if(s.charAt(i) == '('){
  18.                 st.push(')');
  19.             }
  20.             else if(s.charAt(i) == '['){
  21.                 st.push(']');
  22.             }
  23.             else if(s.charAt(i) == '{'){
  24.                 st.push('}');
  25.             }
  26.             else if(st.isEmpty() || st.pop() != s.charAt(i)){
  27.                 return false;
  28.             }
  29.         }
  30.         return st.isEmpty();
  31.     }
  32. }

(2) *leetcode 1614.括号的最大嵌套深度

  1. class Solution {
  2.     public int maxDepth(String s) {
  3.         Stack<Character> st = new Stack();
  4.         int max = 0;
  5.         for(int i = 0; i < s.length(); i++){
  6.             if(s.charAt(i) == '('){
  7.                 st.push(')');
  8.             }
  9.             else if(s.charAt(i) == ')'){
  10.                 max = Math.max(max,st.size());
  11.                 st.pop();
  12.             }
  13.         }
  14.         return max;
  15.     }
  16. }

5. 排列组合（2题） 递归+回溯(dfs)

(1) *leetcode 面试题08.08.有重复字符串的排列组合

  1. class Solution {
  2.     public String[] permutation(String S) {
  3.         List<String> list = new ArrayList();
  4.         char[] c = S.toCharArray();
  5.         Arrays.sort(c);
  6.         boolean[] used = new boolean[c.length];
  7.         dfs(list,new StringBuilder(),used,c);
  8.         String[] str = new String[list.size()];
  9.         for(int i = 0; i < str.length; i++){
  10.             str[i] = list.get(i);
  11.         }
  12.         return str;
  13.     }
  14.  
  15.     public void dfs(List<String> list,StringBuilder sb, boolean[] used, char[] c){
  16.         if(sb.length() == c.length){
  17.             list.add(sb.toString());
  18.             return;
  19.         }
  20.         for(int i = 0; i < c.length; i++){
  21.             // 第i个字符未被使用
  22.             if(!used[i]){
  23.                 //i大于0 且 第 i-1个字符跟第i个字符相同 且 第i-1个字符未被使用
  24.                 if(i > 0 && c[i] == c[i-1] && !used[i - 1]){
  25.                     continue;
  26.                 } else {
  27.                     sb.append(c[i]);
  28.                     used[i] = true;
  29.                     dfs(list,sb,used,c);
  30.                     used[i] = false;
  31.                     sb.deleteCharAt(sb.length() - 1);
  32.                 }
  33.             }
  34.         }
  35.     }
  36. }

(2) leetcode 77.组合

  1. class Solution {
  2.     public List<List<Integer>> combine(int n, int k) {
  3.         int[] nums = new int[n];
  4.         for(int i = 1; i <= n; i++){
  5.             nums[i-1] = i;
  6.         }
  7.         List<List<Integer>> res = new ArrayList();
  8.         dfs(k,res,new ArrayList(),nums,0);
  9.         return res;
  10.     }
  11.  
  12.     public void dfs(int k,List<List<Integer>> res,List<Integer> list, int[] n, int j){
  13.         if(list.size() == k){
  14.             List<Integer> l = new ArrayList();
  15.             l.addAll(list);
  16.             res.add(l);
  17.             return;
  18.         }
  19.         for(int i = j; i < n.length; i++){
  20.                 list.add(n[i]);
  21.                 dfs(k,res,list,n,i+1);
  22.                 list.remove(list.size() - 1);
  23.         }
  24.     }
  25. }

6. 双指针（3题）

(1) *leetcode 674.最长连续递增序列

  1. class Solution {
  2.     public int findLengthOfLCIS(int[] nums) {
  3.         int max = 1;
  4.         int count = 1;
  5.         for(int j = 1; j < nums.length; j++){
  6.             if(nums[j] > nums[j - 1]){
  7.                 count++;
  8.             }
  9.             if(nums[j] <= nums[j - 1] || j == nums.length - 1){
  10.                 max = Math.max(max,count);
  11.                 count = 1;
  12.             }
  13.         }
  14.         return max;
  15.     }
  16. }

(2) NC17.最长回文子串

  1. import java.util.*;
  2.  
  3.  
  4. public class Solution {
  5.     public int getLongestPalindrome (String A) {
  6.         int n = A.length();
  7.         if(n < 2){
  8.             return n;
  9.         }
  10.         int max = 1;
  11.         for(int i = 0; i < n; i++){
  12.             max = Math.max(max,Math.max(fun(A,i,i),fun(A,i,i+1)));
  13.         }
  14.         return max;
  15.     }
  16.     
  17.     public int fun(String s,int begin,int end){
  18.         while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
  19.             begin--;
  20.             end++;
  21.         }
  22.         return end - begin - 1;
  23.     }
  24. }

(3) NC28.最小覆盖子串 滑动窗口

  1. import java.util.*;
  2.  
  3.  
  4. public class Solution {
  5.     public String minWindow (String S, String T) {
  6.         if(S.contains(T)){
  7.             return T;
  8.         }
  9.         int cnt = S.length() + 1;
  10.         int[] hash = new int[128];
  11.         for(int i = 0; i < T.length(); i++){
  12.             hash[T.charAt(i)] -= 1;
  13.         }
  14.         int slow = 0,fast = 0,left = -1,right = -1;
  15.         for(; fast< S.length(); fast++){
  16.             char c = S.charAt(fast);
  17.             hash[c]++;
  18.             while(check(hash)){
  19.                 if(cnt > fast - slow + 1){
  20.                     cnt = fast - slow + 1;
  21.                     left = slow;
  22.                     right = fast;
  23.                 }
  24.                 c = S.charAt(slow);
  25.                 hash[c]--;
  26.                 slow++;
  27.             }
  28.         }
  29.         if(left == -1){
  30.             return "";
  31.         }
  32.         return S.substring(left,right + 1);
  33.     }
  34.     
  35.     public boolean check(int[] hash){
  36.         for(int i = 0; i < hash.length; i++){
  37.            if(hash[i] < 0){
  38.                return false;
  39.            }
  40.         }
  41.         return true;
  42.     }
  43. }

7. 深搜（1题）

(1) HJ41.称砝码

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) throws Exception {
  7.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  8.         String line;
  9.         while ((line = reader.readLine()) != null) {
  10.             int n = Integer.parseInt(line);
  11.             String[] s = reader.readLine().split(" ");
  12.             String[] s2 = reader.readLine().split(" ");
  13.             int[] weight = new int[n];
  14.             int[] number = new int[n];
  15.             for (int i = 0; i < n; i++) {
  16.                 weight[i] = Integer.parseInt(s[i]);
  17.                 number[i] = Integer.parseInt(s2[i]);
  18.             }
  19.             boolean[] exist = new boolean[200000];
  20.             int[] arr = new int[20000];
  21.             arr[0]++;
  22.             for (int i = 0; i < n; i++) {
  23.                 for (int j = 0; j < number[i]; j++) {
  24.                     int index = arr[0];
  25.                     if (!exist[weight[i]]) {
  26.                         exist[weight[i]] = true;
  27.                         arr[++arr[0]] = weight[i];
  28.                     }
  29.                     for (int k = 1; k <= index; k++) {
  30.                         int sum = arr[k] + weight[i];
  31.                         if (!exist[sum]) {
  32.                             exist[sum] = true;
  33.                             arr[++arr[0]] = sum;
  34.                         }
  35.                     }
  36.                 }
  37.             }
  38.             System.out.println(arr[0]);
  39.         }
  40.     }
  41. }

8. 二叉树（2题）队列

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int[] levelOrder(TreeNode root) {
  12.         if(root == null) return new int[0];
  13.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  14.         List<Integer> list = new ArrayList();
  15.         queue.add(root);
  16.         while(!queue.isEmpty()){
  17.            TreeNode node = queue.poll();
  18.            list.add(node.val);
  19.            if(node.left != null){
  20.                queue.add(node.left);
  21.            }
  22.            if(node.right != null){
  23.                queue.add(node.right);
  24.            }
  25.         }
  26.         return list.stream().mapToInt(Integer::intValue).toArray();
  27.     }
  28. }

(1) *leetcode 剑指offer 32 — II.从上到下打印二叉树II

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public List<List<Integer>> levelOrder(TreeNode root) {
  12.         List<List<Integer>> res = new ArrayList();
  13.         if(root == null) return res;
  14.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  15.         queue.add(root);
  16.         while(!queue.isEmpty()){
  17.            List<Integer> list = new ArrayList();
  18.            int size = queue.size();
  19.            for(;size > 0; size--){
  20.             TreeNode node = queue.poll();
  21.             if(node != null){
  22.                 list.add(node.val);
  23.                 if(node.left != null){
  24.                     queue.add(node.left);
  25.                 }
  26.                 if(node.right != null){
  27.                 queue.add(node.right);
  28.                 }
  29.             }
  30.            }
  31.            res.add(list);
  32.         }
  33.         return res;
  34.     }
  35. }

(2) leetcode 剑指offer 32 — III.从上到下打印二叉树III

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public List<List<Integer>> levelOrder(TreeNode root) {
  12.         List<List<Integer>> res = new ArrayList();
  13.         if(root == null) return res;
  14.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  15.         queue.add(root);
  16.         while(!queue.isEmpty()){
  17.            List<Integer> list = new ArrayList();
  18.            int size = queue.size();
  19.            for(;size > 0; size--){
  20.             TreeNode node = queue.poll();
  21.             if(node != null){
  22.                 list.add(node.val);
  23.                 if(node.left != null){
  24.                     queue.add(node.left);
  25.                 }
  26.                 if(node.right != null){
  27.                     queue.add(node.right);
  28.                 }
  29.             }
  30.            }
  31.            res.add(list);
  32.         }
  33.         for(int i=1;i<res.size();i+=2){
  34.             Collections.reverse(res.get(i));
  35.         }
  36.         return res;
  37.     }
  38. }

9. 其他（6题）

(1) *HJ108.求最小公倍数

  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args) {
  6.         Scanner in=new Scanner(System.in);
  7.         int a=in.nextInt();
  8.         int b=in.nextInt();
  9.         System.out.println(a*b/gcd(a,b));
  10.     }
  11.  
  12.     private static int gcd(int a, int b) {
  13.         return b==0?a:gcd(b,a%b);
  14.     }
  15. }

(2) *HJ28.素数伴侣

  1. import java.util.*;
  2. public class Main {
  3.  
  4.     //这里包含了判断素数的方法
  5.     //小技巧！！！素数不是偶数，那么和是素数的话就是奇数+偶数
  6.     //那么可以分成两堆,一堆偶数，一堆奇数
  7.     //匈牙利算法，先到先得 能让就让
  8.     //有机会上，没机会创造机会也要上
  9.     public static void main(String[] args) {
  10.         // TODO Auto-generated method stub
  11.         Scanner scan = new Scanner(System.in);
  12.         while(scan.hasNext()){
  13.             int n = scan.nextInt();
  14.             int[] tempArray = new int[n];
  15.             for(int i = 0; i < n; i++){
  16.                 tempArray[i] = scan.nextInt();
  17.             }
  18.             ArrayList<Integer> evens = new ArrayList<Integer>();
  19.             ArrayList<Integer> odds = new ArrayList<Integer>();
  20.             for(int i = 0; i < n; i++) {
  21.                 if((tempArray[i] & 1) != 1) {
  22.                     evens.add(tempArray[i]);
  23.                 }else {
  24.                     odds.add(tempArray[i]);
  25.                 }
  26.             }
  27.             //下面开始才是重头戏
  28.             //用于标记那个奇数匹配了偶数,直接记录奇数的值，而不是奇数在奇数数组中的下标
  29.             int[] evensMatch =new int[evens.size()];
  30.             int result = 0;
  31.             //遍历奇数去匹配偶数
  32.             for(int i = 0; i < odds.size(); i++) {
  33.                 //每一步重新创建，也就是相当于清空
  34.                 //used数组用于标记某个某数位置是否
  35.                 int[] used = new int[evens.size()];
  36.                 //这里采用了匈牙利算法，先到先得
  37.                 if(find(odds.get(i), evens, used, evensMatch)) {
  38.                     result++;
  39.                 }
  40.             }
  41.             System.out.println(result);
  42.         }
  43.     }
  44.  
  45.     public static boolean isPrime(int num) {
  46.         for(int i = 2; i <= Math.sqrt(num); i++) {
  47.             if(num % i == 0) {
  48.                 return false;
  49.             }
  50.         }
  51.         return true;
  52.     }
  53.  
  54.     public static boolean find(int x, ArrayList<Integer> evens,int[] used, int[] evensMatch) {
  55.         //遍历偶数
  56.         //去检查当前传入的奇数能否与偶数哪些数匹配
  57.         for(int i = 0; i < evens.size(); i++) {
  58.             //如果当前偶数与传入的奇数匹配，并且当前偶数位还没有匹配过奇数
  59.             if(isPrime(x + evens.get(i)) && used[i] == 0) {
  60.                 //设置当前偶数位匹配为true，也就是 1
  61.                 used[i] = 1;
  62.                 //如果第i个偶数没有伴侣
  63.                 //或者第i个偶数原来有伴侣，并且该伴侣能够重新找到伴侣的话(这里有递归调用)
  64.                 //则奇数x可以设置为第i个偶数的伴侣
  65.                 //这里采用了匈牙利算法，能让则让
  66.                 if(evensMatch[i] == 0 || find(evensMatch[i], evens, used, evensMatch)) {
  67.                     evensMatch[i] = x;
  68.                     return true;
  69.                 }
  70.             }
  71.         }
  72.         //遍历完偶数都没有可以与传入奇数做伴侣的，该奇数只能孤独终老了
  73.         return false;
  74.     }
  75.  
  76. }

(3) *HJ60.查找组成一个偶数最接近的两个素数

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         int n = in.nextInt();
  7.         int i = n/2;
  8.         for(;i < n; i += 2){
  9.             if(i % 2 == 0 && i != 2){
  10.                 i++;
  11.             }
  12.             if(isPrime(n - i) && isPrime(i)){
  13.                 System.out.println(n - i);
  14.                 System.out.println(i);
  15.                 break;
  16.             }
  17.         }
  18.     }
  19.     
  20.     public static boolean isPrime(int num) {
  21.         for(int i = 2; i <= Math.sqrt(num); i++) {
  22.             if(num % i == 0) {
  23.                 return false;
  24.             }
  25.         }
  26.         return true;
  27.     }
  28. }

(4) *leetcode 994.腐烂的橘子 (BFS 广度搜索)

  1. class Solution {
  2. public int orangesRotting(int[][] grid) {
  3.     int M = grid.length;
  4.     int N = grid[0].length;
  5.     Queue<int[]> queue = new LinkedList<>();
  6.  
  7.     int count = 0; // count 表示新鲜橘子的数量
  8.     for (int r = 0; r < M; r++) {
  9.         for (int c = 0; c < N; c++) {
  10.             if (grid[r][c] == 1) {
  11.                 count++;
  12.             } else if (grid[r][c] == 2) {
  13.                 queue.add(new int[]{r, c});
  14.             }
  15.         }
  16.     }
  17.  
  18.     int round = 0; // round 表示腐烂的轮数，或者分钟数
  19.     while (count > 0 && !queue.isEmpty()) {
  20.         round++;
  21.         int n = queue.size();
  22.         for (int i = 0; i < n; i++) {
  23.             int[] orange = queue.poll();
  24.             int r = orange[0];
  25.             int c = orange[1];
  26.             if (r-1 >= 0 && grid[r-1][c] == 1) {
  27.                 grid[r-1][c] = 2;
  28.                 count--;
  29.                 queue.add(new int[]{r-1, c});
  30.             }
  31.             if (r+1 < M && grid[r+1][c] == 1) {
  32.                 grid[r+1][c] = 2;
  33.                 count--;
  34.                 queue.add(new int[]{r+1, c});
  35.             }
  36.             if (c-1 >= 0 && grid[r][c-1] == 1) {
  37.                 grid[r][c-1] = 2;
  38.                 count--;
  39.                 queue.add(new int[]{r, c-1});
  40.             }
  41.             if (c+1 < N && grid[r][c+1] == 1) {
  42.                 grid[r][c+1] = 2;
  43.                 count--;
  44.                 queue.add(new int[]{r, c+1});
  45.             }
  46.         }
  47.     }
  48.  
  49.     if (count > 0) {
  50.         return -1;
  51.     } else {
  52.         return round;
  53.     }
  54. }
  55. }

(5) leetcode 204.计数质数

  1. class Solution {
  2.     public int countPrimes(int n) {
  3.         boolean[] isPrim = new boolean[n];
  4.         Arrays.fill(isPrim, true);
  5.         // 从 2 开始枚举到 sqrt(n)。
  6.         for (int i = 2; i * i < n; i++) {
  7.             // 如果当前是素数
  8.             if (isPrim[i]) {
  9.                 // 就把从 i*i 开始，i 的所有倍数都设置为 false。
  10.                 for (int j = i * i; j < n; j+=i) {
  11.                     isPrim[j] = false;
  12.                 }
  13.             }
  14.         }
  15.  
  16.         // 计数
  17.         int cnt = 0;
  18.         for (int i = 2; i < n; i++) {
  19.             if (isPrim[i]) {
  20.                 cnt++;
  21.             }
  22.         }
  23.         return cnt;
  24.     }
  25. }

(6) HJ25. 数据分类处理

  1. jimport java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args){
  6.         Scanner in = new Scanner(System.in);
  7.         int n = in.nextInt();
  8.         String str = in.nextLine();
  9.         String[] strs = str.split(" ");
  10.         int r = in.nextInt();
  11.         Set<Integer> set = new  TreeSet();
  12.         for(int i = 0; i < r; i++){
  13.             set.add(in.nextInt());
  14.         }
  15.         List<String> res = new ArrayList();
  16.         List<String> list = new ArrayList();
  17.         for(Integer s : set){
  18.             if(str.contains(String.valueOf(s))){
  19.                 res.add(String.valueOf(s));
  20.                 int count = 0;
  21.                 for(int i = 0;i < strs.length; i++){
  22.                     if(strs[i].contains(String.valueOf(s))){
  23.                         count++;
  24.                         list.add(String.valueOf(i - 1));
  25.                         list.add(strs[i]);
  26.                     }
  27.                 }
  28.                 res.add(String.valueOf(count));
  29.                 res.addAll(list);
  30.                 list.clear();
  31.             }
  32.         }
  33.         System.out.print(res.size() + " ");
  34.         for(String s1 : res){
  35.             System.out.print(s1 + " ");
  36.         }
  37.     }
  38. }

面试手撕代码

（1）递归：NC68.跳台阶

  1. public class Solution {
  2.     public int jumpFloor(int target) {
  3.         if(target == 1 || target == 0){
  4.             return 1;
  5.         }
  6.         if(target == 2){
  7.             return 2;
  8.         }
  9.         return jumpFloor(target - 1) + jumpFloor(target - 2);
  10.     }
  11. } 
  1. import java.util.*;
  2. public class Solution {
  3.     Map<Integer,Integer> map = new HashMap();
  4.     public int jumpFloor(int target) {
  5.         if(target == 1 || target == 0){
  6.             return 1;
  7.         }
  8.         if(target == 2){
  9.             return 2;
  10.         }
  11.         if(map.containsKey(target)){
  12.             return map.get(target);
  13.         } else{
  14.             map.put(target,jumpFloor(target - 1) + jumpFloor(target - 2));
  15.             return map.get(target);
  16.         }
  17.     }
  18. }

（2）猴子爬山

  1. import java.util.*;
  2. public class Solution {
  3.     Map<Integer,Integer> map = new HashMap();
  4.     public int jumpFloor(int target) {
  5.         if(target == 1 && target == 2){
  6.             return 1;
  7.         }
  8.         if(target == 3){
  9.             return 2;
  10.         }
  11.         if(map.containsKey(target)){
  12.             return map.get(target);
  13.         } else{
  14.             map.put(target,jumpFloor(target - 1) + jumpFloor(target - 3));
  15.             return map.get(target);
  16.         }
  17.     }
  18. }

（3）输出字符串出现次数最少的字符

  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args){
  6.         Scanner in = new Scanner(System.in);
  7.         String s = in.next();
  8.         Map<Character,Integer> map = new HashMap();
  9.         for(char c : s.toCharArray()){
  10.             map.put(c,map.getOrDefault(c,1)+1);
  11.         }
  12.         int min = Integer.MAX_VALUE;
  13.         for(int i : map.values()){
  14.             min = Math.min(min,i);
  15.         }
  16.         for(char c : s.toCharArray()){
  17.             if(map.get(c) == min){
  18.                 System.out.print(c);
  19.             }
  20.         }
  21.     }
  22. }

（4）正方形矩阵顺时针旋转90度

  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args){
  6.         Scanner in = new Scanner(System.in);
  7.         while(in.hasNext()){
  8.             int n = in.nextInt();
  9.             int[][] nums = new int[n][n];
  10.             for(int i = 0; i < n; i++){
  11.                 for(int j = 0; j < n; j++){
  12.                     nums[i][j] = in.nextInt();
  13.                 }
  14.             }
  15.             //对角线翻转
  16.             for(int i = 0; i < n; i++){
  17.                 for(int j = 0; j < i; j++){
  18.                     nums[i][j] = nums[i][j] ^ nums[j][i];
  19.                     nums[j][i] = nums[j][i] ^ nums[i][j];
  20.                     nums[i][j] = nums[j][i] ^ nums[i][j];
  21.                 }
  22.             }
  23.             // 中轴线翻转
  24.             for(int i = 0; i < n; i++){
  25.                 for(int j = 0; j < n/2; j++){
  26.                     nums[i][j] = nums[i][j] ^ nums[i][n-j-1];
  27.                     nums[i][n-j-1] = nums[i][n-j-1] ^ nums[i][j];
  28.                     nums[i][j] = nums[i][n-j-1] ^ nums[i][j];
  29.                 }
  30.             }
  31.             
  32.             // 输出
  33.             for(int i = 0; i < n; i++){
  34.                 for(int j = 0; j < n; j++)
  35.                     System.out.print(nums[i][j] + " ");
  36.                 System.out.println();
  37.             }
  38.         }
  39.     }
  40. }

  1. import java.util.*;
  2.  
  3. public class Solution {
  4.     public int[][] rotateMatrix(int[][] mat, int n) {
  5.         // 对角线对折
  6.         for(int i = 0; i < n; i++){
  7.             for(int j = 0; j < i; j++){
  8.                 mat[i][j] = mat[i][j] ^ mat[j][i];
  9.                 mat[j][i] = mat[i][j] ^ mat[j][i];
  10.                 mat[i][j] = mat[i][j] ^ mat[j][i];
  11.             }
  12.         }
  13.         // 中轴线对折
  14.         for(int i = 0; i < n; i++){
  15.             for(int j = 0; j < n/2; j++){
  16.                 mat[i][j] = mat[i][j] ^ mat[i][n-j-1];
  17.                 mat[i][n-j-1] = mat[i][j] ^ mat[i][n-j-1];
  18.                 mat[i][j] = mat[i][j] ^ mat[i][n-j-1];
  19.             }
  20.         }
  21.         return mat;
  22.     }
  23. }

（5）链表逆序

  1. /*
  2. public class ListNode {
  3.     int val;
  4.     ListNode next = null;
  6.     ListNode(int val) {
  7.         this.val = val;
  8.     }
  9. }*/
  10. public class Solution {
  11.     public ListNode ReverseList(ListNode head) {
  12.         ListNode pre = null;
  13.         ListNode next = null;
  14.         while(head != null){
  15.             next = head.next;
  16.             head.next = pre;
  17.             pre = head;
  18.             head = next;
  19.         }
  20.         return pre;
  21.     }
  22. }

（6）租房信息查询系统

int instance = Math.abs(x1-x2)+Math.abs(y1-y2);

（7）最长公共前缀

  1. class Solution {
  2.     public String longestCommonPrefix(String[] strs) {
  3.         if(strs.length == 0) return "";
  4.         String s = strs[0];
  5.         for(String st : strs){
  6.             while(!st.startsWith(s)){
  7.                 if(s.length() == 0) return "";
  8.                 s = s.substring(0,s.length()-1);
  9.             }
  10.         }
  11.         return s;
  12.     }
  13. }

（8）跳跃游戏I II

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int n = 1;
  4.         for(int i = nums.length - 2; i >= 0; i--){
  5.             if(nums[i] >= n){
  6.                 n = 1;
  7.             }else{
  8.                 n++;
  9.             }
  10.             if(i == 0 && n > 1){
  11.                 return false;
  12.             }
  13.         }
  14.         return true;
  15.     }
  16. }

  1. class Solution {
  2.     public int jump(int[] nums) {
  3.         int max = 0;
  4.         int end = 0;
  5.         int step = 0;
  6.         for(int i = 0; i < nums.length - 1; i++){
  7.             max = Math.max(max, nums[i] + i);
  8.             if (i == end){
  9.                 end = max;
  10.                 step++;
  11.             }
  12.         }
  13.         return step;
  14.     }
  15. }

（9）盛最多水的容器

  1. class Solution {
  2.     public int maxArea(int[] height) {
  3.         int max = 0;
  4.         for(int i = 0, j = height.length - 1; i < j;){
  5.             int minHeight = height[i] < height[j] ? height[i++] : height[j--];
  6.             max = Math.max(max,(j - i + 1) * minHeight);
  7.         }
  8.         return max;
  9.     }
  10. }

（10）字典序排数

  1. class Solution {
  2.     public List<Integer> lexicalOrder(int n) {
  3.         List<String> nums = new ArrayList();
  4.         for(int i = 0; i < n; i++){
  5.             nums.add(String.valueOf(i+1));
  6.         }
  7.         Collections.sort(nums);
  8.         List<Integer> num = new ArrayList();
  9.         for(int i = 0; i < n; i++){
  10.             num.add(Integer.parseInt(nums.get(i)));
  11.         }
  12.         return num;
  13.     }
  14. }
  1. class Solution {
  2.     List<Integer> ans = new ArrayList<>();
  3.     public List<Integer> lexicalOrder(int n) {
  4.         for (int i = 1; i <= 9; i++) dfs(i, n);
  5.         return ans;
  6.     }
  7.     void dfs(int cur, int limit) {
  8.         if (cur > limit) return ;
  9.         ans.add(cur);
  10.         for (int i = 0; i <= 9; i++) dfs(cur * 10 + i, limit);
  11.     }
  12. }
  1. class Solution {
  2.     public List<Integer> lexicalOrder(int n) {
  3.         List<Integer> ans = new ArrayList<>();
  4.         for (int i = 0, j = 1; i < n; i++) {
  5.             ans.add(j);
  6.             if (j * 10 <= n) {
  7.                 j *= 10;
  8.             } else {
  9.                 while (j % 10 == 9 || j + 1 > n) j /= 10;
  10.                 j++;
  11.             }
  12.         }
  13.         return ans;
  14.     }
  15. }

（11）消除游戏

  1. class Solution {
  2.     public int lastRemaining(int n) {
  3.         int head = 1;
  4.         int step = 1;
  5.         boolean left = true;
  6.         
  7.         while (n > 1) {
  8.             //从左边开始移除 or（从右边开始移除，数列总数为奇数）
  9.             if (left || n % 2 != 0) {
  10.                 head += step;
  11.             }
  12.             step *= 2; //步长 * 2
  13.             left = !left; //取反移除方向
  14.             n /= 2; //总数 / 2
  15.         }
  16.  
  17.         return head;
  18.     }
  19. }

（12）验证回文串

  1. class Solution {
  2.     public boolean isPalindrome(String s) {
  3.         StringBuilder sb = new StringBuilder();
  4.         for(char c : s.toCharArray()){
  5.             if(Character.isLetterOrDigit(c)){
  6.                 sb.append(Character.toLowerCase(c));
  7.             }
  8.         }
  9.         String s_re = new StringBuilder(sb).reverse().toString();
  10.         return sb.toString().equals(s_re);
  11.     }
  12. }

（13）最长回文子串

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         int n = s.length();
  4.         if(n < 2) return s;
  5.         int start = 0, end = 0;
  6.         for(int i = 0; i < n; i++){
  7.             int max = Math.max(fun(s,i,i),fun(s,i,i+1));
  8.             if(max > end - start){
  9.                 start = i - (max - 1) / 2;
  10.                 end = i + max / 2;
  11.             }
  12.         }
  13.         return s.substring(start,end+1);
  14.     }
  15.  
  16.     public int fun(String s,int begin,int end){
  17.         while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
  18.             begin--;
  19.             end++;
  20.         }
  21.         return end - begin - 1;
  22.     }
  23. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/612081
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号