算法题java

一、四向链表，输入n生成一个多维4向链表

    @Data
    static class ListNode<T>{
        private T val;
        ListNode<T> up,down,left,right;
        public ListNode(T val){
            this.val = val;
        }
    }
    public static void main(String[] args){
        ListNode<Integer> node = getResult(8);
        ListNode<Integer> row = node;
        while(row != null){
            ListNode currNode = row;
            while(currNode != null){
                System.out.print(currNode.val + "  ");
                currNode = currNode.right;
            }
            System.out.println("");
            row = row.down;
        }

    }
    public static ListNode<Integer> getResult(int n){
        if(n<=0){
            return null;
        }
        ListNode<Integer> head = new ListNode<>(11);
        head.left = null;
        head.up = null;
        ListNode<Integer> current = head;
        for(int i = 2 ; i <= n ; i++){
            ListNode<Integer> node = new ListNode<>(10 + i);
            current.right = node;
            node.left = current;
            current = node;
        }
        ListNode<Integer> prevHead = head;
        ListNode<Integer> rowCurrent = prevHead;
        for(int row = 2 ; row <= n ; row++){
            ListNode<Integer> rowHead = new ListNode<>(row * 10 + 1);
            prevHead.down = rowHead;
            rowHead.up = prevHead;
            current = rowHead;
            for(int col = 2; col <= n ; col++){
                ListNode<Integer> node = new ListNode<>(row * 10 + col);
                node.left = current;
                current.right = node;
                rowCurrent = rowCurrent.right;
                rowCurrent.down = node;
                node.up = rowCurrent;
                current = node;
            }
            prevHead = rowHead;
            rowCurrent = prevHead;
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

二、输入树高，生成一个满二叉树。BinaryTree

 static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
            this.parent = null;
        }
    }
    public static TreeNode generate(TreeNode parent,int depth) {
        if (depth == 0) {
            return null;
        }
        TreeNode node = new TreeNode(depth);
        node.left = generate(node,depth - 1);
        node.right = generate(node,depth - 1);
        node.parent = parent;
        return node;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root = generate(root,3);
        printTree(root);
    }
    public static void printTree(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        printTree(root.left);
        printTree(root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

其它方式参考：https://blog.csdn.net/wellsoonqmail/article/details/128262114

三、java实现双链表

static class ListNode{
        private int val;//值
        private ListNode prev;//前驱
        private ListNode next;//后继

        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;//双向链表的头节点
    public ListNode last;//双向链表的尾节点
    public void display(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public int size(){
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //链表为空时
        if (head == null) {
            head = node;
            last = node;
        }
        //有头指针，不为空
        else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }
    public void addLast(int data){
        ListNode node=new ListNode(data);
        //当链表为空
        if(head==null){
            head=node;
            last=node;
        }
        //有头指针，不为空
        else{
            last.next=node;
            node.prev=last;
            last=last.next;
        }
    }
    //删除第一次出现关键字key的节点，一共三种情况
    public void remove(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //1.当删除头节点
                if(cur == head) {
                    head = head.next;
                    //1.1当头指针不为空时
                    if(head != null) {
                        //考虑只有一个节点的情况下
                        head.prev = null;
                    }else {
                        //1.2头指针为空时
                        last = null;
                    }
                }else {
                    //2.删除中间节点 和  3.尾巴节点
                    if(cur.next != null) {
                        //删除中间节点
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }else {
                        //尾巴节点
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
                return;
            }else {
                cur = cur.next;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

参照：https://blog.csdn.net/m0_63732435/article/details/127195219

四、假设有n个面试官，每个面试者预约的时间是[ai， bi]（包括边界），1号面试官在bi时刻结束后，至多能继续bi+1时刻开始的面试，请帮忙计算1号面试官至多能面试多少个面试者。//贪婪策略：每次选择最早结束的活动

private static int [][] times = {{1,3},{1,4},{3,5},{4,5}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Arrays.sort(times, (o1, o2) -> {
            if(o1[1] == o2[1]){
                return o1[0] - o2[0];
            }else{
                return o1[1] - o2[1];
            }
        });
        int res = 1;
        int end = times[0][1];
        for(int i = 1; i < n; i++){
            if(times[i][0] > end){
                end = times[i][1];
                res++;
            }
        }
        System.out.println(res);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

参照：https://blog.csdn.net/qq_45908682/article/details/124661279
贪婪算法：https://blog.csdn.net/TuttuYYDS/article/details/124636914