题单介绍：

精选 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();}}}
};