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......
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......
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. */......
经典面试题二分查找，当年校招面试经常遇到，先用最简单最直接的方法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......
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......
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......
非常有意思的一道题目，读研的时候当家教，在一个小学奥数辅导班上见到过这个题，先介绍阶乘的概念，然后问结果中有多少个0，很多年过去了，再看这道题感觉很有缘分。
class Solution {
public:
int trailingZeroes(int n) {
int cnt = 0;
while(n) cnt += n/5,n /= 5;
return cnt;
}
};
结果中有0，实际是判断5的个数，如果n > 25,实际上还要判断包含多少个25，因为25中包含两个5，原来加过一个，还需要再加一次，如果n >125，那么还要再加第三次，依次类推。
2021......
204.Count Primes
这么一道求素数个数的简单题目，首先尝试最简单的暴力破解法：
class Solution {
public:
int countPrimes(int n) {
int cnt = 0;
for(int i = 2;i < n;i++)
{
if(isPrime(i))
cnt++;
}
return cnt;
}
private:
bool isPrime(int n) {
for(int i = 2;i <= n/2;i++)
{
if(n % i == 0)
return false;
}
return true;
}
};
执......
326.Power of Three
while循环解法
class Solution {
public:
bool isPowerOfThree(int n) {
while(n > 1)
{
if(n % 3 != 0)
return false;
n /= 3;
}
return (n == 1) ? true:false;
}
};
循环解法更优解法：
class Solution {
public:
bool isPowerOfThree(int n) {
if(n < 1)
return false;
while(n % 3 == 0)
{
n......
15.3Sum
3sum一道非常经典的题目，第一次做，以前只做了2Sum，老规矩先上暴力破解解法：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(),nums.end());
set<vector<int>> result;
vector<vector<int>> res;
for(int i = 0;i < n ......