Derolol Blog

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 收缩右值

Posted 2024-06-24Updated 2024-06-24

平衡二叉搜索树（BST）