【墨鳌】【单调栈~后序遍历】

题目链接
题解链接

解题思路

• 单调栈
• 后序遍历

代码

// 自后向前，维护一个单调递减的栈，成功返回true
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int>s;
        int top=INT_MAX;
        for(auto p=rbegin(postorder);p!=rend(postorder);p++){
            int val=*p;
            if(val>top)return false;
            while(!s.empty() && val<s.top()){
                top=s.top();
                s.pop();
            }
            s.push(val);
        }
        return true;
    }
};

~~Jason_liu O(∩_∩)O

推荐这些文章：

【墨鳌】【卡特兰数】

题目链接
题解链接
解题思路

卡特兰数

代码
// 1 2 5 14 卡特兰数从第二项开始
class Solution {
public:
unordered_map<int,int>C;
int Catalan(int n,int mod){
if(n<=1)return C[n]=1;
if(C[n])return C[n];
int ans=0;
for(int i=1;i<n;i++)
ans=(ans+1LL*Catalan(i,mod)*Catal...

【墨鳌】【面试题19. 正则表达式匹配】

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();

auto matches = [&](int i, int j) {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
...

【墨鳌】【798. 得分最高的最小轮调】

class Solution {
public:
int bestRotation(vector<int>& A) {
int N = A.size();
vector<int> mark(N, 0);
for (int i = 0; i < N; ++i) {
int L = (i + 1) % N; // 得分区间入口
int R = (N + i + 1 - A[i]) % N; // 得分区间出口
mark[L]++;
...

【墨鳌】【LCP 22. 黑白方格画】

组合数学
\(O(N\cdot M)\)
class Solution {
public:
int f[10][10];

int C(int n, int m) {
if (n == m || m == 0) return 1;
return f[n][m] = C(n - 1, m - 1) + C(n - 1, m);
}

int paintingPlan(int n, int k) {
if (k == 0 || k == n * n) return 1;
int ans = 0;
...

【墨鳌】【一题双解】【二分答案 to 遍历+贪心】

题目链接
题解链接
基础: 二分

先从最简单的思路开始
首先，题目满足可二分性
也就是说，当可以构造出 x 个 "balloon" 串
必然，可以构造出 x-1 个 "balloon" 串
于是，二分答案

复杂度

时间复杂度: \(O(Nlog(N))\)
空间复杂度: \(O(1)\)

代码
class Solution {
public:
bool check(string&text,int x){
int b=0,a=0,l=0,o=0,n=0;
for(auto&c:text){
b+=c=='b...

【墨鳌】【只用"加法"和"逻辑运算符"，没有毛病】【《程序员面试金典（第六版）》】

解题思路
不要抖机灵！不要抖机灵！不要抖机灵！

重要的事情说三遍
先找，题源：《程序员面试金典（第六版）》
然后翻评论区 @joswxe 站在巨人的肩膀上
核心思想就是倍增
乘法的本质是：加法
除法的本质是：减法
每次只需要把 乘数 or 除数 按照二进制拆开考虑
即可优化运算为：\(O(log(b))\)
我们可以拼接出如下代码

优化点

使用静态数组，不涉及 vector 的 API
常数 -1 用十六进制码 0xFFFFFFFF 表示，完全不使用任何 - 号
额外实现了取相反数的运算，(from 《程序员面试金典（第六版）》)

代码
class Operations {
publ...

C语言 简单线栈

#include<stdio.h>
int push(int*a, int top, int x){ a[top]=x;
top++;
return top;}//进栈
 
int pop(int *a,int top){
top--;
return top;}//出栈
int main()
{
int top=0;
top=push(    )//in
top=pop(  )//out
int a[1005]={0};
return 0;}
 

...

常用算法模板总结c++DFS&BFS

深度优先遍历

int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过

for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}

宽度优先遍历

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
int t = q.front();
q.pop()...

Leetcode 155. 最小栈 简单

155. 最小栈
题目：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
思路1：
用一个额外的栈保存每次push时的最小值。
如果val小于min，则将val放入最小栈，否则放入min

class MinStack {
public:
MinStack() {
...

leetcode队列单调栈- 滑动窗口中的最大值

import leetcode4.test.MonotonicQueue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
<p>给你一个整数数组 <code>nums</code>，有一个大小为&nbsp;<code>k</code><em>&nbsp;</em>的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 <code>k</...