笔试时间：2024年08月23日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s（1 <= s.length <= 1e4) ，判断字符串是否有效。如果有效，输出有效括号的个数。如果无效，则输出False。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

样例输入

5

()

([])

([[}]]){

){}()

))(())

样例输出

1

2

False

False

False

参考题解

leetcode类似原题，用栈解决。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <string>
#include <stack>
using namespace std;

void solve() {
    string s; 
    cin >> s;
    stack<char> pos;
    int ans = 0;
    
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            pos.push(c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (pos.empty()) {
                cout << "False" << '\n';
                return;
            }
            char t = pos.top();
            pos.pop();
            
            if ((c == ')' && t != '(') || (c == '}' && t != '{') || (c == ']' && t != '[')) {
                cout << "False" << '\n';
                return;
            } else {
                ans++;
            }
        } else {
            cout << "False" << '\n';
            return;
        }
    }
    
    if (pos.empty()) {
        cout << ans << '\n';
    } else {
        cout << "False" << '\n';
    }
}

int main() {
    int t; 
    cin >> t;
    while (t--) solve();    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            solve(scanner);
        }
        scanner.close();
    }

    public static void solve(Scanner scanner) {
        String s = scanner.next();
        Stack<Character> pos = new Stack<>();
        int ans = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                pos.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (pos.isEmpty()) {
                    System.out.println("False");
                    return;
                }
                char t = pos.pop();
                
                if ((c == ')' && t != '(') || (c == '}' && t != '{') || (c == ']' && t != '[')) {
                    System.out.println("False");
                    return;
                } else {
                    ans++;
                }
            } else {
                System.out.println("False");
                return;
            }
        }
        
        if (pos.isEmpty()) {
            System.out.println(ans);
        } else {
            System.out.println("False");
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solve():
    s = input()
    pos = []
    ans = 0
    
    for c in s:
        if c in "({[":
            pos.append(c)
        elif c in ")}]":
            if not pos:
                print("False")
                return
            t = pos.pop()
            
            if (c == ')' and t != '(') or (c == '}' and t != '{') or (c == ']' and t != '['):
                print("False")
                return
            else:
                ans += 1
        else:
            print("False")
            return
    
    if not pos:
        print(ans)
    else:
        print("False")

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

第二题

题目

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。答案就是25.输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。输出最长区域的长度。

样例输入

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

样例输出

25

参考题解

记忆化搜索，用dp{i,j}表示从(i,j)出发能滑的最远距离，用dfs搜索，若dp{i,j}>0即已经计算过，直接返回值即可，否则按照dfs思路递推计算其最大值，递推式为：dp{i,j}=max(dp{i,j},dfs(x,y)+1)（（i,j)与(x,y)相邻，且a{ x, y}<a{i, j}）

C++：[此代码未进行大量数据的测试，仅供参考]

#include<cstdio>
#include<algorithm>
using namespace std;

int r,c,res;
int a[105][105],dp[105][105];
int go[4][2]={-1,0,0,1,1,0,0,-1};

int dfs(int x,int y){
    if(dp[x][y]>0) return dp[x][y];
    dp[x][y]=1;
    for(int i=0;i<4;++i){
        int xx=x+go[i][0],yy=y+go[i][1];
        if(xx>=0&&xx<r&&yy>=0&&yy<c&&a[xx][yy]<a[x][y])
            dp[x][y]=max(dp[x][y],dfs(xx,yy)+1);
    }
    return dp[x][y];
}

int main(){
    scanf("%d%d",&r,&c);
    for(int i=0;i<r;++i)
        for(in