- 数组求和问题，3-sum closest
- 子数组问题系列
- 买卖股票
- 寻找丢失数
- 找主元素
- 排序切分问题
- TOPK问题、最大最小堆
- LRU Cache 问题，linklist+hashmap
- 去重问题，bitmap
- 搜索问题，倒排索引
cnt_perday = 10
try:
刷 cnt_perday 题
except:
cnt_perday = cnt_perday/2
刷 cnt_perday/2 题2022.8.25
当前进度：6/10 14:30 -> 19:15
2sum
https://leetcode.cn/problems/2sum/
nums = [3,2,4]
target=6
返回index[1,2], 用map存储 num->index; 已知1个数，查找另1个数的index
不能返回 [0,0]，两个数下标不能一样。
unordered_map API
https://en.cppreference.com/w/cpp/container/unordered_map
查询key：count(), find(), contains()
限时15min；
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hash;
int n = nums.size();
for (int i = 0; i < n; i++) {
hash[nums[i]] = i;
}
vector<int> ans;
for (int i = 0; i < n; i++) {
if (hash.count(target-nums[i]) && i != hash[target-nums[i]]) {
ans.push_back(i);
ans.push_back(hash[target-nums[i]]);
break;
}
}
return ans;
}
};时间ON，空间ON
如果ONlogN排序之后，双指针，空间O1；
10min 算是练一下快速排序吧，快排一遍过
最后发现，应该返回2个数排序之前的index，因此这题没有完成
class Solution {
public:
void swap(vector<int>&nums, int idx1, int idx2) {
int tmp = nums[idx1];
nums[idx1] = nums[idx2];
nums[idx2] = tmp;
}
// 快速排序，随机选一个切分点，先挪到最右，l～r-1范围内小于切分点的，都换到前方(用write指针)；再将切分点挪到write处，write两侧分治
void quicksort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int partition_idx = rand()%(r-l+1)+l;
swap(nums, partition_idx, r);
int write = l;
for (int i=l; i<r; i++) {
if (nums[i] < nums[r]) {
swap(nums, i, write);
write += 1;
}
}
swap(nums, write, r);
quicksort(nums, l, write-1);
quicksort(nums, write+1, r);
}
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
quicksort(nums, l, r);
// 打印排序结果
for (auto num : nums) {
cout << num << " ";
}
vector<int> ans(2);
while (l < r) {
if (nums[l] + nums[r] == target) {
ans[0] = l; // ! 应该返回排序前的位置
ans[1] = r;
break;
}
else if (nums[l] + nums[r] < target){
l++;
}
else {
r--;
}
}
return ans;
}
};
sort-an-array
刷一下：
https://leetcode.cn/problems/sort-an-array/
c++ rand() 返回 [0, RAND_MAX]
https://cplusplus.com/reference/cstdlib/rand/
v1 = rand() % 100; // v1 in the range 0 to 99
v2 = rand() % 100 + 1; // v2 in the range 1 to 100
v3 = rand() % 30 + 1985; // v3 in the range 1985-2014 class Solution {
public:
void swap(vector<int>&nums, int idx1, int idx2) {
int tmp = nums[idx1];
nums[idx1] = nums[idx2];
nums[idx2] = tmp;
}
// 快速排序，随机选一个切分点，先挪到最右，l～r-1范围内小于切分点的，都换到前方(用write指针)；再将切分点挪到write处，write两侧分治
void quicksort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int partition_idx = rand()%(r-l+1)+l;
swap(nums, partition_idx, r);
int write = l;
for (int i=l; i<r; i++) {
if (nums[i] < nums[r]) {
swap(nums, i, write);
write += 1;
}
}
swap(nums, write, r);
quicksort(nums, l, write-1);
quicksort(nums, write+1, r);
}
vector<int> sortArray(vector<int>& nums) {
int l = 0;
int r = nums.size()-1;
quicksort(nums,l,r);
return nums;
}
};3sum
https://leetcode.cn/problems/3sum/
结果中不能有重复，一个方法是，手动去重，另一个方法是用set.insert()
class Solution {
public:
void swap(vector<int> &nums, int idx1, int idx2) {
int tmp = nums[idx1];
nums[idx1] = nums[idx2];
nums[idx2] = tmp;
}
void quicksort(vector<int> &nums, int l, int r) {
if (l >= r) return;
int partition = rand() % (r-l+1) + l;
swap(nums, partition, r);
int write = l;
for (int i = l; i < r; i++) {
if (nums[i] < nums[r]) {
swap(nums, i, write);
write += 1;
}
}
swap(nums, write, r);
quicksort(nums, l, write-1);
quicksort(nums, write+1, r);
}
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> triple_vec(3);
int n = nums.size();
// 排序+双指针
int l = 0;
int r = nums.size()-1;
quicksort(nums,l,r);
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
for (int i = 0; i <= n-2; i++) {
// 0(a),0,0,0,0,0,0,0,-1(b),-1,1,1(c); a去重
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int l = i+1;
int r = n-1;
while (l < r) {
int total = nums[i] + nums[l] + nums[r];
// 保证三元组不重复，因此。i,i+1,...不能相同
if (total == 0) {
triple_vec[0] = nums[i];
triple_vec[1] = nums[l];
triple_vec[2] = nums[r];
ans.push_back(triple_vec);
// 0(a),,-1(b),-1,-1,-1,-1,1,1,1,1,1(c); b,c去重
while (l < r && nums[l] == nums[l+1]) {
l++;
}
while (l < r && nums[r] == nums[r-1]) {
r--;
}
l++;
r--;
}
else if (total < 0) {
l++;
}
else {
r--;
}
}
}
return ans;
}
};
=======子数组问题
maximum-subarray
https://leetcode.cn/problems/maximum-subarray/
连续子数组的最大和
加入一个数是否变得更大？
以第i个数为结尾的ans
dp[i] = max(nums[i], dp[i-1] + nums[i])
Return max(dp[I…])
数组全为负数，返回最大的负数，ans初始化诶INT_MIN
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
// dp[i] = max(dp[i-1]+nums[i], nums[i]); dp[0] = nums[0]
// premax = max(premax+nums[i], nums[i])
int ans = INT_MIN;
for (int i = 0; i < n; i++) {
ans = max(ans, nums[i]);
}
int premax = nums[0];
for (int i = 1; i < n; i++) {
premax = max(premax+nums[i], nums[i]);
if (premax > ans) {
ans = premax;
}
}
return ans;
}
};
TODO: https://leetcode.cn/problems/subarray-sum-equals-k/
和为K的子数组的个数
ONN，子数组和=左边界前缀和-右边界前缀和
https://leetcode.cn/problems/minimum-size-subarray-sum/
https://leetcode.cn/problems/maximum-product-subarray/
=====买卖股票
gu-piao-de-zui-da-li-run-lcof
https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/
class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp[i][0] 第i天不持有
// dp[i][1] 第i天持有, return dp[n-1][0]
// dp[i][0] = max(dp[i-1][1]+nums[i], dp[i][0]);
// dp[i][1] = max(dp[i-1][0]-nums[i], dp[i][1]);
// dp[0][0] = 0; dp[0][1] = -nums[0];
// dp[0] = max(dp[1]+nums[i], dp[0]);
// dp[1] = max(dp[0]-nums[i], dp[1]); 注意这里 dp[1] = max(-nums[i], dp[0]) 保证
int not_have = 0;
int have = -prices[0];
int n = prices.size();
for (int i = 1; i < n; i++) {
int new_not_have = max(have+prices[i], not_have);
int new_have = max(0-prices[i], have);
not_have = new_not_have;
have = new_have;
}
return not_have;
}
};
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
========寻找丢失数
missing-number-lcci
缺失数
https://leetcode.cn/problems/missing-number-lcci/
数组包含：0,1,2,3,,,,,,n 少了1个，ON找出他
ONlogN，排序之后，看相邻哪个gap=2, 边界case [0] 返回 1；[1] 返回0；
[1,2] 返回 0，[0,1] 返回2
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 1 ; i < n; i ++) {
if (nums[i] - nums[i-1] == 2) {
return nums[i] - 1;
}
}
if (nums[n-1] == n-1) {
return n;
} else if (nums[0] == 1){
return 0;
} else {
return -1;
}
}
};TODO 原地桶排序；看哪个桶是缺的，[1,2] 缺0；[0,1]不缺 返回2
https://leetcode.cn/problems/single-number/
只出现一次的数字，空间O1
a^a^b
010^010 = 000
000^001 = 001
所有数字都异或，相同的异或结果为0，0和独子异或=独子
https://leetcode.cn/problems/single-number-ii/
三进制位运算
======
https://leetcode.cn/problems/majority-element/
找出现次数大于n/2向下去整的数，
时间ONlogN，排序，输出n/2位置的数
时间ON，空间O1：Boyer-Moore 投票算法，证明不出来，放弃。
https://leetcode.cn/problems/majority-element-ii/
找出出现次数超过n/3的数
排序，一个长度超过n/3的滑动窗口，可能出现在n/3，也可能出现在n*2/3；两个位置的数比较一下，谁更多。
=======
排序切分问题
https://leetcode.cn/problems/array-partition/
两两一组，总和 sum(min(a,b)) 最大；min越大越好，大的min出现的越多越好。
=> 从小到大排序，每个数字找离他最近的，即相邻的；min(a,b)=a, 偶数位置求和。
https://leetcode.cn/problems/sort-colors/
0，1，2；0从开头写，2从末尾些，剩下为1
=======TOPK
https://leetcode.cn/problems/smallest-k-lcci/
数组，最小k个数字；
每个数都扔进最小堆，再吐出k个数；nlogn
==> 优化为nlogk；
扔前k个数字进最大堆：klogk
后续数不断把堆中最大的给挤出去。(n-k)logk
共 nlogk
==>快排思想，
【l，r】中划分点和k对比，=k直接返回划分点前方的全部数，小于k 说明划分点还应该在【partition，r】中再找一下；递归调用，直到划分点=k；最后切分数组前k返回；
heap_API
priority_queue<int> Q; 默认是最大堆。
Q.push()
Q.pop()
Q.top() 仅取值=======LRU Cache
tutorialcup.com/leetcode-solutions/lru-cache-leetcode-solution-2.htm
Size满，则淘汰：最近最少使用
实现get(key) ->
实现put(key,value) ->
双向链表，初始化，头尾都是一个dummynode；用于O1 的插入删除
hash[int, linknode]；用于O1的查找
Get时，如果存在，hash查到linknode删了，头插
如果不存在，-1
Put时，如果存在，hash查linknode删了，头插；
如果不存在，满了，删tail.prev，不满，头插；
实现：linklist_cache.addFirst(); linklist_cache.deleteLast(); linklist_cache.delete()
https://leetcode.cn/problems/lru-cache/solution/zui-jin-mian-zi-jie-yi-mian-peng-dao-lia-1t15/
=======去重问题
=======搜索问题，倒排索引
