题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

样例

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

算法1

1. 后序遍历的最后一个节点是二叉树的根节点。
2. 如果是一棵二叉树的后续遍历，根节点可以将数组分为比根节点小的前半部分和比根节点小的后半部分（两部分都能为0）
3. 递归判断左半部分和右半部分
4. 如果少于两个节点，一定是一棵二叉树的后续遍历

Java 代码

class Solution {
    public boolean verifySequenceOfBST(int [] sequence) {
        if(sequence==null)
            return false;
        if(sequence.length<=2 )
            return true;
        int length = sequence.length;
        int root = sequence[length-1];
        int i = 0;
        for(;i<length-1;i++){
            if(sequence[i]>root)
                break;
        }
        int[] left = new int[i];
        for(int k = 0;k<i;k++){
            left[k]=sequence[k];
        }

        int j = i;
        for(;j<length-1;j++){
            if(sequence[j]<root)
                return false;
        }
        int[] right = new int[j-i];
        for(int k = 0;k<j-i;k++){
            right[k]=sequence[i+k];
        }
        return verifySequenceOfBST(left)&&verifySequenceOfBST(right);
    }
}

https://www.luogu.org/problem/P3692
夏幻的考试

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ’*’ 的正则表达式匹配。

’.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

样例

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

算法

BFS $O(n^2)$

在没有*时，直接按顺序匹配就行了。这题关键的点在于不确定*到底代表多少个字符，因此需要搜索的地方就是*的个数。明确了这一点后就会发现这是一个搜索问题，每个状态就是当前的str和pattern的下标位置，如果当前的位能匹配，则分别往后走一位。当两个下标都到达字符串结尾的时候才能终止。

需要就是记录一下访问过哪些状态，避免重复访问，从而保证时间复杂度为$O(n^2)$。

时间复杂度

一共最多有$O(n^2)$个状态，因此时间复杂度为$O(n^2)$。

C++ 代码

class stat{
public:
    int s_pos;
    int p_pos;
    stat(int s, int p){
        s_pos = s;
        p_pos = p;
    }

};
class Solution {
public:
    bool isMatch(string s, string p) {
        queue<stat>q;
        q.push(stat(0, 0));
        //记录访问过哪些状态
        vector<vector<int>>memo(s.size()+2, vector<int>(p.size()+2, 0));
        while(!q.empty()){
            stat top = q.front();
            q.pop();
            if(memo[top.s_pos][top.p_pos] == 1)
                continue;
            memo[top.s_pos][top.p_pos] = 1;
            //终止条件，能够完全匹配
            if(top.s_pos >= s.size() && top.p_pos >= p.size())
                return true;
            if(top.p_pos >= p.size())
                continue;
            if(p[top.p_pos] >= 'a' && p[top.p_pos] <= 'z'){
                if(top.p_pos + 1 < p.size() && p[top.p_pos + 1] == '*'){
                    q.push(stat(top.s_pos, top.p_pos + 2)); //重复0次
                    //枚举*的重复的次数
                    for(int repeat = 1; repeat + top.s_pos <= s.size(); repeat ++){
                        if(p[top.p_pos] == s[top.s_pos + repeat - 1]){
                            q.push(stat(top.s_pos + repeat, top.p_pos + 2));
                        }
                        else
                            break;
                    }
                }
                else{
                    //只能匹配一个字符
                    if(top.s_pos < s.size() && p[top.p_pos] == s[top.s_pos])
                        q.push(stat(top.s_pos + 1, top.p_pos + 1));
                }
            }
            else if (p[top.p_pos] == '.'){
                //.可以匹配任何字符，因此不需要判断字符是否相等，只需要枚举repeat次数即可
                if(top.p_pos + 1 < p.size() && p[top.p_pos + 1] == '*'){
                    q.push(stat(top.s_pos, top.p_pos + 2)); //重复0次
                    for(int repeat = 1; repeat + top.s_pos <= s.size(); repeat ++){
                        q.push(stat(top.s_pos + repeat, top.p_pos + 2));
                    }
                }
                else if(top.s_pos < s.size())
                    q.push(stat(top.s_pos + 1, top.p_pos + 1));
            }
        }
        return false;
    }
};

