Posted Updated algorithm

区间题目集合

leetcode 打气球

右端点排序，合并区间

美团种树

随着种树数量的增加，树总量单调递增，可以通过二分法查询种树量

美团流星

左端点和右端点分开排序，计算最大经过区间数量

Posted Updated algorithm

二分法算法题目集合

leetcode300 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

题解

常规做法是通过一维数组存储当前位置作为结尾的最大子序列长度。 而根据推理可知，若在从左向右遍历时，当前元素不能与已有元素构成更长的子序列，那么替换更小的元素将有更大的可能性构成更长子序列。

1
2
3
4
5
6
7
8
9
10
11
int lengthOfLIS(vector<int>& nums) {
    auto end = nums.begin();
    for (int x : nums) {
        auto it = lower_bound(nums.begin(), end, x);
        *it = x;
        if (it == end) {
            end ++;
        }
    }
    return end - nums.begin();
}

排序序列找区间或值

leetcode34 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

思路

  1. 直接定位，向两个方向找到区间边缘
  2. 定位左边界，再定位右边界

leetcode74 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵： 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

思路

  • 二分定位行
  • 二分定位元素
Posted Updated algorithm

堆题目集合

最小堆

排列组合 TopK 问题

优先队列 priority_queue

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
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int,vector<int>,less<int>> p1;     //默认大根堆
    p1.push(2); p1.push(1); p1.push(3);               //输出 3 2 1
    while(p1.empty()== false){
        cout<<p1.top()<<" ";
        p1.pop();
    }

    priority_queue<int,vector<int>,greater<int>> p2;  //小根堆
    p2.push(2); p2.push(1); p2.push(3);               //输出 1 2 3
    while(p2.empty()== false){
        cout<<p2.top()<<" ";
        p2.pop();
    }

    // 基本数据类型-pair-pair类型默认先比较第一个元素，第一个相等比较第二个
    priority_queue<pair<int, int> > a;
    a.push(pair<int,int>{1,2});
    a.push(pair<int,int>{1,3});
    a.push(pair<int,int>{2,5});
    while (a.empty()== false){
        cout<<a.top().first<<" "<< a.top().second<<endl;
        a.pop();
    }
    //输出:
    //2 5
    //1 3
    //1 2

    return 0;
}

多路归并

每次迭代有 N 个选择，将 N 个选择放入堆得到排序后的值

  • 题型
    • 一维
      • 根据题意队列初始化 1 个值
    • 二维
      • 根据题意队列按序初始化 1 个列表
      • 初始化左上角值，set 判断是否重复插入
  • 注意去重的问题

leetcode264 丑数 II（一维）

给你一个整数 n ，请你找出并返回第 n 个 丑数 。 丑数 就是质因子只包含 2、3 和 5 的正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int nthUglyNumber(int n) {
    long times_num[] = {2, 3, 5};
    set<long> record;
    priority_queue<long, vector<long>, greater<long>> q;
    q.push(1);
    int index = 1;
    while (index <= n) {
        int cur_num = q.top();
        if (index == n) return cur_num;
        q.pop();
        for (long t : times_num) {
            long new_num = cur_num * t;
            if (record.contains(new_num)) continue;
            q.push(new_num);
            record.insert(new_num);
        }
        index ++;
    }
    return 0;
}

leetcode373 查找和最小的 K 对数字（二维）

