Java 夜话(1)

背景

今天上班时被问到一个问题，题目如下：

给定一个 Set<String> 里面一些列关键字字符串，现要求，给定一个长度 length，要求 Set 中的关键字组成一个用 , 分割的并且不超过给定长度的字符串，但 , 不算字数，每个关键词可以随意组合，每个关键词只能使用一次。

例如：Set(String) = {“你好”, “世界”, “来玩”, “LOL”, “学习”, “天气好”, “明天下雨”},length = 5

其中一个正确的输出为 {“你好,世界”, “来玩,LOL”, “学习,天气好”, “明天下雨”}，答案并不固定，只需要符合要求即可。

实现

我们需要记录下 , 的个数，使用 StringBuilder 来构造候选结果集元素，候选结果集元素是包含 , 的全部字符，我们只需要用候选结果集元素减去逗号的个数就能得到真正的字符长度，用此长度来与 length 比较即可。

此种方法并不是最优解，只是遍历了一遍 Set 集合，并没有主动寻找最优的字符串。

public List<String> m1(Set<String> keys, int length) {
    // 逗号计数
    int commaCount = 0;
    // 候选结果临时变量
    StringBuilder tmp = new StringBuilder();
    // 结果集
    final List<String> result = new ArrayList<>();
    for (String key : keys) {
        // 当前候选结果临时变量的长度减去逗号的个数就等于实际存入的关键字的长度
        // 如果实际存入的关键字小于给定的长度，我们认为该 key 合法并添加到候选结果临时变量中
        if (tmp.length() - commaCount + key.length() <= length) {
            // 将当前 key 添加到候选结果中
            tmp.append(key).append(",");
            // 逗号个数 +1
            commaCount++;
        } else {
            // 如果该 key 非法，即加上该 key 会导致候选结果超长，则我们将当前的 tmp 添加到结果集中
            result.add(tmp.substring(0, tmp.length() - 1));
            // tmp 重置
            tmp = new StringBuilder(key).append(",");
            // 将逗号数量初始化为 1
            commaCount = 1;
        }
    }
    // 最后一次边界值考虑
    if (tmp.length() > 0) {
        result.add(tmp.substring(0, tmp.length() - 1));
    }
    return result;
}