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

结果

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

LeetCode-25

[hard] 1377. T 秒后青蛙的位置

题目分析

题目强调为一颗无向树，每次访问未访问过的节点。也就是说，每秒若有子节点，则跳到子节点，否则呆在原地不动。

也就是根据题目构造一棵根节点为1的树，并按照层次遍历该树即可。但是题目输入的边并不一定以1为根节点。

代码

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

LeetCode-24

1616. 分割两个字符串得到回文串

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
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int len = a.length();
        if(len == 1) return true;
        bool flaga = true, flagb = true;
        int i = 0;
        for(; i < len; i++) {
            if(a[i] == b[len-1-i]) {
            } else {
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(b[j] != b[len-1-j]) {
                flagb = false;
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(a[j] != a[len-1-j]) {
                flaga = false;
                break;
            }
        }
        if(flaga || flagb) return true;
        flaga = flagb = true;
        for(i = 0; i < len; i++) {
            if(a[len-1-i] == b[i]) {
            } else {
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(a[j] != a[len-1-j]) {
                flaga = false;
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(b[j] != b[len-1-j]) {
                flagb = false;
                break;
            }
        }
        return flaga || flagb;
    }
};

ab两个字符串在同一个位置分隔开，若 $ pre_a + suf_b $ 或 $ pre_b + suf_a $ 是回文串，则返回true，否则返回false
这个规则相当于ab截取相同且任意长的前缀并交换，看交换后是否存在回文
我的思路是先比较a的第i位与b的倒数第i位是否想等，找到第一次不相等的位置i，此时可以从第i位分割，判断b的剩余部分是否是回文，或者从len-i-1处分割，判断a的剩余部分是否是回文
若都不是，再比较b的第i位与a的倒数i位，找到第一个不满足的i，再比较a，b的剩余部分

优化行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int len = a.length();
        int paliA = len/2-1, paliB = len/2;
        while(paliA > 0 && a[paliA] == a[len-1-paliA]) paliA--;
        while(paliB > 0 && b[paliB] == b[len-1-paliB]) paliB--;
        int i, j;
        for(i = 0; i < len/2; i++) {
            if(a[i] != b[len-1-i]) {
                break;
            }
        }
        
        for(j = 0; j < len/2; j++) {
            if(b[j] != a[len-1-j]) {
                break;
            }
        }
        return min(paliA, paliB) < max(i, j);
    }
};
阅读更多
发表更新LeetCode / 算法12 分钟读完 (大约1759个字)

LeetCode-23

1144. 递减元素使数组呈锯齿状

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
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int odd2less, even2less;
        odd2less = even2less = 0;
        int n = nums.size();
        if(n <= 1) return 0;
        for(int i = 1; i < n - 1; i++) {
            if(i%2 == 0) {
                if(nums[i] >= min(nums[i-1], nums[i+1])) {
                    even2less += nums[i] - min(nums[i-1], nums[i+1]) + 1;
                }
            } else {
                if(nums[i] >= min(nums[i-1], nums[i+1])) {
                    odd2less += nums[i] - min(nums[i-1], nums[i+1]) + 1;
                }
            }
        }
        if(nums[0] >= nums[1]) {
            even2less += nums[0] - nums[1] + 1;
        }
        if(nums[n-1] >= nums[n-2]) {
            if((n-1)%2 == 0) {
                even2less += nums[n-1] - nums[n-2] + 1;
            } else {
                odd2less += nums[n-1] - nums[n-2] + 1;
            }
        }
        return min(even2less, odd2less);

    }
};

遍历所有奇数，使其小于两端，记录操作数1
遍历所有偶数，使其小于两端，记录操作数2
返回最小值

优化代码行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int op[2] = {0}, n = nums.size();
        if(n <= 1) return 0;
        for(int i = 1; i < n - 1; i++) {
            if(nums[i] >= min(nums[i-1], nums[i+1]))
                op[i&1] += nums[i] - min(nums[i-1], nums[i+1]) + 1;
        }
        if(nums[0] >= nums[1]) {
            op[0] += nums[0] - nums[1] + 1;
        }
        if(nums[n-1] >= nums[n-2]) {
            op[(n-1)&1] += nums[n-1] - nums[n-2] + 1;
        } 
        return min(op[0], op[1]);
    }
};

2325. 解密消息

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

LeetCode-22

2347. 最好的扑克手牌

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:
    string bestHand(vector<int>& ranks, vector<char>& suits) {
        vector<int> rank_count(13, 0), suits_count(4, 0);
        for(int i = 0; i < 5; i++) {
            rank_count[ranks[i]-1]++;
            suits_count[suits[i] - 'a']++;
        }
        int count = 0;
        for(int i = 0; i < 4; i++) {
            count = max(count, suits_count[i]);
        }
        if(count == 5) return "Flush";
        count = 0;
        for(int i = 0; i < 13; i++) {
            count = max(count, rank_count[i]);
        }
        if(count >= 3) {
            return "Three of a Kind";
        } else if (count == 2) {
            return "Pair";
        }
        return "High Card";
    }
};

1604. 警告一小时内使用相同员工卡大于等于三次的人

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
class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        map<string, vector<int>> hour_count;
        int len = keyName.size();
        for(int i = 0; i < len; i++) {
            int h = (keyTime[i][0]-'0')*10 + keyTime[i][1] - '0', m = (keyTime[i][3] - '0') * 10 + keyTime[i][4] - '0';
            hour_count[keyName[i]].push_back(h*60+m);
        }
        vector<string> warning_list;
        for(auto ite = hour_count.begin(); ite != hour_count.end(); ite++) {
            bool warn = false;
            sort(ite->second.begin(), ite->second.end());
            int len = ite->second.size();
            for(int i = 0; i < len-2; i++) {
                if(ite->second[i+2] - ite->second[i] <= 60) {
                    warn = true;
                    break;
                }
            }
            if(warn) {
                warning_list.push_back(ite->first);
            }
        }
        return warning_list;
    }
};
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
class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        map<string, priority_queue<int>> hour_count;
        int len = keyName.size();
        for(int i = 0; i < len; i++) {
            int h = (keyTime[i][0]-'0')*10 + keyTime[i][1] - '0', m = (keyTime[i][3] - '0') * 10 + keyTime[i][4] - '0';
            hour_count[keyName[i]].push(h*60+m);
        }
        vector<string> warning_list;
        for(auto ite = hour_count.begin(); ite != hour_count.end(); ite++) {
            int len = ite->second.size();
            if(len <= 2) continue;
            int a, b, c;
            a = ite->second.top();
            ite->second.pop();
            b = ite->second.top();
            ite->second.pop();
            c = ite->second.top();
            ite->second.pop();
            bool warn = a - c <= 60;
            while(!warn && !ite->second.empty()) {
                a = b;
                b = c;
                c = ite->second.top();
                ite->second.pop();
                warn = a - c <= 60;
            }
            if(warn) {
                warning_list.push_back(ite->first);
            }
        }
        return warning_list;
    }
};

2331. 计算布尔二叉树的值

阅读更多
关注我

链接

分类

最新文章

归档

标签

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
×