算法题java

蔚落 2024-03-27 18:48 55阅读 0赞

一、**四向链表，输入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;
        }

**二、输入树高，生成一个满二叉树。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);
        }

其它方式参考：[https://blog.csdn.net/wellsoonqmail/article/details/128262114][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;
                }
            }
        }

参照：[https://blog.csdn.net/m0\_63732435/article/details/127195219][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);
        }

参照：[https://blog.csdn.net/qq\_45908682/article/details/124661279][https_blog.csdn.net_qq_45908682_article_details_124661279]  
贪婪算法：[https://blog.csdn.net/TuttuYYDS/article/details/124636914][https_blog.csdn.net_TuttuYYDS_article_details_124636914]

[https_blog.csdn.net_wellsoonqmail_article_details_128262114]: https://blog.csdn.net/wellsoonqmail/article/details/128262114
[https_blog.csdn.net_m0_63732435_article_details_127195219]: https://blog.csdn.net/m0_63732435/article/details/127195219
[https_blog.csdn.net_qq_45908682_article_details_124661279]: https://blog.csdn.net/qq_45908682/article/details/124661279
[https_blog.csdn.net_TuttuYYDS_article_details_124636914]: https://blog.csdn.net/TuttuYYDS/article/details/124636914?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169778653516800227415944%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169778653516800227415944&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-124636914-null-null.142%5Ev96%5Epc_search_result_base9&utm_term=%E8%B4%AA%E5%BF%83&spm=1018.2226.3001.4187