当前位置：首页 > news >正文

【2024华为OD-E卷-100分-字符串分割】（题目+思路+JavaC++Python解析)

news 来源：原创 2025/6/9 23:04:18

题目

字符串分割

给定一个字符串 s 和一个整数 k，你需要将字符串 s 分割成恰好 k 个非空子字符串，使得这些子字符串中字典序最大的子字符串尽可能小。

输入：

第一行输入一个字符串 s（只包含小写字母）。
第二行输入一个整数 k。

输出：

输出恰好 k 个子字符串，使得这些子字符串中字典序最大的子字符串尽可能小。

示例：

输入：

abacabadabacaba
4

输出：

aba
cab
ada
bacaba

思路

这个问题类似于贪心算法的一个应用。我们需要找到一个平衡点，使得分割后的子字符串中字典序最大的那个尽可能小。为了实现这一点，我们可以从字符串的开头开始，逐步增加子字符串的长度，直到满足以下条件之一：

如果继续增加当前子字符串的长度会导致剩余的子字符串数量少于 k-1 个（因为还需要至少一个子字符串来容纳剩余的部分），则停止增加当前子字符串的长度，并开始一个新的子字符串。
如果当前子字符串已经是字典序最大的可能选择（即继续增加长度会导致字典序变大），则停止增加当前子字符串的长度，并开始一个新的子字符串。

为了实现这个策略，我们可以使用一个双指针的方法来模拟分割过程，同时维护一个字典序的比较器来确定何时停止增加当前子字符串的长度。

Java 编码解析

import java.util.Scanner;

public class StringSplit {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int k = scanner.nextInt();
        scanner.close();

        String[] result = splitString(s, k);
        for (String part : result) {
            System.out.println(part);
        }
    }

    public static String[] splitString(String s, int k) {
        int n = s.length();
        String[] result = new String[k];
        int start = 0;

        for (int i = 0; i < k - 1; i++) {
            int maxLen = (n - start) / (k - i); // Maximum length to keep balance
            int end = findBestEnd(s, start, start + maxLen - 1);
            result[i] = s.substring(start, end + 1);
            start = end + 1;
        }
        result[k - 1] = s.substring(start); // The last substring takes the remaining part

        return result;
    }

    private static int findBestEnd(String s, int start, int maxEnd) {
        String best = s.substring(start, start + 1); // Start with the smallest possible substring
        int bestEnd = start;

        for (int end = start + 1; end <= maxEnd; end++) {
            String candidate = s.substring(start, end + 1);
            if (candidate.compareTo(best) <= 0) {
                best = candidate;
                bestEnd = end;
            }
        }

        return bestEnd;
    }
}

C++ 编码解析

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

using namespace std;

vector<string> splitString(const string& s, int k) {
    int n = s.length();
    vector<string> result(k);
    int start = 0;

    for (int i = 0; i < k - 1; ++i) {
        int maxLen = (n - start) / (k - i); // Maximum length to keep balance
        int end = findBestEnd(s, start, start + maxLen - 1);
        result[i] = s.substr(start, end - start + 1);
        start = end + 1;
    }
    result[k - 1] = s.substr(start); // The last substring takes the remaining part

    return result;
}

int findBestEnd(const string& s, int start, int maxEnd) {
    string best = s.substr(start, 1); // Start with the smallest possible substring
    int bestEnd = start;

    for (int end = start + 1; end <= maxEnd; ++end) {
        string candidate = s.substr(start, end - start + 1);
        if (candidate <= best) {
            best = candidate;
            bestEnd = end;
        }
    }

    return bestEnd;
}

int main() {
    string s;
    int k;
    cin >> s >> k;

    vector<string> result = splitString(s, k);
    for (const string& part : result) {
        cout << part << endl;
    }

    return 0;
}

Python 编码解析

def split_string(s, k):
    n = len(s)
    result = []
    start = 0

    for i in range(k - 1):
        max_len = (n - start) // (k - i) # Maximum length to keep balance
        end = find_best_end(s, start, start + max_len - 1)
        result.append(s[start:end + 1])
        start = end + 1

    result.append(s[start:]) # The last substring takes the remaining part

    return result

def find_best_end(s, start, max_end):
    best = s[start:start + 1] # Start with the smallest possible substring
    best_end = start

    for end in range(start + 1, max_end + 1):
        candidate = s[start:end + 1]
        if candidate <= best:
            best = candidate
            best_end = end

    return best_end

if __name__ == "__main__":
    s = input().strip()
    k = int(input().strip())

    result = split_string(s, k)
    for part in result:
        print(part)

题目

Java 编码解析

C++ 编码解析

Python 编码解析

相关文章：