#include<iostream>
#include<deque>
using namespace std;
const int MAXN = 1e6+10;
int a[MAXN],mi[MAXN],ma[MAXN];
int N,K;
deque<int> q;
int main(){
    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> a[i];

    for(int i = 0; i < N; i++){
        if(i >= K){
            if(q.size() && q.front() == i-K) q.pop_front();
        }
        while(q.size() && a[q.back()] > a[i]){
            q.pop_back();
        }
        q.push_back(i);
        mi[i] = a[q.front()];
    } 
    for(int i = K-1; i < N; i++) cout << mi[i] << " ";
    cout << endl;
    while(q.size()) q.pop_back();

    for(int i = 0; i < N; i++){
        if(i >= K){
            if(q.size() && q.front() == i-K) q.pop_front();
        }
        while(q.size() && a[q.back()] < a[i]){
            q.pop_back();
        }
        q.push_back(i);
        ma[i] = a[q.front()];
    } 
    for(int i = K-1; i < N; i++) cout << ma[i] << " ";

    return 0;
}

C++ 代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 150,maxm = 1e6+10;
int a[maxn][maxn],cnt[maxn][maxn],cntx,n,t,tot,head[maxn*maxn],vis[maxn*maxn],link[maxn*maxn];
struct Edge{ int to,nxt; } e[maxm];
void add(int from,int to)
{
    e[++tot].nxt = head[from],e[tot].to = to;
    head[from] = tot;
}
bool find(int u)
{
    for(int i = head[u];i;i=e[i].nxt)
    {
        int to = e[i].to;
        if(!vis[to])
        {
            vis[to] = 1;
            if(!link[to] || find(link[to])){
                link[to] = u,link[u] = to;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&t);
    int x,y;
    while(t--)
    {
        scanf("%d%d",&x,&y);
        a[x][y] = 1;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(!a[i][j]) cnt[i][j]=++cntx;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
    {
        if(!a[i][j])
        {
            if(j > 1 && !a[i][j-1]) add(cnt[i][j],cnt[i][j-1]);
            if(j < n && !a[i][j+1]) add(cnt[i][j],cnt[i][j+1]);
            if(i > 1 && !a[i-1][j]) add(cnt[i][j],cnt[i-1][j]);
            if(i < n && !a[i+1][j]) add(cnt[i][j],cnt[i+1][j]);
        }
    }

    int ans = 0;
    for(int i = 1; i<= cntx; ++i)
    {
        if(!link[i])
        {
            memset(vis,0,sizeof(vis));
            if(find(i)) ans++;
        }
    }
    printf("%d\n",ans);
}

堆排序

C++ 代码

#include<iostream>
using namespace std;

const int N=1e5+10;

int h[N];   //h[]即为堆 heap  为了方便堆的下标从1开始
int size;   //size为堆的大小

void down(int u)
{
    int t=u;
    /* 判断左右子树是否存在 由于是用完全二叉树存储 
        所以左子树为2x,右子树为2x+1                    */

    if(u*2<=size&&h[t]>h[2*u]) t=2*u;           //这里的顺序是不可以颠倒的不然就不符合堆的定义
    if(u*2+1<=size&&h[t]>h[2*u+1]) t=2*u+1;     //注意这里h【】里面必须填的是t（在下面会提到）
                                                //这和堆排序的定义有关 根小于左小于右    
                                                //所以优先比较的是左，如果左还比右小那么才选择将右上浮
                                                //所以t的值必须先变化为左根的值才能进行比较    
                                                //我自己写的时候就忽略了第二步的比较 所以想写个题解分享一下
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
    }
    size=n;

    for(int i=n/2;i;i--)     //建堆
    {
        down(i);
    }


    while(m--)
    {
        cout<<h[1]<<' ';
        h[1]=h[size];               //最小值由末尾的值覆盖
         down(1);                   //此时1的位置 即根的位置已经是末尾的值，这个操作就是为将其回归原位
                                    //而此时上浮的就是原序列中第二小的值
         size--;                    
    }

    return 0;
}

注意点：

• 由贪心可知，仅需要从较大值和较小值中选择，delta相同时优先选择较小值即可.

#include<cstdio>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int INF=2e9;
set<pair<int,int> > basicSet;//数值存储器

int main(){
    int n;
    scanf("%d",&n);
    int val1;//第一个值
    scanf("%d",&val1);
    basicSet.insert(make_pair(val1,1));
    for(int i=2;i<=n;i++){
        int tmp;
        scanf("%d",&tmp);
        basicSet.insert(make_pair(tmp,i));
        //获取最小值j，选择A_j较小的那个
        //输出最小值点
        set<pair<int,int> >::iterator it=basicSet.find(make_pair(tmp,i));//获取迭代器
        pair<int,int> ans;//答案(first:差值 second:位置)
        ans.first=INF;
        if(++it!=basicSet.end()){
            ans.first=(*it).first-tmp;
            ans.second=(*it).second;
        }
        it=basicSet.find(make_pair(tmp,i));//重置迭代器
        //使用迭代器获得前面的较好值
        if(it--!=basicSet.begin()&&ans.first>=tmp-(*it).first){//能更新
            ans.first=tmp-(*it).first;
            ans.second=(*it).second;
        }
        //输出答案
        printf("%d %d\n",ans.first,ans.second);
    }
    return 0;
}

历尽千辛万苦终于过了这个题…

根据题意可以很简单地整理出目标环
题目中给的交换操作可以让任何一个人到他想要去的位置去
所以简化题意，就是求最少需要变动多少个人，使初始环变为目标环
开始位置就重合的不用动，其他的都需要变动
可以通过转动目标环来让重合的人数变多，枚举转动再求的复杂度是n^2，无法接受

考虑破环成链
可以发现目标环因为可以旋转所以无所谓正逆，而初始环可以有顺时针和逆时针两种表示法
顺时针就是1,2,3,…,n 逆时针是 1,n,n - 1,....,2
一个重要的性质是：转动目标环时所有的点距离重合位置的变化一定是同步的
所以可以通过转动同时重合的点距离重合位置的距离一定相同
直接算出不同距离的点数，找出最多重合的点数
逆时针类似地作一遍取最大值，最后用总点数减去最大重合点数即可

#include <iostream>
#include <cmath>

using namespace std;

const int N = 50010;

int ans,h[N],n,l[N],r[N],num1[N],num2[N];
bool used[N];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
        scanf("%d%d",&l[i],&r[i]);

    h[1] = num1[0] = num1[n] = num2[0] = num2[n] = used[1] = 1;
    for(int i = 2;i <= n;i ++)
    {
        if(!used[l[h[i - 1]]])h[i] = l[h[i - 1]];
        else if(!used[r[h[i - 1]]])h[i] = r[h[i - 1]];
        else {puts("-1");return 0;}
        used[h[i]] = 1;

        ans = max(++ num1[(h[i] - i + n) % n],ans);
        ans = max(++ num2[(h[i] - (n - i + 2) + n) % n],ans);
    }

    cout << n - ans;
}

以下为核心代码：

const int N = 100010;
stack <int> in;
int f [N];
char s [N];

inline bool match ( int i, int j ){
    if ( s [i] == '(' && s [j] == ')' ) return true;
    if ( s [i] == '[' && s [j] == ']' ) return true;
    if ( s [i] == '{' && s [j] == '}' ) return true;
    return false;
}

int main (){
    scanf ( "%s", s+1 );
    for ( int i = 1; i <= (int)strlen(s+1); ++i ){
        if ( in.size() && match (in.top(),i) ){
            f [i] = f [in.top()]+2 + f [i-1];
            if ( i-f[i]>=1 ) f [i] += f [ i-f[i] ];
            in.pop();
        }else
            in.push (i);
    }
    int ans = 0;
    for ( int i = 1; i <= (int)strlen(s+1); ++i ) ans = max ( ans, f [i] );
    printf ( "%d", ans ); return 0;
}

初始状态为f[i]=0任取1<=i<=n

目标状态为MAX{f[i]任取1<=i<=n}

以结尾的位置为阶段，以f[i]即 以i结尾的“完美括号序列”的最大长度为状态，时刻维护位置i之前的f[i]
的正确

思考后容易得出转移方程（见代码）

请读者思考为何将if下第一行替换为以下写法也是正确的（答案在题解最下方）

f [i] = 2 + f [i-1];

思考题答案：以左括号位置结尾的“完美括号序列”的最大长度总是0

题目描述

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例

样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        if(nums.empty()) return -1;
        int len = nums.size()-1;
        int hash[nums.size()];
        fill(hash,hash+nums.size(),0);
        while(len--)
        {
            if(nums[len]>nums.size()-1||nums[len]<0) return -1;
        }
        for(int i=0;i<nums.size();i++)
        {

            hash[nums[i]]++;
            if(hash[nums[i]]>1) return nums[i];
        }
        return -1;
    }
};