按层打印二叉树（中序和前序）

https://exercise.acmcoder.com/online/online_judge_ques?ques_id=4172&konwledgeId=169
image.png

  1. package other;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  7. public class Main4 {
  8.     public static void main(String[] args) {
  9.         //452 3  1后序  425  1  3中序
  10.         // 1 245 3 前序   425 1 3  i-inl
  12.         Scanner input = new Scanner(System.in);
  13.         int num = input.nextInt();
  15.         int[] pre = new int[num];
  16.         int[] in = new int[num];
  17.         for (int i = 0; i < num; i++) {
  18.             pre[i] = input.nextInt();
  19.         }
  21.         for (int i = 0; i < num; i++) {
  22.             in[i] = input.nextInt();
  23.         }
  25.         Node head =  createTree(pre,0,pre.length-1,in,0,in.length-1);
  26.         printTree(head,num);
  27.     }
  29.     public static int findRoot(int root,int[] in,int il,int ir){
  30.         for (int i = il; i <= ir; i++) {
  31.             if(root == in[i]){
  32.                 return i;
  33.             }
  34.         }
  35.         return -1;
  36.     }
  38.     public static void printTree(Node head,int num){
  39.         Queue<Node> q = new LinkedList<>();
  40.         q.add(head);
  41.         int i = 0;
  42.         while(!q.isEmpty()){
  43.             Node n = q.poll();
  44.             i++;
  45.             System.out.print(n.val);
  46.             if(i<num){
  47.                 System.out.print(" ");
  48.             }
  49.             if(n.left!=null){
  50.                 q.add(n.left);
  51.             }
  52.             if(n.right!=null){
  53.                 q.add(n.right);
  54.             }
  55.         }
  56.     }
  58.     public static Node createTree(int[] pre,int pl,int pr,int[] in,int il,int ir){
  59.         if(pl>pr||il>ir){
  60.             return null;
  61.         }
  62.         Node node = new Node();
  63.         node.val = pre[pl];
  64.         int i  = findRoot(pre[pl],in,il,ir);
  65.         node.left = createTree(pre,pl+1,pl+i-il,in,il,i-1);
  66.         node.right = createTree(pre,pl+i-il+1,pr,in,i+1,ir);
  67.         return node;
  68.     }
  70.     private static class Node{
  71.         public int val;
  72.         public Node left;
  73.         public Node right;
  76.     }
  79. }

utf8编码器 业务题

