左云算法1

我会带着你远行 2022-09-03 12:25 56阅读 0赞

# 数组 #

int[] result = new int[k];
    char[] charArray = { 's','a'};

# map #

Map<String,String> map = new HashMap<>();
            map.put("keyww","valefff");
            map.get("keyww");
            boolean isContain = map.containsKey("keyww");
            map.getOrDefault( "keyww","valettt");
            // 循环遍历Map的4中方法
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            map.put(1, 2);
            // 1. entrySet遍历，在键和值都需要时使用（最常用）
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) { 
                System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
            }
            // 2. 通过keySet或values来实现遍历,性能略低于第一种方式
            // 遍历map中的键
            for (Integer key : map.keySet()) { 
                System.out.println("key = " + key);
            }
            // 遍历map中的值
            for (Integer value : map.values()) { 
                System.out.println("key = " + value);
            }
            // 3. 使用Iterator遍历
            Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
            while (it.hasNext()) { 
                Map.Entry<Integer, Integer> entry = it.next();
                System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
            }
    
            // 4. java8 Lambda
            // java8提供了Lambda表达式支持，语法看起来更简洁，可以同时拿到key和value，
            // 不过，经测试，性能低于entrySet,所以更推荐用entrySet的方式
            map.forEach((key, value) -> { 
                System.out.println(key + ":" + value);
            });

# LinkedList #

LinkedList<Integer> list = new LinkedList<>();
            list.add(1);
            list.add(2);
            list.add(3);
            list.addFirst(0);
            list.addLast(4);
            list.removeFirst();
            list.removeLast();

# 1.排序 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70]

## 1.选择排序 O(n2) ##

public static void selectionSort(int[] arr) { 
    		if (arr == null || arr.length < 2) { 
    			return;
    		}
    		// 0 ~ N-1 找到最小值，在哪，放到0位置上
    		// 1 ~ n-1 找到最小值，在哪，放到1 位置上
    		// 2 ~ n-1 找到最小值，在哪，放到2 位置上
    		for (int i = 0; i < arr.length - 1; i++) { 
    			int minIndex = i;
    			for (int j = i + 1; j < arr.length; j++) {  // i ~ N-1 上找最小值的下标 
    				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
    			}
    			swap(arr, i, minIndex);
    		}
    	}
    
    	public static void swap(int[] arr, int i, int j) { 
    		int tmp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = tmp;
    	}

## 2.冒泡排序 O(n2) ##

public static void bubbleSort(int[] arr) { 
    		if (arr == null || arr.length < 2) { 
    			return;
    		}
    		// 0 ~ N-1
    		// 0 ~ N-2
    		// 0 ~ N-3
    		for (int e = arr.length - 1; e > 0; e--) {  // 0 ~ e
    			for (int i = 0; i < e; i++) { 
    				if (arr[i] > arr[i + 1]) { 
    					swap(arr, i, i + 1);
    				}
    			}
    		}
    	}
    
    	// 交换arr的i和j位置上的值
    	public static void swap(int[] arr, int i, int j) { 
    		arr[i] = arr[i] ^ arr[j];
    		arr[j] = arr[i] ^ arr[j];
    		arr[i] = arr[i] ^ arr[j];
    	}

## 3.插入排序O(n2) ##

//保证0-i个数有序
    	public static void insertionSort(int[] arr) { 
    		if (arr == null || arr.length < 2) { 
    			return;
    		}
    		// 不只1个数
    		for (int i = 1; i < arr.length; i++) {  // 0 ~ i 做到有序
    			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { 
    				swap(arr, j, j + 1);
    			}
    		}
    	}
    
    	// i和j是一个位置的话，会出错
    	public static void swap(int[] arr, int i, int j) { 
    		arr[i] = arr[i] ^ arr[j];
    		arr[j] = arr[i] ^ arr[j];
    		arr[i] = arr[i] ^ arr[j];
    	}

## 4. 归并排序O(n\*logn) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 1]

// 递归方法实现
    	public static void mergeSort1(int[] arr) { 
    		if (arr == null || arr.length < 2) { 
    			return;
    		}
    		process(arr, 0, arr.length - 1);
    	}
    
    	// 请把arr[L..R]排有序
    	// l...r N
    	// T(N) = 2 * T(N / 2) + O(N)
    	// O(N * logN)
    	public static void process(int[] arr, int L, int R) { 
    		if (L == R) {  // base case
    			return;
    		}
    		int mid = L + ((R - L) >> 1);
    		process(arr, L, mid);
    		process(arr, mid + 1, R);
    		merge(arr, L, mid, R);
    	}
    
    	public static void merge(int[] arr, int L, int M, int R) { 
    		int[] help = new int[R - L + 1]; 
    		int i = 0;
    		int p1 = L;
    		int p2 = M + 1;
    		while (p1 <= M && p2 <= R) { 
    			help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    		}
    		// 要么p1越界了，要么p2越界了
    		while (p1 <= M) { 
    			help[i++] = arr[p1++];
    		}
    		while (p2 <= R) { 
    			help[i++] = arr[p2++];
    		}
    		for (i = 0; i < help.length; i++) { 
    			arr[L + i] = help[i];
    		}
    	}

# 2. 异或运算题目 #

## 1.交换两个数 不通过第三个数 ##

以下两个结果一样

b = a ^ b;
    		a = a ^ b;
    		b = a ^ b;

a = a ^ b;
    		b = a ^ b;
    		a = a ^ b;

## 2. 只有1个出现奇数次的数 ##

一个数组中一个数出现了奇数次，其他数都出现了偶数次，找到这个数

// arr中，只有一种数，出现奇数次
    	public static void printOddTimesNum1(int[] arr) { 
    		int eor = 0;
    		for (int i = 0; i < arr.length; i++) { 
    			eor ^= arr[i];
    		}
    		System.out.println(eor);
    	}

## 3.找出int型数据二进制格式种最右侧的1 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 2]

public static int bit1counts(int N) { 
    		int count = 0;
    		
    		// 011011010000
    		// 000000010000 1
    		
    		// 011011000000
    		// 
    
    		while(N != 0) { 
    			//取反加1也就是自己的相反数
    			int rightOne = N & ((~N) + 1); //~N 取反
    			count++;
    			N ^= rightOne;
    			// N -= rightOne
    		}
    
    		return count;
    		
    	}

## 4.有2个出现奇数次的数 ##

一个数组中2个数出现了奇数次，其他数都出现了偶数次，找到这2个数

//假设这2个数是a和b
    	// arr中，有两种数，出现奇数次
    	public static void printOddTimesNum2(int[] arr) { 
    		int eor = 0;
    		for (int i = 0; i < arr.length; i++) { 
    			eor ^= arr[i];   //eor最后是a^b的结果
    		}
    		// a 和 b是两不相等的数，所以 eor != 0 
    		// 提取出来 eor 二进制格式种最右侧的1, 
    		//最右侧的为1说明，a和b二进制格式中这一位不相等,
    		//以此为标准将数据数据划分成两类，分别异或，每类即只包含一个出现寄数次的数
    		// eor : 00110010110111000
    		// rightOne :00000000000001000
    		int rightOne = eor & (-eor); // 提取出最右的1
    		
    		int onlyOne = 0; // eor'
    		for (int i = 0 ; i < arr.length;i++) { 
    			// arr[1] = 111100011110000
    			// rightOne= 000000000010000
    			if ((arr[i] & rightOne) != 0) { 
    				onlyOne ^= arr[i];  //最后提取一个
    			}
    		}
    		//a^b^a=b
    		System.out.println(onlyOne + " " + (eor ^ onlyOne));
    	}

## 5. 一种数出现了K次，其他数都出现M次 ##

一个数组种有一种数出现了K次，其他数都出现M次，  
M>1, k<M  
找到出现了K次的数  
要求，额外空间复杂度为O(1)，时间复杂度0(n)

