第一节课：同向双指针（主动指针，辅动指针）
第二节课：Union find： 数据的合并和元素的查找，老大哥节点
Trie：
字母树可以share公共前缀（没有儿子造儿子，有儿子沿着儿子往下走）
数据结构下：双堆（处理滑动窗口中位数，数据流中位数，求前k大的一个堆）
双端队列（求一段数里面最大的，如果一个数在之前比他小，就废掉了没有用）
单调stack（求一个数之前第一个比他大，比他小）
第四节课：二分答案：最大平均和子数组
扫描线：针对区间，区间开始区间结束，排序，有时加一有时减一，共享同一个y坐标的起点终点处理一下
第五节课dp：找到状态用最后一步，化成子问题，然后写dp方程，细心找到初始条件边界情况
滚动数组，只用前一行或者两行，用mod
划分型：最后一步，找最后一段
博弈：必胜态，必败态，必胜下面只要有一个必败就行
必败下面全是必胜
区间型：砍头去尾，二分first balloon
Dp下：双序列：看两个序列尾巴是否匹配
背包：最大总承重m放到dp里面去
Follow up： Iterator, SubarraySum, Wiggle Sort
Iterator
453. Flatten Binary Tree to Linked List
注意要freepointer
把右子树都接到左子树的最右，然后进行递归
class Solution {public:/*** @param root: a TreeNode, the root of the binary tree* @return: nothing*/void flatten(TreeNode * root) {// write your code hereif (root == NULL){return;}if (root -> left){TreeNode* temp = root -> left;while(temp -> right != NULL){temp = temp-> right;}temp -> right = root -> right;root -> right = root -> left;root -> left = NULL;}flatten(root -> right);}};
22. Flatten List（递归以及费递归写法）
递归写法
某一些项放在另外一项之后
res.insert(res.end(), temp.begin(), temp.end());
class Solution {public:// @param nestedList a list of NestedInteger// @return a list of integervector<int> flatten(vector<NestedInteger> &nestedList) {// Write your code herevector <int> res;NestedInteger n;for(int i = 0; i < nestedList.size(); i ++){if (nestedList[i].isInteger()){res.push_back(nestedList[i].getInteger());}else{vector<NestedInteger> sub_list = nestedList[i].getList();vector<int> temp = flatten(sub_list);//vector<int> temp = flatten(nestedList[i].getList());res.insert(res.end(), temp.begin(), temp.end());}}return res;}};
非递归写法
非递归写法中，因为stack是先入后出，所以要先反向。
class Solution {public:// @param nestedList a list of NestedInteger// @return a list of integervector<int> flatten(vector<NestedInteger> &nestedList) {// Write your code herestack <NestedInteger> stk;for(int i = 0; i < nestedList.size(); i++){stk.push(nestedList[i]);}vector<int> res;while(stk.size() > 0){NestedInteger top = stk.top();stk.pop();if (top.isInteger()){res.push_back(top.getInteger());}else{vector<NestedInteger> temp = top.getList();for (int i = temp.size() - 1; i >= 0; i --){stk.push(temp[i]);}}}return res;}};
528. Flatten Nested List Iterator
class NestedIterator {public:stack <NestedInteger> stk;NestedIterator(vector<NestedInteger> &nestedList) {// Initialize your data structure here.for(int i = nestedList.size() - 1; i >= 0; i --){stk.push(nestedList[i]);}}// @return {int} the next element in the iterationint next() {// Write your code hereint ans = stk.top().getInteger();stk.pop();return ans;}// @return {boolean} true if the iteration has more element or falsebool hasNext() {// Write your code herewhile (!stk.empty()){NestedInteger temp = stk.top();if(temp.isInteger()){return true;}else{stk.pop();vector<NestedInteger> tempNew = temp.getList();for(int i = tempNew.size() - 1; i >= 0; i --){stk.push(tempNew[i]);}}}return false;}};
Subarray Sum 前缀和问题
138. Subarray Sum
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> subarraySum(vector<int> &nums) {
// write your code here
vector <int> prefixSum(nums.size() + 1, 0);
int sum = 0;
unordered_map<int, int>pos;
pos[0] = -1;
vector <int> res;
// if (nums[0] == 0){
// res =
// }
for (int i = 1; i < nums.size() + 1; i ++){
sum += nums[i - 1];
prefixSum[i] = sum;
if(pos.find(sum) != pos.end()){
res = {pos[sum] + 1, i - 1};
return res;
}else{
pos[sum] = i - 1;
}
}
return res;
}
};
405. Submatrix Sum（二维的前缀和，时间复杂度O3）
在横向利用搜索和的方法，得到一个字典存进去和
字典可以用？？？。count（） >0来判断key是否在自店内
class Solution {
public:
/*
* @param matrix: an integer matrix
* @return: the coordinate of the left-up and right-down number
*/
vector<vector<int>> submatrixSum(vector<vector<int>> &matrix) {
// write your code here
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> res;
vector<vector<int>> sum(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i < m + 1; i++)
for (int j = 1; j < n + 1; j++)
sum[i][j] += sum[i-1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
for (int i = 0; i < m; i ++){
int sumtemp = 0;
for (int j = i + 1; j < m + 1; j ++){
unordered_map <int, int>check_res;
check_res[0] = 0;
for (int k = 1; k < n + 1; k ++){
sumtemp = sum[j][k] - sum[i][k];
if (check_res.count(sumtemp) > 0){
res = {{i, check_res[sumtemp]}, {j - 1, k - 1}};
return res;
}else{
check_res[sumtemp] = k;
}
}
}
}
return res;
}
};
404. Subarray Sum II（两根指针，因为和全为正数）
写for循环的时候， i是前一个位置，j是最后的位置
public:
/**
* @param A: An integer array
* @param start: An integer
* @param end: An integer
* @return: the number of possible answer
*/
int subarraySumII(vector<int> &A, int start, int end) {
// write your code here
int m = A.size();
int res = 0;
vector<int> preSum(m + 1, 0);
for(int i = 1; i < m + 1; i ++){
preSum[i] = preSum[i - 1] + A[i - 1];
}
for (int i = 0; i < m; i ++){
for (int j = i + 1; j < m + 1; j ++){
if(preSum[j] - preSum[i] >= start && preSum[j] - preSum[i] <= end){
res ++;
}
}
}
return res;
}
};
399. Nuts & Bolts Problem(排序，相互二分，二分的变形)
class Solution {
public:
/**
* @param nuts: a vector of integers
* @param bolts: a vector of integers
* @param compare: a instance of Comparator
* @return: nothing
*/
void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
quickSort(nuts, bolts, 0, nuts.size()-1, compare);
}
void quickSort(vector<string> & nuts, vector<string> & bolts, int l, int r, Comparator compare){
if (l >= r){
return;
}
string pivot = nuts[l];
int cnt = 0, pos = 0;
for (int i = l; i <= r; i ++){
int t = compare.cmp(pivot, bolts[i]);
if (t == 1){
cnt ++;
}else if(t == 0){
pos = i;
}
}
cnt += l;
swap(bolts[pos], bolts[cnt]);
pos = cnt;
for (int i = l, j = r; i < pos && pos < j;){
while(i < pos && compare.cmp(pivot, bolts[i]) == 1)
i++;
while(pos < j && compare.cmp(pivot, bolts[j]) == -1)
j--;
if (i < pos && pos < j){
swap(bolts[i++], bolts[j--]);
}
}
pivot = bolts[pos];
swap(nuts[pos], nuts[l]);
for (int i = l, j = r; i < pos && pos < j; )
{
while (i < pos && compare.cmp(nuts[i], pivot) == -1)
i++;
while (pos < j && compare.cmp(nuts[j], pivot) == 1)
j--;
if (i < pos && pos < j)
swap(nuts[i++], nuts[j--]);
}
quickSort(nuts, bolts, l, pos - 1, compare);
quickSort(nuts, bolts, pos + 1, r, compare);
}
};
402. Continuous Subarray Sum(找最大子数组，O（n）)
如果之前的数组比0小，就不再看，res从头开始
如果currsum比maxsum大，更新区间和maxsum
class Solution {
public:
/*
* @param A: An integer array
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> continuousSubarraySum(vector<int> &A) {
// write your code here
int currSum = 0;
int tempFirst = 0;
int maxSum = INT_MIN;
vector<int> res(2);
for(int i = 0; i < A.size(); i ++){
if (currSum >= 0){
currSum += A[i];
}else{
currSum = A[i];
tempFirst = i;
}
if (currSum > maxSum){
res[0] = tempFirst;
res[1] = i;
maxSum = currSum;
}
}
return res;
}
};
403. Continuous Subarray Sum II（环形问题）
找到数组中最大和和最小和的subarray， 互补思想，环形问题
class Solution {
public:
/*
* @param A: An integer array
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> continuousSubarraySumII(vector<int> &A) {
// write your code here
vector<int> res(2, 0);
int tempRes = 0;
int maxRes = INT_MIN;
int minRes = INT_MAX;
int start = 0, end = 0, sum = 0;
for (int i = 0; i < A.size(); i ++){
sum += A[i];
if(tempRes < 0){
start = end;
tempRes = 0;
}
tempRes += A[end];
if (tempRes > maxRes){
maxRes = tempRes;
res[0] = start;
res[1] = end;
}
end ++;
cout << start <<' ' <<end << ' '<< maxRes<< endl;
}
start = 0;
end = 0;
tempRes = 0;
for(int i = 0; i < A.size() - 1; i ++){
if(tempRes > 0){
start = end;
tempRes = 0;
}
tempRes += A[end];
if (tempRes < minRes){
minRes = tempRes;
// cout << start <<' ' <<end << ' '<< sum<< endl;
// cout << maxRes<< ' ' << minRes << endl;
// cout << sum - minRes << endl;
if (sum - minRes > maxRes){
res[0] = end + 1;
res[1] = start - 1;
}
}
end ++;
}
return res;
}
};
558. Sliding Window Matrix Maximum(二维)
class Solution {
public:
/**
* @param matrix an integer array of n * m matrix
* @param k an integer
* @return the maximum number
*/
int maxSlidingWindow2(vector<vector<int>>& matrix, int k) {
// Write your code here
int n = matrix.size();
if (n == 0 || n < k)
return 0;
int m = matrix[0].size();
if (m == 0 || m < k)
return 0;
vector<vector<int>> sum(n + 1, vector<int>(m + 1));
for (int i = 0; i <= n; ++i) sum[i][0] = 0;
for (int i = 0; i <= m; ++i) sum[0][i] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
sum[i][j] = matrix[i - 1][j - 1] +
sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
int max_value = INT_MIN;
for (int i = k; i <= n; ++i)
for (int j = k; j <= m; ++j) {
int value = sum[i][j] - sum[i - k][j] -
sum[i][j - k] + sum[i - k][j - k];
if (value > max_value)
max_value = value;
}
return max_value;
}
};
若有收获，就点个赞吧
0 人点赞
