发表更新LeetCode / 多线程17 分钟读完 (大约2513个字)

LeetCode-多线程-1

1115. 交替打印 FooBar

信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class FooBar {
    private int n;
    private Semaphore fooSem, barSem;
    public FooBar(int n) {
        this.n = n;
        fooSem = new Semaphore(1);
        barSem = new Semaphore(0);
    }

    public void foo(Runnable printFoo) throws InterruptedException {

        for (int i = 0; i < n; i++) {

            // printFoo.run() outputs "foo". Do not change or remove this line.
            fooSem.acquire();
            printFoo.run();
            barSem.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {

        for (int i = 0; i < n; i++) {

            // printBar.run() outputs "bar". Do not change or remove this line.
            barSem.acquire();
            printBar.run();
            fooSem.release();
        }
    }
}

条件变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class FooBar {
    private int n;
    Lock lock;
    Condition condition;
    boolean fooOrBar = true;
    public FooBar(int n) {
        this.n = n;
        lock = new ReentrantLock();
        condition = lock.newCondition();
    }

    public void foo(Runnable printFoo) throws InterruptedException {

        for (int i = 0; i < n; i++) {

            // printFoo.run() outputs "foo". Do not change or remove this line.
            lock.lock();
            while(!fooOrBar) {
                condition.await();
            }
            printFoo.run();
            fooOrBar = !fooOrBar;
            condition.signalAll();
            lock.unlock();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {

        for (int i = 0; i < n; i++) {

            // printBar.run() outputs "bar". Do not change or remove this line.
            lock.lock();
            while(fooOrBar) {
                condition.await();
            }
            printBar.run();
            fooOrBar = !fooOrBar;
            condition.signalAll();
            lock.unlock();
        }
    }
}

1116. 打印零与奇偶数

阅读更多
发表更新LeetCode / 数据库9 分钟读完 (大约1322个字)

LeetCode-数据库-2

584. 寻找用户推荐人

1
2
3
4
5
6
7
8
SELECT
    name
FROM
    Customer
WHERE
    referee_id <> 2
    OR
    referee_id IS NULL

577. 员工奖金

1
2
3
4
5
6
7
8
9
10
11
SELECT
    E.name,
    B.bonus
FROM
    Employee E
    LEFT JOIN Bonus B
    ON E.empId = B.empId
WHERE
    B.bonus < 1000
    OR
    B.bonus IS NULL

570. 至少有5名直接下属的经理

1
2
3
4
5
6
7
8
9
10
SELECT 
    E1.name
FROM 
    Employee E1 
    LEFT JOIN Employee E2
    ON E1.id = E2.managerId
GROUP BY
    E1.id
HAVING
    COUNT(E1.id) >= 5
阅读更多
发表更新LeetCode / 算法4 分钟读完 (大约626个字)

LeetCode-33

232. 用栈实现队列

  • 两个栈倒腾一下可以得到队列
  • 一个栈用来入队
  • 一个栈用来出队，如果出队栈空，将另一个栈全倒腾过来，如果不空，就出栈一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyQueue {
    stack<int> inStk, outStk;
public:
    MyQueue() {

    }
    
    void push(int x) {
        inStk.push(x);
    }
    
    int pop() {
        if(outStk.empty()) {
            while(!inStk.empty()) {
                outStk.push(inStk.top());
                inStk.pop();
            }
        }
        int top = outStk.top();
        outStk.pop();
        return top;
    }
    
    int peek() {
        if(outStk.empty()) {
            while(!inStk.empty()) {
                outStk.push(inStk.top());
                inStk.pop();
            }
        }
        int top = outStk.top();
        return top;
    }
    
    bool empty() {
        return inStk.empty() && outStk.empty();
    }
};

1976. 到达目的地的方案数

dijkstra

  • 数据范围很大，枚举所有路径是不现实的
  • 由于我们只要求两点之间的最短路，所以用dijkstra就好
  • 应该是dp吧，每次选取最小路径的点更新邻接节点
    • 若使其路径变小了，则到达该节点最短路径数等于根节点到达当前节点的最短路径数
    • 若路径长度等于该节点，则到达该节点最短路径数在原来数量上加上根节点到达当前节点的最短路径数
阅读更多
发表更新LeetCode / 算法29 分钟读完 (大约4301个字)

LeetCode-32

1185. 一周中的第几天

  • Tomohiko Sakamoto算法
  • 虽然是简单题也有很多知识点呢
  • 解释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        // array with leading number of days values
        static int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
        
        // if month is less than 3 reduce year by 1
        if (month < 3)
            year -= 1;
        
        return vector<string>{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}
        [((year + year / 4 - year / 100 + year / 400 + t[month - 1] + day) % 7)];
    }
};

2583. 二叉树中的第 K 大层和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        if(!root) return -1;
        priority_queue<long long> level_sum_q;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()) {
            int q_size = q.size();
            long long level_sum = 0;
            while(q_size--) {
                TreeNode *node =  q.front();
                q.pop();
                level_sum += node->val;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            level_sum_q.push(level_sum);
        }
        while(--k && !level_sum_q.empty()) {
            level_sum_q.pop();
        }
        return !level_sum_q.empty() ? level_sum_q.top() : -1;
    }
};
  • 用ranges获取第k大的数