// 请保证arr中，只有一种数出现了K次，其他数都出现了M次
    	public static int onlyKTimes(int[] arr, int k, int m) { 
    		int[] t = new int[32];
    		//用一个长度为32的数据保存每个数二进制格式种对应位置1的个数，
    		//如果某个位置1的个数与M取模等0，说明出现出现1的个数是M的整数被，即二进制格式种此位置出现K次的那个数为0
    		// 如果取模等于K ,说明二进制格式种此位置出现K次的那个数为1
    		// t[0] 0位置的1出现了几个
    		// t[i] i位置的1出现了几个
    
    		//用一个长度为32的数据保存每个数二进制格式种对应位置1的个数
    		for (int num : arr) { 
    			for(int i= 0; i < 32; i++) { 
    				t[i] += (num >> i ) & 1;
    			}
    			
    /* while (num != 0) { int rightOne = num & (-num); t[map.get(rightOne)]++; num ^= rightOne; }*/
    		}
    		int ans = 0;
    		//取模计算出现k次的数
    		for (int i = 0; i < 32; i++) { 
    			if (t[i] % m != 0) { 
    				if (t[i] % m == k) { 
    					ans |= (1 << i);
    				} else { 
    					return -1;
    				}
    			}
    		}
    		
    		//出现K次的数子是0这个数情况
    		if (ans == 0) { 
    			int count = 0;
    			for (int num : arr) { 
    				if (num == 0) { 
    					count++;
    				}
    			}
    			if (count != k) { 
    				return -1;
    			}
    		}
    		return ans;
    	}

map的方法

public static int test(int[] arr, int k, int m) { 
    			HashMap<Integer, Integer> map = new HashMap<>();
    			for (int num : arr) { 
    				if (map.containsKey(num)) { 
    					map.put(num, map.get(num) + 1);
    				} else { 
    					map.put(num, 1);
    				}
    			}
    			for (int num : map.keySet()) { 
    				if (map.get(num) == k) { 
    					return num;
    				}
    			}
    			return -1;
    		}

# 3.基本数据结构 #

## 1.链表 ##

### 2.单向链表/翻转 ###

public static class Node { 
    		public int value;
    		public Node next;
    
    		public Node(int data) { 
    			value = data;
    		}
    	}

// head
    	// a -> b -> c -> null
    	// c -> b -> a -> null
    	public static Node reverseLinkedList(Node head) { 
    		Node next = null; //暂存翻转前节点指向的(即node前.nest = next)//
    		Node pre = null;  //暂存翻转后节点指向的（即 node后.next=pre）
    
    		while (head != null) { 
    			//翻转
    			next = head.next; //保留翻转前的现场
    			head.next = pre; // 翻转，将node.next指向翻转
    			//移动head为洗一个节点翻转做准备
    			pre = head;  //往后移动pre
    			head = next; //往后移动head
    		}
    		//最后的pre指向追后的一个数，即为翻转后链表的head
    		return pre;
    	}

### 2.双向链表/翻转 ###

public static class DoubleNode { 
    		public int value;
    		public DoubleNode last;
    		public DoubleNode next;
    
    		public DoubleNode(int data) { 
    			value = data;
    		}
    	}

public static DoubleNode reverseDoubleList(DoubleNode head) { 
    		//思想和单向链表翻转一样，就是多了一个head.last = next;
    		DoubleNode pre = null;
    		DoubleNode next = null;
    		while (head != null) { 
    			//翻转
    			next = head.next;
    			head.next = pre;
    			head.last = next;
    			//后移
    			pre = head;
    			head = next;
    		}
    		return pre;
    	}

### 3. 删除链表种的指定值 ###

public class Code02_DeleteGivenValue { 
    
    	public static class Node { 
    		public int value;
    		public Node next;
    
    		public Node(int data) { 
    			this.value = data;
    		}
    	}
    
    	// head = removeValue(head, 2);
    	public static Node removeValue(Node head, int num) { 
    		// head来到第一个不需要删的位置
    		//如果head.vale=num,需要返回新的head
    		while (head != null) { 
    			if (head.value != num) { 
    				break;
    			}
    			head = head.next;
    		}
    		// 1 ) head == null
    		// 2 ) head != null
    		Node pre = head;
    		Node cur = head;
    		while (cur != null) { 
    			if (cur.value == num) { 
    				pre.next = cur.next;
    			} else { 
    				pre = cur;
    			}
    			cur = cur.next;
    		}
    		return head;
    	}
    
    }

## 1.链表面试题常用方法 ##

**需要注意边界问题**

### 1.快慢指针法 ###

慢指针：1次走1步  
快指针：1次走2步

#### 1.求链表的中点 ####

可以先计算出链表的长度，再长度除以2求出链表的中点位置 方法  
**也可以用快慢指针的方法：快指针走到链表终点位置，慢指针的位置就是中点的位置**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 3]

public static class Node { 
    		public int value;
    		public Node next;
    
    		public Node(int v) { 
    			value = v;
    		}
    	}
    
    	// head 头
    	public static Node midOrUpMidNode(Node head) { 
    		if (head == null || head.next == null || head.next.next == null) { 
    			return head;
    		}
    		// 链表有3个点或以上
    		Node slow = head.next;
    		Node fast = head.next.next;
    		while (fast.next != null && fast.next.next != null) { 
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		return slow;
    	}
    
    	public static Node midOrDownMidNode(Node head) { 
    		if (head == null || head.next == null) { 
    			return head;
    		}
    		Node slow = head.next;
    		Node fast = head.next;
    		while (fast.next != null && fast.next.next != null) { 
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		return slow;
    	}
    
    	public static Node midOrUpMidPreNode(Node head) { 
    		if (head == null || head.next == null || head.next.next == null) { 
    			return null;
    		}
    		Node slow = head;
    		Node fast = head.next.next;
    		while (fast.next != null && fast.next.next != null) { 
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		return slow;
    	}
    
    	public static Node midOrDownMidPreNode(Node head) { 
    		if (head == null || head.next == null) { 
    			return null;
    		}
    		if (head.next.next == null) { 
    			return head;
    		}
    		Node slow = head;
    		Node fast = head.next;
    		while (fast.next != null && fast.next.next != null) { 
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		return slow;
    	}

#### 2. 判断链表是否为回文结构 ####

回文结构 ： 一组数正读和翻着读一样  
123321  
1234321  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 4]

1） 把链表先放到栈里，再出栈和链表比较

public static class Node { 
    		public int value;
    		public Node next;
    
    		public Node(int data) { 
    			this.value = data;
    		}
    	}
    
    	// 使用栈方法实现need n extra space
    	public static boolean isPalindrome1(Node head) { 
    		Stack<Node> stack = new Stack<Node>();
    		Node cur = head;
    		while (cur != null) { 
    			stack.push(cur);
    			cur = cur.next;
    		}
    		while (head != null) { 
    			if (head.value != stack.pop().value) { 
    				return false;
    			}
    			head = head.next;
    		}
    		return true;
    	}

2） 先找出中点位置，再将后半部分链表翻转，和上半部分对比。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 5]

L或者R有一个为null 结束  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 6]

// need O(1) extra space
    	public static boolean isPalindrome3(Node head) { 
    		if (head == null || head.next == null) { 
    			return true;
    		}
    		Node n1 = head;
    		Node n2 = head;
    		// 使用快慢指针获取中点位置
    		while (n2.next != null && n2.next.next != null) {  // find mid node
    			n1 = n1.next; // n1 -> mid 慢指针
    			n2 = n2.next.next; // n2 -> end 快指针
    		}
    		// n1 中点
    		
    		
    		n2 = n1.next; // n2 -> right part first node
    		n1.next = null; // mid.next -> null
    		Node n3 = null;
    		//翻转后半部分链表
    		while (n2 != null) {  // right part convert
    			n3 = n2.next; // n3 -> save next node
    			n2.next = n1; // next of right node convert
    			n1 = n2; // n1 move
    			n2 = n3; // n2 move
    		}
    		n3 = n1; // n3 -> save last node
    		n2 = head;// n2 -> left first node
    		boolean res = true;
    //对比
    		while (n1 != null && n2 != null) {  // check palindrome
    			if (n1.value != n2.value) { 
    				res = false;
    				break;
    			}
    			n1 = n1.next; // left to mid
    			n2 = n2.next; // right to mid
    		}
    		n1 = n3.next;
    		n3.next = null;
    		//把之前翻转后半部分再调整过来
    		while (n1 != null) {  // recover list
    			n2 = n1.next;
    			n1.next = n3;
    			n3 = n1;
    			n1 = n2;
    		}
    		return res;
    	}

#### 3.按某值左边下，中间相等，右边大 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 12]

public static Node listPartition2(Node head, int pivot) { 
    		Node sH = null; // small head
    		Node sT = null; // small tail
    		Node eH = null; // equal head
    		Node eT = null; // equal tail
    		Node mH = null; // big head
    		Node mT = null; // big tail
    		Node next = null; // save next node
    		// every node distributed to three lists
    		while (head != null) { 
    			next = head.next;
    			head.next = null;
    			if (head.value < pivot) { 
    				if (sH == null) { 
    					sH = head;
    					sT = head;
    				} else { 
    					sT.next = head;
    					sT = head;
    				}
    			} else if (head.value == pivot) { 
    				if (eH == null) { 
    					eH = head;
    					eT = head;
    				} else { 
    					eT.next = head;
    					eT = head;
    				}
    			} else { 
    				if (mH == null) { 
    					mH = head;
    					mT = head;
    				} else { 
    					mT.next = head;
    					mT = head;
    				}
    			}
    			head = next;
    		}
    		// 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
    		//小于区域和等于区域连接
    		if (sT != null) {  // 如果有小于区域
    			sT.next = eH;
    			eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
    		}
    		// 下一步，一定是需要用eT 去接 大于区域的头
    		// 有等于区域，eT -> 等于区域的尾结点
    		// 无等于区域，eT -> 小于区域的尾结点
    		// eT 尽量不为空的尾巴节点
    		//等于区域和大于区域连接
    		if (eT != null) {  // 小于区域和等于区域，可能都没有
    			eT.next = mH;
    		}
    		return sH != null ? sH : (eH != null ? eH : mH);
    	}

#### 4. 特殊链表拷贝 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 14]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 15]  
方法1 可以使用map 存储老链表 保存rad，再拷贝，根据map找rad

public static Node copyListWithRand1(Node head) { 
    		// key 老节点
    		// value 新节点
    		HashMap<Node, Node> map = new HashMap<Node, Node>();
    		Node cur = head;
    		while (cur != null) { 
    			map.put(cur, new Node(cur.value));
    			cur = cur.next;
    		}
    		cur = head;
    		while (cur != null) { 
    			// cur 老
    			// map.get(cur) 新
    			// 新.next -> cur.next克隆节点找到
    			map.get(cur).next = map.get(cur.next);
    			map.get(cur).rand = map.get(cur.rand);
    			cur = cur.next;
    		}
    		return map.get(head);
    	}

方法2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 16]

