day5题目：、、
学习计划链接：
今日知识点：数学、数组、快排，难度为中等、中等、困难
7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1： 输入：x = 123 输出：321
思路
看了题解才晓得，是数学题嗷，通过不等式变换 这我是真没想到（） 取巧一些的话就用long long存防止溢出
完整代码
class Solution {
public:
int reverse(int x) {
int ans = 0;
while(x) {
if(ans > INT_MAX/10 || ans < INT_MIN/10) return 0;
ans = (ans*10) + x%10;
x /= 10;
}
return ans;
}
};
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
思路
完整代码
暴力（时间反而很快
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
return nums[k-1];
}
};
手写快排，主元在s~e中随机抽取以避免最坏情况。
class Solution {
public:
int quickSort(vector<int>& nums, int k, int s, int e) {
int idx = rand()%(e-s+1)+s;
int m = nums[idx]; // 主元为s~e中随机的一个
int l = s, r = e;
nums[idx] = nums[l];
while(l != r) {
while(l < r && nums[r] <= m) --r; // 遇到右边有比他大的才停下
nums[l] = nums[r];
while(l < r && nums[l] >= m) ++l;
nums[r] = nums[l];
}// 处理完后主元m到了正确的位置nums[l]，左边元素都比他大，右边元素都比他小
nums[l] = m;
if(l == k-1) return nums[l];
else if(l > k-1) return quickSort(nums, k, s, l-1); // 快排左边部分
else return quickSort(nums, k, l+1, e);
}
int findKthLargest(vector<int>& nums, int k) {
int len = nums.size();
return quickSort(nums, k, 0, len-1);
}
};
23. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
思路
day1就写过合并两个有序链表，这次的只需要暴力就好了。 但要优化的话，可以使用优先队列每次链表头的结点，取出最顶上的结点放至答案链表后。
完整代码
暴力版
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var mergeList = function(list1, list2) {
let p1 = list1;
let p2 = list2;
if(!p1 && !p2) return null;
else if(!p1) return p2;
else if(!p2) return p1;
else if(p1.val <= p2.val) {
p1.next = mergeList(p1.next, p2);
return p1;
} else {
p2.next = mergeList(p2.next, p1);
return p2;
}
}
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
let ans = null;
let len = lists.length;
for(let i = 0; i < len; ++i) {
ans = mergeList(ans, lists[i]);
}
return ans;
};
优先队列版
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
struct Node {
int val;
ListNode *nowp;
bool operator<(const Node &p1) const {
return val > p1.val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<Node> q;
ListNode head;
ListNode *tail = &head;
for(auto h: lists) {
if(h) q.push({h->val, h});
}
while(!q.empty()) {
Node nowv = q.top();
q.pop();
tail->next = nowv.nowp;
tail = tail->next;
ListNode* nexp = nowv.nowp->next;
if(nexp) q.push({nexp->val, nexp});
}
return head.next;
}
};
