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

[LeetCode C++实现]225. Implement Stack using Queues

225. Implement Stack using Queues这里使用队列实现stack,使用c++ stl中的deque.

class MyStack {

public:

/** Initialize your data structure here. */

MyStack() {

}

/** Push element x onto stack. */

void push(int x) {

stack.push_back(x);

}

/** Removes the element on top of the stack and returns that element. */......

[LeetCode C++实现]704. Binary Search

经典面试题二分查找,当年校招面试经常遇到,先用最简单最直接的方法AC。

class Solution {

public:

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

int start = 0,end = nums.size() - 1;

while(start <= end)

{

int mid = (start + end) / 2;

if(nums[mid] == target)

return mid;

else if(nums[mid] < target)

start = mid + 1;

else

en......

[LeetCode C++实现]233. Number of Digit One

233. Number of Digit One

老规矩,上来先暴力破解,一眼看上去非常简单,1分钟写出答案,最后Time Limit Exceeded.

class Solution {

public:

int countDigitOne(int n) {

int res = 0;

for(int i = 1;i <= n;i++)

{

res += cal_digit(i);

}

return res;

}

private:

int cal_digit(int n){

int cnt = 0;

while(n)

{

if(n % 10 == 1)

cnt++;

n /= 10......

[LeetCode C++实现]69. Sqrt(x)

69. Sqrt(x)

暴力破解求解:使用最直观的解法,性能也符合预期,非常之慢。

class Solution {

public:

int mySqrt(int x) {

int ans = 0;

for(int i = 1;i <= x;i++)

{

//avoid overflow

if(i > x / i)

return ans;

ans = i;

}

return ans;

}

};

Runtime: 68 ms, faster than 5.95% of C++ online submissions for Sqrt(x).

Memory Usage: 6......