public static Node copyListWithRand2(Node head) { 
    		if (head == null) { 
    			return null;
    		}
    		Node cur = head;
    		Node next = null;
    		// copy node and link to every node
    		// 1 -> 2
    		// 1 -> 1' -> 2
    		while (cur != null) { 
    			// cur 老 next 老的下一个
    			next = cur.next;
    			cur.next = new Node(cur.value);
    			cur.next.next = next;
    			cur = next;
    		}
    		cur = head;
    		Node curCopy = null;
    		// set copy node rand
    		// 1 -> 1' -> 2 -> 2'
    		while (cur != null) { 
    			// cur 老
    			// cur.next 新 copy
    			next = cur.next.next;
    			curCopy = cur.next;
    			curCopy.rand = cur.rand != null ? cur.rand.next : null;
    			cur = next;
    		}
    		// head head.next
    		Node res = head.next;
    		cur = head;
    		// split
    		while (cur != null) { 
    			next = cur.next.next;
    			curCopy = cur.next;
    			cur.next = next;
    			curCopy.next = next != null ? next.next : null;
    			cur = next;
    		}
    		return res;
    	}

#### 5. 判断有环单链表 ####

#### 6.有环单链表的第一个入环节点 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 17]  
方法1： 可以用容器HashSet ,遍历链表，遍历一个对比容器中有没有，没有放入，有的话即是第一个入环节点

**方法2：使用快慢指针法：  
快指针一次走两部，慢指针走一步，  
如果没有环快指针先走到null 直接返回  
如果优化，快指针和满指针第一次相遇，快指针回到head，慢指针原地不动，  
快指针和慢指针每次都走一步，快指针和满指针再次相遇的位置即为第一个入环节点**

// 找到链表第一个入环节点，如果无环，返回null
    	public static Node getLoopNode(Node head) { 
    		if (head == null || head.next == null || head.next.next == null) { 
    			return null;
    		}
    		// n1 慢 n2 快
    		Node slow = head.next; // n1 -> slow
    		Node fast = head.next.next; // n2 -> fast
    		while (slow != fast) { 
    			if (fast.next == null || fast.next.next == null) { 
    				return null;
    			}
    			fast = fast.next.next;
    			slow = slow.next;
    		}
    		// slow fast 相遇
    		fast = head; // n2 -> walk again from head
    		while (slow != fast) { 
    			slow = slow.next;
    			fast = fast.next;
    		}
    		return slow;
    	}

#### 7.如果两个链表都无环，返回第一个相交节点 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 18]

方法1：可以用容器HashSet 把一个链表放到HashSet，遍历另一个链表个HashSet中的对比，相等即是第一个相交节点

**方法2：先分别遍历两个链表，计算两个链表的长度，和最后一个几点的地址  
如果最后一个节点的地址不相等，说明两个链表不相交，如果相等则相交  
长的链表，先走两个链表长度的差值，短的链表再走，第一次相交的位置即是第一个相交节点**

// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
    	public static Node noLoop(Node head1, Node head2) { 
    		if (head1 == null || head2 == null) { 
    			return null;
    		}
    		Node cur1 = head1;
    		Node cur2 = head2;
    		int n = 0;
    		//计算链表1的长度
    		while (cur1.next != null) { 
    			n++;
    			cur1 = cur1.next;
    		}
    		//计算链表2的长度
    		while (cur2.next != null) { 
    			n--;
    			cur2 = cur2.next;
    		}
    		//链表1和链表2的最后一个节点不相等，则两个链表没有相交
    		if (cur1 != cur2) { 
    			return null;
    		}
    		// n : 链表1长度减去链表2长度的值
    		cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
    		cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
    		n = Math.abs(n);
    		//长的链表先走，两个链表的长度差值步
    		while (n != 0) { 
    			n--;
    			cur1 = cur1.next;
    		}
    		//两个链表一起走，相等时即是第一个相交节点
    		while (cur1 != cur2) { 
    			cur1 = cur1.next;
    			cur2 = cur2.next;
    		}
    		return cur1;
    	}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 19]  
**一个有环一个没环不可能相交，所以只可能两都有环，存在以下三种可能**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 20]

public static Node getIntersectNode(Node head1, Node head2) { 
    		if (head1 == null || head2 == null) { 
    			return null;
    		}
    		//获取两个节点的第一个入环节点
    		Node loop1 = getLoopNode(head1);
    		Node loop2 = getLoopNode(head2);
    		//两个都是五环节点相交问题
    		if (loop1 == null && loop2 == null) { 
    			return noLoop(head1, head2);
    		}
    		//两个都是有环节点的相交问题
    		if (loop1 != null && loop2 != null) { 
    			return bothLoop(head1, loop1, head2, loop2);
    		}
    		//一个有环一个没环不可能相交
    		return null;
    	}

// 两个有环链表，返回第一个相交节点，如果不想交返回null
    	//loop1 和loop2分别是两个有环链表额第一个入环节点
    	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { 
    		Node cur1 = null;
    		Node cur2 = null;
    		//loop1 == loop2 对应图1
    		if (loop1 == loop2) { 
    			cur1 = head1;
    			cur2 = head2;
    			int n = 0;
    			while (cur1 != loop1) { 
    				n++;
    				cur1 = cur1.next;
    			}
    			while (cur2 != loop2) { 
    				n--;
    				cur2 = cur2.next;
    			}
    			cur1 = n > 0 ? head1 : head2;
    			cur2 = cur1 == head1 ? head2 : head1;
    			n = Math.abs(n);
    			while (n != 0) { 
    				n--;
    				cur1 = cur1.next;
    			}
    			while (cur1 != cur2) { 
    				cur1 = cur1.next;
    				cur2 = cur2.next;
    			}
    			return cur1;
    		} else { 
    			//loop1 1= loop2 对应图2和图3
    			cur1 = loop1.next;
    			//返回其中的一个一个相交节点
    			while (cur1 != loop1) { 
    				if (cur1 == loop2) { 
    					return loop1;
    				}
    				cur1 = cur1.next;
    			}
    			return null;
    		}
    	}

