[LeetCode C++实现]415. Add Strings

首先使用最直观 最ugly的代码AC,根据失败的case,AC的代码如下:

class Solution {

public:

string addStrings(string num1, string num2) {

int m = num1.size(),n = num2.size();

int carry = 0;

string res;

while(m > 0 && n > 0)

{

int num = num1[m-1]-'0'+num2[n-1]-'0'+carry;

carry = 0;

if(num >= 10)

{

carry = 1;......

[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......

[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......