塔塔开(滑稽
- 1.删除排序链表中的重复元素
- 2.删除排序链表中的重复元素II
- 3.字典序的第k小数字
- 4.下一个排列
- 5.排序链表
- 6.随机链表的复制
- 7.数据流的中位数
1.删除排序链表中的重复元素
使每个元素就出现一次
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return nullptr;
ListNode* cur = head;
while (cur && cur->next) {
if (cur->val == cur->next->val) {
// Skip over duplicate nodes
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp; // Free memory if needed
} else {
// Move to the next distinct node
cur = cur->next;
}
}
return head;
}
};
2.删除排序链表中的重复元素II
重复的全删了，一个也不留
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = dummy;
while(cur && cur->next && cur->next->next){
//先把这个值存下来
int num = cur->next->val;
if(cur->next->next->val == num){
//可能不止2个
while(cur->next && cur->next->val == num){
cur->next = cur->next->next;
}
}
else cur = cur->next;
}
return dummy->next;
}
};
以上两题放在一起是故意的，学一学这个这个写法
3.字典序的第k小数字
给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。
输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
字节考频top10
字典序答，什么是字典序？
简而言之，就是根据数字的前缀进行排序，比如 10 < 9，因为 10 的前缀是 1，比 9 小。再比如 112 < 12，因为 112 的前缀 11 小于 12。这样排序下来，会跟平常的升序排序会有非常大的不同。先给你一个直观的感受，一个数乘 10，或者加 1，哪个大？可能你会吃惊，后者会更大。
class Solution {
public:
int findKthNumber(int n, int k) {
int curr = 1; // 从字典序第一个数字1开始
k--; // 减1是因为我们已经在第一个位置（数字1）
while (k > 0) {
int steps = calculateSteps(n, curr, curr + 1);
if (steps <= k) {
// k在当前前缀范围之外，跳到下一个前缀
curr += 1;
k -= steps;
} else {
// k在当前前缀范围之内，向下移动到更小的前缀
curr *= 10;
k -= 1;
}
}
return curr;
}
private:
int calculateSteps(int n, long curr, long next) {
int steps = 0;
while (curr <= n) {
steps += std::min((long)n + 1, next) - curr;
curr *= 10;
next *= 10;
}
return steps;
}
};
findKthNumber：找到字典序第 k 小的数字。
从 curr = 1 开始，每次根据剩余的 k 确定是向下移动还是进入下一个数字前缀。
当 k == 0 时，curr 就是第 k 小的数字。
calculateSteps：计算以 curr 为前缀的子树节点数量。
curr 和 next 分别代表当前前缀和下一个前缀的起始数字，通过扩大 10 倍逐层计算包含的节点数。
4.下一个排列
整数数组的下一个排列是指其整数的下一个字典序更大的排列。
arr = [1,2,3]的下一个排列是[1,3,2]。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
现在给一个序列5 2 4 3 1，找下一个字典序排列，可以按照以下步骤：
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i = n - 2;
// Step 1: Find the first decreasing element from the end
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// Step 2: If we found a valid i, find the next largest element to swap with
if (i >= 0) {
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums[i], nums[j]);
}
// Step 3: Reverse the decreasing sequence to get the smallest lexicographical order
reverse(nums.begin() + i + 1, nums.end());
}
};
step3中，笃定了nums[i]的右侧一定是降序的，所以总结reverse成升序，为什么这么笃定呢？
因为我们一开始找i，找的就是逆序数，找到了i，就意味着i的右侧都是顺序数，也就是降序
现在交换了nums[i]和一个比nums[i]大的最小数，右侧排序仍然是降序的，不会有任何改变！
5.排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
要对链表进行排序，可以使用归并排序，因为归并排序在链表上非常高效，且可以在O(nlogn)时间复杂度内完成
归并排序的思路是将链表递归拆成两半，对每一半进行排序，然后将它们合并。具体步骤如下：
- 使用快慢指针找到链表的中间节点，以便将链表分成两半。
- 递归对左右两半分别进行排序。
- 使用合并两个有序链表的方法将两半合并成一个有序链表。
class Solution {
public:
ListNode* sortList(ListNode* head) {
// Base case: If the list is empty or has only one node, it's already sorted
if(!head || !head->next) return head;
// Step 1: Use fast and slow pointers to find the middle of the list
ListNode* fast = head;
ListNode* slow = head;
ListNode* pre = nullptr;
while(fast && fast->next){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
// Cut the list into two halves
pre->next = nullptr;
// Step 2: Recursively sort each half
ListNode* left = sortList(head);
ListNode* right = sortList(slow);
// Step 3: Merge the sorted halves
return merge(left, right);
}
ListNode* merge(ListNode* l1, ListNode* l2){
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
while(l1 && l2){
if(l1->val < l2->val){
tail->next = l1;
l1 = l1->next;
}else{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// If there are remaining elements in either list, append them
if(l1){
tail->next = l1;
}else{
tail->next = l2;
}
return dummy->next;
}
};
6.随机链表的复制
题意解读：
创建一个新链表 链表的所有东西 val next random都要与原链表完全相同 但是node的地址不能和原链表相同 也就是进行深拷贝 类似c++类中有指针 要自定义拷贝构造函数
分析：
要复制一个带有随机指针的链表，可以分成几个步骤来完成。这里采用一种O(n)的时间复杂度和O(1)的空间复杂度的方法。这个方法的核心是将链表的节点复制一份并插入到原链表中，然后调整随机指针，最后将原链表和复制的链表分离。
思路：
第一步：在原链表中插入新节点
遍历原链表的每个节点，对每个节点创建一个新节点，并将新节点插入到原节点的后面。如果原链表是A->B->C，插入新节点后变成A->A’->B->B’->C->C’。
第二步：设置新节点的随机指针
遍历链表，对每个新节点设置其random指针。由于新节点在原节点的后面，因此node->next->random应该指向node->random->next（如果 node->random 不为空的话）。
上一句解释：
举例：
假设原链表node1->node2->node3
node1->random = node3
node2->random = node1
node3->random = node2
通过第一步，我们应该将复制的节点node1’，node2’，node3’加上去，结果如下
node1->node1’->node2->node2’->node3->node3’
现在我们需要更改random指针，比如node1’，我们需要他的random指针指向node3’而不是node3
所以更改random指针这一步是node->next->random = node->random->next！！！
第三步：将原链表和复制链表分离
再次遍历链表，将新节点从原链表中分离出来形成新的链表
在这个问题中，深拷贝的知识点是指创建一个完全独立的复制链表，其中每个节点都是原链表中节点的独立副本。具体来说，原链表中的每个节点不仅要复制他的值和next指针，还要复制他的random指针（指向链表中的任意节点或空指针）。而且，复制链表中的节点不能引用到原链表中的节点，必须是完全独立的。
独立的新节点：深拷贝会创建新的节点对象，而不是直接引用原节点对象。这意味着复制链表中的每个节点在内存中是独立的，与原链表中的节点没有共享部分。即使原链表被修改，复制链表的内容也不会受到影响。
复制复杂结构：对于一个有复杂指针结构（例如 random 指针）的数据结构，深拷贝要求复制每一个指针引用关系。在这个链表中，除了复制 next 指针，还要确保 random 指针也复制到新链表中相应位置。
避免浅拷贝问题：浅拷贝只会简单复制原链表节点的指针，使新链表中的节点指向原链表中的节点。这会导致原链表和复制链表共享相同的节点对象，若修改一个链表中的节点，另一个链表也会受到影响。在这个题目中，我们需要完全独立的复制链表，避免这样的副作用。
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
// Step 1: 创建新节点并插入到原节点后面
Node* curr = head;
while (curr) {
Node* newNode = new Node(curr->val);
newNode->next = curr->next;
curr->next = newNode;
curr = newNode->next;
}
// Step 2: 设置新节点的 random 指针
curr = head;
while (curr) {
if (curr->random) {
curr->next->random = curr->random->next;
}
curr = curr->next->next;
}
// Step 3: 将原链表和复制链表分离,注意！！不要破坏原链表！！
curr = head;
Node* newHead = head->next;
Node* copy = newHead;
while (curr) {
curr->next = curr->next->next;
if (copy->next) {
copy->next = copy->next->next;
}
curr = curr->next;
copy = copy->next;
}
return newHead;
}
};
7.数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。
输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
第一个数组是操作顺序，第二个数组是操作对应的数字
本题的核心思路是使用两个堆，也就是两个优先队列
小的倒三角就是个大顶堆，梯形就是个小顶堆，中位数可以通过它们的堆顶元素算出来：
addNum(int num)函数，当添加一个数时，首先判断该数应当放入哪个堆（大根堆或小根堆）。根据当前堆的大小，调整堆的平衡，确保两个堆的元素数目差不超过1。
findMedian()如果两个堆的大小相等，返回两个堆顶元素的平均值，如果堆的大小不等，直接返回大根堆的堆顶元素，因为它代表了数据流的中位数
class MedianFinder {
private:
priority_queue<int> maxHeap; // 大根堆，用于存储较小的一半
priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆，用于存储较大的一半
public:
/** Initialize your data structure here. */
MedianFinder() {}
/** Adds a number into the data structure. */
void addNum(int num) {
// 保证maxHeap存储较小部分，minHeap存储较大部分
if (maxHeap.empty() || num <= maxHeap.top()) {
maxHeap.push(num); // 如果num小于等于maxHeap的堆顶，加入maxHeap
} else {
minHeap.push(num); // 否则加入minHeap
}
// 平衡两个堆，使得maxHeap和minHeap的大小差不超过1
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
/** Returns the median of current data stream */
double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.top() + minHeap.top()) / 2.0; // 两个堆大小相等，取两个堆顶的平均值
} else {
return maxHeap.top(); // 如果maxHeap多一个元素，返回maxHeap的堆顶元素
}
}
};
