[LeetCode C++实现]1361. Validate Binary Tree Nodes
这道题我个人认为非常经典，在评论区看了大神的代码，自己5分钟就手写了一遍，问题的难点从来都不是代码，而是在思路。
当我拿到这个题目时想分析有哪几种异常情况，分析发现根据这些异常情况判断比较复杂，很难较全面的判断。
比如
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: fal......
这道题我个人认为非常经典，在评论区看了大神的代码，自己5分钟就手写了一遍，问题的难点从来都不是代码，而是在思路。
当我拿到这个题目时想分析有哪几种异常情况，分析发现根据这些异常情况判断比较复杂，很难较全面的判断。
比如
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: fal......
数组中元素[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......
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......
最开始想法比较简单，统计当前数字，如果比前一个数字小，那么记录一次，如果出现次数大于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;
}
};
存在无法处理的用例......
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......
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......
最开始的想法代码实现（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......
这道题同样使用贪心算法，和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++......
代码实现起来比较简单，但是贪心的思想理解起来没那么容易，详细的介绍可以阅读贪心算法之区间调度问题
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int ans=0;
if(intervals.size()==0) return 0;
sort(intervals.begin(),intervals.end(),comp);
vector<int> x = intervals[0];
for(int i = 1;i <......
这里使用了贪心策略，由于对两个vector排序，优先满足需要饼干较少的小孩，需要注意的是下标i就是最终满足的小孩数目，无需再使用新变量。
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int i = 0,j = 0;
while(i < g.size() && j < s.size())
{
if(g[......