image.png

  1. package other;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Scanner;
  7. public class Main3 {
  8.     public static void main(String[] args) {
  9.         Scanner in = new Scanner(System.in);
  11.         while(in.hasNext()){
  12.             String str = in.nextLine();
  13.             String[] arr = str.split("\\s+");
  14.             int len = arr.length;
  15.             int[] nums = new int[len];
  16.             for(int i = 0; i < len; ++i){
  17.                 nums[i] = Integer.parseInt(arr[i]);
  18.             }
  20.             int i = 0;
  21.             List<Integer> ans = new ArrayList<>();
  22.             boolean isOk = true;
  24.             while(i<len && isOk){
  25.                 int temp = 0;
  26.                 if(nums[i]<128){
  27.                     //0xxxxxxx
  28.                     ans.add(nums[i++]);
  29.                 }else if(nums[i]<224){
  30.                     //110xxxxx 10xxxxxx
  31.                     for (int j = 0; j < 2; j++) {
  32.                         if(j==0){
  33.                             nums[i]-=192;
  34.                         }else if(i<len && nums[i]>=128&&nums[i]<192){
  35.                             nums[i]-=128;
  36.                         }else{
  37.                             isOk =false;
  38.                         }
  39.                         if(isOk){
  40.                             temp += nums[i++]*Math.pow(2,(1-j)*6);
  41.                         }
  42.                     }
  43.                     ans.add(temp);
  44.                 }else if(nums[i]<240){
  45.                     //1110
  46.                     for (int j = 0; j < 3; j++) {
  47.                         if(j==0){
  48.                             nums[i]-=224;
  49.                         }else if(i<len && nums[i]>=128&&nums[i]<192){
  50.                             nums[i]-=128;
  51.                         }else{
  52.                             isOk =false;
  53.                         }
  54.                         if(isOk){
  55.                             temp += nums[i++]*Math.pow(2,(2-j)*6);
  56.                         }
  57.                     }
  58.                     ans.add(temp);
  59.                 }else if(nums[i]<248){
  60.                     //11110
  61.                     for (int j = 0; j < 4; j++) {
  62.                         if(j==0){
  63.                             nums[i]-=240;
  64.                         }else if(i<len && nums[i]>=128&&nums[i]<192){
  65.                             nums[i]-=128;
  66.                         }else{
  67.                             isOk =false;
  68.                         }
  69.                         if(isOk){
  70.                             temp += nums[i++]*Math.pow(2,(3-j)*6);
  71.                         }
  72.                     }
  73.                     ans.add(temp);
  74.                 }else if(nums[i]<252){
  75.                     //111110
  76.                     for (int j = 0; j < 5; j++) {
  77.                         if(j==0){
  78.                             nums[i]-=248;
  79.                         }else if(i<len && nums[i]>=128&&nums[i]<192){
  80.                             nums[i]-=128;
  81.                         }else{
  82.                             isOk =false;
  83.                         }
  84.                         if(isOk){
  85.                             temp += nums[i++]*Math.pow(2,(4-j)*6);
  86.                         }
  87.                     }
  88.                     ans.add(temp);
  89.                 }else if(nums[i]<254){
  90.                     //1111110
  91.                     for (int j = 0; j < 6; j++) {
  92.                         if(j==0){
  93.                             nums[i]-=252;
  94.                         }else if(i<len && nums[i]>=128&&nums[i]<192){
  95.                             nums[i]-=128;
  96.                         }else{
  97.                             isOk =false;
  98.                         }
  99.                         if(isOk){
  100.                             temp += nums[i++]*Math.pow(2,(5-j)*6);
  101.                         }
  102.                     }
  103.                     ans.add(temp);
  104.                 }else{
  105.                     isOk=false;
  106.                     break;
  107.                 }
  108.             }
  109.             if(isOk){
  110.                 for (int j = 0; j < ans.size() ; j++) {
  111.                         System.out.print(ans.get(j)+" ");
  112.                 }
  113.             }else{
  114.                 System.out.print("no");
  115.             }
  116.             System.out.println();
  117.         }
  120.     }
  121. }

IP过滤器 前缀树

https://www.nowcoder.com/questionTerminal/8389e1ccd47d40ba859c2497a428d0ca
image.png

