头像

utlw


访客:8533

离线:3个月前



utlw
7个月前

题目描述

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

样例

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

算法1

sort + min-heap $O(n)$

时间复杂度

C++ 代码

    // 先sort,然后遍历所有 intervals,
    // 在当前 interval的开始时刻,结束可以结束的meetings,
    // 剩下的就是还在进行的meeting, 再加上当前meeting
    // 用 end time 的小顶堆 manage meetings,可以快速知道 在给定时刻,哪些meeting可以结束。
    // 这个题目 sort start 和 srot by [start, end) 效果一样

    int minMeetingRooms(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;

        sort(begin(intervals), end(intervals));

        int res = 1;
        priority_queue<int, vector<int>, greater<int>> pq;

        for(const auto& x : intervals) {
            while(pq.size() && pq.top() <= x[0]) pq.pop();   
            pq.push(x[1]);
            res = max(res, (int)pq.size());
        }
        return res;
    }


算法2

tree map $O(n)$

C++ 代码

    // map<int, int> : time -> num_meetings,即 时刻 -> 该时刻正在进行的meeting数量
    // 将所有meeting加入到map中,start 时刻+1,end 时刻-1
    // 在 tree map 里 key是有序的,扫描一遍,累加 num_meetings,最大值就是同时进行的meeting数量

    // 时间:   0  5   10  15  20  30
    // event: +1  +1  -1  +1  -1  -1
    // 累计   1   2   1   2   1   0

    int minMeetingRooms(vector<vector<int>>& xs) {
        int n = xs.size();
        if(n<=1) return n;

        map<int, int> m;

        for(auto& x : xs) {
            m[x[0]] ++;
            m[x[1]] --;
        }

        int res = 0, acc = 0;
        for(auto& kv : m) {
            acc += kv.second;
            res = max(res, acc);
        }
        return res;
    }



utlw
7个月前

题目描述

这题居然是medium。。。


算法1

贪心 $O(n)$

C++ 代码

    // 核心思想是 最后需要的 #slot 等于 #tasks + #idles

    // 找出 most frequent task,假设是A,个数是count(A)
    // 有可能 most frequent task不止一个,假如有k个,比如k=2,有2个task,AB,都出现count(A)次
    // 将AB依次排开,构成count(A)-1个区间

    // 例如,tasks = 3 A, 3 B, 2 C, 1 D
    // A B _ _ A B _ _ A B

    // 下面计算要填充多少个idle tasks。

    // 每个区间有多少个empty slots? most frequent task,除了A外,都要放在区间里,
    // 所以每个区间还剩 n-(k-1) 个empty slots

    // 这些区间一共有多少个empty slots?有 #empty_slots = ( count(A)-1 ) *(n-k+1)

    // 除了出现次数最多的tasks,A和B,还有多少要处理的tasks? #available_tasks = #tasks - k*count(A)
    // 需要填充多少个idle task?#idles = #empty_slots - #available_tasks

    // 如果 #available_tasks > #empty_slots,则不需要填充 idle task
    // 所以,#idles = max(0, #empty_slots - #available_tasks)

    // 一共需要多少slots? #task + #idles

    // 例外情况,如果 most frequent task 大于n+1个, k>n+1 -> n-k+1<0,则每个区间没有empty slots,但此时每个区间可扩充到容纳不同的task,而不需要填idle task,一共需要#tasks个slots

    int leastInterval(vector<char>& tasks, int n) {
        // 找出most frequent tasks
        vector<int> count(26, 0);
        for(auto c : tasks) count[c-'A'] ++;

        int mx = 0, n_mx = 0;
        for(int i=0; i<26; i++) {
            if(count[i] > mx) {
                mx = count[i];
                n_mx = 1;
            } else if(count[i] == mx) {
                n_mx ++;
            }
        }

        int n_empty_slots = (mx-1) * (n - (n_mx-1) );
        if(n_empty_slots < 0) return tasks.size();

        int n_available_tasks = tasks.size() - mx * n_mx;
        int n_idles = max(0, n_empty_slots - n_available_tasks);

        return tasks.size() + n_idles;
    }

算法2

heap, $O(n)$

