华为算法岗笔试4.20复盘

这次笔试和以前不一样算法和软开都考了二叉树，考法基本相同，求二叉树的子节点。第二题是常用的拓扑排序，第三题是一个单调栈计算器。与以前的第一题字符串处理，第三题图有所不同。

1、按照路径返回子节点

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class T1 {
    public static TreeNode result;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String s = sc.nextLine();
            if (s.length()==0) break;
            String[] substring = s.substring(1, s.length() - 1).split(",");
            int [] nums=new int[substring.length];
            for (int i=0;i<substring.length;i++){
                nums[i]=Integer.parseInt(substring[i]);
            }
            String [] s1 = sc.nextLine().substring(1).split("/");
            int [] son=new int[s1.length];
            for (int i=0;i<son.length;i++){
                son[i]=Integer.parseInt(s1[i]);
            }
            TreeNode father=create(nums);
            result=new TreeNode();
            helper(father,son,1);
            ArrayList<Integer> list = CengCi(result);

            System.out.println(Arrays.toString(list.toArray()));
        }
    }
    //创建二叉树
    private static TreeNode create(int [] arr){
        TreeNode root=new TreeNode();
        List<TreeNode> dataS=new ArrayList<>();
        for (int ele:arr){
            dataS.add(new TreeNode(ele));
        }
        root=dataS.get(0);
        for (int i=0;i<dataS.size()/2;i++){
            if (dataS.get(i*2+1).val!=0) {
                dataS.get(i).left = dataS.get(i * 2 + 1);
            }
            if (i*2+2<dataS.size()&&dataS.get(i*2+2).val!=0){
                dataS.get(i).right=dataS.get(i*2+2);
            }
        }
        return root;
    }
    //dfs循环
    public static void helper(TreeNode root,int [] path,int i){
        if(i==path.length-1){

            if(root.left!=null && root.left.val == path[i]){
                result=root.left;
                return;
            }else if(root.right!=null && root.right.val == path[i]){

                result=root.right;
                return;
            }
        }

        if (root.left != null && root.left.val == path[i]) {
            helper(root.left, path, i + 1);
        } else if (root.right != null && root.right.val == path[i]) {
            helper(root.right, path, i + 1);
        }

    }
    //层次遍历
    public static ArrayList<Integer> CengCi(TreeNode root){
        ArrayList<Integer> list=new ArrayList<>();
        ArrayList<TreeNode > queue=new ArrayList<>();
        if (root==null) return list;
        queue.add(root);
        while (queue.size()!=0){
            TreeNode temp=queue.remove(0);
            if (temp.left!=null&&temp.left.val!=0){
                queue.add(temp.left);

            }
            if (temp.right!=null&&temp.right.val!=0){
                queue.add(temp.right);
            }
            if (temp.val!=0) {
                list.add(temp.val);
            }
        }
        return list;
    }
}

