日常开发笔记总结(八)

下列程序编译是否会报错:

// directive_1.c

#include <stdio.h>

#ifndef MIN

#define MIN(x, y) ((x) > (y) ? (y) : (x))

#endif /**/x

int main()

{

printf("min val = %d\n", MIN(100, -1));

return 0;

}

讲道理程序endif后面有个多余的x应该会编译失败,可是程序编译仅仅有个告警,运行正常。

[root c++]#gcc -g -Wall -o gcc gcc.c

gcc.c:6:12: warn......

[LeetCode C++实现]111. Minimum Depth of Binary Tree

非递归解法可以套用广度优先算法解法,在循环中添加判断条件,如果节点左右子树均为NULL,则最小深度就在该层。

/**

* 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)......

[LeetCode C++实现]104. Maximum Depth of Binary Tree

C语言实现:

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

int maxDepth(struct TreeNode* root)

{

if(NULL == root)

{

return 0;

}

int llen = maxDepth(root->left) + 1;

int rlen = maxDepth(root->right) ......

[LeetCode C++实现]102. Binary Tree Level Order Traversal

二叉树广度优先算法(水平搜索),使用队列保存各节点,初步完成能编译通过代码:

/**

* 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++实现]122. Best Time to Buy and Sell Stock II

贪心算法:

贪心法又称贪心算法、贪婪算法,在对问题求解时,总是做出在当前看来最好的选择。

简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。

贪心算法与动态规划的不同在于它对每个子问题的解决方案做的选择不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

一个例子说明贪心算法与动态规划的不同:

假如有面值20 10 5 1的四种纸币,那么要兑换36块钱,最少需要几张纸币?

36 -20 = 16

16 - 10 = 6

6 - 5 = 1

1 - 1 = 0

所以一共需要4张纸币......

C++指针两例

分析程序给出下面两段代码的输出结果,并给出具体原因(运行环境基于gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)):

代码一

#include <iostream>

using namespace std;

void foo(const void* ptr)

{

std::cout << "In foo(void*)" << std::endl;

}

void foo(bool b)

{

std::cout << "In foo(bool)" << std::endl;

}

......

[LeetCode C++实现]236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

和235题类似,236的答案可以放在235里AC,但235是二叉搜索树,可以利用该特性优化代码实现。

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

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

* };

*/

class Soluti......

[LeetCode C++实现]235. Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

先用最ugly 最随心所欲的代码AC,基本思想是生成两个路径,然后找到最后一个相同的值,然后在BST中查找到这个值返回结点地址,最直观,最容易理解,代码相对啰嗦。

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

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

[LeetCode C++实现]64. Minimum Path Sum

64. Minimum Path Sum

这道是非常非常典型的动态规划问题,以前读书的时候记得老师讲的时候死活听不懂,现在工作了几年后,维基百科看了一些介绍,手写一遍AC通过。

class Solution {

public:

int minPathSum(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

vector<vector<int>> sum(m,vector<int>(n,grid[0][0]));

for......

[LeetCode C++实现]98. Validate Binary Search Tree

98. Validate Binary Search Tree

验证给定二叉树是否是二叉搜索树,个人认为属于面试题中的高频题目。

首先我们用最直观 最暴力 最ugly的代码先AC(中序遍历,验证vector中是否有重复元素 是否是升序):

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullpt......