1--数组中的逆序对（51）
主要思路：
基于归并排序，视频讲解参考：数组中的逆序对
#include <iostream>
#include <vector>
class Solution {
public:
int reversePairs(std::vector<int>& nums) {
if(nums.size() <= 1) return 0;
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(std::vector<int>& nums, int left, int right){
if(left >= right) return 0;
int mid = left + (right - left) / 2;
int count1 = mergeSort(nums, left, mid);
int count2 = mergeSort(nums, mid+1, right);
int count3 = merge(nums, left, mid, mid+1, right);
return count1 + count2 + count3;
}
int merge(std::vector<int>& nums, int l1, int r1, int l2, int r2){
std::vector<int> tmp;
int count = 0;
int i = l1, j = l2;
while(i <= r1 && j <= r2){
if(nums[i] > nums[j]){
count = count + l2 - i;
tmp.push_back(nums[j]);
j++;
}
else{
tmp.push_back(nums[i]);
i++;
}
}
while(i <= r1){
tmp.push_back(nums[i]);
i++;
}
while(j <= r2){
tmp.push_back(nums[j]);
j++;
}
for(int i = l1, k = 0; i <= r2; i++, k++){
nums[i] = tmp[k];
}
return count;
}
};
int main(int argc, char *argv[]){
std::vector<int> test = {7, 5, 6, 4};
Solution S1;
int Res = S1.reversePairs(test);
std::cout << Res << std::endl;
return 0;
}2--两个链表的第一个公共结点（52）
主要思路：
两个指针分别指向 A 链表和 B 链表，先让两个指针走完自己的链表，再去走别人的链表，这样两个指针走的总路程是相等的；因此两个指针最终肯定会相遇，相遇的地点要么在结尾（不相交），要么在共有的结点中（相交），只需找到第一个共有的结点即可，此时两个指针指向同一个结点； （所以题目都可以这么浪漫的吗。。。 2023 07 20）
#include <iostream>
#include <vector>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == NULL || headB == NULL) return NULL;
ListNode *A = headA;
ListNode *B = headB;
while(A != B){
if(A != NULL){
A = A->next; // 先走完A
}
else{
A = headB; // 再走B
}
if(B != NULL){
B = B->next; // 先走完B
}
else{
B = headA; // 再走A
}
}
return A; // 走的总路程相等，A最终肯定会和B相遇，要么在NULL（不相交），要么在第一个共同的结点（相交）
}
};
int main(int argc, char *argv[]){
ListNode *Node1 = new ListNode(4);
ListNode *Node2 = new ListNode(1);
ListNode *Node3 = new ListNode(8);
ListNode *Node4 = new ListNode(4);
ListNode *Node5 = new ListNode(5);
Node1->next = Node2;
Node2->next = Node3;
Node3->next = Node4;
Node4->next = Node5;
ListNode *Node6 = new ListNode(5);
ListNode *Node7 = new ListNode(0);
ListNode *Node8 = new ListNode(1);
Node6->next = Node7;
Node7->next = Node8;
Node6->next = Node3;
Solution S1;
ListNode *Res = S1.getIntersectionNode(Node1, Node6);
std::cout << Res->val << std::endl;
return 0;
}3--在排序数组中查找数字 I（53-I）
主要思路：
假如数组不是有序的，可以使用哈希，哈希表 key 表示数组的元素，value表示出现的次数，最后只需查询 key 为target对应的个数即可；
#include <iostream>
#include <vector>
#include <map>
class Solution {
public:
int search(std::vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
std::map<int, int> hash;
for(int i = 0; i < nums.size(); i++){
if(hash.find(nums[i]) != hash.end()) hash[nums[i]] += 1;
else hash[nums[i]] = 1;
}
if(hash.find(target) != hash.end()) return hash[target];
else return 0;
}
};
int main(int argc, char *argv[]){
std::vector<int> test = {5, 7, 7, 8, 8, 10};
int target = 8;
Solution S1;
int res = S1.search(test, target);
std::cout << res << std::endl;
return 0;
}主要思路：
由于题目是有序的，因此使用二分法查询；
查找第一个比 target 大的数（右边界 right），查找第一个比 target 小的数（左边界 left），则与target 相同的数目为：right - left - 1;
#include <iostream>
#include <vector>
#include <map>
class Solution {
public:
int search(std::vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
int i = 0, j = nums.size() - 1;
// 查找右边界
while(i <= j){
int mid = i + (j - i) / 2;
if(target < nums[mid]) j = mid - 1;
else i = mid + 1;
}
int right = i;
i = 0;
// 查找左边界
while(i <= j){
int mid = i + (j - i) / 2;
if(target <= nums[mid]) j = mid - 1;
else i = mid + 1;
}
int left = j;
return right - left - 1;
}
};
int main(int argc, char *argv[]){
std::vector<int> test = {5, 7, 7, 8, 8, 10};
int target = 8;
Solution S1;
int res = S1.search(test, target);
std::cout << res << std::endl;
return 0;
}4--0~n-1中缺失的数字（53-II）
主要思路：
由于数组是有序的，可以使用二分法来查找缺失的数字；
当 nums[mid] == mid 时，缺失的数字肯定在右区间，执行 i = mid + 1;
否则执行 j = mid - 1，最后返回左指针即可；
#include <iostream>
#include <vector>
class Solution {
public:
int missingNumber(std::vector<int>& nums) {
int i = 0, j = nums.size() - 1;
while(i <= j){
int mid = i + (j - i) / 2;
if(nums[mid] == mid) i = mid + 1;
else j = mid - 1;
}
return i;
}
};
int main(int argc, char *argv[]){
std::vector<int> test = {0, 1};
Solution S1;
int res = S1.missingNumber(test);
std::cout << res << std::endl;
return 0;
}5--二叉搜索树的第k大结点（54）
主要思路：