给定两个以 非递减顺序排列 的整数数组 和 , 以及一个整数 。 定义一对值 ，其中第一个元素来自 ，第二个元素来自 。 请找到和最小的 k 个数对 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {

    vector<vector<int>> result;
    int l1 = nums1.size(), l2 = nums2.size();

    auto cmp = [&](const auto& a, const auto& b) {
        return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
    for (int i = 0; i < l1; i ++) {
        q.push({i, 0});
    }

    while (result.size() < k) {
        auto [ia, ib] = q.top();
        result.push_back({nums1[ia], nums2[ib]});
        q.pop();
        if (ib + 1 < l2) q.push(pair<int, int>{ia, ib + 1});
    }

    return result;
}
Posted Updated algorithm

字符串题目集合

字符串输入流

  • 库 sstream
  • 类 stringstream

leetcode58 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

1
2
3
4
5
6
int lengthOfLastWord(string s) {
    stringstream ss(s);
    string word;
    while (ss >> word) ;
    return word.size();
}

KMP 算法

在匹配之前需要计算匹配字符串各个位置的最长重合前后缀。初始化第一个位置为 0，后缀末尾位置从 1 开始，若当前前缀的末尾与后缀末尾相同，则更新长度；否则根据当前前缀寻找新的重合前缀，这个阶段是最难理解的部分，如下图所示。

kmp

leetcode28 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int strStr(string haystack, string needle) {
    // next数组表示到该位置的字串的最大相同前后缀的长度
    vector<int> next(needle.size());
    int j = 0;
    next[0] = 0;
    for (int i = 1, len = needle.size(); i < len; i ++) {
        // 末尾不相同则查找以当前前缀的最大重复长度
        while (j && needle[i] != needle[j]) j = next[j - 1];
        // 末尾相同则记录长度
        if (needle[i] == needle[j]) j ++;
        next[i] = j;
    }
    // 通过回溯重合位置减少遍历次数
    for (int i = 0, j = 0, len = haystack.size(); i < len; i ++) {
        // 若当前位置不匹配则变换比对位置
        while (j && haystack[i] != needle[j]) j = next[j - 1];
        // 若比对成功则向后比对
        if (haystack[i] == needle[j]) j ++;
        // 判断是否已完成比对
        if (j == needle.size()) return i - needle.size() + 1;
    }
    return -1;
}

leetcode767 重构字符串

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

题解

参考题解

leetcode228 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出： "a->b" ，如果 a != b "a" ，如果 a == b

思路

参考leetcode 题解

  • to_string 方法快速将数字转换为字符串
  • 使用 i 和 j 表示区间的端点
  • 在遍历的过程中，若位置 j 与位置 j+1 的值相差 1，则向右拓展区间，从而找到完整区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        // Lambda 函数构建字符串
        auto f = [&](int i, int j) {
            return i == j ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[j]);
        };
        // i 在迭代时为上一个区间结尾 + 1
        for (int i = 0, j, n = nums.size(); i < n; i = j + 1) {
            j = i;
            // 若差为 1，右端点移动
            while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
                ++ j;
            }
            // 添加区间
            ans.emplace_back(f(i, j));
        }
        return ans;
    }
};

leetcode820 单词的压缩编码

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足： words.length == indices.length 助记字符串 s 以 '#' 字符结尾 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等 给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

Trie快速判断末尾重合字串

若字符串s1完全与字符串s2的末尾部分或整体重合，则字符串s1可作为同一部分助记字符串 因此，可以使用Trie构建字符串树 为了正确计算包含关系，需要优先按照字符串长度倒序排序字符串

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
class Solution {
private:
    // 使用长度为26的数组存储下一个字符
    struct Node {
        vector<Node*> next;
    };
public:
    int minimumLengthEncoding(vector<string>& words) {
        int n = words.size();
        // 初始化根节点
        Node* root = new Node();
        root->next.resize(26, nullptr);
        Node* p = nullptr;
        // 按字符串长度排序
        sort(words.begin(), words.end(), [&](const string& a, const string& b) {
            return a.size() > b.size();
        });
        int count = 0;
        // 遍历各个字符串
        for (int i = 0; i < n; i ++) {
            bool include = true;
            string& w = words[i];
            p = root;
            // 从字符串尾部开始遍历
            for (int j = w.size() - 1; j >= 0; j --) {
                int charIndex = w[j] - 'a';
                // 若为非空指针则表示已有该字符序列
                if (p->next[charIndex]) {
                    p = p->next[charIndex];
                }
                // 创建新的字符
                else {
                    include = false; // 标识为新字符串
                    Node* newNode = new Node();
                    newNode->next.resize(26, nullptr);
                    p->next[charIndex] = newNode;
                    p = newNode;
                }
            }
            // 若为新字符串则加上当前字符串长度以及"#"的长度
            if (! include) count += w.size() + 1;
        }
        return count;
    }
};
Posted Updated algorithm

链表题目集合

leetcode86 分隔链表

思路

  • 遍历链表，分两个链表存储

leetcode23 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。

多路归并选择节点

Posted Updated algorithm

