左神算法笔记-4 链表

2022-08-10 13:28:12

我将违背我的本能，忤逆我的天性，永远爱你。

先总结一下之前讲的排序（上一节课遗留内容）

一、排序的稳定性 (02:56)
排序过程中相同的值，再经过排序算法的排序后，他们的相对次序保持不变。
（对于简单的基础类型数组中，用处不大，3和3都是3无所谓）但是按照两个指标来排序，可以得到，1到10班，每个班的同学都是按年龄排序 || 得到网站中物美价廉的商品

选择排序（不稳定）
33331333
先找1和第一个3交换第一个3就跑到后面去了
冒泡排序（可以实现稳定）
6 5 4 5 3 4 6
相邻两个数字比较，相等时不交换顺序，就可以保持稳定
插入排序（稳定）
3 2 2 —
右边的数在比较时，出现相等情况停在此时的位置即可实现稳定
归并排序（稳定）
merge是关键，当两个组merge的时候，比较左右数字的时候出现相等，先merge左边的就可以实现稳定性
快排（不稳定）
partation时不行了
6 7 6 6 3
以5为划分值，看6下一个，看7下一个，看6下一个，看6下一个，看3，比5小，直接交换3和第一个6，导致不稳定
堆排序（不稳定）
5 4 4 6
构建堆的时候很容易出现数字的交换导致稳定性被破坏
桶排序和基数排序（稳定）
不基于比较的排序容易实现相对次序不变
只要维持桶内的相对次序就可以实现。

二、总结（21：03）
按照时间复杂度空间复杂度稳定性三个维度

算法	时间复杂度	空间复杂度	稳定性
选择排序	O(N^2)	O(1)	NO
冒泡	O(N^2)	O(1)	YES
插入	O(N^2)	O(1)	YES
归并	O(N*logN)	O(N)	YES
随机快排	O(N*logN)	O(logN)	NO
堆排序	O(N*logN)	O(1)	NO

（1）基于比较的排序没法做到时间复杂度在O(NlogN)以下
（2）时间复杂度为O(NlogN)的排序，在保证空间复杂度在O(N)以下的，没法保证稳定性。

所以：
快排是最快的；
空间限制的时候用堆排；
需要稳定性用归并。

面试中的大坑：
奇数放在数组左边，偶数放在数组右边，稳定，时O（N）空O（1）能不能？
不能，经典快排的partition做不到稳定性但是经典快排的partition又是0-1标准和本题时一种调整策略，快排做不到，所以没法。

工程上对算法的改进
（1）充分利用O(NlogN)和O(N^2)的优势
调度整体运用的还是快排的思想，但是对小样本量的排序，采用常数时间极低的插
入排序，充分利用O(NlogN)和O(N^2)的优势

（2）考虑稳定性
对于基础类型的会使用不管稳定性的速度较快的排序策略，但是一旦出现非基础类型时，就会用考虑稳定性的算法策略，考虑稳定性

PS:在很多编程语言中提供的排序方法中都会利用这种综合排序的方法来写排序（为了充分利用每种算法的优势，使该语言的排序性能最大化）

三、哈希表和有序表（44：37）

Set和Map的区别？
Map：key–>value
Set：key

1.哈希表
在C++里叫UnOrderedMap/UnSortedMap 和 UnOrderedSet/UnSortedSet
在Java里叫HashSet和HashMap

hashSet1的key是基础类型->int类型（按值传递，针对基础类型，占的空间就是存放的东西的大小本身）

HashSet <Integer> hashSet1 = new HashSet<>();
hashSet1.add(1);//增
System.out.println(hashSet1.contains(1));//查（输出haspset中有没有1这个key）
//输出结果：true
hashSet1.remove(1);//删
System.out.println(hashSet1.contains(1));
//输出结果：false


//hashMap
HashMap <Integer,String> mapTest = new HashMap<>();
mapTest.put(1,"meng");//增
System.out.println(mapTest.containsKey(1));//查是否存在这个key
//输出结果：true
System.out.println(mapTest.get(1));//查这个key对应的value
//输出结果：meng
mapTest.put(1,"fan")；//当存储的key已经存在时，增就是改
System.out.println(mapTest.get(1));//查这个key对应的value
//输出结果：fan
mapTest.remove(1);//删除key = 1 的键值对，value一起会消失
System.out.println(mapTest.get(1));
输出结果：//null