## 2.队列(先进先出) ##

### 1. 双链表实现队列 ###

方法1:  
后进来放到双向链表的尾部，  
出的队列直接从双向链表的头部取，取完再往后移动头部

public static class Node<T> { 
    		public T value;
    		public Node<T> last;
    		public Node<T> next;
    
    		public Node(T data) { 
    			value = data;
    		}
    	}
    
    	public static class DoubleEndsQueue<T> { 
    		public Node<T> head;
    		public Node<T> tail; //尾
    
    //后进来放到双向链表的尾部，
    		public void addFromBottom(T value) { 
    			Node<T> cur = new Node<T>(value);
    			if (head == null) { 
    				head = cur;
    				tail = cur;
    			} else { 
    				cur.last = tail;
    				tail.next = cur;
    				tail = cur;
    			}
    		}
    //出的队列直接从双向链表的头部取，取完再往后移动头部
    		public T popFromHead() { 
    			if (head == null) { 
    				return null;
    			}
    			Node<T> cur = head;
    			if (head == tail) { 
    				head = null;
    				tail = null;
    			} else { 
    				head = head.next;
    				cur.next = null;
    				head.last = null;
    			}
    			return cur.value;
    		}
    
    		public boolean isEmpty() { 
    			return head == null;
    		}
    
    	}

方法二：  
后进来放到双向链表的头部，  
出的队列直接从双向链表的尾部取，取完再往前移动尾部

public static class Node<T> { 
    		public T value;
    		public Node<T> last;
    		public Node<T> next;
    
    		public Node(T data) { 
    			value = data;
    		}
    	}
    
    	public static class DoubleEndsQueue<T> { 
    		public Node<T> head;
    		public Node<T> tail;
    //后进来放到双向链表的头部，
    		public void addFromHead(T value) { 
    			Node<T> cur = new Node<T>(value);
    			if (head == null) { 
    				head = cur;
    				tail = cur;
    			} else { 
    				cur.next = head;
    				head.last = cur;
    				head = cur;
    			}
    		}
    //出的队列直接从双向链表的尾部取，取完再往前移动尾部
    		public T popFromBottom() { 
    			if (head == null) { 
    				return null;
    			}
    			Node<T> cur = tail;
    			if (head == tail) { 
    				head = null;
    				tail = null;
    			} else { 
    				tail = tail.last;
    				tail.next = null;
    				cur.last = null;
    			}
    			return cur.value;
    		}
    
    		public boolean isEmpty() { 
    			return head == null;
    		}
    
    	}

public static class MyQueue<T> { 
    		private DoubleEndsQueue<T> queue;
    
    		public MyQueue() { 
    			queue = new DoubleEndsQueue<T>();
    		}
    
    		public void push(T value) { 
    			queue.addFromHead(value);
    		}
    
    		public T poll() { 
    			return queue.popFromBottom();
    		}
    
    		public boolean isEmpty() { 
    			return queue.isEmpty();
    		}
    
    	}

### 2. 数组现队列 ###

polli;// begin 控制进队列的位置  
pushi;// end 控制出队列的位置  
size：控制队列的中可用的容量

package class03;
    
    public class Code04_RingArray { 
    
    	public static class MyQueue { 
    		private int[] arr;
    		private int pushi;// end
    		private int polli;// begin
    		private int size;
    		private final int limit;
    
    		public MyQueue(int limit) { 
    			arr = new int[limit];
    			pushi = 0;
    			polli = 0;
    			size = 0;
    			this.limit = limit;
    		}
    
    		public void push(int value) { 
    			if (size == limit) { 
    				throw new RuntimeException("队列满了，不能再加了");
    			}
    			size++;
    			arr[pushi] = value;
    			pushi = nextIndex(pushi);
    		}
    
    		public int pop() { 
    			if (size == 0) { 
    				throw new RuntimeException("队列空了，不能再拿了");
    			}
    			size--;
    			int ans = arr[polli];
    			polli = nextIndex(polli);
    			return ans;
    		}
    
    		public boolean isEmpty() { 
    			return size == 0;
    		}
    
    		// 如果现在的下标是i，返回下一个位置
    		private int nextIndex(int i) { 
    			return i < limit - 1 ? i + 1 : 0;
    		}
    
    	}
    
    }

## 3.栈(先进后出) ##

### 1. 双链表实现队列 ###

后进来放到双向链表的头部，并向前移动头部，  
出的栈直接从双向链表的头部取，取完再往后移动头部

public static class MyStack<T> { 
    		private DoubleEndsQueue<T> queue;
    
    		public MyStack() { 
    			queue = new DoubleEndsQueue<T>();
    		}
    
    		public void push(T value) { 
    			queue.addFromHead(value);
    		}
    
    		public T pop() { 
    			return queue.popFromHead();
    		}
    
    		public boolean isEmpty() { 
    			return queue.isEmpty();
    		}
    
    	}

### 2. 数组实现栈 ###

维护之歌index 记录数组的唯一

后进来的数据依次往数组里面放，index++  
出栈，根据index直接取出，index–

## 4. 栈和队列面试题 ##

### 1.可以直接获取栈中最小值的栈 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 21]

package class03;
    
    import java.util.Stack;
    
    
    //使用两个栈，一个栈存数据，一个栈存放最小值
    //两个栈同步进栈出栈,
    //最小值栈进栈: 如果进栈的数据小于等于最小值栈栈顶的数据，则将此数据压入最小值栈;
    		//如果进栈的数据打于最小值栈栈顶的数据，则将最小值栈栈顶的数据重复压入最小值栈;
    //最小值栈出栈: 与正常存储数据的栈同步出栈
    public class Code05_GetMinStack { 
    
    	public static class MyStack1 { 
    		private Stack<Integer> stackData;
    		private Stack<Integer> stackMin;
    
    //方法1
    	public static class MyStack2 { 
    		private Stack<Integer> stackData;
    		private Stack<Integer> stackMin;
    
    		public MyStack2() { 
    			this.stackData = new Stack<Integer>();
    			this.stackMin = new Stack<Integer>();
    		}
    
    		public void push(int newNum) { 
    			if (this.stackMin.isEmpty()) { 
    				this.stackMin.push(newNum);
    			} else if (newNum < this.getmin()) { 
    				this.stackMin.push(newNum);
    			} else { 
    				int newMin = this.stackMin.peek();
    				this.stackMin.push(newMin);
    			}
    			this.stackData.push(newNum);
    		}
    
    		public int pop() { 
    			if (this.stackData.isEmpty()) { 
    				throw new RuntimeException("Your stack is empty.");
    			}
    			this.stackMin.pop();
    			return this.stackData.pop();
    		}
    
    		public int getmin() { 
    			if (this.stackMin.isEmpty()) { 
    				throw new RuntimeException("Your stack is empty.");
    			}
    			return this.stackMin.peek();
    		}
    	}
    
    //方法2
    		public MyStack1() { 
    			this.stackData = new Stack<Integer>();
    			this.stackMin = new Stack<Integer>();
    		}
    
    		public void push(int newNum) { 
    			if (this.stackMin.isEmpty()) { 
    				this.stackMin.push(newNum);
    			} else if (newNum <= this.getmin()) { 
    				this.stackMin.push(newNum);
    			}
    			this.stackData.push(newNum);
    		}
    
    		public int pop() { 
    			if (this.stackData.isEmpty()) { 
    				throw new RuntimeException("Your stack is empty.");
    			}
    			int value = this.stackData.pop();
    			if (value == this.getmin()) { 
    				this.stackMin.pop();
    			}
    			return value;
    		}
    
    		public int getmin() { 
    			if (this.stackMin.isEmpty()) { 
    				throw new RuntimeException("Your stack is empty.");
    			}
    			return this.stackMin.peek();
    		}
    	}
    	public static void main(String[] args) { 
    		MyStack1 stack1 = new MyStack1();
    		stack1.push(3);
    		System.out.println(stack1.getmin());
    		stack1.push(4);
    		System.out.println(stack1.getmin());
    		stack1.push(1);
    		System.out.println(stack1.getmin());
    		System.out.println(stack1.pop());
    		System.out.println(stack1.getmin());
    
    		System.out.println("=============");
    
    		MyStack1 stack2 = new MyStack1();
    		stack2.push(3);
    		System.out.println(stack2.getmin());
    		stack2.push(4);
    		System.out.println(stack2.getmin());
    		stack2.push(1);
    		System.out.println(stack2.getmin());
    		System.out.println(stack2.pop());
    		System.out.println(stack2.getmin());
    	}
    
    }