`

2、猪场防疫

import java.util.*;

public class T2 {
    public static int [][] graph;
    public static List<Integer> tu;
    public static List<List<Integer>> lists;
    public static int index;
    public static int head;
    public static int start;
    public static int n;
    public static int [] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String s = sc.nextLine();
            if (s.length()==0) break;
            n=Integer.parseInt(s);
            int m=Integer.parseInt(sc.nextLine());
            graph=new int[n][n];
            visited=new int[n];
            lists=new ArrayList<>();
            for (int i=0;i<m;i++){
                String [] sss= sc.nextLine().split(" ");
                for (int j=1;j<sss.length;j++){
                    graph[Integer.parseInt(sss[j])][Integer.parseInt(sss[0])]=1;
                }
            }
            String [] ss= sc.nextLine().split(" ");
            start=Integer.parseInt(ss[0]);
            head=Integer.parseInt(ss[1]);

            tu=new ArrayList<>();
            if (!dfs(head)){
                System.out.println(-1);
            }else {
                lists.add(new ArrayList<>(tu));
            }
            tu=new ArrayList<>();
            visited=new int[n];
            if (dfs(start)){
                lists.add(new ArrayList<>(tu));
            }
            boolean valid=false;

            for (int j=0;j<lists.get(0).size();j++){
                if (lists.get(0).get(j)==start){
                    valid=true;
                    System.out.println(lists.get(0).size()-j);
                    break;
                }
            }
            boolean flag=false;
            if (Objects.equals(lists.get(0).get(0), lists.get(1).get(0))) {
                for (int i = 0; i < lists.get(1).size() && !valid; i++) {
                    if (!Objects.equals(lists.get(0).get(i), lists.get(1).get(i))) {
                        System.out.println(lists.get(1).size() - i + lists.get(0).size() - i + 1);
                        flag = true;
                        break;
                    }
                }
            }
            if (!valid&&!flag){
                System.out.println(-1);
            }
        }
    }
    private static boolean dfs(int i){
        if (visited[i]==1) return true;
        else if (visited[i]==-1) return false;
        visited[i]=-1;
        for (int j=0;j<n;j++){
            if (graph[i][j]>0){
                if (!dfs(j)) return false;
            }
        }
        if (i!=head) tu.add(i);
        visited[i]=1;
        return true;
    }
}

3、多进制计算器

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String s = sc.nextLine();
            int n=Integer.parseInt(sc.nextLine());
            int calculate = (int)calculate(s,n);
            if (n==2){
                System.out.println(dToB(calculate));
            }else if (n==8){
                System.out.println(d2B(calculate));
            }else if (n==16){
                System.out.println(d2H(calculate));
            }else {
                System.out.println(calculate);
            }
         }
    }
    public static double calculate(String s,int n) {
        List<Character> list = new ArrayList<>();
        for(int i = 0; i < s.length(); i++)
            list.add(s.charAt(i));
        return helper(list,n);
    }
    public static double helper(List<Character> s,int n){
        Stack<Double> stack = new Stack<>();
        char sign = '+';
        double num = 0, res = 0;
        while(s.size() > 0)
        {
            char c = s.remove(0);
            if (Character.isDigit(c)||(c<='f'&&c>='a'))
            {
                if (n!=16) {
                    num = n * num + (c - '0');  //包含大于等于10的数字
                }else {
                    double temp=c - '0';
                    if (c=='a'){
                        temp=10;
                    }else if (c=='b'){
                        temp=11;
                    }else if (c=='c'){
                        temp=12;
                    }else if (c=='d'){
                        temp=13;
                    }else if (c=='e'){
                        temp=14;
                    }else if (c=='f'){
                        temp=15;
                    }
                    num = n * num +temp;
                }
            }
            if (c == '(')
                num = helper(s,n);
            if ((!Character.isDigit(c) && c != ' ') || s.size() == 0)
            {
                if (sign == '+')
                    stack.push(num);
                else if (sign == '-')
                    stack.push(-num);
                else if (sign == '*')
                {
                    stack.push(stack.pop() * num);
                }
                else if (sign == '/')
                {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
            if (c == ')')
            {
                break;
            }
        }
        while (!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }
    public static String dToB(int a){
        StringBuilder str=new StringBuilder();
        while (a > 0) {
            //因为上面我们说了二进制需要我们倒着写，所以干脆就把第一个余数存到数组最后一位
            str.append(a % 2);
            //上面算的是余数，a/=2是为了算下次a的值
            a /= 2;
        }
        return str.reverse().toString();
    }
    public static String d2B(int a){
        StringBuilder str=new StringBuilder();
        while (a > 0) {
            //因为上面我们说了二进制需要我们倒着写，所以干脆就把第一个余数存到数组最后一位
            str.append(a % 8);
            //上面算的是余数，a/=2是为了算下次a的值
            a /= 8;
        }
        return str.reverse().toString();
    }
    public static String d2H(int a){
        StringBuilder str=new StringBuilder();
        while (a > 0) {
            //因为上面我们说了二进制需要我们倒着写，所以干脆就把第一个余数存到数组最后一位
            int temp=a%16;
            if (temp==10){
                str.append("a");
            }else if (temp==11){
                str.append("b");
            }else if (temp==12){
                str.append("c");
            }else if (temp==13){
                str.append("d");
            }else if (temp==14){
                str.append("e");
            }else if (temp==15){
                str.append("f");
            }else {
                str.append(temp);
            }
            //上面算的是余数，a/=2是为了算下次a的值
            a /= 16;
        }
        return str.reverse().toString();
    }