[LeetCode C++实现]42. Trapping Rain Water
大名鼎鼎的一道题，看讨论区居然有5 6种解法，令人尴尬的是我一种都没AC，看了大神的解题思路，自己较轻松的完成了代码。
暴力破解
暴力破解方法是后续所有解法的基础，如果理解不了暴力破解解法，那么后续所有解法将无法理解。
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: Th......
52coder
52coder[LeetCode C++实现]1. Two Sum
鼎鼎大名的第一道题，最直观的n平方复杂度解法：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0;i < nums.size();i++)
{
for(int j = i+1;j < nums.size();j++)
{
if(nums[i] + nums[j] == target)
return {i,j};
}
}
return {-1,-1};
}
};
优化后的解法：
class Soluti......
[LeetCode C++实现]1361. Validate Binary Tree Nodes
这道题我个人认为非常经典，在评论区看了大神的代码，自己5分钟就手写了一遍，问题的难点从来都不是代码，而是在思路。
当我拿到这个题目时想分析有哪几种异常情况，分析发现根据这些异常情况判断比较复杂，很难较全面的判断。
比如
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: fal......
[LeetCode C++实现]540. Single Element in a Sorted Array
数组中元素[1,1,2,3,3,4,4,8,8]，只有一个元素出现一次，其余出现两次，这里题目要求使用时间复杂度O(logn) 空间复杂度O(1),这里显而易见的方法是使用O(n) O(1)
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int res = 0;
for(int i = 0;i < nums.size();i++)
res ^= nums[i];
return res;
}
};
运行效率:
Runtime: 8 ms, faster tha......
[LeetCode C++实现]744. Find Smallest Letter Greater Than Target
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int l = 0, r = letters.size() - 1;
while(l <= r )
{
int mid = l + (r -l)/2;
if(letters[mid] <= target)
l = mid + 1;
else
r = mid - 1;
}
return letters[l % letters.size()];
}
};
手动实现了upper_bound......
[LeetCode C++实现]665. Non-decreasing Array
最开始想法比较简单，统计当前数字，如果比前一个数字小，那么记录一次，如果出现次数大于1那么返回false.
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int size = nums.size(),cnt = 0;
for(int i = 1;i < size;i++)
{
if(nums[i] < nums[i-1])
{
cnt++;
if(cnt > 1) return false;
}
}
return true;
}
};
存在无法处理的用例......
[LeetCode C++实现]605. Can Place Flowers
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int size = flowerbed.size();
for(int i = 0;i < size;i++)
{
if(flowerbed[i] == 1) continue;
//需要特殊处理第一个和最后一个
int prev = (i == 0) ? 0:flowerbed[i-1];
int next = (i == size - 1) ?0 :flowerbed[i+1];
if(prev + n......
[LeetCode C++实现]406. Queue Reconstruction by Height
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),comp);
vector<vector<int>> res;
for(auto person:people)
res.insert(res.begin() + person[1],person);
return res;
}
private:
static boo......
[LeetCode C++实现]56. Merge Intervals
最开始的想法代码实现（WA):
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),comp);
vector<vector<int>> res;
int size = intervals.size();
if(size == 1)
return vector<vector<int>>{{in......
[LeetCode C++实现]452. Minimum Number of Arrows to Burst Balloons
这道题同样使用贪心算法，和435是同一类型问题，这里需要求解不相交区间个数。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),comp);
int size = points.size(),ans = 1;
if(size <= 0) return 0;
vector<int> x = points[0];
for(int i = 1;i < size;i++......