打印树

题目描述

给定一组节点，每个节点包含以下信息：

• id：节点编号（唯一标识）。
• parentId：父节点编号（如果 parentId = 0，表示根节点）。
• name：节点名称。

请根据这些节点关系构建一棵（或多棵）树，并以缩进的形式打印树结构。

---

示例输入

[
(1, 0, "AA"),
(2, 1, "BB"),
(3, 1, "CC"),
(4, 3, "DD"),
(5, 3, "EE"),
(6, 2, "FF"),
(7, 2, "GG"),
(8, 4, "HH"),
(9, 5, "II"),
(10, 0, "JJ"),
(11, 10, "KK"),
(12, 10, "LL"),
(13, 12, "MM"),
(14, 13, "NN"),
(15, 14, "OO")
]

---

示例输出

AA
 BB
   FF
   GG
 CC
   DD
     HH
   EE
     II
JJ
 KK
 LL
   MM
     NN
       OO

package InterviewProblems;

import java.util.*;

public class ShowMeBug {
    static class Node {
        int id;
        int parentId;
        String name;

        public Node(int id, int parentId, String name) {
            this.id = id;
            this.parentId = parentId;
            this.name = name;
        }
    }

    public static void main(String[] args) {
        List<Node> nodeList = Arrays.asList(
                new Node(1, 0, "AA"),
                new Node(2, 1, "BB"), 
                new Node(3, 1, "CC"),
                new Node(4, 3, "DD"), 
                new Node(5, 3, "EE"),
                new Node(6, 2, "FF"), 
                new Node(7, 2, "GG"),
                new Node(8, 4, "HH"), 
                new Node(9, 5, "II"),
                new Node(10, 0, "JJ"), 
                new Node(11, 10, "KK"),
                new Node(12, 10, "LL"),
                new Node(13, 12, "MM"),
                new Node(14, 13, "NN"),
                new Node(15, 14, "OO")
        );
        print(nodeList);
    }

    public static void print(List<Node> nodeList) {
        Map<Integer,List<Node>> map = new HashMap<>();
        for(Node node : nodeList){
            if(!map.containsKey(node.parentId)){
                map.put(node.parentId, new ArrayList<Node>());
            }
            map.get(node.parentId).add(node);
        }
        printTree(map, 0, 0);
    }

    private static void printTree(Map<Integer, List<Node>> map, int parentId, int depth) {
        List<Node> children = map.get(parentId);
        if(children == null){
            return;
        }
        for(Node node : children){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < depth;i++){
                sb.append("  ");  // 两个空格缩进
            }
            System.out.println(sb.toString() + node.name);
            printTree(map, node.id, depth + 1);
        }
    }

}

多线程打印0-200

系统学习多线程有感，再写这一题

相关信息

多线程编程步骤:

1. 创建资源类，在资源类中定义属性和方法
2. 判断->干活->通知
3. 创建多个线程调用资源类的方法

class Share{
    private int num = 0;
    private boolean flag = true;
    public synchronized boolean print1() throws InterruptedException {
        //判断
        while(!flag && num <= 200){
            this.wait();
        }
        if(num > 200){
        //避免有未唤醒的线程导致永远无法结束
            notifyAll();
            return false;
        }
        //干活
        System.out.println(Thread.currentThread().getName() + "打印"+ num++);
        flag = false;
        //通知
        this.notifyAll();
        return true;
    }
    public synchronized boolean print2() throws InterruptedException {
        //判断
        while(flag && num <= 200){
            this.wait();
        }
        if(num > 200){
            notifyAll();
            return false;
        }
        //干活
        System.out.println(Thread.currentThread().getName() + "打印"+ num++);
        flag = true;
        //通知
        this.notifyAll();
        return true;
    }
    public synchronized int getNum(){
        return this.num;
    }
}
public class ConcurrentPrint {
    public static void main(String[] args) {
        Share share = new Share();
        new Thread(()->{
            while (true) {
                try {
                    if (!share.print1()) break;
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
        },"A").start();
        new Thread(()->{
            while(true){
                try {
                    if (!share.print2()) break;
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
        },"B").start();

    }
}

public class Main {
    private static final int MAX = 200;
    private static int num = 0;
    private static final Object lock = new Object();
    private static boolean flag = true;

    static void print() {
        Thread thread1 = new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    while (!flag) { // 等待轮到线程1
                        try {
                            lock.wait();//释放锁，并等待
                        } catch (InterruptedException e) {
                            throw new RuntimeException(e);
                        }
                    }
                    if (num > MAX) {
                        lock.notifyAll();//唤醒在等待的线程
                        break;
                    }
                    System.out.println("线程1: " + num++);
                    flag = false; // 切换到线程2
                    lock.notifyAll();//唤醒在等待的线程
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    while (flag) { // 等待轮到线程2
                        try {
                            lock.wait();
                        } catch (InterruptedException e) {
                            throw new RuntimeException(e);
                        }
                    }
                    if (num > MAX) {
                        lock.notifyAll();//唤醒在等待的线程
                        break;
                    }
                    System.out.println("线程2: " + num++);
                    flag = true; // 切换到线程1
                    lock.notifyAll();//唤醒在等待的线程
                }
            }
        });

        thread1.start();
        thread2.start();
    }

