oppo筆試 oppo筆試題 0329

筆試時間：2025年03月29日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目：踩石頭過河

有一條長度為n的河流，小O初始位于左岸邊(即河流左側(cè)的位置)，他想要跨越到河的對岸(即河流右側(cè)的位置)。河上有一些石頭可以供小O踩在上面。小O只能踩在石頭或者岸邊，他想知道他在能跨到河對岸的情況下，最長的一步最短是多少。

輸入描述

第一行輸入一個整數(shù)n(1 <= n <= 2*10^5)代表河流的長度。第二行輸入n 個正整數(shù) a1,a2,...,an(0 <= ai <= 1)代表是否是石頭，如果ai=1，則說明當(dāng)前位置是石頭可以踩;否則是水流，不能踩。

輸出描述

在一行上輸出一個整數(shù)，表示最長的一步的最小值。

樣例輸入

5

0 1 1 0 1

樣例輸出

2

參考題解

模擬

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

#include <iostream>
#include <vector>
#include <algorithm>

usingnamespacestd;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> pos;
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            pos.push_back(i + 1);
        }
    }
    pos.push_back(0);
    pos.push_back(n + 1);
    sort(pos.begin(), pos.end());
    int res = 0;
    for (int i = 1; i < pos.size(); ++i) {
        res = max(res, pos[i] - pos[i - 1]);
    }
    cout << res << endl;
    return0;
}

Java：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (a[i] != 0) {
                pos.add(i + 1); // 1-based position
            }
        }

        pos.add(0);       // add left boundary
        pos.add(n + 1);   // add right boundary
        Collections.sort(pos);

        int res = 0;
        for (int i = 1; i < pos.size(); i++) {
            res = Math.max(res, pos.get(i) - pos.get(i - 1));
        }

        System.out.println(res);
        scanner.close();
    }
}

Python：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

n = int(input())
a = list(map(int, input().split()))

pos = [i + 1 for i in range(n) if a[i] != 0]
pos.append(0)
pos.append(n + 1)
pos.sort()

res = 0
for i in range(1, len(pos)):
    res = max(res, pos[i] - pos[i - 1])

print(res)

第二題

題目：分割最少段數(shù)

小O有一個長度為 n 的數(shù)組 a，他在數(shù)組x上定義了一個函數(shù)f(x)，表示數(shù)組x中所有元素做按位|運(yùn)算的結(jié)果。(例如x=[1,2,4,8]，則f(x)=1|2|4|8=15)小O現(xiàn)在希望將數(shù)組a分割成盡可能少的段，使得所有段的f函數(shù)值中的最大值不超過 k，請問他最少可以將a分為幾段，請你幫幫他吧。