Derolol Blog

Posted 2024-07-17Updated 2024-07-17algorithm

leetcode274 H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数是指他（她）至少发表了 h 篇论文，并且至少有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数是其中最大的那个。

题解

int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int h = 0, i = citations.size() - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }

给定数组求组合

leetcode39 组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路

题目要求得到所有组合，而不是值。所以考虑通过递归和回溯的方式得到不用的组合组成元素和数量相同的两个组合为同一种组合，所以在递归的时候需要传递当前的候选值范围由于有目标值的要求，可以通过排序剪枝不可能的组合

class Solution {
private:
    vector<vector<int>> ret;
public:

    void getSum(vector<int>& candidates, int target, int start, int sum, vector<int>& host) {
        // 若满足条件则记录
        if (sum == target) {
            ret.push_back(host);
            return;
        }
        // 从取值起始点遍历候选值
        for (int i = start, num = candidates.size(); i < num; i ++) {
            // 如果加上最小值都超过目标条件，那么可以直接结束遍历
            if (sum + candidates[i] > target) break;
            // 加入当前值到组合中
            host.push_back(candidates[i]);
            // 通过罗列自身及之后的候选值构建满足条件的组合
            getSum(candidates, target, i, sum + candidates[i], host);
            // 回溯组合
            host.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> v;
        getSum(candidates, target, 0, 0, v);
        return ret;
    }
};

Posted 2024-07-17Updated 2024-07-17algorithm

贪心算法题目集合

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

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

题解

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

Posted 2024-07-16Updated 2024-07-16algorithm

树算法题目集合

leetcode199 二叉树的右视图

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

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

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

题解

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

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 题解

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 树的中序遍历

中序遍历

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

/**
 * 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，计算左右子树和根节点的和，更新当前最大值注意递归的返回值需包含根节点，已构成完整路径

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 ，求出该树的节点个数。

比较有趣的思路：参考

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

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);
        }
    }
};

Posted 2024-07-12Updated 2024-07-12algorithm

栈算法题目集合

leetcode71 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格绝对路径（以 '/' 开头），请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。请注意，返回的规范路径必须遵循下述格式：始终以斜杠 '/' 开头。两个目录名之间必须只有一个斜杠 '/' 。最后一个目录名（如果存在）不能以 '/' 结尾。此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。返回简化后得到的规范路径。

题解

参考题解

leetcode150 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意：有效的算符为 '+'、'-'、'*' 和 '/' 。每个操作数（运算对象）都可以是一个整数或者另一个表达式。两个整数之间的除法总是向零截断。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位整数表示。

题解

从左向右遍历，用栈存储数字，遇到符号出栈两个数字

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        long result = 0;
        stack<int> nums;
        for (string token : tokens) {
            if (token != "+" && token != "-" && token != "*" && token != "/") {
                nums.push(stoi(token));
                continue;
            }
            int n2 = nums.top();nums.pop();
            int n1 = nums.top();nums.pop();
            if (token == "+") {
                nums.push(n1 + n2);
            }
            else if (token == "-") {
                nums.push(n1 - n2);
            }
            else if (token == "*") {
                nums.push(n1 * n2);
            }
            else if (token == "/") {
                nums.push(n1 / n2);
            }
        }
        return nums.top();
    }
};

leetcode84 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

单调栈获取两端更小值的索引

刚接触到题目以为与最大盛水量是相同解法，这题的不同之处在于面积取决于区间内的最小值，而不是两端的最小值由此，对于柱高上升的区间，起始柱总能取其高计算面积，若新加入的柱高小于栈顶高，则表示已到达栈顶对应开区间的右端点，将栈顶弹出，新的栈顶表示开区间的左端点

int largestRectangleArea(vector<int>& heights) {
    int maxS = 0;
    // 方便计算开头与末尾的柱面积
    heights.insert(heights.begin(), 0);
    heights.emplace_back(0);
    int n = heights.size();
    // 单调栈
    stack<int> rise;
    rise.emplace(0);
    for (int i = 1; i < n; i ++) {
        // 触及右边界，出栈直到栈再次单调或为空
        while (! rise.empty() && heights[rise.top()] > heights[i]) {
            int h = heights[rise.top()]; rise.pop();
            int w = i - rise.top() - 1;
            maxS = max(maxS, h * w);
        }
        rise.emplace(i);
    }
    return maxS;
}

leetcode85 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

逐行求解最大矩形

int maximalRectangle(vector<vector<char>>& matrix) {
    int maxS = 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<int> heights(n + 2, 0);
    stack<int> rise;
    // 遍历每一行
    for (int i = 0; i < m; i ++) {
        rise.emplace(0);
        // 计算当前高度
        for (int j = 0; j < n + 1; j ++) {
            if (j < n) {
                // 若为0则高度置0
                if (matrix[i][j] - '0') heights[j + 1] += 1;
                // 若为1高度加1
                else heights[j + 1] = 0;
            }
            // 区间判断
            while (! rise.empty() && heights[rise.top()] > heights[j + 1]) {
                int h = heights[rise.top()]; rise.pop();
                int w = (j + 1) - rise.top() - 1;
                maxS = max(maxS, h * w);
            }
            rise.emplace(j + 1);
        }
        while (! rise.empty()) rise.pop();
    }
    return maxS;
}

leetcode739 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

单调递减栈

若当前温度比当前栈顶高，则必为最近一个高温，否则记录在栈中待找寻下一个高温

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ret(n, 0);
    stack<int> down;
    down.emplace(0);
    for (int i = 1; i < n; i ++) {
        while (! down.empty() && temperatures[down.top()] < temperatures[i]) {
            ret[down.top()] = i - down.top();
            down.pop();
        }
        down.emplace(i);
    }
    return ret;
}

Posted 2024-07-12Updated 2024-07-12algorithm

哈希表算法题目集合

leetcode380 O(1) 时间插入、删除和获取随机元素

实现 RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。 bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。 int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有相同的概率被返回。你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

题解

STL 关联式容器中： set 和 map 的底层数据结构为红黑树，因为 map 和 set 要求是自动排序的，红黑树能够实现这一功能，并且各个操作的时间复杂度都较低，而 unordered_set 和 unordered_map 的底层数据结构为哈希表，查找时间复杂度为常数级

class RandomizedSet {
public:
    vector<int> data;
    unordered_map<int, int> record;

    RandomizedSet() {

    }

    bool insert(int val) {
        if (record.contains(val)) {
            return false;
        }
        data.push_back(val);
        record[val] = data.size() - 1;
        return true;
    }

    bool remove(int val) {
        if (! record.contains(val)) {
            return false;
        }
        data[record[val]] = data[data.size() - 1];
        record[data[record[val]]] = record[val];
        data.pop_back();
        record.erase(val);
        return true;
    }

    int getRandom() {
        return data[rand() % data.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

leetcode128 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题解

unordered_set 去重
遍历找到各个连续子序列的头

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for (auto n : nums) num_set.insert(n);
        int max_len = 0;
        for (auto n : num_set) {
            if (!num_set.count(n - 1)) {
                int cur_num = n;
                while (num_set.count(cur_num + 1)) {
                    cur_num ++;
                }
                max_len = max(cur_num - n + 1, max_len);
            }
        }
        return max_len;
    }
};

Posted 2024-07-11Updated 2024-07-11algorithm

双指针算法题目集合

思路

指针从两端收缩

遍历解空间为上三角，参考解析

leetcode11 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器

题解

两端逼近，优先短边收缩

leetcode167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[] 和 numbers[] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [, ] 的形式返回这两个整数的下标和。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。

题解

两端逼近，< target 收缩左值，> target 收缩右值