ARTS #64 | 善战者无赫赫之功

Algorithm

规则如下：

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case.
Each word in text are separated by a single space.

Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.

Example 2:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.

Example 3:

Input: text = "To be or not to be"
Output: "To be or to be not"

Constraints:

text begins with a capital letter and then contains lowercase letters and single space between words.
1 <= text.length <= 10^5

Solution

把单词换成数字可以发现这就是一个稳定排序。

基于 right-most 的二分：

class Solution:
    def arrangeWords(self, text: str) -> str:
        ans = []

        def right_most(target: int) -> int:
            left, right = 0, len(ans)
            while left < right:
                middle = (left + right) // 2
                if len(ans[middle]) > target:
                    right = middle
                else:
                    left = middle + 1
            return left

        start, end = 0, 0
        while end <= len(text):
            if end == len(text) or text[end] == " ":
                word = text[start:end]
                index = right_most(len(word))
                if index == len(ans):
                    ans.append(word)
                else:
                    ans.insert(index, word)
                start = end + 1
            end += 1
        return " ".join(ans).capitalize()

基于归并排序：

class Solution:
    def arrangeWords(self, text: str) -> str:
        def merge_sort(words:[]) -> []:
            half = len(words) // 2
            if half:
                left, right = merge_sort(words[:half]), merge_sort(words[half:])
                for i in range(len(words)):
                    if not right or (left and len(left[0]) <= len(right[0])):
                        words[i] = left.pop(0)
                    else:
                        words[i] = right.pop(0)
            return words
        
        ans = text.split(" ")
        ans[0] = ans[0].lower()
        merge_sort(ans)
        ans[0] = ans[0].capitalize()
        return " ".join(ans)

Review

A Complete Guide to Dark Mode on the Web

很不错的 Dark Mode 设计指南，细节丰富、例子生动，对我完成网站的 Dark Mode 帮助很大。

Tip

在读 Tocbot 的源码时发现 CSS 有个好玩的关键字 currentColor :

The currentcolor keyword represents the value of an element’s color property. This lets you use the color value on properties that do not receive it by default.
If currentcolor is used as the value of the color property, it instead takes its value from the inherited value of the color property.

该关键字可以帮助我们更好的维护 CSS，如下例子：

/*a 标签*/
.button {
    color: #117B6F;
    font-size: 1.2em;
}
.button:hover, .button:focus {
    color: #01B19A;
}
.button:active {
    color: #02D7BB;
}

/*svg 标签*/
.button svg {
    height: 17px;
    width: 17px;
    fill: #117B6F;
}
.button:hover svg, .button:focus svg {
    fill: #01B19A;
}
.button:active svg {
    fill: #02D7BB;
}

使用 currentColor 后：

/*a 标签*/
.button {
    color: #117B6F;
    font-size: 1.2em;
}
.button:hover, .button:focus {
    color: #01B19A;
}
.button:active {
    color: #02D7BB;
}

/*svg 标签*/
.button svg {
    height: 17px;
    width: 17px;
    fill: currentColor;
}

例子来自网上：传送门

来自某个我关注的公众号里的例子：

我曾引用过曼联和弗格森的故事：弗爵爷根据下滑的铲球数据卖掉了后防中坚斯塔姆，但事后承认自己犯了大错。铲球通常是最后一招，斯塔姆的位置感和阅读比赛的能力超强，他的铲球变少，是因为可以提前到达正确的位置解除危机。斯塔姆的价值在于肉眼看不到的地方。

这里存在的陷阱是：数据描述的是对过去的影响，它只关注已发生的事件，对未曾发生过的事件是忽略的。看不见的东西也需要关注，所谓善战者无赫赫之功，我想它们说的其实是同一件事。

本周发布了 CodingTour 的更新记录：更新 CodingTour。

Algorithm

Solution

Review

Tip

Share