五子棋迷 - 华为OD统一考试

OD统一考试（B卷）

分值： 100分

题解： Java / Python / C++

题目描述

张兵和王武是五子棋迷，工作之余经堂切磋棋艺。这不，这会儿又下起来了。走了一会儿，轮张兵了，对着一条线思考起来了，这条线上的棋子分布如下:

用数组表示: -1 0 1 1 1 0 1 0 1 -1

棋了分布说明:

-1代表白子，0代表空位，1代表黑子

• 数组长度L，满足1 < L < 40，L为奇数

你得帮他写一个程序，算出最有利的出子位置。 最有利定义:

• 找到一个空位(0)，用棋子(1/-1)填充该位置，可以使得当前子的最大连续长度变大
• 如果存在多个位置，返回最靠近中间的较小的那个坐标
• 如果不存在可行位置，直接返回-1
• 连续长度不能超过5个(五字棋约束)

输入描述

第一行: 当前出子颜色。

第二行: 当前的棋局状态。

输出描述

1个整数，表示出子位置的数组下标

示例1

输入：
1
-1 0 1 1 1 0 1 -1 1

输出：
5

说明：
当前为黑子(1)，放置在下标为5的位置，黑子的最大连续长度，可以由3到5

示例2

输入：
-1
-1 0 1 1 1 0 1 0 1 -1 1

输出：
1

说明：
当前为白子，唯一可以放置的位置下标为1，白字的最大长度，由1变为2

输入：
1
0 0 0 0 1 0 0 0 0 1 0

输出：
5

说明：
可以的位置很多，5最接近中间的位置坐标

题解

思路

首先，我们可以遍历棋盘，找到当前棋子的最大连续长度。然后，对于每一个空位，我们尝试在该位置放置棋子，然后重新计算最大连续长度。如果新的长度大于之前的最大长度，我们更新最优位置（选择距离中间更近的位置）。

时间复杂度

假设棋盘的长度为L，遍历一次棋盘计算最大连续长度的时间复杂度为O(L)，对每一个空位的尝试放置棋子的时间复杂度也是O(L)。因此，总体时间复杂度为O(L^2)。

空间复杂度

除了输入和输出所占用的空间外，我们只需要使用常数额外的空间来存储一些中间变量。因此，空间复杂度为O(1)。

Java

import java.util.Arrays;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int x = Integer.parseInt(scanner.nextLine());
        int[] arr = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(t -> Integer.parseInt(t))
                .toArray();
        int L = arr.length;

        //下棋前 “当前子的最大连续长度”
        int maxSeqLength = 0;
        for (int i = 0, seqLength = 0; i < L; i++) {
            seqLength = (arr[i] == x) ? seqLength + 1 : 0;
            maxSeqLength = Math.max(maxSeqLength, seqLength);
        }

        int bestIdx = -1;
        for (int i = 0; i < L; i++) {
            if (arr[i] != 0) continue;

            int l = i, r = i;
            while (l > 0 && arr[l - 1] == x) l--;
            while (r + 1 < L && arr[r + 1] == x) r++;
            int seqLength = r - l + 1;

            // 连续长度不能超过5个(五字棋约束)
            // 下棋后“可以使得当前子的最大连续长度变大”
            if (seqLength <= 5 && seqLength > maxSeqLength) {
                if (Math.abs(L / 2 - bestIdx) > Math.abs(L / 2 - i)) {
                    bestIdx = i;
                } else if (Math.abs(L / 2 - bestIdx) == Math.abs(L / 2 - i)) {
                    bestIdx = Math.min(bestIdx, i);
                }
            }
        }

        System.out.println(bestIdx);
    }
}

Python

x = int(input())
arr = list(map(int, input().split()))
L = len(arr)

# 下棋前 “当前子的最大连续长度”
max_seq_length = 0
seq_length = 0
for cur in arr:
    if cur == x:
        seq_length += 1
    else:
        max_seq_length = max(max_seq_length, seq_length)
        seq_length = 0


# 最佳的下子位置
best_idx = -1

for i in range(L):
    if arr[i] != 0:
        continue

    # 尝试在 i 的位置下棋子
    l, r = i, i
    while l > 0 and arr[l - 1] == x:
        l -= 1
    while r + 1 < L and arr[r + 1] == x:
        r += 1

    # 最大连续长度
    seq_length = r - l + 1
    if seq_length > 5:  # 连续长度不能超过5个(五字棋约束)
        continue

    if seq_length > max_seq_length:  # 下棋后“可以使得当前子的最大连续长度变大”
        # 长度相同， 存在多个位置
        # 返回最靠近中间的较小的那个坐标
        if abs(L // 2 - best_idx) > abs(L // 2 - i):
            best_idx = i
        elif abs(L // 2 - best_idx) == abs(L // 2 - i):
            best_idx = min(best_idx, i)


print(best_idx)

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int x,num;
    cin >> x;
    vector<int> arr;
    while (cin >> num) {
        arr.push_back(num);
    }

    int L = arr.size();

    // 下棋前 “当前子的最大连续长度”
    int maxSeqLength = 0;
    int seqLength = 0;
    for (int i = 0; i < L; i++) {
        seqLength = (arr[i] == x) ? seqLength + 1 : 0;
        maxSeqLength = max(maxSeqLength, seqLength);
    }

    int bestIdx = -1;
    for (int i = 0; i < L; i++) {
        if (arr[i] != 0) continue;

        int l = i, r = i;
        while (l > 0 && arr[l - 1] == x) l--;
        while (r + 1 < L && arr[r + 1] == x) r++;
        int seqLength = r - l + 1;

        // 连续长度不能超过5个(五字棋约束)
        // 下棋后“可以使得当前子的最大连续长度变大”
        if (seqLength <= 5 && seqLength > maxSeqLength) {
            if (abs(L / 2 - bestIdx) > abs(L / 2 - i)) {
                bestIdx = i;
            } else if (abs(L / 2 - bestIdx) == abs(L / 2 - i)) {
                bestIdx = min(bestIdx, i);
            }
        }
    }

    cout << bestIdx << endl;

    return 0;
}

🙏整理题解不易， 如果有帮助到您，请给点个赞 ???? 和收藏 ?，让更多的人看到。🙏🙏🙏