滑动窗口题目集合

leetcode209 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的子数组[, , ..., , ] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

题解

确定左值，向右扩展直到满足 target，记录当前窗口大小，移动左值，重复上述动作，直到右值不能再拓展

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:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int left = 0;
        int right = 0;
        int sum = nums[0];
        int minLen = size + 1;
        while (left < size && right < size) {
            if (sum >= target) {
                minLen = min(minLen, right - left + 1);
                sum -= nums[left];
                left ++;
                continue;
            }
            if (right == size - 1) break;
            right ++;
            sum += nums[right];
        }
        if (minLen == size + 1) return 0;
        return minLen;
    }

};
Posted Updated algorithm

矩阵处理算法题目集合

leetcode48 旋转图像

思路

  • 1/4 矩阵旋转

leetcode289 生命游戏

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律： 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活； 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡； 如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

题解

leecode 题解

使用二进制的第二位存储修改后的状态。

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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int dx[] = {-1,  0,  1, -1, 1, -1, 0, 1};
        int dy[] = {-1, -1, -1,  0, 0,  1, 1, 1};

        for(int i = 0; i < board.size(); i++) {
            for(int j = 0 ; j < board[0].size(); j++) {
                int sum = 0;
                for(int k = 0; k < 8; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) {
                        sum += (board[nx][ny]&1); // 只累加最低位
                    }
                }
                if(board[i][j] == 1) {
                    if(sum == 2 || sum == 3) {
                        board[i][j] |= 2;  // 使用第二个bit标记是否存活
                    }
                } else {
                    if(sum == 3) {
                        board[i][j] |= 2; // 使用第二个bit标记是否存活
                    }
                }
            }
        }
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[i].size(); j++) {
                board[i][j] >>= 1; //右移一位，用第二bit覆盖第一个bit。
            }
        }
    }
};

矩阵哈希

leetcode36 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

题解

分别从行、列和九宫格统计数字出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isValidSudoku(vector<vector<char>>& board) {

    vector<vector<bool>> row(9, vector<bool>(9, false));
    vector<vector<bool>> col(9, vector<bool>(9, false));
    vector<vector<bool>> box(9, vector<bool>(9, false));

    for (int i = 0; i < 9; i ++) {
        for (int j = 0; j < 9; j ++) {
            if (board[i][j] == '.') continue;
            int b = i / 3 * 3 + j / 3;
            int no = board[i][j] - '0' - 1;
            if (row[i][no] || col[j][no] || box[b][no]) return false;
            row[i][no] = true;
            col[j][no] = true;
            box[b][no] = true;
        }
    }

    return true;
}

leetcode240 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

利用特性缩小检索范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int a = 0, b = 0;
    int i = m - 1, j = n - 1;
    while (i >= 0 && j >= 0) {
        if (matrix[i][j] < target) return false;
        while (b < n - 1 && matrix[i][b] < target) {
            b ++;
        }
        if (matrix[i][b] == target) return true;
        i --;
        while (a < m - 1 && matrix[a][j] < target) {
            a ++;
        }
        if (matrix[a][j] == target) return true;
        j --;
    }
    return false;
}

转换为二叉搜索树

参考题解

Posted Updated algorithm

数学推理算法题目集合

2024 360 秋招提前批 最大曼哈顿距离

给定一个包含若干个点的集合，求其中任意两点之间的最大/最小曼哈顿距离。

题解

由上述式子可得：

整理合并可得：

所以，问题转换为比较点和点的横纵坐标和与差。 在遍历各个点的时候分别计算横纵坐标的和与差，且分别排序。 将最大值减去最小值得到两种情况下的最大曼哈顿距离，然后再从中选择最大的曼哈顿距离作为最终答案。

1
2
3
4
5
6
7
8
9
vector<int> d1;
vector<int> d2;
for (int i = 0; i < points.size(); i ++)
    d1.push_back(points[i][0] - points[i][1])
    d2.push_back(points[i][0] + points[i][1])
sort(d1.begin(), d1.end())
sort(d2.begin(), d2.end())

cout << max(d1[d1.size() - 1] - d1[0], d2[d2.size() - 1] - d2[0]))

相似题型

1014. 最佳观光组合

leetcode172 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。 提示 