C++ 代码

    // 用hashtable求每个task的数量
    // 用max-heap存task,每一轮,从heap中取n+1个task来处理
    // 每个task处理后计数减1,如果不为0,该轮结束后,再放入heap中
    // 当heap中task个数小于n时,用idle填充
    // 对最后一轮,只需要加实际处理的task数量

    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> hash;
        for(auto c : tasks) hash[c]++;

        // max heap
        using TPair = pair<char, int>; // task, count
        priority_queue<TPair, vector<TPair>,
            function<bool(const TPair& a, const TPair& b)>>
                pq( [](const TPair& a, const TPair& b) {
                    return b.second > a.second;
                });

        for(auto& kv : hash) pq.push(kv);

        int res = 0;
        while(pq.size()) {
            int sz = pq.size();
            // 有多于 n+1个task要处理
            if(sz >= n+1) {
                vector<TPair> tmp; //暂存处理后仍不为0的task
                for(int i=0; i<n+1; i++) {
                    auto task = pq.top();
                    pq.pop();
                    task.second--;
                    if(task.second != 0) tmp.push_back(task);
                }
                // 将未处理完的task放回heap
                for(auto& task : tmp) pq.push(task);

                res += (n+1);

            } else { // 少于n+1个task要处理,要用idle填充
                vector<TPair> tmp;
                for(int i=0; i<sz; i++) {
                    auto task = pq.top();
                    pq.pop();
                    task.second--;
                    if(task.second != 0) tmp.push_back(task);
                }
                // 如果tmp.size==0,所有task都已经处理完了,不需要填idle
                // 否则,要填idle到n+1
                if(tmp.size()==0) {
                    res += sz; // while(pq.size()) 将结束
                }
                else {
                    for(auto& task: tmp) pq.push(task);
                    res += (n+1);
                }                    
            }
        }
        return res;
    }



utlw
7个月前

题目描述

算法1

DFS $O(n!)$

C++ 代码

    // row[i]=j:第i行的queen放在第j列
    // col[j]= true/false:第j列已经放置了queen

    vector<int> row;
    vector<bool> col;
    int res;

    // 在第i行放queen,枚举所有列
    void dfs(int i, int n) {
        if(i==n) { res++; return; }

        for(int j=0; j<n; j++) {
            // 检查列和对角线上是否已经有queen
            if(col[j] || diag(i, j, n)) continue;

            row[i] = j;
            col[j] = true;
            dfs(i+1, n);
            col[j] = false;
            row[i] = -1;
        }
    }

    // 如果queen放在(i,j),与已有的queen,在对角线上是否有冲突
    bool diag(int i, int j, int n) {
        for(int r=0; r<n; r++){
            if(row[r]==-1) continue;
            if(abs(r-i) == abs(row[r]-j) ) return true;
        }
        return false;
    }

    int totalNQueens(int n) {
        row = vector<int>(n, -1);
        col = vector<bool>(n, false);

        dfs(0, n);
        return res;
    }


活动打卡代码 LeetCode 52. N-Queens II

utlw
7个月前
    // row[i]=j:第i行的queen放在第j列
    // col[j]= true/false:第j列已经放置了queen

    vector<int> row;
    vector<bool> col;
    int res;

    // 在第i行放queen,枚举所有列
    void dfs(int i, int n) {
        if(i==n) { res++; return; }

        for(int j=0; j<n; j++) {
            // 检查列和对角线上是否已经有queen
            if(col[j] || diag(i, j, n)) continue;

            row[i] = j;
            col[j] = true;
            dfs(i+1, n);
            col[j] = false;
            row[i] = -1;
        }
    }

    // 如果queen放在(i,j),与已有的queen,在对角线上是否有冲突
    bool diag(int i, int j, int n) {
        for(int r=0; r<n; r++){
            if(row[r]==-1) continue;
            if(abs(r-i) == abs(row[r]-j) ) return true;
        }
        return false;
    }

    int totalNQueens(int n) {
        row = vector<int>(n, -1);
        col = vector<bool>(n, false);

        dfs(0, n);
        return res;
    }


活动打卡代码 LeetCode 79. Word Search

utlw
7个月前
- DFS,要用visited数组记录每个cell是否visit过,需要:
    visited[i][j] = true;
    dfs( ...);
    visited = false;
    Bad case: board=[['a', 'a']], word="aaa"
- 将recurrence fail的条件放在一起,写起来简洁
- O(nm * 3^k), k为路径平均长度。nm个起点,假设每个search的path平均长度是k,k里的每个char面临3个选择,最坏情况3个都可选,则一个path的选择数为3^k。

    bool dfs(const string& word, int idx, 
             const vector<vector<char>>& board, int i, int j,
             vector<vector<bool>> &visited) {
        if(idx==word.size()) { return true; }

        if(i<0 || i>=board.size() || j<0 || j>=board[0].size() 
           || visited[i][j] || word[idx]!=board[i][j]) {
            return false;
        }

        visited[i][j] = true;        
        bool res = 
            dfs(word, idx+1, board, i-1, j, visited) 
            || dfs(word, idx+1, board, i+1, j, visited) 
            || dfs(word, idx+1, board, i, j-1, visited)
            || dfs(word, idx+1, board, i, j+1, visited);
        visited[i][j] = false;
        return res;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(); 
        if(m==0) return false;
        int n = board[0].size();
        if(n==0) return false;

        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(dfs(word, 0, board, i, j, visited)) { return true; }
            }
        }

        return false;
    }




