算法题java

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

    @Datastatic 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

三、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

四、假设有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/TuttuYYDS/article/details/124636914