牛客网在线编程比赛题目代码公布，欢迎收藏， V 友你们可以做出几个？

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;
    }
}

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);
    }

}

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;
    }

}

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]);
    }
}

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;
    }

}

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;
    }

}