感谢小伙伴的热情参与，比赛的编程题目现在已经开放，大家可以随时自我挑战。
第一场 http://www.nowcoder.com/test/5409/summary?from=v2ex
第二场 http://www.nowcoder.com/test/6091/summary?from=v2ex
稍后放出比赛排行版，以下是用户提交的最优解
第一场
第一题 http://www.nowcoder.com/questionTerminal/b89b14a3b5a94e438b518311c5156366
public class Solution {
/**
* 奇数位上都是奇数或者偶数位上都是偶数
* 输入：数组arr，长度大于2
* 将arr调整成奇数位上都是奇数或者偶数位上都是偶数
*/
public void oddInOddEvenInEven(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int evenIndex = 0;
int oddIndex = 1;
int endIndex = arr.length - 1;
while (evenIndex < arr.length && oddIndex < arr.length) {
if ((arr[endIndex] & 1) == 0) {
swap(arr, endIndex, evenIndex);
evenIndex += 2;
} else {
swap(arr, endIndex, oddIndex);
oddIndex += 2;
}
}
}
public void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
第二题 http://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
import java.util.HashSet;
public class Solution {
/**
* 正数数组中的最小不可组成和
* 输入：正数数组arr
* 返回：正数数组中的最小不可组成和
*/
public int getFirstUnFormedNum(int[] arr) {
if (arr == null || arr.length == 0) {
return 1;
}
HashSet<Integer> sumSet = new HashSet<Integer>();
HashSet<String> isCompute = new HashSet<String>();
setSumSetProcessDP(arr, 0, 0, isCompute, sumSet);
int min = Integer.MAX_VALUE;
for (int i = 0; i != arr.length; i++) {
min = Math.min(min, arr[i]);
}
for (int i = min; i != Integer.MIN_VALUE; i++) {
if (!sumSet.contains(i)) {
return i;
}
}
return 0;
}
public void setSumSetProcessDP(int[] arr, int index, int preSum,
HashSet<String> isCompute, HashSet<Integer> sumSet) {
String curKey = String.valueOf(index + "+" + preSum);
if (isCompute.contains(curKey)) {
return;
}
if (index == arr.length) {
sumSet.add(preSum);
isCompute.add(curKey);
return;
}
setSumSetProcessDP(arr, index + 1, preSum, isCompute, sumSet);
setSumSetProcessDP(arr, index + 1, preSum + arr[index], isCompute, sumSet);
isCompute.add(curKey);
}
}
第三题 http://www.nowcoder.com/questionTerminal/3e6310ec9fb6445c814d4e0e21692f04
public class Solution {
/**
* 得到硬币博弈问题的获胜分值
* 输入：代表硬币排列情况的数组arr
* 返回：硬币博弈问题的获胜分值
*/
public int getWinValue(int[] arr) {
int[][] map = new int[arr.length][arr.length];
int player1Value = getOptimale(arr, 0, arr.length - 1, map);
int player2Value = getArraySum(arr) - player1Value;
return Math.max(player1Value, player2Value);
}
public int getOptimale(int[] arr, int start, int end, int[][] map) {
if (start == end) {
return arr[start];
}
if (map[start][end] != 0) {
return map[start][end];
}
int result = Math.max(
arr[start] + getMinRest(arr, start + 1, end, map), arr[end]
+ getMinRest(arr, start, end - 1, map));
map[start][end] = result;
return result;
}
public int getMinRest(int[] arr, int start, int end, int[][] map) {
if (start == end) {
return 0;
}
return Math.min(getOptimale(arr, start + 1, end, map),
getOptimale(arr, start, end - 1, map));
}
public int getArraySum(int[] arr) {
int result = 0;
for (int i = 0; i != arr.length; i++) {
result += arr[i];
}
return result;
}
}
第二场
第一题 http://www.nowcoder.com/questionTerminal/498a758089e4472f8698092295e45ce4
public class Solution {
/**
* 求左部分中的最大值减去右部分最大值的绝对值
* arr：输入数组
* 返回：左部分中的最大值减去右部分最大值的绝对值
*/
public int getMaxABSLeftAndRight(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i != arr.length; i++) {
max = Math.max(arr[i], max);
}
return max - Math.min(arr[0], arr[arr.length - 1]);
}
}
第二题 http://www.nowcoder.com/questionTerminal/56f059fc033f46b98c73e2caea760a8d
public class Solution {
/**
* 按照左右半区的方式重新组合单链表
* 输入：一个单链表的头节点head
* 将链表调整成题目要求的样子
*
* 后台的单链表节点类如下：
*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public void relocateList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode head2 = null;
if (head.next.next == null || head.next.next.next == null) {
head2 = head.next;
head.next = null;
mergeLinkedList(head, head2);
return;
}
boolean midMove = true;
ListNode midNode = head;
ListNode cur = head.next.next.next;
while (cur != null) {
if (midMove) {
midNode = midNode.next;
}
midMove = !midMove;
cur = cur.next;
}
head2 = midNode.next;
midNode.next = null;
mergeLinkedList(head, head2);
}
public void mergeLinkedList(ListNode head1, ListNode head2) {
ListNode cur1 = head1;
ListNode cur2 = head2;
while (cur1.next != null) {
ListNode nextCur1 = cur1.next;
ListNode nextCur2 = cur2.next;
cur1.next = cur2;
cur2.next = nextCur1;
cur1 = nextCur1;
cur2 = nextCur2;
}
cur1.next = cur2;
}
}
第三题 http://www.nowcoder.com/questionTerminal/f2981aa0dc4a4b2190a0f26b7003a688
public class Solution {
/**
* 将路径数组变为统计数组
* 输入：代表一张图的数组paths
* 将paths数组变为距离数组numArr
*/
public void pathArrToNumArr(int[] paths) {
if (paths == null || paths.length == 0) {
return;
}
// citiesPath -> distancesArray
pathArrToDistanceArr(paths);
// distancesArray -> numArray
distanceArrToNumArr(paths);
}
public void pathArrToDistanceArr(int[] paths) {
int cap = 0;
for (int i = 0; i != paths.length; i++) {
if (paths[i] == i) {
cap = i;
} else if (paths[i] > -1) {
int curI = paths[i];
paths[i] = -1;
int preI = i;
while (paths[curI] != curI) {
if (paths[curI] > -1) {
int nextI = paths[curI];
paths[curI] = preI;
preI = curI;
curI = nextI;
} else {
break;
}
}
int value = paths[curI] == curI ? 0 : paths[curI];
while (paths[preI] != -1) {
int lastPreI = paths[preI];
paths[preI] = --value;
curI = preI;
preI = lastPreI;
}
paths[preI] = --value;
}
}
paths[cap] = 0;
}
public void distanceArrToNumArr(int[] disArr) {
for (int i = 0; i != disArr.length; i++) {
int index = disArr[i];
if (index < 0) {
disArr[i] = 0; // important
while (true) {
index = -index;
if (disArr[index] > -1) {
disArr[index]++;
break;
} else {
int nextIndex = disArr[index];
disArr[index] = 1;
index = nextIndex;
}
}
}
}
disArr[0] = 1;
}
}
这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.