面经整理(4)

基础

读取输入

// 多行输入元素，其中第一行几个数字表示下面几行的个数

import java.util.Arrays;
import java.util.Scanner;

public class myScanner {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		System.out.println("输入：");
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		int[] num1 = new int[m];
		int[] num2 = new int[n];
		// 换成其他数据类型也一样，其他数值类型就修改int跟nextInt就可以了，
		//String就把nextInt()换成next()
		for(int i = 0; i < m; i ++) {
			num1[i] = sc.nextInt();  // 一个一个读取
		}
		for(int i = 0; i < n; i ++) {
			num2[i] = sc.nextInt();
		}
	}
}

//一行输入多个参数
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();  // 读取一行

//第一行一个数字，后面每行按字符串读取
Scanner sc = new Scanner(System.in);
int line = sc.nextInt();
sc.nextLine();  // 很重要，跳到第二行
// 若直接确定行数，注释掉上面两行，加入下面一行
String[] strArr = new String[line];
// 从第二行开始读取
for(int i = 0; i < line; i++) {
    strArr[i] = sc.nextLine();
}

重写hash、equals

import java.util.Objects;

public class User {
    private String id;
    private String name;

    //重写equals方法，id 和 name 相同的对象就判定为相同对象
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(id, user.id) &&
                Objects.equals(name, user.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

String 字典序

// 当str比str2大时，输出一个正整数；当str比str2小的时候输出一个负整数；str和str2相等时输出0
str.compareTo(str2)

数据结构

最小堆

算法

哈夫曼树

• 二叉树中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();
    List<Integer> res = new ArrayList<>();

    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.addLast(root);
            root = root.left;
        }
        if (!stack.isEmpty()) {
            TreeNode node = stack.removeLast();
            res.add(node.val);
            root = node.right;
        }
    }

    return res;
}

快排

public static void quickSort(int[] arr,int low,int high){
    int i,j,temp,t;
    if(low > high)
        return;
    i=low;
    j=high;
    //temp就是基准位
    temp = arr[low];

    while (i<j) {
        //先看右边，依次往左递减
        while (temp<=arr[j]&&i<j) {
            j--;
        }
        //再看左边，依次往右递增
        while (temp>=arr[i]&&i<j) {
            i++;
        }
        //如果满足条件则交换
        if (i<j) {
            t = arr[j];
            arr[j] = arr[i];
            arr[i] = t;
        }
    }
    //最后将基准为与i和j相等位置的数字交换
    arr[low] = arr[i];
    arr[i] = temp;
    //递归调用左半数组
    quickSort(arr, low, j-1);
    //递归调用右半数组
    quickSort(arr, j+1, high);
}

多线程

交替打印

打印“01020304”，0、奇数、偶数分三个线程打印

class ZeroEvenOdd {
    private int n;
    private Object lock = new Object();
    private int flag = 0;
    
    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        synchronized (lock) {
            for (int i = 0; i < n; i++) {
                while (flag != 0) {
                    lock.wait();
                }
                printNumber.accept(0);
                flag = i % 2 == 1 ? 2 : 1;
                lock.notifyAll();
            }
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        synchronized (lock) {
            for (int i = 2; i <= n; i = i+2) {
                while (flag != 2) {
                    lock.wait();
                }
                printNumber.accept(i);
                flag = 0;
                lock.notifyAll();
            }
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        synchronized (lock) {
            for (int i = 1; i <= n; i = i+2) {
                while (flag != 1) {
                    lock.wait();
                }
                printNumber.accept(i);
                System.out.println(flag);
                flag = 0;
                lock.notifyAll();
            }
        }
    }
}

交替打印n轮

class FooBar {
    private int n;
    private volatile int state;
    private Object lock = new Object();
    private boolean run;

    public FooBar(int n) {
        this.n = n;
        this.state = 0;
        this.run = false;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            synchronized(lock) {
                if (run) {
                    lock.wait();
                }
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printFoo.run();
                run = true;
                lock.notify();
            }

            state += 1;
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            synchronized(lock) {
                if (!run) {
                    lock.wait();
                }
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printBar.run();
                run = false;
                lock.notify();
            }
        }
    }
}

死锁