【LeetCode】HOT 100（7）

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

题单介绍：

题目：42. 接雨水 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：46. 全排列 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

题目：42. 接雨水 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    int trap(vector<int>& height) {

    }  
};

解题思路：

这道题又是动态规划的题目，但是也可以不用动态规划做，

这里我用的是单调栈：

遍历数组，如果遇到小的值就入栈，如果遇到比栈顶大的值就开始算雨水面积，

让栈内的有效数据保持单调递减的状态，

这个思路的核心就是找出右边更高的柱子，开始结算雨水，

然后以这个柱子为新的左柱子，继续往右边找相对更高的柱子。

代码入下：

代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for(int i = 0; i < height.size(); i++) { //遍历
            while(!st.empty() && height[st.top()] < height[i]) { //遇到较大的值
                int top = st.top();
                st.pop();
                if(st.empty()) break; //如果是栈内只有一个值的情况，就跳过（没法接雨水）
                int l = st.top();
                int r = i;
                int h = min(height[r], height[l]) - height[top]; //矮柱子的高度 - 中间的高度 
                ans += (r - l - 1) * h;
            }
            st.push(i);
        }
        return ans;
    }  
};

过过过过啦！！！！

题目：46. 全排列 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {

    }
};

解题思路：

这道题其实就是经典的搜索题目，

或者说是搜索的入门题目，

学搜索必刷题型，全排列，

我之前在蓝桥杯刷题的时候也有写深度优先搜索相关的博客，

感兴趣的可以去看一下，

这里我就不废话，直接上代码：

代码：

class Solution {
public:
    vector<int> v;
    vector<vector<int>> vv;
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return vv;
    }
private:
    void dfs(vector<int>& nums) {
        if(v.size() == nums.size()) {
            vv.push_back(v);
            return;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != 99) { //这边是巧妙的记录已经使用过的值，因为排列中只允许一个数出现一次
                int used = nums[i];

                v.push_back(nums[i]);
                nums[i] = 99;
                dfs(nums);
                nums[i] = used;
                v.pop_back();
            }
        }
    }
};