string - 查找需要发送的最少消息数

Question

我最近在我的编码面试测试中遇到了一个问题。问题如下。

Suppose there is a service to send messages to a user. Each message has the length of maximum 30 characters. This service receives a complete message and then breaks it into sub-messages, each of size 30 characters at most. But there is an issue with the service. It doesn't guarantee the order in which the sub-messages are received by the user. Hence, for every sub-message, it appends a suffix (k/n) where k denotes the kth sub-message out of the n sub-messages. This suffix is also considered when counting the number of characters in the sub-message which cannot exceed 30. Find the minimum number of sub-messages required to send.

例1:

消息:敏捷的棕色狐狸跳过懒惰的狗

第一条子消息可以是:The quick brown fox jumps (1/2) but

以上内容不正确，因为它超过了 30 个字符。这有 31 个字符。

因此，正确的子消息是:

敏捷的棕狐(1/2)

越过懒狗(2/2)

所以，答案是2。

例子2:

消息:敏捷的棕色狐狸跳过懒惰的乌龟

因此，正确的子消息是:

敏捷的棕狐(1/3)

越过懒人(2/3)

乌龟(3/3)

所以，答案是 3。

例子3:

消息:你好，我的名字是

子消息:你好我的名字是

答案 = 1。

注意:一个词不能跨子消息打断。假设没有一个单词的长度超过 30 个字符。如果是单个消息，则无需使用后缀

我的做法:如果字符串的总字符长度小于30则返回1。如果不是，则获取子消息直到字符数为30，逐字检查。但是现在它变得复杂了，因为我不知道后缀中 n 的值。有没有更简单的方法来解决这个问题？

Answer 1

感谢您发帖，我确实很喜欢这类问题。

正如上面提到的domen，这里有一点挑战，你不知道需要多少行。因此，您不知道消息编号/消息总数是否允许 2(或更多)位数字。此外，您能否使用十六进制(16 条消息需要一个数字，甚至是 base 62 格式数字(0-9，然后是 A-Z，然后是 a-z)？

您当然可以猜测，如果输入超过 200 个字符，那么您可以使用两位数的消息编号，但如果消息是单个字母后跟一个重复的空格100 次，那么您可能只需要个位数的消息编号就可以逃脱。

因此，您可能会发现需要多次运行该算法。我假设单个数字的消息编号对于此问题是可接受的，如果您愿意，您可以增强我的解决方案以使用 base 52 消息编号。

我的方法使用 2 个类:

1. 创建一个代表单行消息的 MessageLine 类。
2. MessageSender 一个收集 MessageLine(s) 的类。它有一个辅助方法，可以处理消息并返回 MessageLines 列表。

这是主要的 MessageSender 类。如果您运行它，您可以在命令行上传递一条消息以供其处理。

package com.gtajb.stackoverflow;

import java.util.LinkedList;

public class MessageSender {

    public static void main(String[] args) {
        if (args.length == 0) {
            System.out.println("Please supply a message to send");
            System.exit(1);
        }

        // Collect the command line parameters into a single string.
        StringBuilder sb = new StringBuilder();
        boolean firstWord = true;
        for (String s: args) {
            if (!firstWord) {
                sb.append(" ");
            }
            firstWord = false;
            sb.append(s);
        }

        // Process the input String and create the MessageSender object.
        MessageSender ms = new MessageSender(sb.toString());
        System.out.println("Input message: " + sb.toString());

        // Retrieve the blocked message and output it.
        LinkedList<MessageLine> msg = ms.getBlockedMessage();
        int lineNo = 0;
        for (MessageLine ml : msg) {
            lineNo += 1;
            System.out.printf("%2d: %s\n", lineNo, ml.getFormattedLine(msg.size()));
        }
    }

    private String msg;

    public MessageSender(String msg) {
        this.msg = msg;
        processMessage();
    }

    private LinkedList<MessageLine> blockedMessage = new LinkedList<MessageLine> ();

    public LinkedList<MessageLine> getBlockedMessage() {
        return blockedMessage;
    }

    private static final int LINE_MAX_SIZE = 30;
    /**
     * A private helper method that processes the supplied message when
     * the object is constructed.
     */
    private void processMessage() {

        // Split the message into words and work out how long the message is.
        String [] words = msg.split("\\s+");
        int messageLength = 0;
        for (String w: words) {
            messageLength += w.length();
        }
        messageLength += words.length - 1;            // Add in the number of words minus one to allow for the single spaces.

        // Can we get away with a single MessageLine?
        if (messageLength < LINE_MAX_SIZE) {
            // A single message line is good enough.
            MessageLine ml = new MessageLine(1);
            blockedMessage.add(ml);
            for (String w: words) {
                ml.add(w);
            }
        } else {
            // Multiple MessageLines will be required.
            int lineNo = 1;
            MessageLine ml = new MessageLine(lineNo);
            blockedMessage.add(ml);
            for (String w: words) {
                    // check if this word will blow the max line length.
                    // The maximum number of lines is 2. It can be anything that is > 1.
                if (ml.getFormattedLineLength(2) + w.length() + 1 > LINE_MAX_SIZE) {
                    // The word will blow the line length, so create a new line.
                    lineNo += 1;
                    ml = new MessageLine(lineNo);
                    blockedMessage.add(ml);
                }
                ml.add(w);
            }
        }
    }
}

这是消息行类:

package com.gtajb.stackoverflow;

import java.util.LinkedList;

public class MessageLine extends LinkedList<String> {

    private int lineNo;
    public MessageLine(int lineNo) {
        this.lineNo = lineNo;
    }

    /**
     * Add a new word to this message line.
     * @param word the word to add
     * @return true if the collection is modified.
     */
    public boolean add(String word) {
        if (word == null || word.trim().length() == 0) {
            return false;
        }
        return super.add(word.trim());
    }

    /**
     * Return the formatted message length.
     * @param totalNumLines the total number of lines in the message.
     * @return the length of this line when formatted.
     */
    public int getFormattedLineLength(int totalNumLines) {
        return getFormattedLine(totalNumLines).length();
    }

    /**
     * Return the formatted line optionally with the line count information.
     * @param totalNumLines the total number of lines in the message.
     * @return the formatted line.
     */
    public String getFormattedLine(int totalNumLines) {

        boolean firstWord = true;
        StringBuilder sb = new StringBuilder();
        for (String w : this) {
            if (! firstWord) {
                sb.append (" ");
            }
            firstWord = false;
            sb.append(w);
        }
        if (totalNumLines > 1) {
            sb.append (String.format(" (%d/%d)", lineNo, totalNumLines));
        }
        return sb.toString();
    }
}

我测试了您的方案，它似乎产生了正确的结果。

如果我们得到这份工作，请告诉我。 :-)