第一题：
给定一个长度不小于2的数组arr。
写一个函数调整arr，使arr中要么全部的偶数位上都是偶数，要么全部的奇数位上都是奇数上。 要求：假设数组长度为N。时间复杂度请达到O(N)，额外空间复杂度请达到O(1),下标0,2,4,6...算作偶数位,下标1,3,5,7...算作奇数位，比如[1,2,3,4]调整为[2,1,4,3]就可以
分析：
时间复杂度请达到O(N)，就不能用多重循环。额外空间复杂度请达到O(1),，也就不能用辅助的数组之类的，就是要在单次扫描中，通过交换2个数的位置来实现。
事实上我们换个思维来想，假设有2个同样长度数组A,B。满足要么A数组全是偶数。要么B数组全是奇数，是不是就能非常快的有思路了。想一下再看以下分析。
2个指针P_A和P_B分别指向A，B，首先P_A找出第一个奇数，然后P_B找出第一个偶数，交换。然后循环这个方案，直到某个指针达到数组的末尾。
事实上这个题和上面的思路一样。相当于把2个数组交叉放在一起。偶数位置的相当于A数组。奇数位置相当于B数组。仅仅是每次移动2个位置
代码：
public class Solution {
/**
* 奇数位上都是奇数或者偶数位上都是偶数
* 输入：数组arr。长度大于2
* 将arr调整成奇数位上都是奇数或者偶数位上都是偶数
*/
public void oddInOddEvenInEven(int[] arr) {
int len = arr.length;
if (len <= 2) {
return;
}
int even = 0;
int odd = 1;
while (even < len && odd < len) {
if (arr[even] % 2 != 0)
{
odd = findEven(arr, odd);
if (odd < len) {
int temp = arr[odd];
arr[odd] = arr[even];
arr[even] = temp;
}
}
even += 2;
}
}
private int findEven(int[] arr, int odd) {
for (int i = odd; i < arr.length; i+=2) {
if (arr[i] % 2 == 0) {
return i;
}
}
return arr.length;
}
}
第二题
给定一个全是正数的数组arr。定义一下arr的最小不可组成和的概念：
1。arr的全部非空子集中，把每一个子集内的全部元素加起来会出现非常多的值。当中最小的记为min，最大的记为max； 2。在区间[min,max]上。假设有一些正数不能够被arr某一个子集相加得到。那么这些正数中最小的那个，就是arr的最小不可组成和； 3。在区间[min,max]上。假设全部的数都能够被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr = {3,2,5} arr的min为2，max为10，在区间[2,10]上。4是不能被不论什么一个子集相加得到的值中最小的，所以4是arr的最小不可组成和；
arr = {3,2,4} arr的min为2，max为9。在区间[2,9]上。8是不能被不论什么一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = {3,1,2} arr的min为1。max为6，在区间[2,6]上，不论什么数都能够被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。
1。arr的全部非空子集中，把每一个子集内的全部元素加起来会出现非常多的值。当中最小的记为min，最大的记为max； 2。在区间[min,max]上。假设有一些正数不能够被arr某一个子集相加得到。那么这些正数中最小的那个，就是arr的最小不可组成和； 3。在区间[min,max]上。假设全部的数都能够被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr = {3,2,5} arr的min为2，max为10，在区间[2,10]上。4是不能被不论什么一个子集相加得到的值中最小的，所以4是arr的最小不可组成和；
arr = {3,2,4} arr的min为2，max为9。在区间[2,9]上。8是不能被不论什么一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = {3,1,2} arr的min为1。max为6，在区间[2,6]上，不论什么数都能够被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。
分析：
我个人的思路是这样
假设仅仅有一个元素。那么肯定是arr[0]+1
假设有2个元素，假设a1<=a2 假设a1+1=a2 那么肯定是a2+1， 否则肯定是a1+1
3个元素以上,如果排序后的顺序为 a1<=a2<=a3<=a4...<=ai，先取前面2个元素a1和a2，a1和a2能组合成的全部情况。就能够利用一个辅助集S合记录，首先集合里面仅仅有3个元素(a1,a2,a1+a2),
然后考虑第3个元素a3，那么a1，a2,a3,a4能组合的全部情况是什么呢：
然后考虑第3个元素a3，那么a1，a2,a3,a4能组合的全部情况是什么呢：
a1
a2
a3
a1+a2
a1+a3
a2+a3
a1+a2+a3
事实上能够看出规律，与辅助集合S中的元素相比，多了的a3，a1+a3,a2+a3,a1+a2+a3,除了a3，其它是不是就是原有集合S中的元素分别与s3相加呢？
原理是这样，辅助集合S的作用就是保存前面全部可能出现的，通过相加能得到数，这样再与新的元素分别相加。就能得到当前全部的组合。
要找出最小的，不用找出全部的不可组成和。当我们新增加一个元素ai的时候。仅仅用推断a1到ai之间的数，是不是都在辅助集合S中，第一次不可组成和，就是最小不可组成和，由于，ai之后的元素都不会比ai小。
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Solution {
/**
* 正数数组中的最小不可组成和
* 输入：正数数组arr
* 返回：正数数组中的最小不可组成和
*/
public int getFirstUnFormedNum(int[] arr) {
int len=arr.length;
if(len==0){
return 0;
}
if(len==1){
return arr[0]+1;
}
Arrays.sort(arr);
if(len==2){
return arr[1]-arr[0]==1? arr[1]+1:arr[0]+1;
} int min=arr[0];
int max=arr[len-1];
int sum=0;
for(int i=0;i<arr.length;i++){
sum+=arr[i];
}
int[] flag=new int[sum-min+1]; Set<Integer> integers=new HashSet<Integer>();
integers.add(arr[0]);
integers.add(arr[1]);
integers.add(arr[1]+arr[0]); int set_max=arr[1]+arr[0];
setFlag(arr[0],min,flag);
setFlag(arr[1],min,flag);
setFlag(set_max,min,flag);
for(int i=2;i<len;i++){
int temp=arr[i];
Set<Integer> temp_set=new HashSet<Integer>(integers);
temp_set.add(temp);
setFlag(temp,min,flag); for (Iterator iterator = integers.iterator(); iterator.hasNext();) {
int v = (Integer) iterator.next();
temp_set.add(v+temp);
setFlag(v+temp,min,flag);
}
set_max+=temp;
integers=temp_set;
int res=judge(flag,temp-min);
if(res!=-1){
return res+min;
}
}
int res=judge(flag,sum-min);
if(res!=-1){
return res+min;
}
return sum+1;
} private int judge(int[] flag, int max) {
for(int i=0;i<max;i++){
if(flag[i]==0){
return i;
}
}
return -1;
} private void setFlag(int i, int min, int[] flag) {
flag[i-min]=1;
}
}
第三题
面值为正数的硬币放置成一排。玩家1和玩家2轮流拿走硬币。规定每一个玩家在拿硬币时，仅仅能拿走最左或最右的硬币。
比如： 硬币面值与排列为：1,2,3,4,5，如今轮到玩家1拿硬币。 在当前状态下，玩家1仅仅能拿走1或5。 假设玩家1拿走1。则排列变为2,3,4,5。那么接下来玩家2能够拿走2或5。然后继续轮到玩家1拿硬币... 假设玩家1拿走5。则排列变为1,2,3,4，那么接下来玩家2能够拿走1或4；然后继续轮到玩家1拿硬币... 游戏依照这个规则进行，直到全部的硬币被拿完。每一个玩家获得的分数是各自拿走硬币的总和。
比如： 硬币面值与排列为：1,2,3,4,5，如今轮到玩家1拿硬币。 在当前状态下，玩家1仅仅能拿走1或5。 假设玩家1拿走1。则排列变为2,3,4,5。那么接下来玩家2能够拿走2或5。然后继续轮到玩家1拿硬币... 假设玩家1拿走5。则排列变为1,2,3,4，那么接下来玩家2能够拿走1或4；然后继续轮到玩家1拿硬币... 游戏依照这个规则进行，直到全部的硬币被拿完。每一个玩家获得的分数是各自拿走硬币的总和。
游戏胜负的规定： 假设玩家1最后获得的分数大于玩家2，则玩家1获胜； 假设玩家2最后获得的分数大于玩家1，则玩家2获胜；
由于玩家1先拿硬币。所以假设最后两人获得分数一样则玩家2获胜； 给定一个数组arr。表示硬币的面值和排列状况，请返回终于获胜者的分数。
样例： arr=[8,7,5,3] 玩家1将获胜，分数为13 所以返回13 arr=[1,9,1] 玩家2将获胜，分数为9 所以返回9
分析，事实上就是从动态规划。用一个动态数组d。d[i][j]=max(arr[i]-d[i+1][j],arr[j]-d[i][j-1])
i<j
i<j
事实上d[i][j]就是表示。假设先取的人。会比后取的人，多多少分？负值表示少多少分。
那么每次比較取左边和取右边，找出最优的
至于return那个公式。事实上是这样来的。x+y=sum ,x-y=d --> x=(sum+d)/2
public class Solution {
/**
* 得到硬币博弈问题的获胜分值
* 输入：代表硬币排列情况的数组arr
* 返回：硬币博弈问题的获胜分值
*/
public int getWinValue(int[] arr) {
int len=arr.length;
int[][] d=new int[len][len];
int sum=0;
for(int i=0;i<len;i++){
d[i][i]=arr[i];
sum+=arr[i];
}
for(int w=1;w<len;w++){
for(int i=0;i<len-w;i++) {
rule(arr,i,i+w,d);
}
}
return (Math.abs(d[0][len-1])+sum)/2;
}
private void rule(int[] arr, int i, int w, int[][] d) {
int left=arr[i]-d[i+1][w];
int right=arr[w]-d[i][w-1];
if(left>right){
d[i][w]=left;
}else{
d[i][w]=right;
}
}
}