### 2.栈实现队列 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 22]  
使用两个栈实现队列

一个队列中数据导入到另个一个栈中

注意：每次导数据要把数据导干净，每次进栈的时候要检查栈是不是干净的

package class03;
    
    import java.util.Stack;
    
    public class Code06_TwoStacksImplementQueue { 
    
    	public static class TwoStacksQueue { 
    		public Stack<Integer> stackPush;
    		public Stack<Integer> stackPop;
    
    		public TwoStacksQueue() { 
    			stackPush = new Stack<Integer>();
    			stackPop = new Stack<Integer>();
    		}
    
    		// push栈向pop栈倒入数据
    		private void pushToPop() { 
    			if (stackPop.empty()) { 
    				while (!stackPush.empty()) { 
    					stackPop.push(stackPush.pop());
    				}
    			}
    		}
    
    		public void add(int pushInt) { 
    			stackPush.push(pushInt);
    			pushToPop();
    		}
    
    		public int poll() { 
    			if (stackPop.empty() && stackPush.empty()) { 
    				throw new RuntimeException("Queue is empty!");
    			}
    			pushToPop();
    			return stackPop.pop();
    		}
    
    		public int peek() { 
    			if (stackPop.empty() && stackPush.empty()) { 
    				throw new RuntimeException("Queue is empty!");
    			}
    			pushToPop();
    			return stackPop.peek();
    		}
    	}
    
    	public static void main(String[] args) { 
    		TwoStacksQueue test = new TwoStacksQueue();
    		test.add(1);
    		test.add(2);
    		test.add(3);
    		System.out.println(test.peek());
    		System.out.println(test.poll());
    		System.out.println(test.peek());
    		System.out.println(test.poll());
    		System.out.println(test.peek());
    		System.out.println(test.poll());
    	}
    
    }

### 2.队列实现栈 ###

使用两个队实现栈列

每次从一个队列中数据导入到另个一个队列中，只需要留队列中的最后一个数据返回即可

package class03;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class Code07_TwoQueueImplementStack { 
    
    	public static class TwoQueueStack<T> { 
    		public Queue<T> queue;
    		public Queue<T> help;
    
    		public TwoQueueStack() { 
    			queue = new LinkedList<>();
    			help = new LinkedList<>();
    		}
    
    		public void push(T value) { 
    			queue.offer(value);
    		}
    
    		public T poll() { 
    			while (queue.size() > 1) { 
    				help.offer(queue.poll());
    			}
    			T ans = queue.poll();
    			Queue<T> tmp = queue;
    			queue = help;
    			help = tmp;
    			return ans;
    		}
    
    		public T peek() { 
    			while (queue.size() > 1) { 
    				help.offer(queue.poll());
    			}
    			T ans = queue.poll();
    			help.offer(ans);
    			Queue<T> tmp = queue;
    			queue = help;
    			help = tmp;
    			return ans;
    		}
    
    		public boolean isEmpty() { 
    			return queue.isEmpty();
    		}
    
    	}
    
    	public static void main(String[] args) { 
    		System.out.println("test begin");
    		TwoQueueStack<Integer> myStack = new TwoQueueStack<>();
    		Stack<Integer> test = new Stack<>();
    		int testTime = 1000000;
    		int max = 1000000;
    		for (int i = 0; i < testTime; i++) { 
    			if (myStack.isEmpty()) { 
    				if (!test.isEmpty()) { 
    					System.out.println("Oops");
    				}
    				int num = (int) (Math.random() * max);
    				myStack.push(num);
    				test.push(num);
    			} else { 
    				if (Math.random() < 0.25) { 
    					int num = (int) (Math.random() * max);
    					myStack.push(num);
    					test.push(num);
    				} else if (Math.random() < 0.5) { 
    					if (!myStack.peek().equals(test.peek())) { 
    						System.out.println("Oops");
    					}
    				} else if (Math.random() < 0.75) { 
    					if (!myStack.poll().equals(test.pop())) { 
    						System.out.println("Oops");
    					}
    				} else { 
    					if (myStack.isEmpty() != test.isEmpty()) { 
    						System.out.println("Oops");
    					}
    				}
    			}
    		}
    
    		System.out.println("test finish!");
    
    	}
    
    }

## 5. 哈希 ##

### 1.HashMap ###

**treepMap利用哈希算法 get 的时间复杂度是O(1)**

public class HashMapAndSortedMap { 
    
    	public static class Node { 
    		public int value;
    
    		public Node(int v) { 
    			value = v;
    		}
    	}
    
    	public static class Zuo { 
    		public int value;
    
    		public Zuo(int v) { 
    			value = v;
    		}
    	}
    
    	public static void main(String[] args) { 
    
    		HashMap<Integer, String> test = new HashMap<>();
    		Integer a = 19000000;
    		Integer b = 19000000;
    		System.out.println(a == b);  //按以用传递 false
    
    		test.put(a, "我是3");
    		System.out.println(test.containsKey(b)); //在哈希表中原生的引用基本数据也是按值传递 true
    
    		Zuo z1 = new Zuo(1);
    		Zuo z2 = new Zuo(1);
    		HashMap<Zuo, String> test2 = new HashMap<>();
    		test2.put(z1, "我是z1");
    		System.out.println(test2.containsKey(z2));//在哈希表中非原生的引用数据按值引用传递 false
    
    		// UnSortedMap
    		HashMap<Integer, String> map = new HashMap<>();
    		map.put(1000000, "我是1000000");
    		map.put(2, "我是2");
    		map.put(3, "我是3");
    		map.put(4, "我是4");
    		map.put(5, "我是5");
    		map.put(6, "我是6");
    		map.put(1000000, "我是1000001");
    
    		System.out.println(map.containsKey(1));
    		System.out.println(map.containsKey(10));
    
    		System.out.println(map.get(4));
    		System.out.println(map.get(10));
    
    		map.put(4, "他是4");
    		System.out.println(map.get(4));
    
    		map.remove(4);
    		System.out.println(map.get(4));
    
    		// key
    		HashSet<String> set = new HashSet<>();
    		set.add("abc");
    		set.contains("abc");
    		set.remove("abc");
    
    		// 哈希表，增、删、改、查，在使用时，O（1）
    
    		System.out.println("=====================");
    
    		Integer c = 100000;
    		Integer d = 100000;
    		System.out.println(c.equals(d));
    
    		Integer e = 127; // - 128 ~ 127
    		Integer f = 127;
    		System.out.println(e == f);
    
    		HashMap<Node, String> map2 = new HashMap<>();
    		Node node1 = new Node(1);
    		Node node2 = node1;
    		map2.put(node1, "我是node1");
    		map2.put(node2, "我是node1");
    		System.out.println(map2.size());
    
    		System.out.println("======================");
    
    	}
    
    }

### 2.TreepMap 有序表 ###

**treepMap get的时间复杂度是O(logN)**

public class HashMapAndSortedMap { 
    
    	public static class Node { 
    		public int value;
    
    		public Node(int v) { 
    			value = v;
    		}
    	}
    
    	public static class Zuo { 
    		public int value;
    
    		public Zuo(int v) { 
    			value = v;
    		}
    	}
    
