一直找不到原因:请检查是否存在数组越界等非法访问情况
这道题来自网易2017春招笔试真题编程题合集 第11题
我的思路是先得到保存砖块高度的数组 A 的所有组合,遍历这些组合,遍历时把当前组合与 A
中除去该组合后剩下的元素的所有组合依次相加,如果两组合中元素的和相等就保存到集合 S 中,最后输出集合 S 中最大的元素。
请检查是否存在数组越界等非法访问情况
case通过率为50.00%
case通过率为50.00%
import java.util.*; public class Main { private static ArrayList<int[]> addList = new ArrayList<>(); private static int[] nums; public static void main(String[] args) { Scanner in = new Scanner(System.in); int count = in.nextInt(); if (count < 1 || count > 50) return; in.nextLine(); String str = in.nextLine(); String[] strs = str.split(" "); nums = new int[count]; int ii = 0; for (String s : strs) { int num = Integer.parseInt(s); if (num < 1 || num > 500000) return; nums[ii++] = num; } //对所有“砖块”进行组合 List<int[]> list = getArrays(nums); List<Integer> results = new ArrayList<>(); //移除第一个,“所有都有”的组合 list.remove(0); for (int[] ins : list) { //得到该组合方式下剩余哪些高度的砖块 int[] tempArry = new int[count]; int j = 0; for (int i = 0; i < count; i++) { if (ins[i] == 0) tempArry[j++] = nums[i]; } //要对“剩余砖块”进行组合因而使数组大小等于“剩余砖块个数” int[] rest = new int[j]; for (int i = 0; i < rest.length; i++) { rest[i] = tempArry[i]; } //得到“剩余砖块”的所有组合 List<int[]> restList = getArrays(rest); for (int[] ins1 : restList) { int sum; if ((sum = getSum(ins)) == getSum(ins1)) results.add(sum); } } System.out.print((results.size() == 0 ? -1+"" : Collections.max(results)+"")); } private static int getSum(int[] ins) { int sum = 0; for (int i : ins) sum += i; return sum; } /** * 获得数组的全部组合集合 * * @param res 要进行组合的数组 * @return 数组集合,返回从元素个数为 n 的数组中选择 [1...n] 个元素组合的所有可能组合:<br> * 示例:从 {1,2,3,4} 中选择二个则返回的数组集合中有如下数组:<br>{1,2,0,0} <br>{1,0,3,0} <br>{1,0,0,4} <br>{0.2,3,0} <br>{0,2,0,4} <br>{0,0,3,4} */ private static List<int[]> getArrays(int[] res) { ArrayList<int[]> result = new ArrayList<>(); int count = res.length; for (int i = 1; i < count; i++) { int[] temp = new int[count]; for (int j = 0; j < temp.length; j++) { temp[j] = 0; } for (int j = 0; j < i; j++) { temp[j] = 1; } combination(temp); } result.add(0, res); for (int[] ins : addList) { int[] temp = new int[count]; for (int i = 0; i < temp.length; i++) { temp[i] = ins[i] == 1 ? res[i] : 0; } result.add(temp); } addList.clear(); return result; } //组合 private static void combination(int[] arr) { //TODO arr即为每次递归的结果值,将其保存在全局变量中 addList.add(arr.clone()); int count = 0, index = 0; boolean ch = false; for (; index < arr.length - 1; index++) { count = arr[index] == 1 ? count + 1 : count; if (arr[index] == 1 && arr[index + 1] == 0) { ch = true; break; } } if (ch) { arr[index] = 0; arr[index + 1] = 1; for (int j = 0; j < index; j++) { arr[j] = j < count - 1 ? 1 : 0; } combination(arr); } else return; } }