发表更新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);
 */

优化

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

LeetCode-位运算

位运算常见技巧

  • 位运算计算
a op b res
x xor 0x00 x
x xor 0xff ~x
x xor x 0
x and 0x00 0
x and 0xff x
x and x x
x or 0x00 x
x or 0xff 0xff
x or x x
x and x-1 去掉最低位
x and -x 得到最低位
  • 状态压缩

用二进制位表示状态

268. 丢失的数字

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

LeetCode-27

[Medium] 29. 两数相除

分析

  • 只能用加减法，最朴素的方法是循环相减/加，直到小于0/大于0，计算加/减的次数
  • 这样算法是o(n)，考虑到i+=i或者i<<=1相当于i*=2,i>>=1相当于i/=2
  • 只考虑divisor, divident都大于0的情况，先找到整数p，使得 divisor∗2p<=dividentdivisor*2^p <= divident，divident−=divisor∗2p,ratio+=2pdivident-=divisor*2^p, ratio+=2^p若divident为0，则商为ratio，否则重复上面的过程，直到divident为0。
  • 考虑divisor, divident到可能正，可能负，而负数的范围大于正数，直接将所有整数变成负数，并记录符号
  • 注意取相反数的时候要用位运算~x+1

代码

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
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend < divisor && dividend > 0) return 0;
        if(dividend > divisor && dividend < 0) return 0;
        if((dividend == INT_MIN) && (divisor == -1)) return INT_MAX;
        if((dividend == INT_MIN) && (divisor == 1)) return INT_MIN;
        if(dividend == divisor) return 1;
        if(dividend < 0 && divisor > 0 && dividend == ~divisor+1) return -1;
        if(dividend > 0 && divisor < 0 && ~dividend+1 == divisor) return -1;
        bool sign = false;
        if(dividend < 0) {
            sign = !sign;
        } else {
            dividend = ~dividend+1;
        }
        if(divisor < 0) {
            sign = !sign;
        } else {
            divisor = ~divisor+1;
        }
        int res = 0;
        int i = -1;
        while(dividend < divisor && divisor >= (INT_MIN >> 1)) {
            divisor += divisor;
            i+=i;
        }
        while(true) {
            while(dividend > divisor) {
                if(i == -1) {
                    return sign ? (res) : (~res+1);
                }
                divisor >>= 1;
                i>>=1;
            }
            dividend -= divisor;
            res+=i;
        }
    }
};

275. H 指数 II

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

LeetCode-26

[Medium] 1110. 删点成林

分析

  1. 使用什么样的数据结构
    1. 直接用数组
    2. 用孩子兄弟表示法
  2. 使用什么样的遍历方法？

代码

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 Solution {
public:
    vector<TreeNode*> forest;
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        if(root){
            if(del(root, to_delete)) {
                push_forest(root);
            } else {
                forest.push_back(root);
            }
        }
        return forest;
    }
    bool del(TreeNode* root, vector<int>& to_delete) {
        if(root->left && del(root->left, to_delete)) {
            push_forest(root->left);
            root->left = nullptr;
        }
        if(root->right && del(root->right, to_delete)) {
            push_forest(root->right);
            root->right = nullptr;
        }
        for(int d : to_delete) {
            if(d == root->val) {
                return true;
            }
        }
        return false;
    }
    void push_forest(TreeNode *root) {
        if(root->left) {
            forest.push_back(root->left);
        }
        if(root->right) {
            forest.push_back(root->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
×