阅读更多
发表更新LeetCode / 算法29 分钟读完 (大约4316个字)

LeetCode-31

1276. 不浪费原料的汉堡制作方案

  • 解方程，判断是非负整数解就行
  • 用位运算，能快一点
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        int jumbo = 0, small = 0;
        // jumbo + small == cheeseSlices;
        // 4*jumbo + 2*small == tomatoSlices;
        small = ((cheeseSlices << 2) - tomatoSlices);
        jumbo = (tomatoSlices - (cheeseSlices << 1));
        if(jumbo >= 0 && small >= 0 && (small & 1) == 0 && (jumbo & 1) == 0)
            return {jumbo >> 1, small >> 1};
        return {};
    }
};

1185. 一周中的第几天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        int week = 0;
        for(int i = 1971; i < year; i++) {
            week = (week + 31 * 7 + 30 * 4 + 28) % 7;
            if((i % 100 != 0 && i % 4 == 0) || i % 400 == 0) {
                week = (week + 1) % 7;
            }
        }
        for(int i = 1; i < month; i++) {
            if(i == 2) {
                week = (week + 28) % 7;
                if((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) {
                    week = (week + 1) % 7;
                }
            } else if(i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 12) {
                week = (week + 31) % 7;
            } else {
                week = (week + 30) % 7;
            }
        }
        week = (week + day + 4) % 7;
        return vector<string>{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}[week];
    }
};
阅读更多
发表更新LeetCode / 算法27 分钟读完 (大约4100个字)

LeetCode-单调栈

739. 每日温度

  • 简单，通过单调栈，弹出栈中小于当前元素的元素，可以找到弹出元素的第一个大于其的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> monoStk;
        int len = temperatures.size();
        vector<int> res(len);
        for(int i = 0; i < len; i++) {
            while(!monoStk.empty() && temperatures[monoStk.top()] < temperatures[i]) {
                int top = monoStk.top();
                res[top] = i - top;
                monoStk.pop();
            }
            monoStk.push(i);
        }
        return res;
    }
};

42. 接雨水

AC1

思路

阅读更多
发表更新LeetCode / 算法16 分钟读完 (大约2471个字)

LeetCode-30

162. 寻找峰值

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int index = 0;
        int n = nums.size();
        while(index < n-1 && nums[index] < nums[index+1]) index++;
        return index;
    }
};

1901. 寻找峰值 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int x = 0, y = 0;
        int m = mat.size(), n = mat[0].size();
        bool findPoint = true;
        while(findPoint) {
            findPoint = false;
            if(x + 1 < m && mat[x+1][y] > mat[x][y]) {
                findPoint = true;
                x++;
            } else if(x - 1 >= 0 && mat[x-1][y] > mat[x][y]) {
                findPoint = true;
                x--;
            } else if(y + 1 < n && mat[x][y+1] > mat[x][y]) {
                findPoint = true;
                y++;
            } else if(y - 1 >= 0 && mat[x][y-1] > mat[x][y]) {
                findPoint = true;
                y--;
            }

        }
        return {x, y};
    }
};