    	public static void main(String[] args) { 
    
    		// TreeMap 有序表：接口名
    		// 红黑树、avl、sb树、跳表
    		// O(logN)
    		System.out.println("有序表测试开始");
    		TreeMap<Integer, String> treeMap = new TreeMap<>();
    
    		treeMap.put(3, "我是3");
    		treeMap.put(4, "我是4");
    		treeMap.put(8, "我是8");
    		treeMap.put(5, "我是5");
    		treeMap.put(7, "我是7");
    		treeMap.put(1, "我是1");
    		treeMap.put(2, "我是2");
    
    		System.out.println(treeMap.containsKey(1));
    		System.out.println(treeMap.containsKey(10));
    
    		System.out.println(treeMap.get(4));
    		System.out.println(treeMap.get(10));
    
    		treeMap.put(4, "他是4");
    		System.out.println(treeMap.get(4));
    
    		// treeMap.remove(4);
    		System.out.println(treeMap.get(4));
    
    		System.out.println("新鲜：");
    		//treeMap中的数据是有序的，可以获取最小最大值
    		//基本的引用数据类型(Integetr,String等)，TreeMap知道根据数据怎么排序
    		//如果是自定的类型，需要自己实现compare方法
    		System.out.println(treeMap.firstKey());
    		System.out.println(treeMap.lastKey());
    		// <= 4 可以获得小于等于4的值
    		System.out.println(treeMap.floorKey(4));
    		// >= 4
    		System.out.println(treeMap.ceilingKey(4));
    		// O(logN)
    
    	}
    }

# 4.比较器 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 23]

public static class Student { 
    		public String name;
    		public int id;
    		public int age;
    
    		public Student(String name, int id, int age) { 
    			this.name = name;
    			this.id = id;
    			this.age = age;
    		}
    	}
    
    	// 任何比较器：
    	// compare方法里，遵循一个统一的规范：
    	// 返回负数的时候，认为第一个参数应该排在前面
    	// 返回正数的时候，认为第二个参数应该排在前面
    	// 返回0的时候，认为无所谓谁放前面
    	public static class IdShengAgeJiangOrder implements Comparator<Student> { 
    
    		// 根据id从小到大，但是如果id一样，按照年龄从大到小
    		@Override
    		public int compare(Student o1, Student o2) { 
    			return o1.id != o2.id ? (o1.id - o2.id) : (o2.age - o1.age);
    		}
    
    	}
    
    	public static class IdAscendingComparator implements Comparator<Student> { 
    
    		//自定义比较器
    		//任何比较器的compare方法规则：
    		// 返回负数的时候，第一个参数排在前面
    		// 返回正数的时候，第二个参数排在前面
    		// 返回0的时候，谁在前面无所谓
    		@Override
    		public int compare(Student o1, Student o2) { 
    			return o1.id - o2.id;
    		}
    
    	}

public static void main(String[] args) { 
    
    		Integer[] arr = {  5, 4, 3, 2, 7, 9, 1, 0 };
    
    		Arrays.sort(arr, new IdAscendingComparator ());
    //=================================================
    	   Student student1 = new Student("A", 4, 40);
    		Student student2 = new Student("B", 4, 21);
    		Student student3 = new Student("C", 3, 12);
    		Student student4 = new Student("D", 3, 62);
    		Student student5 = new Student("E", 3, 42);
    		// D E C A B
    
    		Student[] students = new Student[] {  student1, student2, student3, student4, student5 };
    		System.out.println("第一条打印");
    
    		Arrays.sort(students, new IdAscendingComparator ());
    
    //=================================
    ArrayList<Student> studentList = new ArrayList<>();
    		studentList.add(student1);
    		studentList.add(student2);
    		studentList.add(student3);
    		studentList.add(student4);
    		studentList.add(student5);
    		studentList.sort(new IdShengAgeJiangOrder());
    }

有序表，自定义类型排序，需要指定排序规则

student1 = new Student("A", 4, 40);
    		student2 = new Student("B", 4, 21);
    		student3 = new Student("C", 4, 12);
    		student4 = new Student("D", 4, 62);
    		student5 = new Student("E", 4, 42);
    		//TreeMap<Student, String> treeMap = new TreeMap<>((a, b) -> (a.id - b.id));
    		TreeMap<Student, String> treeMap = new TreeMap<>(new IdAscendingComparator());
    		treeMap.put(student1, "我是学生1，我的名字叫A");
    		treeMap.put(student2, "我是学生2，我的名字叫B");
    		treeMap.put(student3, "我是学生3，我的名字叫C");
    		treeMap.put(student4, "我是学生4，我的名字叫D");
    		treeMap.put(student5, "我是学生5，我的名字叫E");

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 24]

# 5.堆结构 #

# 6.图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 25]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 26]

对点的描述  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 27]

package class16;
    
    import java.util.ArrayList;
    
    // 点结构的描述
    public class Node { 
    	public int value;
    	public int in; //有多少个点指向本点
    	public int out;//本点指向多少其他的点
    	public ArrayList<Node> nexts; //从本点出发有那些指向的邻居
    	public ArrayList<Edge> edges;//从本点出发有多少直接的边
    
    	public Node(int value) { 
    		this.value = value;
    		in = 0;
    		out = 0;
    		nexts = new ArrayList<>();
    		edges = new ArrayList<>();
    	}
    }

对边的描述

package class16;
    
    import java.util.HashMap;
    import java.util.HashSet;
    
    public class Graph { 
    	public HashMap<Integer, Node> nodes;
    	public HashSet<Edge> edges;
    	
    	public Graph() { 
    		nodes = new HashMap<>();
    		edges = new HashSet<>();
    	}
    }

## 1.图的宽度优先遍历 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 28]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 29]

package class16;
    
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class Code01_BFS { 
    
    	// 从node出发，进行宽度优先遍历
    	public static void bfs(Node start) { 
    		if (start == null) { 
    			return;
    		}
    		Queue<Node> queue = new LinkedList<>();
    		HashSet<Node> set = new HashSet<>();
    		queue.add(start);
    		set.add(start);
    		while (!queue.isEmpty()) { 
    			Node cur = queue.poll();
    			System.out.println(cur.value);
    			for (Node next : cur.nexts) { 
    				if (!set.contains(next)) { 
    					//放入队列同步放入set,防止后续重复放入队列
    					set.add(next);
    					queue.add(next);
    				}
    			}
    		}
    	}
    
    }

## 图的深度优先遍历 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 30]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 31]

package class16;
    
    import java.util.HashSet;
    import java.util.Stack;
    
    public class Code02_DFS { 
    
    	public static void dfs(Node node) { 
    		if (node == null) { 
    			return;
    		}
    		Stack<Node> stack = new Stack<>();
    		HashSet<Node> set = new HashSet<>();
    		stack.add(node);
    		set.add(node);
    		//入栈后就打印
    		System.out.println(node.value);
    		while (!stack.isEmpty()) { 
    			Node cur = stack.pop();
    			for (Node next : cur.nexts) { 
    				if (!set.contains(next)) { 
    					stack.push(cur);
    					stack.push(next);
    					set.add(next);
    					System.out.println(next.value);
    					//如果节点next节点（一个邻居）不存在set中就跳出循环，不在遍历这个节点其他邻居
    					break;
    				}
    			}
    		}
    	}
    	
    	
    	
    
    }

# 5.二叉树 #

## 1. 遍历二叉树 ##

### 1.递归方式遍历 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 32]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 33]

public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int v) { 
    			value = v;
    		}
    	}
    
    	public static void f(Node head) { 
    		if (head == null) { 
    			return;
    		}
    		// 1
    		f(head.left);
    		// 2
    		f(head.right);
    		// 3
    	}
    
    	//先中后，指的是头打印的位置
    	// 先序打印所有节点 //先序遍历, 头左右
    	public static void pre(Node head) { 
    		if (head == null) { 
    			return;
    		}
    		System.out.println(head.value);
    		pre(head.left);
    		pre(head.right);
    	}
    	//中序遍历, 左头右
    	public static void in(Node head) { 
    		if (head == null) { 
    			return;
    		}
    		in(head.left);
    		System.out.println(head.value);
    		in(head.right);
    	}
    //后续遍历 左右头
    	public static void pos(Node head) { 
    		if (head == null) { 
    			return;
    		}
    		pos(head.left);
    		pos(head.right);
    		System.out.println(head.value);
    	}