utlw
7个月前
    vector<string> m {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    vector<string> res;
    string tmp;

    void dfs(const string& digits, int idx) {
        if(idx == digits.size()) {
            res.push_back(tmp);
            return;
        }

        for(auto c : m[digits[idx]-'2'] ) {
            tmp.push_back(c);
            dfs(digits, idx+1);
            tmp.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return res;

        dfs(digits, 0);
        return res;
    }



utlw
7个月前
求组合,用start记录可选数的动态范围。
    vector<int> tmp;
    vector<vector<int>> res;

    // 在[start..9]中选k个数,使其和为n,
    void dfs(int k, int n, int start) {
        if(k==0) { // 已经选了k个数
            if(n==0) { res.push_back(tmp); }
            return;
        }
        if(n<0) return; // 可选都是整数,n为负数时,无解。

        for(int i=start; i<=9; i++) {
            tmp.push_back(i);
            dfs(k-1, n-i, i+1);
            tmp.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        if(k<=0 || n<=0) return res;

        dfs(k, n, 1);
        return res;
    }


活动打卡代码 LeetCode 90. Subsets II

utlw
7个月前
    vector<vector<int>> res;
    vector<int> tmp;

    void dfs(const vector<int>& x, int start) {
        res.push_back(tmp);

        for(int i=start; i<x.size(); i++) {
            if(i!=start && x[i]==x[i-1]) continue;

            tmp.push_back(x[i]);
            dfs(x, i+1);
            tmp.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // res = vector<vector<int>>();

        sort(begin(nums), end(nums));
        dfs(nums, 0);
        return res;
    }


活动打卡代码 LeetCode 78. Subsets

utlw
7个月前
解法:2种解法,BFS和DFS
1. BFS
初始解只有一个空集,依次take x, appned到已有的集合中,所有产生过的集合皆为解。
[] -- x=1 --> [1] -- x=2 --> [2], [1,2] -- x=3 --> [3], [1,3], [2,3], [1,2,3]

    // 因为q中的每个元素都要原样再入队,所以可以用vector,取巧
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n==0) return res;

        res.push_back(vector<int>()); // 空集
        for(auto x : nums) {
            int cur_set_size = res.size();
            for(int i=0; i<cur_set_size; i++){
                vector<int> tmp = res[i];
                tmp.push_back(x);
                res.push_back(tmp);
            }
        }
        return res;
    }

    // 标准 BFS
    vector<vector<int>> subsets(vector<int>& nums) {
        int n= nums.size();
        vector<vector<int>> res;
        if(n==0) return res;

        queue<vector<int>> q;
        q.push({});

        for(int x : nums) {
            int sz = q.size();
            while(sz--) {
                auto t = q.front(); q.pop(); // 要pop,然后再push回去,不能不pop
                q.push(t); // 再push到队尾
                t.push_back(x);
                q.push(t);
            }
        }

        while(q.size()) {
            res.push_back(q.front());
            q.pop();
        }
        return res;
    }

2. DFS
考虑dfs的搜索树,树中的每个节点都要收集。
            []
    [1]     [2]     [3]
[1,2] [1,3] [2,3]
[1,2,3]

    vector<vector<int>> res;
    int n;

    void dfs(const vector<int>& nums, int start, vector<int>& tmp) {
        res.push_back(tmp);
        if(tmp.size() == nums.size()) return;

        for(int i=start; i<n; i++) {
            tmp.push_back(nums[i]);
            dfs(nums, i+1, tmp);
            tmp.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        n= nums.size();
        if(n==0) return res;

        vector<int> tmp;
        dfs(nums, 0, tmp);
        return res;
    }


活动打卡代码 LeetCode 47. Permutations II

utlw
7个月前
    // 处理重复解的问题
    // 将 nums 排序,当对每个输出位置枚举数字时,对于相同的数字只取第一个。

    vector<vector<int>> res;
    vector<int> visited;
    vector<int> t;

    void dfs(const vector<int>& x){
        if(t.size() == x.size()) {
            res.push_back(t);
            return;
        }

        for(int i=0; i<x.size(); i++) {
            if(visited[i]) continue;

            // 如果i不是第一个数字,且与前面数字相等,且前面数字对当前位置可选,跳过i
            if(i!=0 && x[i]==x[i-1] && !visited[i-1]) continue;

            visited[i] = true;
            t.push_back(x[i]);
            dfs(x);
            t.pop_back();
            visited[i] = false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        res = vector<vector<int>>();
        int n = nums.size();
        if(n == 0) return res;

        visited = vector<int>(n, false);

        sort(begin(nums), end(nums));

        dfs(nums);
        return res;
    }