哈希表在使用时认为，所有增删改查操作都是常数级别，但是这个常数是比数组直接寻址要大的

// hashSet2的key是非基础类型->Node类型（按照引用传递，哈希表中存放的值就是要放的东西的地址，此时哈希表的大小不受Node的影响，Node很大，在哈希表中也只是一个8字节的地址）
		nodeA = new Node(1)；//这个1是存储在Node结点里的一个属性
		nodeB = new Node(1);
		HashSet<Node> hashSet2 = new HashSet<>();
		hashSet2.add(nodeA);//增
//假设NodeA的地址是0x1122，那么在哈希表中存储的就是0x1122
		System.out.println(hashSet2.contains(nodeA));//检查值是否存在
		//输出结果：true
		System.out.println(hashSet2.contains(nodeB));
		//输出结果：false
		hashSet2.remove(nodeA);//删
		System.out.println(hashSet2.contains(nodeA));
		//输出结果：false

2、有序表（58：50）
在C++里叫OrderedMap/SortedMap 和 OrderedSet/SortedSet
在Java里叫TreeMap和TreeSet


//有序表是根据Key有序组织的，比HashMap更牛一些，HashMap能做到TreeMap都可以做到而且会有更多的功能

TreeMap<Integer, String> treeMap1 = new TreeMap<>();//这种key是基础类型的是天然可以比较大小，如果用非基础类型来做key就需要自己加入一个比较器、按值传递
		treeMap1.put(7, "我是7");//put与哈希表同样既是增也是改
		treeMap1.put(5, "我是5");
		treeMap1.put(4, "我是4");
		treeMap1.put(3, "我是3");
		treeMap1.put(9, "我是9");
		treeMap1.put(2, "我是2");
		System.out.println(treeMap1.containsKey(5));//同哈希表
		System.out.println(treeMap1.get(5));
		System.out.println(treeMap1.firstKey() + ", 我最小");//由于是有序组织的所以 可以找到最小的
		System.out.println(treeMap1.lastKey() + ", 我最大");//也能找到最大的
		System.out.println(treeMap1.floorKey(8) + ", 在表中所有<=8的数中，我离8最近");//能找到小于等于中最近的
		System.out.println(treeMap1.ceilingKey(8) + ", 在表中所有>=8的数中，我离8最近");//能找到大于等于中最近的
		System.out.println(treeMap1.floorKey(7) + ", 在表中所有<=7的数中，我离7最近");
		System.out.println(treeMap1.ceilingKey(7) + ", 在表中所有>=7的数中，我离7最近");
		treeMap1.remove(5);//可以删
		System.out.println(treeMap1.get(5) + ", 删了就没有了哦");

有序表在使用时操作是O（logN）级别（也很不错了）

四、单链表和双链表（1：10：10）
链表题目中有涉及换头的操作就需要返回值，不涉及换头操作时就不用返回值

简单例子：
打印有序链表的公共部分：两个指针分别指向链表的一头（以最小开始为例），比较
指针所指的元素，小的移动到下一个，相等打印并同时移动到下一个直到有一个越界

链表解题方法论（1：15：24）
笔试和面试对待题目的思想：
笔试一切为了时间复杂度；
面试时间复杂度第一位，寻找空间最省的方法

重要技巧：
（1）额外数据结构记录
（2）快慢指针

判断链表是否是回文结构（1：17：44）
笔试用栈，先进后出，挨个比较（只放右侧一半跟左侧挨个比较也可以）
怎么知道到一半了呢？
快慢指针：
快指针一次走两步，慢指针一次走一步，快指针走完时，慢指针刚好一半

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

// need n/2 extra space
	public static boolean isPalindrome2(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		Node right = head.next;
		Node cur = head;
		while (cur.next != null && cur.next.next != null) {
			right = right.next;
			cur = cur.next.next;
		}
		Stack<Node> stack = new Stack<Node>();
		while (right != null) {
			stack.push(right);
			right = right.next;
		}
		while (!stack.isEmpty()) {
			if (head.value != stack.pop().value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

面试：

把链表暂时修改成为

然后两个指针记住头和尾往中间移动的同时作比较到最后有一个为空了停止，每一步都一样的话就是回文，
返回前，将链表恢复；

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

看代码！！！

（1：45：00）
哈希表
key（老Node）value（新克隆的Node）

不用哈希表

码农公寓

相关文章