71-80
leetcodehot100
class Solution {
public:
string getDigits(string &s, size_t &ptr){
string ans = "";
while (isdigit(s[ptr])){
ans.push_back(s[ptr++]);
}
return ans;
}
string getString(vector<string> &v){
string ret;
for(const auto &s:v){
ret += s;
}
return ret;
}
string decodeString(string s) {
vector <string> stk;
size_t ptr = 0;
while(ptr < s.size()){
char cur = s[ptr];
if(isdigit(cur)){
string digits = getDigits(s , ptr);
stk.push_back(digits);
}else if(isalpha(cur) || cur == '['){
stk.push_back(string(1, s[ptr++]));
}else{//]
ptr++;
vector<string> sub;
while(stk.back() != "["){
sub.push_back(stk.back());
stk.pop_back();
}
reverse(sub.begin(), sub.end());
stk.pop_back();
int repTime = stoi(stk.back());
stk.pop_back();
string t, o = getString(sub);
while(repTime--) t+=o;
stk.push_back(t);
}
}
return getString(stk);
}
};//71
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n), next(101, INT_MAX);
for(int i = n-1; i>=0; i--){
int warmerIbdex = INT_MAX;
for(int t = temperatures[i] + 1; t <= 100; t++){
warmerIbdex = min(warmerIbdex, next[t]);
}
if(warmerIbdex != INT_MAX){
ans[i] = warmerIbdex - i;
}
next[temperatures[i]] = i;
}
return ans;
}
};//72
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n);
stack<int> momo_stack;
for(int i = 0; i<n; i++){
while(!momo_stack.empty() && heights[momo_stack.top()] >= heights[i]){
momo_stack.pop();
}
left[i] = (momo_stack.empty()? -1:momo_stack.top());
momo_stack.push(i);
}
momo_stack = stack<int>();
for(int i = n-1; i>=0; i--){
while(!momo_stack.empty() && heights[momo_stack.top()] >= heights[i]){
momo_stack.pop();
}
right[i] = momo_stack.empty()? n:momo_stack.top();
momo_stack.push(i);
}
int ans = 0;
for(int i = 0; i<n; i++){
ans = max(ans, (right[i] - left[i] -1)*heights[i]);
}
return ans;
}
};
// class Solution {
// public:
// int largestRectangleArea(vector<int>& heights) {
// int n = heights.size();
// int ans = 0;
// // 枚举左边界
// for (int left = 0; left < n; ++left) {
// int minHeight = INT_MAX;
// // 枚举右边界
// for (int right = left; right < n; ++right) {
// // 确定高度
// minHeight = min(minHeight, heights[right]);
// // 计算面积
// ans = max(ans, (right - left + 1) * minHeight);
// }
// }
// return ans;
// }
// };
//73
class Solution {
public:
int quickSelect(vector<int>&nums, int l, int r, int k){
if(l == r) return nums[k];
int partition = nums[l], i = l-1, j = r+1;
while(i < j){
do i++; while(nums[i] < partition);
do j--; while(nums[j] > partition);
if(i < j) swap(nums[i], nums[j]);
}
if(k <= j) return quickSelect(nums, l, j, k);
else return quickSelect(nums, j+1, r, k);
}
int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size()-1, nums.size()-k);
}
};//74
class Solution {
public:
void qsort(vector<pair<int, int>>& values, int l , int r, vector<int> &ret, int k){
int picked = rand() % (r - l + 1) + l;
swap(values[picked], values[l]);
int pivot = values[l].second;
int index = l;
for(int i = l +1; i<=r; i++){
if(values[i].second >= pivot){
swap(values[index+1], values[i]);
index++;
}
}
swap(values[l], values[index]);
if(k <= index - l){
qsort(values, l, index-1, ret, k);
}else{
for(int i = l; i<=index; i++){
ret.push_back(values[i].first);
}
if(k > index - l + 1){
qsort(values, index+1, r, ret, k-(index-l+1));
}
}
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mp;
for(auto &num:nums){
mp[num]++;
}
vector<pair<int,int>> values;
for(auto& it:mp){
values.push_back(it);
}
vector<int> ret;
qsort(values, 0 ,values.size() - 1, ret, k);
return ret;
}
};//75
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> queMin;
priority_queue<int, vector<int>, greater<int>> queMax;
MedianFinder() { }
void addNum(int num) {
if(queMin.empty() || num <= queMin.top()){
queMin.push(num);
if(queMax.size() + 1 < queMin.size()){
queMax.push(queMin.top());
queMin.pop();
}
}else{
queMax.push(num);
if(queMax.size() > queMin.size()){
queMin.push(queMax.top());
queMax.pop();
}
}
}
double findMedian() {
return queMin.size() > queMax.size() ? queMin.top()/1.0 : (queMax.top()+queMin.top())/2.0;
}
};//76
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
int minPrice=prices[0],cha=0;
for(int i=1;i<len;i++){
minPrice = min(minPrice, prices[i]);
cha = max(cha, prices[i]-minPrice);
}
return cha;
}
};//77
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for(int i = 0; i<n; i++){
if(i<=rightmost){
rightmost = max(rightmost, nums[i]+i);
if(rightmost >= n -1) return true;
}
}
return false;
}
};//78
class Solution {
public:
int jump1(vector<int>& nums) {
int position = nums.size() - 1;
int steps = 0;
while(position > 0){
for(int i = 0 ; i<position; i++){
if(i + nums[i] >= position){
position = i;
steps++;
break;
}
}
}
return steps;
}
int jump(vector<int>& nums) {
int n = nums.size();
int maxPos = 0, end = 0, steps = 0;
for(int i = 0; i < n-1; i++){
if(maxPos >= i){
maxPos = max(maxPos, i + nums[i]);
if(i == end){
end = maxPos;
steps++;
}
}
}
return steps;
}
};//79
class Solution {
public:
vector<int> partitionLabels(string s) {
int last[26];
int len = s.size();
for(int i = 0; i<len; i++) last[s[i]-'a'] = i;
vector<int> ans;
int start = 0, end = 0;
for(int i = 0; i<len; i++){
end = max(end, last[s[i] - 'a']);
if(i == end){
ans.push_back(end - start +1);
start = end + 1;
}
}
return ans;
}
};//80