1
2
3
4
5
6
7
8
9
10
11
int trailingZeroes(int n) {
    int times = 0;
    for (int i = 5; i <= n; i += 5) {
        int count = i;
        while (count && count % 5 == 0) {
            times ++;
            count /= 5;
        }
    }
    return times;
}

leetcode201 数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

题解

相邻两个数相与，末尾的 0 将会被消除，通过移位找公共前缀得到区间相与结果

1
2
3
4
5
6
7
8
9
10
int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    // 找到公共前缀
    while (left < right) {
        left >>= 1;
        right >>= 1;
        ++shift;
    }
    return left << shift;
}

leetcode1823 找出游戏的获胜者

思路

leetcode29 两数相除

思路

  • 特殊情况处理
  • 除数左移位，与被除数比较

leetcode238 除自身以外数组的乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

题解

正反向前缀积，使用中间变量记录累积

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

leetcode69 x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

题解

官方题解

乘方拆解

leetcode50 Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，）。

题解

将拆解为

其中，式子可转换为

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
double myPow(double x, int n) {
    // 特殊情况
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n == -1) return 1 / x;

    bool flag = n < 0;
    long nn = n;
    if (flag) nn = -1 * nn;

    double temp = x;
    double res = 1;

    // 将 n 次累乘拆解为 logn 次
    while (nn > 1) {

        long times = 2;
        temp = x;

        while (true) {
            temp *= temp;
            if (times * 2 <= nn) times *= 2;
            else break;
        }

        nn -= times;
        res *= temp;

    }

    for (long i = 0; i < nn; i ++) res *= x;

    return flag ? 1 / res : res;
}

二进制位计数

leetcode137 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

题解

统计每个二进制位 1 的出现次数，若只出现一次的数在该为为 0，那么统计次数应为 3 的倍数，否则有余数

1
2
3
4
5
6
7
8
9
10
11
int singleNumber(vector<int>& nums) {
    int ret = 0;
    for (int i = 0; i < 32; i ++) {
        int count = 0;
        for (auto n : nums) {
            count += n >> i & 1;
        }
        if (count % 3) ret += 1 << i;
    }
    return ret;
}

另一种方法通过状态机的思想，用一个两位二进制数统计当前二进制位的状态，00 -> 01 -> 10 -> 00

1
2
3
4
5
6
7
8
9
10
11
12
13
int singleNumber(vector<int>& nums) {
    // n1 表示二进制的低位
    // n2 表示二进制的高位
    int n1 = 0, n2 = 0;
    for (auto n : nums) {
        // 若高位 n2 为 0，则低位 n1 只与当前值 n 有关；否则计数已满 3，低位直接置 0
        n1 = ~n2 & n1 ^ n;
        // 若低位 n1 为 0，则高位 n2 只与当前值 n 有关，若 n 为 1，则表示要进位，否则表示计数已满；若低位为 1，那么高位只能为 0
        n2 = ~n1 & n2 ^ n;
    }
    // 若计数满 3，低位应为 0，若计数除以 3 余 1，则低位应为 1，所以返回低位
    return n1;
}

leetcode169 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

排序后中值必包含多数元素

1
2
3
4
int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
}

摩尔投票法

参考题解推荐了这种方法，思考方向为若与当前假设的众数相同，则投赞成票 1，否则投否认票-1，当得票为 0 时，则继续进行假设，多数元素将获得更多投票将投票值稳定为正；另外，从代码上理解，多数元素总有更多数量的连续元素

1
2
3
4
5
6
7
8
int majorityElement(vector<int>& nums) {
    int x = 0, votes = 0;
    for (int num : nums){
        if (votes == 0) x = num;
        votes += num == x ? 1 : -1;
    }
    return x;
}

集合类题目

leetcode2306 公司命名

Posted Updated algorithm

贪心算法题目集合

leetcode452 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [, ] 表示水平直径在 和 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 , 且满足 ≤ x ≤ ，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。 给你一个数组 points ，返回引爆所有气球所必须射出的 最小弓箭数 。

题解

排序，记录最小右边界（箭所能移动的最远方向），若不在射程范围内，记录新的右边界，否则更新最小右边界

Posted Updated algorithm

树算法题目集合

leetcode199 二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