自己做的前缀树法

  1. package mypractice;
  3. import java.util.HashMap;
  4. import java.util.Map;
  5. import java.util.Scanner;
  7. public class Main2 {
  8.     public static void main(String[] args) {
  9.         Scanner in = new Scanner(System.in);
  10.         int N = in.nextInt();
  11.         int M = in.nextInt();
  12.         in.nextLine();
  13.         Node head = new Node(new HashMap<String,Node>());
  14.         for (int i = 0; i < N; i++) {
  15.             String s = in.nextLine();
  16.             String[] rule = s.split("\\.");
  17.             Node cur = head;
  18.             for (int j = 0; j < rule.length ; j++) {
  19.                 if(!cur.children.containsKey(rule[j])){
  20.                     cur.children.put(rule[j],new Node(new HashMap<>()));
  21.                 }
  22.                 cur = cur.children.get(rule[j]);
  23.             }
  24.             cur.isEnd=true;
  25.         }
  26.         for(int i=0;i<M;i++){
  27.             String s = in.nextLine();
  28.             String[] ip = s.split("\\.");
  29.             boolean res = search(head,ip);
  30.             System.out.print((res ? 1 : 0)+" ");
  31.         }
  32.     }
  34.     private static boolean search(Node head,String[] ip){
  35.         Node cur = head;
  36.         if(cur.children.containsKey(ip[0])){
  37.             cur = cur.children.get(ip[0]);
  38.             for (int i = 1; i < ip.length ; i++) {
  39.                 if(cur.children.containsKey(ip[i])){
  40.                     cur = cur.children.get(ip[i]);
  41.                 }else if(cur.children.containsKey("*")){
  42.                     return true;
  43.                 }else{
  44.                     break;
  45.                 }
  46.             }
  47.             if(cur.isEnd)return true;
  48.         }
  49.         cur = head;
  50.         if(cur.children.containsKey("*")){
  51.             cur = cur.children.get("*");
  52.             // ip地址的第一个 第二个 第三个都可以用*去匹配
  53.             for (int i = 3; i >= 1 ; i--) {
  54.                 boolean res = help(i,ip,cur);
  55.                 if(res)return true;
  56.             }
  57.         }
  58.         return false;
  59.     }
  61.     private static boolean help(int i,String[] ip,Node cur){
  62.         for (; i <ip.length ; i++) {
  63.             if(cur.children.containsKey(ip[i])){
  64.                 cur = cur.children.get(ip[i]);
  65.             }
  66.         }
  67.         return cur.isEnd;
  68.     }
  70.     private static class Node{
  71.         public boolean isEnd;
  72.         public Map<String,Node> children;
  74.         public Node(Map<String, Node> children) {
  75.             isEnd = false;
  76.             this.children = children;
  77.         }
  78.     }
  80. }

暴力法

/**
 * 前缀 后缀 的匹配问题 easy
 */

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        sc.nextLine();

        //读取规则
        String[] patterns = new String[N];
        for(int i =0 ;i < N;i++){
            patterns[i] = sc.nextLine();
        }

        //读取IP
        String[] IPs = new String[M];
        for(int i = 0;i < M; i++){
            IPs[i] = sc.nextLine();
        }

        //暴力匹配
        for(int i = 0; i < IPs.length;i++){
            boolean lock = false;
            for(int j = 0; j < patterns.length;j++){
                String t = "";
                if(patterns[j].charAt(0) == '*'){
                    t = patterns[j].replace("*","");
                    if(IPs[i].endsWith(t)){
                        System.out.print(1 + " ");
                        lock = true;
                        break;
                    }
                }else if(patterns[j].charAt(patterns[j].length()-1) == '*'){
                    t = patterns[j].replace("*","");
                    if(IPs[i].startsWith(t)){
                        System.out.print(1 + " ");
                        lock = true;
                        break;
                    }
                }else{

                    if(patterns[j].equals(IPs[i])){
                        System.out.print(1 + " ");
                        lock = true;
                        break;
                    }
                }
            }
            if(lock == false){
                System.out.print(0 + " ");
            }
        }
    }
}

排队问题 动态规划

image.png
https://www.nowcoder.com/questionTerminal/5b36556ae602486f96be163c1ee21f1f

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] score = new int[n];
        for (int i = 0; i < score.length; i++) {
            score[i] = in.nextInt();
        }
        int k = in.nextInt();
        int d = in.nextInt();
        int[][] maxdp = new int[k][n];
        int[][] mindp = new int[k][n];
        //j位置结束 选取i+1个人能力最大值   i:0~k-1
        for (int i = 0; i < n; i++) {
            maxdp[0][i] = score[i];
            mindp[0][i] = score[i];
        }
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < k; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = j-1; p >=Math.max(0,j-d) ; p--) {
                    maxdp[i][j] = Math.max(maxdp[i][j],maxdp[i-1][p]*score[j]);
                    maxdp[i][j] = Math.max(maxdp[i][j],mindp[i-1][p]*score[j]);
                    mindp[i][j] = Math.min(mindp[i][j],mindp[i-1][p]*score[j]);
                    mindp[i][j] = Math.min(mindp[i][j],maxdp[i-1][p]*score[j]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            max = Math.max(maxdp[k-1][i],max);
        }
        System.out.println(max);
    }
}