General Motors

01Prepare Notification

Prepare a notification of the given message which will be displayed on a mobile device. The message is made of words separated by single spaces. The length of the notification is limited to K characters. If the message is too long to be displayed fully, some words from the end of the message should be cropped, keeping in mind that: the notification should be as long as possible; only whole words can be cropped; if any words are cropped, the notification should end with '...'; the dots should be separated from the last word by a single space; the notification may not exceed the K-character limit, including the dots. If all the words need to be cropped, the notification is '...' (three dots without a space). Write up the func in the editor Given a string message and an integer K, returns the notification to display, which has no more than K chars, as described above.

Constraints

K is an integer within the range [3, 500]
the len of string msg i within the range [1, 500]
string msg is made of English letters ('a' - 'z', 'A-Z') and space ('')
msg does not contains spaces at the beginning of at the end
words are separated by a single space (there are never 2 or more consecutive sapces)

Example 1

Input:

message = "And now here is my secret"
K = 15

Output:

"And now ..."

Explanation: no explanation is provided

Example 2

Input:

message = "There is an animal with four legs"
K = 15

Output:

"There is an ..."

Explanation: no explanation is provided

Example 3

Input:

message = "super dog"
K = 4

Output:

"..."

Explanation: no explanation is provided

Example 4

Input:

message = "how are you"
K = 20

Output:

"how are you"

Explanation: no explanation is provided

解法

若整条消息长度 ≤ K 直接返回。否则贪心从前往后累计单词，要求累计 + " ..." 不超过 K；选最长合法前缀。若一个词也放不下则返回 "..."。复杂度 O(|message|)。

def prepare_notification(message: str, K: int) -> str:
    if len(message) <= K:
        return message
    words = message.split()
    chosen = []
    cur = 0
    for w in words:
        extra = len(w) if not chosen else len(w) + 1
        if cur + extra + 4 <= K:
            chosen.append(w)
            cur += extra
        else:
            break
    if not chosen:
        return "..."
    return " ".join(chosen) + " ..."

class Solution {
    String prepareNotification(String message, int K) {
        if (message.length() <= K) return message;
        String[] words = message.split(" ");
        StringBuilder sb = new StringBuilder();
        int cur = 0;
        for (String w : words) {
            int extra = sb.length() == 0 ? w.length() : w.length() + 1;
            if (cur + extra + 4 <= K) {
                if (sb.length() > 0) sb.append(' ');
                sb.append(w);
                cur += extra;
            } else break;
        }
        if (sb.length() == 0) return "...";
        sb.append(" ...");
        return sb.toString();
    }
}

class Solution {
public:
    string prepareNotification(string message, int K) {
        if ((int) message.size() <= K) return message;
        vector<string> words;
        string w;
        for (char c : message) {
            if (c == ' ') { if (!w.empty()) { words.push_back(w); w.clear(); } }
            else w += c;
        }
        if (!w.empty()) words.push_back(w);
        string out;
        int cur = 0;
        for (auto& wd : words) {
            int extra = out.empty() ? (int) wd.size() : (int) wd.size() + 1;
            if (cur + extra + 4 <= K) {
                if (!out.empty()) out += ' ';
                out += wd;
                cur += extra;
            } else break;
        }
        if (out.empty()) return "...";
        return out + " ...";
    }
};

02Come Looking for the Smallest Num Which Must Be > Than a Specific Num.

To solve this problem, you gonna need to write up the func in the editor What you've been given: int Z What your func is gonna do:

find the smallest num that is > than Z.
total of all the digits of the num you find must == 2 * (total of all digits of Z) Memo : When solving this problem, you can mainly focus on correctness. As for your code performance, it would not be the focus this time .

Constraints

1 ≤ Z ≤ 500.

Example 1

Input:

N = 10

Output:

Explanation: As we can see, 11 is the smallest num that is > 10. What is the total sum of all digits of 10? The ans is 1 + 0 = 1... What is the total sum of all digits of 11? The ans is 1 + 1 = 2... 2 == 1 * 2, so 11 should be returned.

Example 2

Input:

N = 14

Output:

Explanation: The total of all the digits of 19 (1 + 9 = 10) == 2 * total of digits of 14 (1 + 4 = 5)

Example 3

Input:

N = 99

Output:

Explanation: The sum of digits of 9999 (9 + 9 + 9 + 9 = 36) == total of digits of 99 (9 + 9 = 18).

解法

题目说只关注正确性，直接从 Z + 1 暴力枚举，对每个候选求数字和，找到第一个数字和 == 2 * digitSum(Z) 即返回。由于 Z ≤ 500 范围小，循环范围可控。复杂度 O(answer · log answer)。

def find_smallest_double_digit_sum(Z: int) -> int:
    target = 2 * sum(int(c) for c in str(Z))
    x = Z + 1
    while True:
        if sum(int(c) for c in str(x)) == target:
            return x
        x += 1

class Solution {
    int findSmallestDoubleDigitSum(int Z) {
        int target = digitSum(Z) * 2;
        long x = Z + 1L;
        while (true) {
            if (digitSum(x) == target) return (int) x;
            x++;
        }
    }

    private int digitSum(long n) {
        int s = 0;
        while (n > 0) { s += (int) (n % 10); n /= 10; }
        return s;
    }
}

class Solution {
public:
    int findSmallestDoubleDigitSum(int Z) {
        auto ds = [](long long n) { int s = 0; while (n > 0) { s += n % 10; n /= 10; } return s; };
        int target = ds(Z) * 2;
        long long x = Z + 1LL;
        while (true) {
            if (ds(x) == target) return (int) x;
            ++x;
        }
    }
};