leetcode230 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

题解

root->left->val < root->val < root->right->val

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
int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    stack<TreeNode*> treeStack;
    treeStack.push(root);
    while (treeStack.size() > 0) {
        TreeNode* base = treeStack.top();
        if (base->left == nullptr) {
            count ++;
            treeStack.pop();
            if (count == k) {
                return base->val;
            }
            if (base->right != nullptr) {
                treeStack.push(base->right);
                continue;
            }
        }
        else {
            treeStack.push(base->left);
            base->left = nullptr;
            continue;
        }
    }
    return 0;
}

leetcode148 排序链表

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表

题解

归并排序链表，递归分治，子链表按序合并

树和算式

Leetcode 题解

各种表达式没有本质区别，他们其实是同一个语法树，只是遍历方式不同而得到的不同式子；是一个事物的一体多面，只不过是从不同角度观察罢了。

中缀表达式是其对应的语法树的中序遍历； 后缀表达式是其对应的语法树的后序遍历； 前缀表达式是其对应的语法树的前序遍历；

leetcode105 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

题解

前序遍历提供根节点，中序遍历提供子树结构

Leetcode 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++)
            dic[inorder[i]] = i;
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector<int> preorder;
    unordered_map<int, int> dic;
    TreeNode* recur(int root, int left, int right) {
        if (left > right) return nullptr;                        // 递归终止
        TreeNode* node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic[preorder[root]];                            // 划分根节点、左子树、右子树
        node->left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                            // 回溯返回根节点
    }
};

leetcode94 树的中序遍历

中序遍历

使用栈数据结构控制遍历节点顺序，类比递归调用的栈

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;
        stack<TreeNode*> tree;
        tree.push(root);
        while (! tree.empty()) {
            TreeNode* top = tree.top();
            if (top->left != nullptr) {
                tree.push(top->left);
                top->left = nullptr;
                continue;
            }
            ret.push_back(top->val);
            tree.pop();
            if (top->right != nullptr) {
                tree.push(top->right);
            }
        }
        return ret;
    }
};

通过递归重复根节点操作

leetcode124 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

思路

共有两种路径，一种是左右节点跨越根的环形路径，一种为父子节点的直线路径 在递归的过程中，若子树的值为负，对最大和无贡献，可置为 0，计算左右子树和根节点的和，更新当前最大值 注意递归的返回值需包含根节点，已构成完整路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    int maxSum = 0;
public:
    int getMax(TreeNode_ root) {
        if (! root) return 0;
        int left = max(0, getMax(root->left));
        int right = max(0, getMax(root->right));
        maxSum = max(maxSum, root->val + left + right);
        return root->val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        getMax(root);
        return maxSum;
    }

};

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。

leetcode222 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

比较有趣的思路：参考

比较左右子树高度，若相等则左子树必为满树，若不相等则右子树必为满树

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:

    // 计算子树高度
    int getHeight(TreeNode* root) {
        if (! root) return 0;
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }

    // 计算子树节点数
    int countNodes(TreeNode* root) {
        if (! root) return 0;
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        // 比较子树高度
        if (leftHeight == rightHeight) {
            // 递归计算子树节点数，累加完全树节点数
            return countNodes(root->right) + (1 << leftHeight);
        }
        else {
            return countNodes(root->left) + (1 << rightHeight);
        }
    }
};
Follow

Categories

Links

Tags

AI Agent1
CL1
CV6
CVPR20221
CVPR20233
Data Synthesis1
Data enhancement1
GAN1
Generative Model1
HPC1
Image Process2
LLM3
Multimodal1
NLP2
Prototype1
Python Lib1
Pytorch1
RAG1
Semantic Segmentation1
Transformer1
ZSL1
algorithm1
computer network1
data structure1
dataset1
deep learning1
high-performance computing1
interview2
language2
leetcode14
machine learning1
math1
prompt1
tree1
written test1
二分法1
企业1
动态规划1
区间1
区间合并1
双指针1
哈希表1
图1
堆1
多模态2
字符串1
扩散模型2
排序辅助1
操作系统1
数学推理1
文生图1
栈1
树1
正则匹配1
滑动窗口1
矩阵处理1
编译工具1
链表1
风格迁移1

Recents

p

×