Round Robin輪詢算法

名字高大上，其實就是循環、周遊這個意思，

不過它強調的一個輪轉，且每個均勻，是以通常有取模的操作。

比如在排程中應用：

Round Robin 是一種CPU 排程算法，其中每個程序以循環方式配置設定一個固定的時隙。

• 它簡單、易于實作且無饑餓，因為所有程序都獲得公平的 CPU 份額。
• 作為核心的 CPU 排程中最常用的技術之一。
• 它是搶占式的，因為程序最多隻能在固定的時間片内配置設定 CPU。
• 它的缺點是更多的上下文切換開銷。

比如在Go和Redis中：

将任務通過取模的方式，分給每個線程的本地隊列

LC 68. 文本左右對齊

困難題，模拟，主要就是字元串填充。其中的

round_robin

函數就是輪流給前n-1的單詞添加一個空格，直到空格填完。

class Solution:
    def round_robin(self, words, space_num): # 輪流填充
        n = len(words)
        for i in range(space_num):
            words[i%((n-1) or 1)] += ' '
        
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res, cur, cur_len = [], [], 0 
        for word in words:
            if(cur_len + len(cur) + len(word) > maxWidth):
                self.round_robin(cur, maxWidth-cur_len)
                line = ''.join(cur)
                res.append(line)
                cur, cur_len = [], 0
            cur.append(word)
            cur_len += len(word)
        # 最後一行
        res.append(' '.join(cur).ljust(maxWidth))
        return res
           

LC 621. 任務排程器

題意：帶冷卻時間的輪流執行

方法：由頻率最高的決定，其實是道數學題，不需要去逐一填充。前m-1段預設補充至n+1，最後一段不需要補充，而最後一段的長度就看有幾個最高頻率的。

class Solution {
public:
    // 
    int cnt[26];
    int leastInterval(vector<char>& tasks, int n) {
        int len = tasks.size();
        for(int i = 0;i < len;i++)  cnt[tasks[i]-'A']++;
        sort(cnt, cnt+26);
        int res = (cnt[25]-1)*(n+1);  // 前m-1段排滿
        for(int i = 25;i >= 0;i--)
        {
            if(cnt[i] != cnt[25]) break; 
            res++;   // 加上最後一段
        }
        res = max(res, len);
        return res;
    }
};
           

參考連結

1. leetcode 68：Text Justification（Round Robin算法應用
2. https://leetcode-cn.com/problems/task-scheduler/comments/30672

個性簽名：時間會解決一切