1. 面试题 02.04. 分割链表
题目来源
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* left = head;
ListNode* right = head;
while (right){
if (right->val < x){
std::swap(left->val, right->val);
left = left->next;
}
right = right->next;
}
return head;
}
};
2. LCR 170. 交易逆序对的总数
题目来源
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
示例 1：
输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
class Solution {
public:
void MergeSort(vector<int>& record, int left, int right, vector<int>& temp, int& ret){
if (left >= right) return;
int mid = left + (right - left) / 2;
MergeSort(record, left, mid, temp, ret);
MergeSort(record, mid + 1, right, temp, ret);
int k = left, l = left, r = mid + 1;
while (l <= mid && r <= right){
if (record[l] > record[r]){
ret += mid - l + 1;
temp[k++] = record[r++];
}else{
temp[k++] = record[l++];
}
}
while (l <= mid) temp[k++] = record[l++];
while (r <= right) temp[k++] = record[r++];
for (int i = left; i <= right; i++){
record[i] = temp[i];
}
}
int reversePairs(vector<int>& record) {
vector<int> temp;
int ret = 0;
int n = record.size();
temp.resize(n);
MergeSort(record, 0, n - 1, temp, ret);
return ret;
}
};