今天下午领导不在比较闲，继续刷题吧~哈
根据身高重建队列
题目：假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意：总人数少于1100人。
示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
思路：先说审题，照着这个示例看了两遍就懂了，没啥难的，然后我的想法是先从k是0的开始。然后从小到大。刚审完题想法不明确，隐约的甚至想构建什么矩阵，但是怎么构建不知道，哈哈，我去试试代码找找思路。刚刚有一个确切的念头：这个数组中绝对不会出现一模一样的两个数组：比如5,0 只会出现一次，因为出现两次肯定有一个是摆放不了的。emmmm...暂时就想到这里，我继续看。
我先直接附上代码然后再一点点解释：
class Solution {
public int[][] reconstructQueue(int[][] people) {
if (0 == people.length || 0 == people[0].length)
return new int[0][0];
//h降序，k升序
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
}
});
List<int[]> output = new LinkedList<>();
for(int[] p : people){
output.add(p[1], p);
}
int n = people.length;
return output.toArray(new int[n][2]);
}
}
首先，有一个很必然的认识：身高相同的，k越大拍的越往后，这个肯定是没问题的。也是最根本的规则。
其次，对高的人来说，矮的是看不见的，所以在高的人中间前面插入多少矮的都是对的。
所以有了上面的排序：h降序（保证个高的在前面），k升序（排名小的在前面。）
其实能理解这个排序这个题就差不多完事了。比如示例的例子：
如果排序完了。第一个是7,0。这个时候这个0就是他的下标位置：
答案变成：{ 7,0}
第二个是7,1.1是他的下标位置，答案变成{ 7,0}，{ 7,1}
第三是6,1.这个1是他的下标位置，属于中间插入，把原本的1以及往后都往后挤了，答案变成：{ 7,0}，{ 6,1}，{ 7,1}
因为对于7来说，6是看不见的，所以7,1的位置还是对的。
继续第四个是5,0，下标是0，所以插入到第一个。后面的顺序往后，答案变成：{5,0}，{ 7,0}，{ 6,1}，{ 7,1}。
第五个是5,2,，插入到下标是2的位置，答案变成:{5,0}，{ 7,0}，{5,2},{ 6,1}，{ 7,1}.
第六个是4,4.插入到下标是4的位置，然后整个统计就完了。
重点就是一点：个子高的看不到个子矮的，所以只要先插入高个子，剩下的矮个子咋折腾都不影响。
然后这道题就这样了，其实这个题不算难，但是测试案例的要很讲究的，比如说最高个子的必然有一个下标是0的，不然这个队列都不成立。剩下的其实条条框框也很多，才能保证该队列的正常。然后这道题就这样，下一题了。
等差数列划分
题目：如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。函数要返回数组 A 中所有为等差数组的子数组个数。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
思路：其实这个题我觉得还不算难，题目说的有些冗余了。首先三个等差的数可以凑成一个数组。其次1,2,3,4这种四个等差的数可以凑成三组数组。1，2,3,4,5这种五个等差的数可以凑成6组。六个等差的数可以凑成10组，这个其实是有规律的，三个凑1组是基本。 然后四个就是1+2.五个是1+2+3.六个是1+2+3+4，七个应该是1+2+3+4+5也就是15种，我去测试案例试试。
这是基本的知识，然后涉及到多段，比如1,2,3,4,6,8,10。如这段数就是两个大的等差数列：1-4.4-10.每段都是四个元素，不出意外这个答案是6个，我去测试案例试一下，没问题我就直接去写代码了.
艾玛，一次过不说，而且性能超过百分之百，激动了哈，最近好久没这么顺的做题，一次通过性能及格了，哈哈。直接贴代码：
class Solution {
public int numberOfArithmeticSlices(int[] A) {
if(A.length<3) return 0;
int n = 2;
int step = A[1]-A[0];
int res = 0;
for(int i = 1;i<A.length-1;i++){
if(A[i+1]-A[i]==step){
n++;
}else{
if(n>=3){
res += sum(n);
}
n = 2;
step = A[i+1]-A[i];
}
}
if(n>=3) res += sum(n);
return res;
}
public int sum(int n){
int res = 0;
int i = 1;
while(i<=n-2){
res += i;
i++;
}
return res;
}
}
整体来说就是一次遍历，然后判断子串能组成几个等差数组，这个我单独用一个方法来判断的。反正整体来说这个题比较简单，但是代码我觉得是挺复杂的，因为这个性能比较好所以我膨胀了，也不看性能第一的代码了，直接过，下一题了。
分割等和子集
题目：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思路：说真的这个题目中两个注意：元素不会超过100，元素个数不会超过200，我都觉得这个题有点简单啊。首先几个思路：全部元素累加。和是奇数则肯定是false。和是偶数则有可能，接下来是判断其中元素能不能组成总和/2的,隐隐约约有dp的感觉。毕竟是多种情况，每个元素可以选和不选，选中的元素的和能不能凑成target。。我去写代码试试。
代码出来了。预感对了，是dp。我先贴代码再解释：
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i : nums) sum += i;
if((sum&1) == 1 ) return false;
int target = sum/2;
boolean[] dp = new boolean[target+1];
dp[0] = true;//当target是0的时候肯定是true
for (int i : nums) {
for (int j=target; j>0; j--) {
if (i<=j) {
dp[j] = dp[j] || dp[j - i];
}
}
if (dp[target]) return true;
}
return false;
}
}
这块怎么说呢，首先用一个布尔数组来表示可以和不可以。下标代表凑成的数。我们的最终目标是凑成target，所以这里数组的长度是target+1.
然后凑成0的话是肯定可以的，所以这里dp[0]是true。
其实这里可以有一步：所有元素自身肯定是可以凑成的，所以可以遍历一遍，所有出现了的元素的下标都是true。但是注意这样会有一个问题，那就是如果先这么走一遍，有些同样的元素出现两边，那么怎么知道这元素*2的位置可不可以凑成？所以这里不单独走这一遍了。
而是从第一个元素开始遍历，每个元素去逐个对比现在能凑成的数字。如果在比对过程中就凑出了target则直接返回true。否则就继续遍历。如果每个元素都走完了还没凑成target，则直接返回false就行了。
这个dp其实说复杂不复杂，但是也比较麻烦。主要是怎么把模糊的思路具体化实现。我之前在想的时候是有那么点感觉，但是抓不住。画图慢慢理的思路。
这道题就到这里了。
本篇文章就到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利，生活健健康康！java技术交流群：130031711，欢迎各位踊跃加入！