### 2.非递归方式遍历 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 34]

public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int v) { 
    			value = v;
    		}
    	}

//先中后，指的是头打印的位置
    	// 先序打印所有节点 //先序遍历, 头左右
    	public static void pre(Node head) { 
    		System.out.print("pre-order: ");
    		if (head != null) { 
    			Stack<Node> stack = new Stack<Node>();
    			stack.add(head);
    			while (!stack.isEmpty()) { 
    				head = stack.pop();
    				System.out.print(head.value + " ");
    				// 因为是先序，头左右 ，所以进栈的一定先右后左，出栈的时候才能先左后右
    				// 有右压入右
    				if (head.right != null) { 
    					stack.push(head.right);
    				}
    				//有左压入左
    				if (head.left != null) { 
    					stack.push(head.left);
    				}
    			}
    		}
    		System.out.println();
    	}

**后续打印：使用两个栈，  
先续打印的时候不打印，直接放到最后一个栈中，最后再打印。**

//后续遍历 左右头
    	public static void pos1(Node head) { 
    		System.out.print("pos-order: ");
    		if (head != null) { 
    			Stack<Node> s1 = new Stack<Node>();
    			Stack<Node> s2 = new Stack<Node>();
    			s1.push(head);
    			while (!s1.isEmpty()) { 
    				head = s1.pop(); // 头 右 左
    				//先续打印的时候不打印，直接放到最后一个栈中
    				s2.push(head);
    				if (head.left != null) { 
    					s1.push(head.left);
    				}
    				if (head.right != null) { 
    					s1.push(head.right);
    				}
    			}
    			// 左 右 头
    			//最后再打印 第二个栈
    			while (!s2.isEmpty()) { 
    				System.out.print(s2.pop().value + " ");
    			}
    		}
    		System.out.println();
    	}

中序打印  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 35]

//中序遍历, 左头右
    	public static void in(Node cur) { 
    		System.out.print("in-order: ");
    		if (cur != null) { 
    			Stack<Node> stack = new Stack<Node>();
    			while (!stack.isEmpty() || cur != null) { 
    				//先压入整条左边界
    				if (cur != null) { 
    					stack.push(cur);
    					cur = cur.left;
    				} else { 
    					//取出打印
    					cur = stack.pop();
    					System.out.print(cur.value + " ");
    					cur = cur.right;
    				}
    			}
    		}
    	}

### 3.按层遍历 ###

二叉树的按层遍历即是图的宽度遍历，使用队列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 36]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 37]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 38]

public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int v) { 
    			value = v;
    		}
    	}
    
    	public static void level(Node head) { 
    		if (head == null) { 
    			return;
    		}
    		//LinkedList可以最为队列
    		Queue<Node> queue = new LinkedList<>();
    		queue.add(head);
    		while (!queue.isEmpty()) { 
    			Node cur = queue.poll();
    			System.out.println(cur.value);
    			if (cur.left != null) { 
    				queue.add(cur.left);
    			}
    			if (cur.right != null) { 
    				queue.add(cur.right);
    			}
    		}
    	}

### 4. 求二叉树最宽的层有多少个节点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 39]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 40]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 41]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 42]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 43]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 44]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 45]

public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) { 
    			this.value = data;
    		}
    	}
    
    
    	public static int maxWidthNoMap(Node head) { 
    		if (head == null) { 
    			return 0;
    		}
    		Queue<Node> queue = new LinkedList<>();
    		queue.add(head);
    		Node curEnd = head; // 当前层，最右节点是谁
    		Node nextEnd = null; // 下一层，最右节点是谁
    		int max = 0;
    		int curLevelNodes = 0; // 当前层的节点数
    		while (!queue.isEmpty()) { 
    			Node cur = queue.poll();
    			if (cur.left != null) { 
    				queue.add(cur.left);
    				nextEnd = cur.left;
    			}
    			if (cur.right != null) { 
    				queue.add(cur.right);
    				nextEnd = cur.right;
    			}
    			curLevelNodes++;
    			if (cur == curEnd) { 
    				max = Math.max(max, curLevelNodes);
    				curLevelNodes = 0;
    				curEnd = nextEnd;
    			}
    		}
    		return max;
    	}

//map记录层数

public static int maxWidthUseMap(Node head) { 
    		if (head == null) { 
    			return 0;
    		}
    		Queue<Node> queue = new LinkedList<>();
    		queue.add(head);
    		// key 在 哪一层，value
    		HashMap<Node, Integer> levelMap = new HashMap<>();
    		levelMap.put(head, 1);
    		int curLevel = 1; // 当前你正在统计哪一层的宽度
    		int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
    		int max = 0;
    		while (!queue.isEmpty()) { 
    			Node cur = queue.poll();
    			int curNodeLevel = levelMap.get(cur);
    			if (cur.left != null) { 
    				levelMap.put(cur.left, curNodeLevel + 1);
    				queue.add(cur.left);
    			}
    			if (cur.right != null) { 
    				levelMap.put(cur.right, curNodeLevel + 1);
    				queue.add(cur.right);
    			}
    			if (curNodeLevel == curLevel) { 
    				curLevelNodes++;
    			} else { 
    				max = Math.max(max, curLevelNodes);
    				curLevel++;
    				curLevelNodes = 1;
    			}
    		}
    		max = Math.max(max, curLevelNodes);
    		return max;
    	}

### 5 返回后继节点 ###

中序遍历，给定节点的后一个节点就是后继节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 46]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 47]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 48]

public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    		public Node parent;
    
    		public Node(int data) { 
    			this.value = data;
    		}
    	}
    
    	public static Node getSuccessorNode(Node node) { 
    		if (node == null) { 
    			return node;
    		}
    		if (node.right != null) { 
    			return getLeftMost(node.right);
    		} else {  // 无右子树
    			Node parent = node.parent;
    			while (parent != null && parent.right == node) {  // 当前节点是其父亲节点右孩子
    				node = parent;
    				parent = node.parent;
    			}
    			return parent;
    		}
    	}
    
    	public static Node getLeftMost(Node node) { 
    		if (node == null) { 
    			return node;
    		}
    		while (node.left != null) { 
    			node = node.left;
    		}
    		return node;
    	}

### 6.判断二叉树是否是完全二叉树 ###

按层遍历

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 49]

public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) { 
    			this.value = data;
    		}
    	}
    
    	public static boolean isCBT1(Node head) { 
    		if (head == null) { 
    			return true;
    		}
    		LinkedList<Node> queue = new LinkedList<>();
    		// 是否遇到过左右两个孩子不双全的节点
    		boolean leaf = false;
    		Node l = null;
    		Node r = null;
    		queue.add(head);
    		while (!queue.isEmpty()) { 
    			head = queue.poll();
    			l = head.left;
    			r = head.right;
    			if (
    			// 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
    			    (leaf && (l != null || r != null)) 
    			    || 
    			    (l == null && r != null)  //有右无左不是完全二叉树直接返回false
    
    			) { 
    				return false;
    			}
    			if (l != null) { 
    				queue.add(l);
    			}
    			if (r != null) { 
    				queue.add(r);
    			}
    			if (l == null || r == null) { 
    				leaf = true;
    			}
    		}
    		return true;
    	}

### 7.判断二叉树是否为平衡二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 50]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 51]

public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) { 
    			this.value = data;
    		}
    	}
    
    	public static boolean isBalanced1(Node head) { 
    		boolean[] ans = new boolean[1];
    		ans[0] = true;
    		process1(head, ans);
    		return ans[0];
    	}
    
    	public static int process1(Node head, boolean[] ans) { 
    		if (!ans[0] || head == null) { 
    			return -1;
    		}
    		int leftHeight = process1(head.left, ans);
    		int rightHeight = process1(head.right, ans);
    		if (Math.abs(leftHeight - rightHeight) > 1) { 
    			ans[0] = false;
    		}
    		return Math.max(leftHeight, rightHeight) + 1;
    	}