贪心，从某一点开始，如果上下左右存在比当前点大的数，移动过去，直到无法移动

746. 使用最小花费爬楼梯

阅读更多
发表更新LeetCode / 算法16 分钟读完 (大约2418个字)

LeetCode-29

2661. 找出叠涂元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> cnt_row(m, 0), cnt_col(n, 0);
        vector<int> index(m*n+1);
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                index[mat[i][j]] = i*n+j;
            }
        }
        int len = arr.size();
        for(int i = 0; i < len; i++) {
            int x = index[arr[i]]/n, y = index[arr[i]]%n;
            cnt_row[x]++;
            cnt_col[y]++;
            if(cnt_row[x] == n || cnt_col[y] == m) return i;
        }
        return -1;
    }
};

1657. 确定两个字符串是否接近

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    inline bool logicXor(bool a, bool b) {
        return (a && !b) || (b && !a);
    }
    bool closeStrings(string word1, string word2) {
        vector<int> word1_cnt(26, 0), word2_cnt(26, 0);
        for(char c : word1) {
            word1_cnt[c - 'a']++;
        }
        for(char c : word2) {
            word2_cnt[c - 'a']++;
        }
        for(int i = 0; i < 26; i++) {
            if(logicXor(word1_cnt[i] == 0, word2_cnt[i] == 0)) return false;
        }
        sort(word1_cnt.begin(), word1_cnt.end());
        sort(word2_cnt.begin(), word2_cnt.end());
        for(int i = 0; i < 26; i++) {
            if(word1_cnt[i] != word2_cnt[i]) return false;
        }
        return true;
    }
};

2336. 无限集中的最小数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class SmallestInfiniteSet {
    vector<pair<unsigned, unsigned>> s;
public:
    SmallestInfiniteSet() {
        s.emplace_back(1, -1);
    }
    
    int popSmallest() {
        int smallest = s[0].first++;
        if(s[0].first == s[0].second) {
            s.erase(s.begin());
        }
        return smallest;
    }
    
    void addBack(int num) {
        // cout << "add\n";
        int n = s.size();
        int i = 0;
        while(i < n && s[i].second <= num) i++;
        if(i >= n) {
            s.emplace_back(num, num + 1);
            return;
        }
        if(s[i].first <= num) {
            return;
        } else {
            if(s[i].first-1 == num) {
                s[i].first--;
                // 检查前面的，拼接
                if(i-1 >= 0 && s[i-1].second == s[i].first) {
                    s[i-1].second = s[i].second;
                    s.erase(s.begin() + i);
                }
            } else {
                if(i - 1 >= 0 && s[i-1].second == num) {
                    s[i-1].second++;
                } else {
                    s.insert(s.begin() + i, make_pair(num, num+1));
                }
            }
        }
    }
};

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */
阅读更多
发表更新LeetCode / 算法17 分钟读完 (大约2620个字)

LeetCode-28

[Hard] 715. Range 模块

