左神算法基础巩固--2
文章目录
- 稳定性
- 选择排序
- 冒泡排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
- 哈希表
- 链表
- 解题
- 总结
稳定性
稳定性是指算法在排序过程中保持相等元素之间相对顺序的特性。具体来说，如果一个排序算法是稳定的，那么对于任意两个相等的元素，在排序前它们的相对顺序与排序后它们的相对顺序是相同的。
稳定性对于常见进行数字排序的情况没有意义但对于复杂类型的排序来说是一个特别重要的一件事。
举例说明：我们对于一个班级的所有学生先按照年龄进行排序，再按照成绩进行排序，如果排序算法具有稳定性的话便会得到一个如果成绩相同则年龄较小的会排在前面的对象数组。这就是算法稳定性的运用。
前文我们提到的那几种排序算法中并不是所有的算法都具有稳定性的
选择排序
选择选择排序是不具有稳定性的，根据选择排序的算法思路来说，选择排序会先在数组中找到小值并将其与对应位置的数进行交换，故如果出现以下这种情况，那么其就不具有稳定性
冒泡排序
冒泡排序是否具有稳定性得看你在什么时候交换位置，如果相等你不交换二者的位置，那么冒泡排序便是具有稳定性的。以以下数组为例
由冒泡排序的算法思想得在第一次遍历后0位置上的6会在5位置上只要原0位置上的数不与5位置上的6交换则此时算法是具有稳定性的
插入排序
插入排序和冒泡排序类似，只要我们设定正确的在两数相同的情况下不交换两数的位置，那么此时该算法就是具有稳定性的以以下数组为例
该数组在0-0范围内是有序的，在0-1范围内需要交换位置，交换后数组为2 3 2 … ，在0-2范围内由于2位置上的数与0位置上的数相同只要我们不交换二者的位置，此时该算法具有稳定性
归并排序
归并排序的稳定性取决于其merge的实现，只要我们在merge的时候实现两数相等时先拷贝左侧的数便能实现稳定性
以以下数组为例
在这个数组中1与1相等，只要我们在将数组整理时，先拷贝左侧的1便能实现该算法的稳定性
快速排序
快速排序则是做不到稳定性的，主要原因在于快速排序的partition过程，在partition过程中会将从前往后的第一个小于基准值的数与左界限后的第一个数交换位置，这一步骤便破坏了稳定性。
以以下数组为例
在该数组中找到第一个小于基准数的数为3此时他要与左界限后的第一个数6交换位置此时便破坏了稳定性。
堆排序
堆排序也做不到稳定性，堆排序是以维护自身的堆结构来实现排序的，因此其在设计之初便完全没有考虑稳定性
以以下数组为例
在加入这个6后堆排序会去维持其堆结构即将6挂载在第一个4的后面并进行比较由于6比4大，所以6会与第一个4交换位置，此时便破坏了稳定性
下面是算法稳定性的总结
一些常见的坑
注意：这些算法并不是相互分离不可结合的，以选择排序和快速排序为例，虽然选择排序的时间复杂度为n^2快速排序的时间复杂度为nlogn 但是在n比较小的情况下，其实选择排序的所需时间是比快速排序要少的，因此可以进行判断如果n较小便使用选择排序，如果n较大便使用快速排序。
哈希表
常用的操作
链表
解题
笔试思路：先用快慢指针遍历这个链表得到链表的前半部分和后半部分，将这个链表的前半部分加入到一个栈中，在加入后，遍历后半个链表，每遍历一个都与使栈弹出的数进行比较如果两数相等便接着比较，如果栈或链表为空了则说明该链表是回文结构，如果出现不相等的情况则说明该链表不是回文结构。
import java.util.Stack;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 使用快慢指针找到中间节点
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 将前半部分链表的节点值压入栈中
Stack<Integer> stack = new Stack<>();
ListNode temp = head;
while (temp != slow) {
stack.push(temp.val);
temp = temp.next;
}
// 如果链表长度为奇数，跳过中间节点
if (fast != null) {
slow = slow.next;
}
// 比较后半部分链表的节点值与栈中的值
while (slow != null) {
if (slow.val != stack.pop()) {
return false;
}
slow = slow.next;
}
return true;
}
public static void main(String[] args) {
Solution solution = new Solution();
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(1);
boolean isPalindrome = solution.isPalindrome(head);
System.out.println("链表是否为回文结构: " + isPalindrome);
}
}
面试思路： 先用快慢指针，使当快指针走到尽头时，慢指针指向中点位置，然后将链表的后半部分反转，并使前半部分和后半部分均向中点靠拢并比较，如果两数相等便接着比较，直到遍历前半部分的指针和遍历后半部分的指针指向中点，就先将后半部分复原后返回true，如果不等就复原后返回false
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 使用快慢指针找到中间节点
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转链表的后半部分
ListNode prev = null;
ListNode curr = slow;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// 比较前半部分和反转后的后半部分
ListNode left = head;
ListNode right = prev;
boolean isPalindrome = true;
while (right != null) {
if (left.val != right.val) {
isPalindrome = false;
break;
}
left = left.next;
right = right.next;
}
// 恢复链表的后半部分
curr = prev;
prev = null;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return isPalindrome;
}
public static void main(String[] args) {
Solution solution = new Solution();
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(1);
boolean isPalindrome = solution.isPalindrome(head);
System.out.println("链表是否为回文结构: " + isPalindrome);
}
}
笔试思路：遍历链表，将链表的值加入到数组中，对数组进行partition，之后再将用得到的数组构建出一个链表。
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode partition(ListNode head, int pivot) {
if (head == null) return null;
// 初始化三个指针，分别指向小于、等于、大于pivot的链表头部
ListNode beforeSmaller = new ListNode(0);
ListNode beforeEqual = new ListNode(0);
ListNode beforeGreater = new ListNode(0);
// 当前节点
ListNode current = head;
// 尾指针
ListNode tailSmaller = beforeSmaller;
ListNode tailEqual = beforeEqual;
ListNode tailGreater = beforeGreater;
while (current != null) {
if (current.val < pivot) {
tailSmaller.next = current;
tailSmaller = tailSmaller.next;
} else if (current.val == pivot) {
tailEqual.next = current;
tailEqual = tailEqual.next;
} else {
tailGreater.next = current;
tailGreater = tailGreater.next;
}
current = current.next;
}
// 连接三个链表
tailSmaller.next = beforeEqual.next;
tailEqual.next = beforeGreater.next;
tailGreater.next = null;
// 返回新链表的头节点
return beforeSmaller.next;
}
public static void main(String[] args) {
Solution solution = new Solution();
ListNode head = new ListNode(4);
head.next = new ListNode(3);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(-1);
head.next.next.next.next = new ListNode(2);
head.next.next.next.next.next = new ListNode(3);
head.next.next.next.next.next.next = new ListNode(5);
int pivot = 2;
ListNode newHead = solution.partition(head, pivot);
// 打印结果，用于验证
while (newHead != null) {
System.out.print(newHead.val + " ");
newHead = newHead.next;
}
}
}
面试思路：遍历这个链表并根据他们的情况将链表节点加入到新建的三个链表中，遍历完成后，对链表进行拼接便能得到完整的解
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode partition(ListNode head, int pivot) {
// 虚拟头节点，方便操作
ListNode dummyBeforeSmaller = new ListNode(0);
ListNode dummyBeforeEqual = new ListNode(0);
ListNode dummyBeforeGreater = new ListNode(0);
ListNode smaller = dummyBeforeSmaller;
ListNode equal = dummyBeforeEqual;
ListNode greater = dummyBeforeGreater;
while (head != null) {
if (head.val < pivot) {
smaller.next = head;
smaller = smaller.next;
} else if (head.val == pivot) {
equal.next = head;
equal = equal.next;
} else {
greater.next = head;
greater = greater.next;
}
head = head.next;
}
// 连接三个链表
smaller.next = dummyBeforeEqual.next;
equal.next = dummyBeforeGreater.next;
greater.next = null;
return dummyBeforeSmaller.next;
}
public static void main(String[] args) {
Solution solution = new Solution();
ListNode head = new ListNode(4);
head.next = new ListNode(3);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(-1);
head.next.next.next.next = new ListNode(2);
head.next.next.next.next.next = new ListNode(3);
head.next.next.next.next.next.next = new ListNode(5);
int pivot = 2;
ListNode newHead = solution.partition(head, pivot);
// 打印结果，用于验证
while (newHead != null) {
System.out.print(newHead.val + " ");
newHead = newHead.next;
}
}
}
笔试思路：使用hash表将原节点与原节点对应的克隆节点加入到hash表中，其中hash表的key为原节点，value为克隆节点，之后再从原链表中找到对应的next指针对应的节点，将其从hash表中找到对应的克隆节点并赋值给源节点对应克隆节点的next指针，rand指针也是一样不断重复直到所有节点都判断过
class Node {
int value;
Node next;
Node rand;
Node(int val) {
value = val;
next = null;
rand = null;
}
}
public class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
// Step 1: 创建哈希表存储原始节点和克隆节点的映射
Map<Node, Node> map = new HashMap<>();
// Step 2: 遍历原始链表，克隆每个节点并存储在哈希表中
Node current = head;
while (current != null) {
map.put(current, new Node(current.value));
current = current.next;
}
// Step 3: 复制next和rand指针
current = head;
while (current != null) {
Node clone = map.get(current);
clone.next = map.getOrDefault(current.next, null);
clone.rand = map.getOrDefault(current.rand, null);
current = current.next;
}
// Step 4: 返回新链表的头节点
return map.get(head);
}
}
面试思想：首先在原链表上克隆每个节点并使原节点的的next指针指向克隆节点，克隆节点的next指针指向原节点的next指针所指节点，之后再遍历原链表节点的next指针和rand指针并在克隆节点上对应指向
class Node {
int value;
Node next;
Node rand;
Node(int val) {
value = val;
next = null;
rand = null;
}
}
public class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
// 第一步：克隆节点并建立连接
Node current = head;
while (current != null) {
Node clone = new Node(current.value);
clone.next = current.next;
current.next = clone;
current = clone.next;
}
// 第二步：复制 rand 指针
current = head;
while (current != null) {
Node clone = current.next;
if (current.rand != null) {
clone.rand = current.rand.next;
}
current = clone.next;
}
// 第三步：分离链表并返回新链表的头节点
Node newHead = head.next; // 新链表的头节点是原链表第一个节点的克隆节点
current = head;
while (current != null) {
Node clone = current.next;
current.next = clone.next; // 断开原始节点和克隆节点的连接
if (clone.next != null) {
clone.next = clone.next.next; // 跳过原始节点，连接到下一个克隆节点
}
current = current.next;
}
return newHead;
}
}
这道题需要直到环中快慢指针的问题，需要明确的是用两个指针其中快指针一次走两步，慢指针一次走一步遍历这个链表当这个链表存在环时，他两一定在环上相遇，同时再将快指针指向第一个节点，再次同时出发，他两一定在入环处相遇。
这道题要分为几种情况进行讨论：
1.两个链表不相交且无环
在这种情况下，我们先用快慢指针知道是否有环后，遍历这两个链表，并记录下每个链表的最后的节点和这个数组的长度，当这两个链表不相交且无环时，这两个链表所对应的最后的节点是不同的。
2.无环但相交
这种情况的判定方法，第一种情况类似我们先用快慢指针知道是否有环后，遍历这两个链表，并记录下每个链表的最后的节点和这两个链表的长度，并作差值n，当这两个链表相交但无环时，这两个链表所对应的最后的节点是相同的，同时记录下较长的链表让用指针指向其头部并先走n步，之后用指针指向另一链表的头部，两者同时走，两指针相等时便是两指针的相交节点。
之后便是有环结构了，这种情况需要统一分析
这三种情况的判定条件是入环节点loop1和loop2均不为空判断loop1是否等于loop2，如果相等则为情况2，否则让loop1继续往下走，如果loop1每遇见loop2就是第一种情况，如果遇见了就是情况3。
遇到情况1便可直接返回null,遇到情况二则与前面的无环链表相交类型，但以loop1为链表最后一个节点，遇到情况三则返回loop1或loop2
总结
提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。