### 8.判断二叉树是否为搜索二叉树 ###

搜索二叉树：任何一个子树的 左树比头小，右数比头大

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。  
节点的右子树只包含大于当前节点的数。  
所有左子树和右子树自身必须也是二叉搜索树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 52]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 53]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 54]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 55]

public static class Info { 
    		public boolean isBST;
    		public int max;
    		public int min;
    
    		public Info(boolean i, int ma, int mi) { 
    			isBST = i;
    			max = ma;
    			min = mi;
    		}
    
    	}
    
    	public static Info process(Node x) { 
    		if (x == null) { 
    			return null;
    		}
    		Info leftInfo = process(x.left);
    		Info rightInfo = process(x.right);
    		int max = x.value;
    		if (leftInfo != null) { 
    			max = Math.max(max, leftInfo.max);
    		}
    		if (rightInfo != null) { 
    			max = Math.max(max, rightInfo.max);
    		}
    		int min = x.value;
    		if (leftInfo != null) { 
    			min = Math.min(min, leftInfo.min);
    		}
    		if (rightInfo != null) { 
    			min = Math.min(min, rightInfo.min);
    		}
    		boolean isBST = true;
    		if (leftInfo != null && !leftInfo.isBST) { 
    			isBST = false;
    		}
    		if (rightInfo != null && !rightInfo.isBST) { 
    			isBST = false;
    		}
    		if (leftInfo != null && leftInfo.max >= x.value) { 
    			isBST = false;
    		}
    		if (rightInfo != null && rightInfo.min <= x.value) { 
    			isBST = false;
    		}
    		return new Info(isBST, max, min);
    	}

### 9. ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 56]

# 牛客网 #

## NC93 设计LRU缓存结构 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57Sr6J225L6g_size_20_color_FFFFFF_t_70_g_se_x_16]

public class Main { 
    
        public static void main(String[] args) { 
    
            int[][] operators = new int[][]{ { 1,1,1},{ 1,2,2},{ 1,3,2},{ 2,1},{ 1,4,4},{ 2,2}};
    
           Integer[]  result = LRU(operators,  3);
    
            List r = Arrays.asList(result);
            System.out.println(r);
            System.out.println("===============");
        }
    
        public static Integer[] LRU(int[][] operators, int k) { 
    
            List<Integer> result = new ArrayList<>();
    
            Lru lru = new Lru(k);
    
            for(int i = 0; i < operators.length; i++) { 
                int[] row = operators[i];
    
                if(row[0] == 1) { 
                    lru.set(row[1], row[2]);
                }
                 else if(row[0] == 2) { 
                    result.add(lru.get(row[1])) ;
                    }
                }
            // write code here
            System.out.println("=============");
            Integer[] r = new Integer[result.size()];
            return result.toArray(r);
        }
    }
    class Lru { 
        private LinkedList<Integer> list;
        private Map map;
        int size;
    
        public Lru(int k) { 
            list = new LinkedList<Integer>();
            map = new HashMap<>();
            this.size = k;
        }
    
        public void set(Integer key,Integer value) { 
            if(list.size() == size) { 
                map.remove(list.getFirst());
                list.removeFirst();
                map.remove(key);
            }
            list.addLast(key);
            map.put(key,value);
        }
    
        public Integer get(Integer key) { 
    
            if(map.containsKey(key)) { 
                list.remove(key);
                list.addLast(key);
                return (Integer)map.get(key);
            }
            return  -1;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70]: /images/20220829/e6761b9540784f10a6042feb7105ccc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 1]: /images/20220829/075f0b46c34647f885e8a3f74779ea4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 2]: /images/20220829/1f7722d4e30b4e7d9226ff25b1ce625e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 3]: /images/20220829/1c6a101243ef4540b1e332470da4136a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 4]: /images/20220829/60fbee7be3d046c7b4ac14cf4b0a75df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 5]: /images/20220829/be309deeac394cbcb4afd50ed9c19a4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 6]: /images/20220829/db0de598c9224bd486017d12ba76be79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 7]: /images/20220829/0aa872e4df74478eb6b6768d34198799.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 8]: /images/20220829/953224af64a645d8b9732fbb8da51877.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 9]: /images/20220829/3bdb4734f34644a0ade7ae694524ddf8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 10]: /images/20220829/70468e93a0184b46b1a1028a801d6c8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 11]: /images/20220829/5a764dc5e90444589dfeeb0d18ac310d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 12]: /images/20220829/34346339deb849cda20a8a874bfd34b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 13]: /images/20220829/2a3ddcf9099e4f768a4213ba07633b18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 14]: /images/20220829/b9c695f05e344596be56fc6db9b2eac0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 15]: /images/20220829/eb71f49cccda4542a17d29cdc6121169.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 16]: /images/20220829/cc41b44b57344ba597ee393465b9ed46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 17]: /images/20220829/464263749a814b858c67ea5c7eca2d96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 18]: /images/20220829/90131b9121b54b859720a8782dcca7e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 19]: /images/20220829/48c378930bc74070ad65a4b63963e5a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 20]: /images/20220829/f802a07abcaf4e26b2c898c74e8d3e92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 21]: /images/20220829/7599675f2b6e452fa422c1190b98a632.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 22]: /images/20220829/e12e1d83fdea4a289b44b3c861381125.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 23]: /images/20220829/9cdbfdc4e2fc461d948d8425cef4c51e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 24]: /images/20220829/a1e7d57fde70482e97a7e6cb8fc2cda8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 25]: /images/20220829/2660517082c640cb9afeffa0d450cee3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 26]: /images/20220829/bca6af0b0de54e328ae904283010ca8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 27]: /images/20220829/05d055a276b6484ca58bf3ed973a9703.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 28]: /images/20220829/0bddb9db12e84da7a7c725f6b0ce6a70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 29]: /images/20220829/2eabcee6a17e4190b8b455e35b2c32d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 30]: /images/20220829/80e6d465d2234a3694c3d8f158d5b34a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 31]: /images/20220829/e061a83883f44e18be258a06f5221b40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 32]: /images/20220829/e89832b34df94b88a1a2000974594166.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 33]: /images/20220829/25c4f2c8266b4ea0ad32e060173b4570.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 34]: /images/20220829/81ec9f7b5a7a4a0cba32a6c3b27edfcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 35]: /images/20220829/699af2beedce430caf64cd86e0d51512.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 36]: /images/20220829/8c7d1a22f5bd4116b84c0218f9d0a2a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 37]: /images/20220829/89d0f861af2e4fc597931d39c41e1a71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 38]: /images/20220829/c4b828a43a004791afe88a83d4a9995a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 39]: /images/20220829/972b8a40e4124324a13dab590aeef125.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 40]: /images/20220829/0ff6bc9b48694611bac36ec86d050093.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 41]: /images/20220829/4b3c25063156469fb7d822f97c92633c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 42]: /images/20220829/fecdb1e6a3fb4f86af30f2f0d962a66f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 43]: /images/20220829/d4680cf37af948209012c03d0389cc22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 44]: /images/20220829/df618f927eb4452e9e8121dbac5f3223.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 45]: /images/20220829/f0262ed2df124214a6f523f975486d81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 46]: /images/20220829/dff1826d16884956a7995b8a46a2d4ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 47]: /images/20220829/040f15bb9fe5428fac5a9c40aff44666.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 48]: /images/20220829/b0bff045360e42e19d3cba8896089453.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 49]: /images/20220829/32749b191c2b4e5c93bb2585b24fae39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 50]: /images/20220829/a96742ac43c04daf86000c06ec3486ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 51]: /images/20220829/7d91e08bf198490eb5061570fc8c244e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 52]: /images/20220829/859f947188df410cb938455fd6cfa029.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 53]: /images/20220829/ebb348976b0f44ee85d3fabfb36a609c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 54]: /images/20220829/4c9f92f4e22f45d0b7bcf1cdc0556a87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 55]: /images/20220829/4e7dcf2f1e6c46928087fd992d62dd2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 56]: /images/20220829/a76fc7daa5174651886f27d100f075f7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57Sr6J225L6g_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/6dfc05b680de4a949b67298d5d7346ee.png