算法与数据结构_4_稳定性、排序算法总结、综合排序、哈希表、有序表

HashSet<Integer> hashSet1 = new HashSet<>();
hashSet1.add(3); // add 添加
System.out.printf(hashSet1.contains(3)); // contains 是否包含
hashSet1.remove(3); // remove 删除
System.out.printf(hashSet1.contains(3));

HashMap<Integer, String> mapTest = new HashMap<>();
mapTest.put(1, "jia"); // 添加
mapTest.put(1, "yi"); // 覆盖
mapTest.put(2, "2"); // 添加

System.out.printf(mapTest.containsKey(1));
System.out.printf(mapTest.get(1));

mapTest.remove(2);
System.out.printf(mapTest.get(2)); // null

TreeMap<Integer, String> treeMap1 = new TreeMap<>();
treeMap1.put(7, "我是7");
treeMap1.put(2, "我是2");
treeMap1.put(9, "我是9");

System.out.printf(treeMap1.containsKey(7));
System.out.printf(treeMap1.get(7));
System.out.printf(treeMap1.firstKey() + "我最小");
System.out.printf(treeMap1.lastKey() + "我最大");
System.out.printf(treeMap1.floorKey(8) + "在表中<=8，且离8最近");
System.out.printf(treeMap1.ceilingKey(8) + "在表中>=8，且离8最近");
treeMap1.remove(7);

// 准备一个栈，所有东西压到栈里去，从头遍历,每一次比较head和栈里弹出的，有一次不同就返回false，每一步都一样返回true
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;
}

public static boolean isPalindrome2(Node head)
{
	if (head == null || head.next == null)
	{
		return true;
	}
	Node n1 = head;
	Node n2 = head;
	while (n2.next != null && n2.next.next != null) // 找中点
	{
		n1 = n1.next; // 慢指针一次走一步，最终走到中点
		n2 = n2.next.next; // 快指针一次走两步，最终走到结束
	}

	// 从n1开始做逆序
	// 1->2->3->3->2->1
	// 1->2->3  3<-2<-1
	//       ↓
	//      null
	// 1->2->3->4->3->2->1
	// 1->2->3->4  3<-2<-1  (慢指针n1最初指向3)
	//          ↓
	//         null
	n2 = n1.next; // n2 -> right part first node
	n1.next = null; // mid.next -> null
	Node n3 = null;
	while (n2 != null)
	{
		n3 = n2.next; // 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)
	{
		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;
}

// 不用额外的数据结构，用有限的几个变量搞定
// 6个变量，<部分的头、尾 =部分的头、尾 >部分的头、尾 初始值为null
// 遍历，发现第一个，头和尾都指向这个数，再发现一个，尾改成这个
// 最后3部分串起来，注意空指针，注意边界

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 bH = null; // big head
	Node bT = null; // big tail
	Node next = null; // save next node

	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 (bH == null)
			{
				bH = head;
				bT = head;
			}
			else
			{
				bT.next = head;
				bT = head;
			}
		}
		head = next;
	}
	if (sT != null) // 如果有小于区域
	{
		sT.next = eH;
		eT = eT == null ? sT : eT; // 谁去连大于区域的头谁就变成eT
	}
	// 上面的if 不管跑了没有，et
	if (eT != null) // 如果小于区域和等于区域不是都没有
	{
		eT.next = bH;
	}
	return sH != null ? sH : (eH != null ? eH : bH);
}

// 如果用额外空间，用哈希表
// key(老节点) value(新节点)
// 第二部设置新节点的next、rand指针，通过map

public static Node copyListWithRand1(Node head)
{
	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) 新
		map.get(cur).next = map.get(cur.next);
		map.get(cur).rand = map.get(cur.rand);
		cur = cur.next;
	}
	return map.get(head);
}

// 不用哈希表
// 把克隆节点就放在老链表中该老节点的下一个，
// 克隆节点去串上老链表的这个节点
// 如1->1’->2->2’->null
// 这时设置新节点的next、rand指针都为老节点的next + 1、rand + 1位置
// 最后在next位置上把新链表分离开来

public static Node copyListWithRand2(Node head)
{
	if (head == null)
	{
		return null;
	}
	Node cur = head;
	Node next = null; // tmp node
	// copy node and link to every node
	// 1 -> 2
	// 1 -> 1’ -> 2
	while (cur != null)
	{
		next = cur.next;
		cur.next = new Node(cur.value);
		cur.next.next = next;
		cur = next;
	}
	cur = head;
	Node curCopy = null;
	// set copy node rand
	while (cur != null)
	{
		next = cur.next.next;
		curCopy = cur.next;
		curCopy.rand = cur.rand != null ? cur.rand.next : null;
		cur = next;
	}
	Node res = head.next;
	cur = head;
	// split
	while (cur != null)
	{
		next = cur.next.next;
		curCopy = cur.next;
		cue.next = next;
		curCopy.next = next != null ? next.next : null;
		cur = next;
	}
	return res;
}

// 找到链表第一个入环节点，如果无环，返回null
public static Node getLoopNode(Node head)
{
	if (head == null || head.next == null || head.next.next == null)
	{
		return null;
	}
	Node n1 = head.next; // 慢指针
	Node n2 = head.next.next; // 快指针
	while (n1 != n2)
	{
		if (n2.next == null || n2.next.next == null)
		{
			return null;
		}
		n2 = n2.next.next;
		n1 = n1.next;
	}

	n2 = head; // walk again
	while (n1 != n2)
	{
		n1 = n1.next;
		n2 = n2.next;
	}
	return n1;
}

// 情况1 : loop1 == null , loop2 == null
// 两个无环单链表，如果相交，从相交的时刻走到最后一定相同
// 链表1 : head1 ...len1(假设长度为100)... end1
// 链表2 : head2 ...len2(假设长度为80)... end2
// 先判断end1和end2是否相同，如果相同，则有相交
// 长链表先走差值步(假设为100-80=20)，再两链表一起走，一定会共同迈到交叉节点

public static Node noLoop(Node head1, Node head2)
{
	if (head1 == null || head2 == null)
	{
		return null;
	}
	Node cur1 = head1;
	Node cur2 = head2;
	int n = 0;
	while (cur1.next != null)
	{
		n++;
		cur1 = cur1.next;
	}
	while (cur2.next != null)
	{
		n--;
		cur2 = cur2.next;
	}
	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;
}

// 情况2 : loop1、loop2有一个为null，即一个有环一个无环
// 情况3 : 两个链表都有环
// 情况3分为3种情况
// 1) 两个链表不相交
// 2) 两个链表相交，且入环节点相同
// 3) 两个链表相交，且入环节点不同

public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2)
{
	Node cur1 = null;
	Node cur2 = null;
	if (loop1 == loop2) // 情况2
	{
		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
	{
		cur1 = loop1.next;
		while (cur1 != loop1)
		{
			if (cur1 == loop2)
			{
				return loop1;
			}
			cur1 = cur1.next;
		}
		return null;
	}
}

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;
}