Day4力扣打卡

打卡记录

同积元组（哈希表 + 排列组合）

链接

思路：用哈希表将数组中出现的两不同数乘积依次记录，将出现两次以上的乘积组通过排列组合计算总情况个数。

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        unordered_map<int, int> hash;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                hash[nums[i] * nums[j]]++;
        for (auto& e : hash) {
            if (e.second > 1) ans += e.second * (e.second - 1) / 2;
        }
        return ans * 8;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

接雨水（单调栈）

链接

思路：横向计算填坑的面积，遍历数组时当前元素小于栈顶依次入栈，如果大于当前元素开始计算需要填补坑位的面积。（需记录底部高度）

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stack;
        for (int i = 0; i < height.size(); ++i) {
            while (!stack.empty() && height[stack.top()] <= height[i]) {
                int bottom = stack.top();
                stack.pop();
                if (stack.empty()) break;
                int h = min(height[stack.top()], height[i]) - height[bottom];
                ans += h * (i - stack.top() - 1);
            }
            stack.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18