模拟std::sort
class Solution {
public:
const int __threshold = 16;
int getMid(int a, int b, int c) {
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
return b;
}
void __quick_sort_v3(vector<int> &nums, int l, int r) {
while (r - l > __threshold) {
int x = l, y = r, z = getMid(nums[l], (nums[(l + r) >> 1]), nums[r]);
do {
while (nums[x] < z) x++;
while (nums[y] > z) y--;
if (x <= y) {
swap(nums[x], nums[y]);
x++, y--;
}
} while (x <= y);
__quick_sort_v3(nums, x + 1, r);
r = y;
}
}
void final_insert_sort(vector<int> &nums, int l, int r) {
// 无监督
int ind = l;
for (int i = l + 1; i <= r; i++) {
if (nums[i] < nums[ind]) ind = i;
}
while (ind > l) {
swap(nums[ind], nums[ind - 1]);
ind--;
}
for (int i = l + 2; i <= r; i++) {
int j = i;
while (nums[j] < nums[j - 1]) {
swap(nums[j], nums[j - 1]);
j--;
}
}
return ;
}
vector<int> sortArray(vector<int>& nums) {
__quick_sort_v3(nums, 0, nums.size() - 1);
final_insert_sort(nums, 0, nums.size() - 1);
return nums;
}
};输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
if (nums.size() == 0) return nums;
int x = 0, y = nums.size() - 1;
do {
while (x < nums.size() && nums[x] & 1) x++;
while (y >= 0 && nums[y] % 2 == 0) y--;
if (x <= y) {
swap(nums[x], nums[y]);
x++, y--;
}
} while (x <= y);
return nums;
}
};采用类似快排的思想
怎么着partition的基准值呢？
这里取链表最大元素和最小元素的平均比较合适
所以就需要我们遍历一边链表保存max min
遍历链表拆成两部分。
h1链接比中间值小的
h2链接比中间值大的
最后再进行merge的操作
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr) return head;
int l = head->val, r = head->val;
double mid;
// h1链接比中间值小的 h2链接比中间值大的
// 最后再将h1的尾巴指向h2的头
ListNode *p = head, *q, *h1 = nullptr, *h2 = nullptr;
while (p) {
// 遍历一边链表保存max min
l = min(p->val, l);
r = max(p->val, r);
p = p->next;
}
if (l == r) return head;
// 取基准值
// 不能 / 2 会丢失精度
// -1 / 2 = 0
mid = (l + r) / 2.0;
p = head;
// 下面进行partition的过程
// h1->node(val <= mid)
// h2->node(val > mid)
while (p) {
// 保存p的下一个
// 不然p->next = h1之后就找不到了
q = p->next;
if (p->val <= mid) {
// 对h1 h2采用头插法
p->next = h1;
// p成为新的链表头节点
h1 = p;
} else {
p->next = h2;
h2 = p;
}
p = q;
}
// partition必然伴随着递归的过程
h1 = sortList(h1);
h2 = sortList(h2);
// 把h2接到h1尾部
p = h1;
while (p->next) p = p->next;
p->next = h2;
return h1;
}
};非常像快排的partition操作
也是双指针
三路partition操作
class Solution {
public:
void three_partition(vector<int> &nums, int l, int r, int mid) {
if (l >= r) return ;
int x = -1, y = r + 1, i = l;
while (i < y) {
// 令i走到第一个不是1颜色的节点
if (nums[i] == mid) i++;
// 0颜色往前放
// 此时x++正好指向1颜色
// 也就是一定是将1颜色换过来了
// 而1颜色是不需要判断位置的 所以往后走
else if (nums[i] < mid) {
x++;
swap(nums[x], nums[i]);
i++;
} else if (nums[i] > mid) {
// 为什么这里不能i++？
// 因为不知道换过来的nums[y]是0还是1
// 要对这个位置判断
y--;
swap(nums[y], nums[i]);
}
}
return ;
}
void sortColors(vector<int>& nums) {
three_partition(nums, 0, nums.size() - 1, 1);
return ;
}
};因为每次快排总能分出两部分相对有序的数来
左边的n个一定小于基准值
也就是完成一趟之后 基准值左边是k个数
返回左边的区间就ok了
所以就可以利用快排的这个性质
class Solution {
public:
int getMid(int a, int b, int c) {
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
return b;
}
void quick_select(vector<int> &nums, int l, int r, int k) {
if (l >= r) return ;
int x = l, y = r, mid = getMid(nums[l], nums[(l + r) >> 1], nums[r]);
while (x <= y) {
// 分别找第一个不符合大小顺序的位置
// 然后交换
while (nums[x] < mid) x++;
while (nums[y] > mid) y--;
if (x <= y) {
swap(nums[x], nums[y]);
x++, y--;
}
}
// 注意这时x = y + 1了
// 因为y最小了
// 此时不妨以y为分割点看y前面是不是够k - 1个
if (y - l == k - 1) return ;
if (y - l >= k) {
// 缩小范围
quick_select(nums, l, y, k);
} else {
// 这里就不用扩大范围了
// 因为找出的y - l个有序
// 所以在右边找k - (y - k) + 1 == k - x + l个
quick_select(nums, x, r, k - x + l);
}
return ;
}
vector<int> smallestK(vector<int>& arr, int k) {
vector<int> ans;
if (k == 0) return ans;
quick_select(arr, 0, arr.size() - 1, k);
while (k) ans.push_back(arr[--k]);
return ans;
}
};其实就是站在每个节点向下看
看下面的子节点会有多少种结构
然后分层遍历
每层从l遍历到r
每个节点都生成两个子树
再进入这两个子树递归子树的字节点
和代码随想录的回溯框架一样
终止条件就是l >= r
站在3的位置看到左子树会有两种结构
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode *> dfs(int l, int r) {
vector<TreeNode *> ans;
if (l > r) {
ans.push_back(nullptr);
return ans;
}
for (int i = l; i <=r; i++) {
vector<TreeNode *>left_tree = dfs(l, i - 1);
vector<TreeNode *>right_tree = dfs(i + 1, r);
for (TreeNode *left : left_tree) {
for (TreeNode *right : right_tree) {
TreeNode *t = new TreeNode(i, left, right);
ans.push_back(t);
}
}
}
return ans;
}
vector<TreeNode*> generateTrees(int n) {
vector<TreeNode *> ans;
if (n == 0) return ans;
return dfs(1, n);
}
};跟着题目走就行 然后递归
class Solution {
public:
string decodeString(string s) {
// ret记录字串
string ret;
int i = 0;
while (s[i]) {
// 为什么可以这么自信的处理字母？
// 因为串一定是数字 + 括号 + 字母排列的
// 不用担心顺序问题
if (s[i] < '0' || s[i] > '9') {
ret += s[i++];
} else {
int num = 0;
while (s[i] >= '0' && s[i] <= '9') {
num = num * 10 + (s[i++] - '0');
}
i++;
// cnt 记录括号数量
// 因为有括号嵌套的情况
// 循环完成之后r指向与第一个[对应的]位置
// 截取字串递归处理即可
int l = i, r = i, cnt = 1;
while (cnt) {
r += 1;
if (s[r] == '[') cnt++;
else if (s[r] == ']') cnt--;
}
string tmp = decodeString(s.substr(l, r - l));
while (num--) ret += tmp;
i = r + 1;
}
}
return ret;
}
};class Solution {
public:
// 快排思想 双指针
// 盛水的多少取决于长和宽两个变量
// 所以不妨设l，r指向头尾
// 面积s = (r - l) * min(h[r], h[l])
int maxArea(vector<int>& height) {
int ans = 0, i = 0, j = height.size() - 1;
while (i < j) {
ans = max(ans, (j - i) * min(height[i], height[j]));
// 哪个小就舍弃哪个
if (height[i] < height[j]) i++;
else j--;
}
return ans;
}
};其实就是等概率生成1-10内的每个数
我们知道Rand7()可以生成1-7内的等概率的数
7*（Rand7() - 1） = {0， 7， 14， 21， 28， 35， 42}，这7个数等概率
7*（Rand7() - 1） + Rand() - 1表示{0,1,2,3,4,5,6,......40, ... 48}，这49个数等概率
但是如果用1-10去填充1-49 发现10的概率是4/49 别的数都是5/49
对x >= 40的拒绝采样
这样每个数字的概率都是$\frac{1}{10}$ $$ p = \frac{\frac{40}{49}\frac{1}{40} }{\frac{40}{49}\frac{1}{40} + \frac{9}{49}} = \frac{1}{10} $$
最后将1-40的映射回1-10就好了
算法流程
/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution {
public int rand10() {
int num = 0;
while (true) {
int x = rand7();
num = 7 * (x - 1) + rand7();
if (num <= 40) return (num % 10) + 1;
}
}
}