牛客网在线编程比赛题目代码公布，欢迎收藏， 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; } }