346. Moving Average from Data Stream

题目描述

求一个滑动窗口内的平均值

276. Paint Fence

题目描述

有一排栅栏，现在有k的颜色。要求只能最多有两个连续的栅栏有相同得颜色，求总共可能有多少种上颜料的方式。

算法

在这题的DP中，主要存在了两种状态：

1. 下一个与上一个同样颜色
2. 下一个与上一不同颜色

但是这样想我们发现题目并不要解决，因为我们还要考虑上一个的前一个的颜色，如果为相同，那么必须为不同的颜色。因此我们的状态转移矩阵使用最后的两个颜色的相同或不同作为状态转移矩阵，same和differ

对于新来的栅栏，如果我们希望是same状态，那么只有一种情况，即上两个是differ而且与最后一个相同颜色，那么总的数量只能是differ。如果希望是differ状态，那么情况时(same + differ) * (k-1)

第一题 653. Two Sum IV - Input is a BST

题目描述

给定二叉搜索树BST与一个目标数target，判断BST中是否存在两个数之和等于target。

算法

两种方法：一种是利用HashSet进行查看；另一种将BST按sort的顺序取出后，利用two pointer进行遍历。

第一题 225. Implement Stack using Queues

题目描述

使用队列实现栈的下列操作：

push(x) – 将元素x压入栈.
pop() – 移除栈顶元素.
top() – 获得栈顶元素.
empty() – 返回栈是否为空.

注意：

你可以假设所有的操作都是有效的（例如，不会对空栈执行pop或者top操作）
取决于你使用的语言，queue可能没有被原生支持。你可以使用list或者deque（双端队列）模拟一个队列，只要保证你仅仅使用队列的标准操作即可——亦即只有如下操作是有效的：push to back（加入队尾），pop from front（弹出队首），size（取队列大小）以及is empty（判断是否为空）

第一题 452. Minimum Number of Arrows to Burst Balloons

题目描述

二维空间中有一组气球。对于每一个气球，输入其水平直径的起止点坐标。由于是水平的，不需要考虑y坐标，因而用x坐标表示起止点即可。起点总是小于终点。最多10^4个气球。

一支箭从x轴的不同点竖直射出。某气球的起止点坐标为xstart和xend，当xstart ≤ x ≤ xend时，该气球会被射中。射出的弓箭数目没有限制。弓箭可以保持无限移动。计算最少需要多少弓箭可以将所有气球射中。

第一题 57. Insert Interval

题目描述

假定现在给定一些间距(Intervals)，要求他们是不重复的且是按照顺序的，求插入一个间距后(Interval)，形成的新的间距样式

算法

思路较为清晰，如果interval.end < newInterval.start说明其肯定在newInterval之前，按照原来的形式进行插入

第一题 125. Valid Palindrome

题目描述

判断一个字符串是不是回文，忽略所有不是字母和数字的字符。

算法

从后往前即可，注意一下这题的姊妹题，先将指针前后赛跑，然后再进行原地反转，再进行对比，是一道非常好的题目。