iT邦幫忙

2026 iThome 鐵人賽

DAY 10
0
Software Development

30天刷完leetcoode75系列 第 10 篇

C++ 演算法練習 Day10|933, 649 題解與思路分享

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20260924/20184265hfkymhYoNb.png

題目解析: 實作一個計數器,每次輸入一個時間點,就要算出包含這個時間點在內,過去3000毫秒內總共有幾次輸入
解題思路: 先設一個佇列v來裝每次輸入的時間,然後每次呼叫ping的時候就把新時間加進去。接著丟進迴圈開始跑,如果佇列最前面的時間比目前時間減去3000還要小,就把最前面的拔掉,最後回傳佇列裡剩下的數量

class RecentCounter {
public:
    queue<int> v;

    RecentCounter() {
        
    }
    
    int ping(int t) {
        v.push(t);
        while(v.front() < t - 3000){
            v.pop();
        }
        return v.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

https://ithelp.ithome.com.tw/upload/images/20260924/20184265nAQ8YVSNIM.png

題目解析: 給一個代表兩個陣營參議員的字串,每個參議員可以行使權力把對手陣營的下一個參議員淘汰,輪流投票直到只剩下同一個陣營為止,回傳最後贏的陣營
解題思路: 先設兩個變數R跟D來紀錄兩個陣營目前被抵消的額度,然後丟進一個無窮迴圈開始跑。每次跑的時候設一個空字串s來記下一輪活下來的人,接著把原始字串一個一個拿出來看。如果遇到D,且R的額度是0,代表D活下來了,就把D的額度加1並加進s裡,不然就消耗一次R的額度;遇到R的邏輯也一樣。跑完一輪後檢查s裡面是不是只剩同一種人,如果是就直接回傳贏家,不然就把s替換掉原本的字串繼續下一輪

class Solution {
public:
    string predictPartyVictory(string senate) {
        int R = 0, D = 0;

        while(true){
            string s = "";
            for(char c : senate){
                if(c == 'D'){
                    if (R == 0){
                        D++; 
                        s += 'D';
                    }else R--;
                }else{
                    if(D == 0){ 
                        R++; 
                        s += 'R'; 
                    }else D--;
                }
            }

            if (count(s.begin(), s.end(), 'R') == 0) return "Dire";
            if (count(s.begin(), s.end(), 'D') == 0) return "Radiant";

            senate = s;
        }
    }
};

上一篇
C++ 演算法練習 Day9|735, 394題解與思路分享
下一篇
C++ 演算法練習 Day11|746, 1137 題解與思路分享
系列文
30天刷完leetcoode75 共 11 篇
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

0
godlichen
iT邦新手 5 級 ‧ 2026-09-24 19:00:54

呃>>>>太強了啦!!!!

0
godlichen
iT邦新手 5 級 ‧ 2026-09-24 19:00:55

呃>>>>太強了啦!!!!

我要留言

立即登入留言