    public static void main(String[] args) {
        print();
    }
}

使用ArrayBlockingQueue

public class ThreadsPrint {
    public static void main(String[] args) {
        ArrayBlockingQueue<Integer> queue1 = new ArrayBlockingQueue<>(1);
        ArrayBlockingQueue<Integer> queue2 = new ArrayBlockingQueue<>(1);
        try {
            queue1.put(0);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        Thread thread1 = new Thread(()->{
            for(int i = 0; i <= 200;i+=2){
                try {
                    queue1.take();
                    System.out.println(i);
                    queue2.put(0);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
        },"线程1");
        Thread thread2 = new Thread(()->{
            for(int i = 1; i <= 200;i+=2){
                try {
                    queue2.take();
                    System.out.println(i);
                    queue1.put(0);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
        },"线程2");
        thread1.start();
        thread2.start();

    }
}

创建多线程的方法

①继承Thread

public class Main {
    static class MyThread extends Thread{
        @Override
        public void run(){
            System.out.println("hello");
        }
    }

    public static void main(String[] args) {
        Thread thread = new MyThread();
        thread.start();
        System.out.println("你好");
    }

}

②实现Runable

public class Main {
    static class MyThread implements Runnable{
        @Override
        public void run(){
            System.out.println("hello");
        }
    }

    public static void main(String[] args) {
        Thread thread = new Thread(new MyThread());
        thread.start();
        System.out.println("你好");
    }

}

③实现lambda

public class Main {
    public static void main(String[] args) {
        Thread t1 = new Thread(() -> {
            System.out.println(Thread.currentThread().getName() + " 执行");
        });
        t1.start();
    }
}

不想让方法抛出异常该怎么办

转化为运行时异常

public String readFile(String path) {
    try {
        return Files.readString(Path.of(path));
    } catch (IOException e) {
        throw new RuntimeException("文件读取失败", e);
    }
}

实现一个方法，统计指定文件中单词的个数

这里用字符流

public int countWords(String filePath) throws IOException {
    int cnt = 0;
    File file = new File(filePath);
    BufferedReader reader = new BufferedReader(new FileReader(file));
    String line;
    while ((line = reader.readLine()) != null) {
        String[] strs = line.split("\\s+"); // 按空白符切分
        for (String s : strs) {
            if (s.isEmpty() || s.equals(",") || s.equals(".")) {
                continue;
            }
            cnt++;
        }
    }
    reader.close();
    return cnt;
}

• 字节流（byte 为单位）
  • 基类：InputStream / OutputStream
  • 用来处理二进制数据（图片、音频、视频、压缩包…）
  • 常见类：
    • FileInputStream / FileOutputStream（文件字节流）
    • BufferedInputStream / BufferedOutputStream（带缓冲，提高效率）
• 字符流（char 为单位）
  • 基类：Reader / Writer
  • 用来处理文本数据（纯文字文件，如 .txt、.java）
  • 常见类：
    • FileReader / FileWriter（文件字符流）
    • BufferedReader / BufferedWriter（带缓冲，可以 readLine()
• 普通流：一次读写就访问底层文件系统，效率相对低
• 缓冲流：在内存中加了一层缓存区（默认 8KB），减少磁盘访问次数，效率更高
  • BufferedInputStream、BufferedOutputStream
  • BufferedReader、BufferedWriter

怎么实现项目中缓存一致性的？

1. 第一次删除：在更新数据库前，先删除缓存。

2. 2更新数据库：执行数据库的写操作。

3. 延迟等待：等待一段时间（通常为主从同步延迟时间 + 少量缓冲时间）。

4. 第二次删除：再次删除缓存。

   第一次删除的目的是为了清除缓存旧值，强制后续读请求直接访问数据库（避免直接返回旧缓存）。

   第二次删除（延迟后）的目的是为了清除在数据库更新期间可能被其他请求写入的旧缓存值

new对象内存分配在哪里

一般分配在堆中，特定情况可能分配在栈中。JVM的JIT(即时编译)会做逃逸分析，判断对象是否“逃出方法作用域”，如果没有逃逸出方法可能会将对象分配到栈中。

编辑此页

贡献者: scrazyakai

上一页IO流

下一页二分