oppo笔试 oppo笔试题 0426

笔试时间：2025年04月26日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：op 串问题

小欧有一个仅由 'o'、'p' 组成的字符串，要删除 2 个 'o' 和 2 个 'p'，求字典序最小的字符串。字典序比较规则为：a 是 b 的前缀且 a≠b ；或 a 与 b 第一个不同位置处，a 的字母在字母表中位置前于 b 相应字母。

输入描述

一行输入长度为 | s|（5 ≤ |s| ≤ 10⁵）的仅由 'o'、'p' 组成的字符串 s，且字符串中 'o'、'p' 各有两个以上。

输出描述

输出一行，为字典序最小的答案字符串。

样例输入

oppoop

样例输出

op

解释：一种删除方法是删除前四个字母，可证明 “op” 在所有删除方法中字典序最小。

参考题解

该问题的目标是删除字符串中的 2 个 'o' 和 2 个 'p'，并返回字典序最小的字符串。处理过程中，我们需要维护栈，以便在遇到不合适的字符时能够进行删除。最终结果是要输出删除后的最小字典序字符串。

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (!(cin >> s)) return 0;
    int n = s.size();
    int tot_o = 0, tot_p = 0;
    for (char c : s) {
        if (c == 'o') ++tot_o;
        elseif (c == 'p') ++tot_p;
    }
    int rem_del_o = 2, rem_del_p = 2;
    int keep_o = tot_o - rem_del_o;
    int keep_p = tot_p - rem_del_p;

    int rem_o = tot_o, rem_p = tot_p;

    string st;
    st.reserve(n);

    int cnt_o = 0, cnt_p = 0;
    for (char c : s) {
        if (c == 'o') --rem_o;
        else           --rem_p;

        while (!st.empty()) {
            char top = st.back();
           
            if (top > c) {
                if (top == 'o') {
                    if (rem_del_o > 0 && (cnt_o - 1 + rem_o) >= keep_o) {
                        st.pop_back();
                        --cnt_o;
                        --rem_del_o;
                        continue;
                    }
                } else { 
                    if (rem_del_p > 0 && (cnt_p - 1 + rem_p) >= keep_p) {
                        st.pop_back();
                        --cnt_p;
                        --rem_del_p;
                        continue;
                    }
                }
            }
            break;
        }

        if (c == 'o') {
            if (cnt_o < keep_o) {
                st.push_back('o');
                ++cnt_o;
            } else {
                --rem_del_o;
            }
        } else { 
            if (cnt_p < keep_p) {
                st.push_back('p');
                ++cnt_p;
            } else {
              
                --rem_del_p;
            }
        }
    }
    cout << st << "\n";
    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);
        String s = scanner.nextLine();
        int n = s.length();
        int tot_o = 0, tot_p = 0;
        for (char c : s.toCharArray()) {
            if (c == 'o') tot_o++;
            else if (c == 'p') tot_p++;
        }
        int rem_del_o = 2, rem_del_p = 2;
        int keep_o = tot_o - rem_del_o;
        int keep_p = tot_p - rem_del_p;

        int rem_o = tot_o, rem_p = tot_p;

        Stack<Character> stack = new Stack<>();

        int cnt_o = 0, cnt_p = 0;
        for (char c : s.toCharArray()) {
            if (c == 'o') rem_o--;
            else rem_p--;

            while (!stack.isEmpty()) {
                char top = stack.peek();
                if (top > c) {
                    if (top == 'o') {
                        if (rem_del_o > 0 && (cnt_o - 1 + rem_o) >= keep_o) {
                            stack.pop();
                            cnt_o--;
                            rem_del_o--;
                            continue;
                        }
                    } else {
                        if (rem_del_p > 0 && (cnt_p - 1 + rem_p) >= keep_p) {
                            stack.pop();
                            cnt_p--;
                            rem_del_p--;
                            continue;
                        }
                    }
                }
                break;
            }

            if (c == 'o') {
                if (cnt_o < keep_o) {
                    stack.push('o');
                    cnt_o++;
                } else {
                    rem_del_o--;
                }
            } else {
                if (cnt_p < keep_p) {
                    stack.push('p');
                    cnt_p++;
                } else {
                    rem_del_p--;
                }
            }
        }

        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        System.out.println(result);
    }
}

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

s = input().strip()
n = len(s)
tot_o = s.count('o')
tot_p = s.count('p')
rem_del_o = 2
rem_del_p = 2
keep_o = tot_o - rem_del_o
keep_p = tot_p - rem_del_p

rem_o = tot_o
rem_p = tot_p

st = []
cnt_o = 0
cnt_p = 0

for c in s:
    if c == 'o':
        rem_o -= 1
    else:
        rem_p -= 1

    while st:
        top = st[-1]
        if top > c:
            if top == 'o':
                if rem_del_o > 0 and (cnt_o - 1 + rem_o) >= keep_o:
                    st.pop()
                    cnt_o -= 1
                    rem_del_o -= 1
                    continue
            else:
                if rem_del_p > 0 and (cnt_p - 1 + rem_p) >= keep_p:
                    st.pop()
                    cnt_p -= 1
                    rem_del_p -= 1
                    continue
        break

    if c == 'o':
        if cnt_o < keep_o:
            st.append('o')
            cnt_o += 1
        else:
            rem_del_o -= 1
    else:
        if cnt_p < keep_p:
            st.append('p')
            cnt_p += 1
        else:
            rem_del_p -= 1

print(''.join(st))

第二题

题目

小欧和小皮正在摘苹果，小欧在地面，小皮在苹果树上，小欧、小皮、苹果可以视为一个二维平面。小欧初始时在(t, 0)位置，她每个单位时间可以向左或向右移动1个单位长度，即移动到(t - 1, 0)或(t + 1, 0)位置，当然，她也可以不移动。摘苹果时，小皮会在开始的时候剪断苹果在的树枝，剪断树枝后苹果就会开始下落，下落速度会越来越快：第一个单位时间下落1个单位长度；第二个单位时间下落2个单位长度； … 第i个单位时间下落i个单位长度，以此类推。例如苹果初始时位置在(x, y)，那么第一个单位时间后苹果在(x, y - 1)的位置，第二个单位时间后苹果在(x, y - 3)的位置上，……。若苹果落地之后（即y值小于等于0的时刻）直至该单位时间结束，小欧都不在(x, 0)位置上，则这个苹果就坏掉了。对于每颗苹果，小欧想知道她是否可以在苹果坏掉前拿到这颗苹果（若苹果和小欧同时到达(x, 0)位置，视为小欧可以拿到这棵苹果）。在本题中，假设时间是非连续的，单位时间是最小的单位，只需要在每一个单位时间末判断，而不需要考虑单位时间内发生的问题。