[LeetCode C++实现]297. Serialize and Deserialize Binary Tree

自己写的代码状况百出,根据失败的用例反复修改,看起来非常的乱,看了评论区大神的解法,学习体会思路,这里有一个非常值得学习的点是deserialize参数是string &,而我们需要不断的修改这个参数,所以增加一个辅助函数mydeserialize,这样在不更改给定接口的情况下,可以满足我们的需求。

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x)......

[LeetCode C++实现]75. Sort Colors

由于使用整数0 1 2分别代表红色 白色 和蓝色,而且是按照红色 白色和蓝色顺序排列。

所以直接排序肯定是正确的。

class Solution {

public:

void sortColors(vector<int>& nums) {

sort(nums.begin(),nums.end());

}

};

运行效率:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sort Colors.

Memory Usage: 8.3 MB, less than 64.12% o......

[LeetCode C++实现]504. Base 7

给定整数,转换为7进制字符串,这里美中不足的是针对数字0需要特殊处理,递归条件里无法区分0这种情况。

class Solution {

public:

string convertToBase7(int num) {

if(num == 0) return "0";

string res;

if(num < 0)

{

res+='-';

num = -1 * num;

}

helper(res,num);

return res;

}

private:

void helper(string& res,int num) {

if(num == 0) return;

helper......

[LeetCode C++实现]437. Path Sum III

完全理解这道题的话,对递归应该来说理解比较深了,这道题目是递归中嵌套一个递归,dfs主要是求解和等于sum的数量,然后pathSum是根据新的结点,求解符合条件的个数。

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x),......

[LeetCode C++实现]279. Perfect Squares

这道题目看似平平无奇,AC的过程中遇到了不少坑。

首先我们按照最直观、最快速的解法来写代码:

class Solution {

public:

int numSquares(int n) {

int sum = 0;

int num = n;

int cnt = 0;

while(num > 0) {

while(n >= sum + num && is_squares(num))

{

sum += num;

cnt += 1;

if(sum == n) return cnt;

}

num--;

}

return cnt;

}

private:

bool i......

快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。归并排序和快速排序一样均采用了分治法。

C语言实现:

来自算法导论的单向扫描算法,从左往右去扫描直到倒数第二个元素,出现小于最右边的元素则将小的那个元素与i标识的下标的元素交换,单向扫描法存在着冗余的元素交换,比如此时数组已有序1,2,3,4,5,6,单向扫描前5个元素均小于最后的元素6,那么每......

[LeetCode C++实现]113. Path Sum II

与Path Sum不同的是这里需要记录每条符合条件的路径信息,最直观的代码:

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNo......

[LeetCode C++实现]112. Path Sum

首先使用最直观的解法,思路是递归从上向下,调用hasPathSum时targetSum减去当前结点值。当到达叶子结点时判断当前传入的targetSum是否和本结点相同。

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x),......

[LeetCode C++实现]470. Implement Rand10() Using Rand7()

使用提供的rand7实现rand10,要求随机数字出现的概率相同,这个问题如果反过来要求rand10实现rand7就比较简单了,每次调用rand10,如果返回的数据在1-7直接返回,否则使用rand10重新生成。

按照相同的思路,我们调用多次rand7,比如尝试构造rand7 + rand7,范围是2-14无法等概率求解,我们可以使用rand7 * rand7,范围是1-49,如果生成的范围在1-40,那么我们直接对10取余加一即可,如果在40-49这个范围那么重新生成。视频题解参考

// The rand7() API is already defined for you.

// i......

[LeetCode C++实现]33. Search in Rotated Sorted Array

以前总觉得二分查找简单,刷了一些题目后再也不觉得二分查找简单了,各种边界条件,简直要了老命,但对这道题而言,我们只要找到某半段有序数组即可,如果target恰好位于其中,那么问题就转换为普通的二分查找。下面是两种形式的写法:

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0,r = nums.size() - 1;

while(l <= r)

{

int mid = l + (r - l)/2;

if(nums[mid] == target) return......