思路

  • 二分查找
  • 一开始想的是用[left, right)和全部区间进行比较查找，但是这样比较困难，在处理边界合并情况时会变成O(N)
  • 用left和right分别在所有ranges中查找
    • 对于query，如果两个下标相同，则true，否则false
    • 对于add，查找left-1和right的下标，然后其间的所有ranges删除，插入新range
    • 对于remove，查找left和right-1的下标，然后根据下标把之间的删除，插入剩余的区间

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class RangeModule {
    vector<pair<int, int>> ranges;
    int len = 0;
    int ops = 0;
    static constexpr bool debug = false;
    void printRanges() {
        int size = ranges.size();
        cout << "len = " << len << ", size = " << size << "\n";
        for(int i = 0; i < size; i++) {
            cout << "[" << ranges[i].first << ", " << ranges[i].second << "]\n";
        }
    }
    bool inRange(int n, int index) {
        return ranges[index].first <= n && n < ranges[index].second;
    }
    bool bigger(int n, int index) {
        return n >= ranges[index].second;
    }
    bool smaller(int n, int index) {
        return ranges[index].first > n;
    }
    int searchRanges(int n) {
        int l = 0, r = len;
        while(l < r) {
            int mid = (r - l) / 2 + l;
            if(inRange(n, mid)) return mid;
            else if(bigger(n, mid)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
public:
    RangeModule() {

    }
    
    void addRange(int left, int right) {
        // if(debug) {
        //     ops++;
        //     cout << "[" << ops << "], " << "addRange" << "[" << left << ", " << right << "]" << "\n";
        // }
        _addRange(left, right);
        // if(debug) printRanges();
    }
    void _addRange(int left, int right) {
        int leftIndex = searchRanges(left-1);
        int rightIndex = searchRanges(right); // add时考虑合并相邻的集合，所以把边界放宽
        // if(leftIndex > 0 && ranges[leftIndex - 1].second == left) {
        //     leftIndex--;
        // }
        // if(rightIndex < len - 1 && ranges[rightIndex + 1].first == )
        // if(debug) cout << "leftIndex = " << leftIndex << ",  rightIndex = " << rightIndex << "\n";
        if(leftIndex == rightIndex && leftIndex == len) {
        } else {
            left = min(left, ranges[leftIndex].first);
            if(rightIndex < len) {
                if(inRange(right, rightIndex)) {
                    right = max(right, ranges[rightIndex].second);
                    rightIndex++;
                }
            }
            ranges.erase(ranges.begin() + leftIndex, ranges.begin() + rightIndex);
            len -= rightIndex - leftIndex;
        }
        ranges.insert(ranges.begin() + leftIndex, make_pair(left, right));
        len++;
    }
    
    bool queryRange(int left, int right) {
        // if(debug) {
        //     ops++;
        //     cout << "[" << ops << "], " << "queryRange" << "[" << left << ", " << right << "]" << "\n";
        // }
        bool ret = _queryRange(left, right);
        // if(debug) cout << (ret ? "ok" : "not found") << "\n";
        // if(debug) printRanges();
        return ret;
    }
    bool _queryRange(int left, int right) {
        int leftIndex = searchRanges(left);
        int rightIndex = searchRanges(right-1);
        if(leftIndex >= len || rightIndex >= len) return false;
        return leftIndex == rightIndex && inRange(left, leftIndex) && inRange(right-1, rightIndex);
    }
    void removeRange(int left, int right) {
        // if(debug) {
        //     ops++;
        //     cout << "[" << ops << "], " << "removeRange" << "[" << left << ", " << right << "]" << "\n";
        // }
        _removeRange(left, right);
        // if(debug) printRanges();
    }
    void _removeRange(int left, int right) {
        int leftIndex = searchRanges(left);
        int rightIndex = searchRanges(right-1);
        // if(debug) cout << "leftIndex = " << leftIndex << ",  rightIndex = " << rightIndex << "\n";
        if(leftIndex == rightIndex && leftIndex == len) {
            return;
        } else {
            int leftLeft = left, rightRight = right;
            if(inRange(left, leftIndex)) {
                leftLeft = ranges[leftIndex].first;
            }
            if(rightIndex < len) {
                if(inRange(right-1, rightIndex)) {
                    rightRight = ranges[rightIndex].second;
                    rightIndex++;
                }
            }
            // if(debug) cout << "leftIndex = " << leftIndex << ",  rightIndex = " << rightIndex << "\n";
            // if(debug) cout << "leftLeft = " << leftLeft << ",  rightRight = " << rightRight << "\n";
            ranges.erase(ranges.begin() + leftIndex, ranges.begin() + rightIndex);
            len -= rightIndex - leftIndex;
            // if(debug) cout << "len = " << len << "\n";
            if(rightRight > right) {
                len++;
                ranges.insert(ranges.begin() + leftIndex, make_pair(right, rightRight));
                // if(debug) cout << "add right len = " << len << "\n";
            }
            if(leftLeft < left) {
                len++;
                ranges.insert(ranges.begin() + leftIndex, make_pair(leftLeft, left));
                // if(debug) cout << "add left len = " << len << "\n";
            }
        }
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */

优化

阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码5
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×