string 用法
int repeatTimes = stoi(stack.top()); 转化string to int
char转string用 string s(1,x)
存数字 to_string(number)
class Solution {public:/*** @param s: an expression includes numbers, letters and brackets* @return: a string*/string expressionExpand(string &s) {// write your code herestack <char> res;for (int i = 0; i < s.size(); i++) {string duplicate;res.push(s[i]);if (s[i] == ']') {res.pop();while (res.top() != '[') {duplicate.push_back(res.top());res.pop();}res.pop();int num = 0;int times = 1;while (!res.empty() && isdigit(res.top())) {num += times * (res.top() - '0');res.pop();times *= 10;}for (int j = 0; j < num; j++) {for (int k = duplicate.size() - 1; k > -1; k--) {res.push(duplicate[k]);}}}}string result;while (!res.empty()) {result = res.top() + result;res.pop();}return result;}};
接雨水问题
找到左边右边最大的中的最小的减去height
class Solution {public:/*** @param heights: a list of integers* @return: a integer*/int trapRainWater(vector<int> &heights) {// write your code hereint totalSize = heights.size();vector <int> left(totalSize);vector <int> right(totalSize);int temp = 0;for (int i = 0; i < totalSize; i ++){temp = max(temp, heights[i]);left[i] = temp;}temp = 0;for (int i = totalSize - 1; i > -1; i --){temp = max(temp, heights[i]);right[i] = temp;}int res = 0;for (int i = 1; i < totalSize - 1; i ++){if(min(left[i - 1], right[i + 1]) > heights[i]){res += (min(left[i - 1], right[i + 1]) - heights[i]);}}return res;}};
接雨水问题2
从边界出发，不断出queue，动态求min，push进去四个方向，求吃水线和现在的点的差
注意+=后面如果有不止一项要加（）
class Node{
public:
int row, column;
int height;
Node(int row, int column, int height){
this -> row = row;
this -> column = column;
this -> height = height;
}
};
struct cmp{
bool operator ()(const Node* a, const Node* b){
return a -> height > b -> height;
}
};
class Solution {
public:
/**
* @param heights: a matrix of integers
* @return: an integer
*/
bool exist(int rowNow, int colNow, int m, int n){
return (rowNow < m && rowNow >= 0 && colNow < n && colNow >= 0);
}
int trapRainWater(vector<vector<int>> &heights) {
// write your code here
vector<int> rowCoordinate = {-1, 0, 1, 0};
vector<int> colCoordinate = {0, -1, 0, 1};
int m = heights.size();
int n = heights[0].size();
int res = 0;
//vector <vector<Node*>> nodeSave (m, vector<int>(n));
vector <vector<int>> visited (m, vector<int>(n));
priority_queue <Node *, vector<Node*>, cmp> Q;
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
if (i == 0 || i == m - 1 || j == 0 || j == n - 1){
Node* temp = new Node(i, j, heights[i][j]);
Q.push(temp);
visited[i][j] = 1;
}
}
}
while (! Q.empty()){
Node * temp = Q.top();
Q.pop();
for (int i = 0; i < 4; i ++){
int tempRow = temp -> row + rowCoordinate[i];
int tempCol = temp -> column + colCoordinate[i];
if (exist(tempRow, tempCol, m, n) && visited[tempRow][tempCol] == 0){
int heightThreshold = max(heights[tempRow][tempCol], temp -> height);
Node* temp = new Node(tempRow, tempCol, heightThreshold);
Q.push(temp);
visited[tempRow][tempCol] = 1;
res += (heightThreshold - heights[tempRow][tempCol]);
//cout << tempRow<< ' ' << tempCol<< ' ' << heightThreshold - heights[tempRow][tempCol] << endl;
}
}
}
return res;
}
};
81. Find Median from Data Stream
class Solution {
public:
/**
* @param nums: A list of integers
* @return: the median of numbers
*/
void heapBal(priority_queue <int, vector<int>> &smallHeap, priority_queue <int, vector<int>, greater<int>> &largeHeap){
if (smallHeap.size() > largeHeap.size() + 1){
int temp = smallHeap.top();
smallHeap.pop();
largeHeap.push(temp);
}
if (smallHeap.size() < largeHeap.size()){
int temp = largeHeap.top();
largeHeap.pop();
smallHeap.push(temp);
}
}
vector<int> medianII(vector<int> &nums) {
// write your code here
priority_queue <int, vector<int>> smallHeap;
priority_queue <int, vector<int>, greater<int>> largeHeap;
vector<int> res;
for (int i = 0; i < nums.size(); i ++){
if (!smallHeap.empty() && nums[i] <= smallHeap.top()){
smallHeap.push(nums[i]);
//cout << nums[i] << "smallheap"<< endl;
}else{
largeHeap.push(nums[i]);
//cout << nums[i] << "largeheap" << endl;
}
heapBal(smallHeap, largeHeap);
res.push_back(smallHeap.top());
}
return res;
}
};
stack
12. Min Stack
维护两个堆，一个堆放最小值，一个堆正常
class MinStack {
private:
stack <int> minimunStack, originalStack;
public:
MinStack() {
// do intialization if necessary
}
/*
* @param number: An integer
* @return: nothing
*/
void push(int number) {
// write your code here
if (minimunStack.size() == 0 || number < minimunStack.top()){
minimunStack.push(number);
}else{
minimunStack.push(minimunStack.top());
}
originalStack.push(number);
}
/*
* @return: An integer
*/
int pop() {
// write your code here
int temp = originalStack.top();
minimunStack.pop();
originalStack.pop();
return temp;
}
/*
* @return: An integer
*/
int min() {
// write your code here
return minimunStack.top();
}
};
122. Largest Rectangle in Histogram
找每个pop出来的点的左边界和右边界，注意每次判断栈为空时的情况
两个栈一个用来记录位置，一个记录高度
维护一个pos栈即可，无需ST
class Solution {
public:
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
int largestRectangleArea(vector<int> &height) {
// write your code here
height.push_back(-1);
stack <int> ST;
stack <int> pos;
int res = 0;
for (int i = 0; i < height.size(); i ++){
int tempST = 0;
int tempPos = i;
while(!ST.empty() && ST.top() > height[i]){
tempST = ST.top();
tempPos = pos.top();
ST.pop();
pos.pop();
if (pos.empty()){
res = max(res, i * height[tempPos]);
}else
res = max(res, (i - pos.top() - 1) * height[tempPos]);
}
// res = max(res, (i - tempPos + 1) * height[i]);
//cout << res << endl;
ST.push(height[i]);
pos.push(i);
}
return res;
}
};
510. Maximal Rectangle
将上一题化成二维，注意每次清空stack
class Solution {
public:
/**
* @param matrix: a boolean 2D matrix
* @return: an integer
*/
int maximalRectangle(vector<vector<bool>> &matrix) {
// write your code here
if (matrix.size() == 0 || matrix[0].size() == 0){
return 0;
}
int m = matrix.size();
int n = matrix[0].size();
vector <int> height (n + 1, 0);
height[n] = -1;
int res = 0;
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
if (matrix[i][j] == 0){
height[j] = 0;
}else{
height[j] += matrix[i][j];
}
//cout << height[j]<< endl;
}
stack <int> pos;
for (int j = 0; j <= n; j ++){
int temp = 0;
int tempheight = 0;
while(!pos.empty() && height[pos.top()] >= height[j]){
tempheight = height[pos.top()];
pos.pop();
if (pos.empty()){
res = max(res, tempheight * j);
}else{
temp = pos.top();
res = max(res, tempheight * (j - pos.top() - 1));
}
//cout << res<< endl;
}
pos.push(j);
}
}
return res;
}
};
126. Max Tree
每次连接左树（左边最大值）
右子树不断更新，出现更大的节点存在右子树当中
class Solution {
public:
/**
* @param A: Given an integer array with no duplicates.
* @return: The root of max tree.
*/
TreeNode * maxTree(vector<int> &A) {
// write your code here
stack <TreeNode *> ST;
for (int i = 0; i < A.size(); i ++){
TreeNode * tempTN = new TreeNode(A[i]);
while(! ST.empty() && A[i] > ST.top() -> val){
tempTN -> left = ST.top();
ST.pop();
}
if (ST.size() > 0){
ST.top() -> right = tempTN;
}
ST.push(tempTN);
}
while(ST.size() != 1){
ST.pop();
}
return ST.top();
}
};
Heap
360. Sliding Window Median
erase 可以接（iterator位置或者值）
reverse指针不可以erase
使用multiset实现PQ
class Solution {
public:
/**
* @param nums: A list of integers
* @param k: An integer
* @return: The median of the element inside the window at each moving
*/
void rearrange(multiset <int> &minSet, multiset <int> &maxSet) {
if (minSet.size() > maxSet.size() + 1) {
int temp = *minSet.rbegin();
minSet.erase(minSet.lower_bound(*minSet.rbegin()));
maxSet.insert(temp);
}
if (maxSet.size() > minSet.size() ){
int temp = *maxSet.begin();
maxSet.erase(maxSet.begin());
minSet.insert(temp);
}
}
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
// write your code here
//minSet is like 1, 2, 3 maxSet is like 4, 5, 6
multiset <int> minSet, maxSet;
vector<int> res;
if (nums.size() == 0){
return res;
}
for (int i = 0; i < k; i++) {
minSet.insert(nums[i]);
}
for (int i = 0; i < k / 2; i++) {
maxSet.insert(*minSet.rbegin());
minSet.erase(minSet.lower_bound(*minSet.rbegin()));
// minset 1, maxset 7
}
res.push_back(*minSet.rbegin());
for (int i = k; i < nums.size(); i++) {
if (minSet.size() == 0 || *minSet.rbegin() >= nums[i]) {
minSet.insert(nums[i]);
}else {
maxSet.insert(nums[i]);
}
//cout << i << endl;
if (minSet.find(nums[i - k]) != minSet.end()) {
minSet.erase(minSet.find(nums[i - k]));
//minset {}, maxset 2;
}else {
maxSet.erase(maxSet.find(nums[i - k]));
}
rearrange(minSet, maxSet);
res.push_back(*minSet.rbegin());
}
return res;
}
};
若有收获，就点个赞吧
0 人点赞
