713. 乘积小于K的子数组（2020-03-02 medium）
题意：给定一个正整数数组 nums。找出该数组内乘积小于 k 的连续的子数组的个数。
题解：双指针。 ptr1，ptr2。 nums[ptr1,ptr2] 为以ptr1开始的最长的乘积小于 k 的连续的子数组，那么以ptr1开头的符合条件的数组个数是ptr2-ptr1+1。之后ptr1++，由于ptr2没有回退操作，所以时间复杂O(N).
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int ans = 0; int ptr1 = 0,ptr2 = 0; int len = nums.size();
int key = nums[ptr1];
while(ptr1<len){
int flag = 0;
while(key<k&&ptr2+1<len&&ptr1<len){
flag = 1;
ptr2++;
key *= nums[ptr2];
}
if(key>=k) {
key /= nums[ptr2];
ptr2--;
}
key /= nums[ptr1];
ans += ptr2 - ptr1 + 1;
ptr1++;
if(ptr1 == len) break;
if(ptr2<ptr1) {
ptr2 = ptr1;
key = nums[ptr1];
}
}
return ans;
}
};
面试题32 - I. 从上到下打印二叉树（2020-03-02 medium）
题意：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
题解：层序遍历，队列实现
729. 我的日程安排表 I（2020-03-02 medium）
题意：插入 1e3 (start, end) 线段，没有覆盖返回true，有冲突返回false
题解：维护一个pair<int,int>数组存线段，插入一个就O(nlogn) sort一下，判断是否合法就O(N)暴力搞,注意边界情况
1140. 石子游戏 II（2020-03-04 medium）
题意：A和B玩取石子游戏。有一排石子，每堆有p[i]个， 每轮可以拿 x ∈ [1, 2*M]个石子，M初始值是1，每轮M取max(M, x)。双方都采取最优策略，问先手最多可以拿多少石子。
题解：定义 dp[i][m] 的含义为 先手在 [i: ] 的石子堆里且M值为m的情况下能够拿到的最多的石子，那么题目所求即为 dp[1][1] 的值。因为双方都采取最优策略，那么这个方程的定义照样适用于后手。先手拿最多，那么后手就要拿最少。状态转移就是枚举先手所有可采取的策略。那么可以得到转移方程 dp[i][m] = sum(p[i: ]) - min(dp[i+x][max(m,x)]) 。时间复杂度O(N3)。
class Solution {
public:
int stoneGameII(vector<int>& piles) {
int dp[106][106];
memset(dp,0,sizeof(dp));
int len = piles.size(), sum[110];sum[0]=0;
for(int i = 1;i<=len; i++)
sum[i] = sum[i-1] + piles[i-1];
for(int i=len;i>=1;i--)
for(int j=len;j>=1;j--)
for(int x=1;x<=min(2*j,len-i+1);x++)
dp[i][j] = max(dp[i][j], sum[len]-sum[i]+piles[i-1]-dp[i+x][max(j,x)]);
return dp[1][1];
}
};
826. 安排工作以达到最大收益（2020-04-29 medium）
题意：difficulty[i]，profit[i]分别表示表示工作的难度和收益，worker[i]是工人的能力，只能完成难度小于等于worker[i]的工作。每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。问最大收益。
题解：贪心，双指针。最大收益，优先处理收益大的工作，相同收益则先处理难度大的工作。
1081. 不同字符的最小子序列（2020-04-30 medium）
题意：返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
题解：贪心。要想字典序最小，那么字典序小的字符优先排在前面，如果前面已经有了字典序大的字符，考虑其在之后还有没有重复字符出现，假如有，就可以先删除。类似于栈。
面试题 17.14. 最小K个数（2020-05-04 medium）
题意：找出数组中最小的k个数。数组1e5。
题解：直接排序。
754. 到达终点数字（2020-05-05 medium）
题意：求 使用连续的1~n的数字，自由使用+，-符号，使得sum==target时，n的最小值
题解：target的正负没有关系，统一视为正数。先假设1~n全加，直接得到target就返回。如果大于target就针对差值进行分类讨论。当差值是偶数时，把差值/2的那个偶数符号由加改为减就可以直接得到target，所以要把差值凑成偶数。偶数的话直接返回。奇数的话n+1是奇数就再走一步，偶数的话就再走两步。
98. 验证二叉搜索树 （2020-05-05 medium）
题意：给一个二叉树，判断是否是二叉搜索树
题解：首先注意NULL节点的判断。如果左右子树都满足的情况下，根节点的值要大于左子树里的最大值，也就是左子树中最右节点。根节点的值要小于右子树里的最小值，也就是右子树中最左节点。
983. 最低票价（2020-05-06 medium）
题意：你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。火车票有三种不同的销售方式：costs[0] 美元为期一天，costs[1] 美元为期七天，costs[2] 美元为期三十天。通行证允许数天无限制的旅行。返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
题解：dp。设dp[i]为到第i天的最小花费。先初始化为无穷大，dp[0]=0。从1遍历到365，假如这天不旅行，那么最小花费和前一日相同。假如这天要旅行，那么有两种策略：1.这天要买票，那么有三种买法。2.这天不买票，有两种转移过来的方式，每种方式要遍历具体是哪一天买的票。注意数组边界。
class Solution { public: int mincostTickets(vector<int>& days, vector<int>& costs) { int dp[366]; for(int i=0; i<366; i++) dp[i]=1000000; dp[0]=0; int pos = 0; for(int i=1;i<=365;i++){ if(i != days[pos]){ dp[i] = dp[i-1]; continue; } dp[i] = min(dp[i], dp[i-1] + costs[0]); dp[i] = min(dp[i], dp[i-1] + costs[1]); dp[i] = min(dp[i], dp[i-1] + costs[2]); for(int j=i-30+1;j<i;j++){ if(j>0) dp[i] = min(dp[i], dp[j-1] + costs[2]); } for(int j=i-7+1;j<i;j++){ if(j>0) dp[i] = min(dp[i], dp[j-1] + costs[1]); } pos++; if(pos >= days.size()) break; } return dp[days[days.size()-1]]; } };
572. 另一个树的子树（2020-05-07 easy）
题意：给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
题解：dfs枚举所有s的节点，并判断以该节点为根的子树是否和t完全相同。注意判NULL。
221. 最大正方形（2020-05-08 medium）
题意：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
题解：dp。设dp[i][j]是以matrix[i][j]为右下角的最大正方形的边长。那么dp[i][j] += min(min(dp[i-1][j-1], dp[i][j-1]), min(dp[i-1][j-1], dp[i-1][j])) + 1.时间复杂度（N*M）。
69. x 的平方根（2020-05-09 easy）
题意：计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
题解：二分查找k，使得k满足 x/k==k或者 （x/k>k && x/(k+1)<(k+1))。
236. 二叉树的最近公共祖先（2020-05-10 medium）
题意：LCA模板题
题解：LCA。dfs遍历整棵树，当前根节点的值和p或q相等时，直接返回根节点。当左/右子树含有p或q且右/左子树都不含有p、q时，返回左/右子树。当左/右子树都含有p或q时，返回当前根节点。注意叶子节点NULL的判断。
50. Pow(x, n)（2020-05-11 medium）
题意：实现 pow(x, n) ，即计算 x 的 n 次幂函数。
题解：快速幂。当n是奇数时 pow(x, n) = x*pow(x*x, n/2) ，n是偶数时 pow(x, n) = pow(x*x, n/2)。注意判断n是1，-1,0以及n是负数时pow(x, n) = 1/pow(x, -n)。