9.25-58同城软开编程题

    /**
     * 零钱兑换
     * AC100
     */
    public static int weight(int[] weights, int total) {
        //dp[i]表示凑够i元需要的最小的金币数量...
        int[] dp = new int[total + 1];  //dp
        //给dp[1..]元素赋值为Integer.MAX_VALUE>>1，dp[0]=0
        //为什么要设置为Integer.MAX_VALUE>>1呢？因为计算过程中还涉及到+1因此有可能溢出因此不能设置为Integer.MAX_VALUE...
        Arrays.fill(dp, 1, total, 0x3fffffff);
        for (int i = 1; i <= total; i++) {
            for (int weight : weights) {
                //只有i>=weight才有可能会选择当前金币
                if (i >= weight) {
                    //转移条件，dp=min(dp[i-w[j])   i>=w[j]  
                    dp[i] = Math.min(dp[i], dp[i - weight] + 1);
                }
            }
        }
        //如果不能凑够total该数量，那么return -1，如果能凑够才返回对应的数量...
        return dp[total] == 0x3fffffff ? -1 : dp[total];
    }

    /**
     * 每一行是一个数组，需要对每行的元素进行归并，并且进行去重...
     * 暴力解法，AC100
     */
    public static int[] rec(int[][] results) {
        for (int[] result : results) {
            Arrays.sort(result);
        }
        int[] mergeArray;
        //如果长度为1，那么就不需要进行归并了...
        if (results.length == 1) {
            mergeArray = results[0];
        } else {
            //如果长度大于1，那么需要把所有的元素全部归并到mergeArray中去
            mergeArray = mergeArray(results[0], results[1]);
            //遍历每个数组进行合并，其实这里可以使用归并去合并数组，但是这里暂时省略...能解决问题优先
            for (int i = 2; i < results.length; i++) {
                mergeArray = mergeArray(mergeArray, results[i]);
            }
        }
        //使用LinkedHashSet进行去重，利用LinkedHashSet的有序性以及它可以自动去重
        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        //把mergeArray中的元素全部放到LinkedHashSet中
        Arrays.stream(mergeArray).forEach(set::add);
        //把LinkedHashSet中的全部元素直接转成数组...
        Integer[] toArray = set.toArray(new Integer[0]);
        int N = toArray.length;
        int[] ret = new int[N];  //用来最终返回的数组
        //因为归并的结果是正序的，需要返回的是逆序的，因此第i个元素应该设置为原来的N-i-1位置
        for (int i = 0; i < N; i++) {
            ret[i] = toArray[N - i - 1];
        }
        return ret;
    }

    //普通的合并两个数组的方式而已
    public static int[] mergeArray(int[] arr1, int[] arr2) {
        int L = 0, R = 0, index = 0;
        int[] merge = new int[arr1.length + arr2.length];
        for (; L < arr1.length && R < arr2.length; ) {
            merge[index++] = arr1[L] > arr2[R] ? arr2[R++] : arr1[L++];
        }
        for (; L < arr1.length; ) {
            merge[index++] = arr1[L++];
        }
        for (; R < arr2.length; ) {
            merge[index++] = arr2[R++];
        }
        return merge;
    }

    public static boolean[] pathAvailable(int[][] matrix, int[][] starts, int[][] ends) {
        boolean[] resultRet = new boolean[starts.length];  //最终return的结果...
        for (int i = 0; i < starts.length; i++) {
            boolean[] result = new boolean[1];
            dfs(matrix, starts[i][0], starts[i][1], ends[i][0], ends[i][1], result, new boolean[matrix.length][matrix[0].length]);
            resultRet[i] = result[0];  //统计i这个点的结果
        }
        return resultRet;
    }

    public static void dfs(int[][] matrix, int iStart, int jStart, int iEnd, int jEnd, boolean[] result, boolean[][] visit) {
        //1.如果到达边界条件，那么直接return，不可能继续往下走了...
        //2.如果当前路径中已经访问过该节点，那么return...
        if (iStart == -1 || iStart == matrix.length || jStart == -1 || jStart == matrix[0].length || visit[iStart][jStart]) {
            return;
        }
        //如果可以到达目的地，那么需要统计结果...(修改result标志为true)
        if (iStart == iEnd && jStart == jEnd) {
            result[0] = true;
            return;
        }
        //如果遇到了不可通行的地方...那么直接return
        if (matrix[iStart][jStart] == 0) {
            return;
        }

        visit[iStart][jStart] = true;  //选择
        //往四个方向去进行尝试...
        dfs(matrix, iStart + 1, jStart, iEnd, jEnd, result, visit);
        dfs(matrix, iStart, jStart + 1, iEnd, jEnd, result, visit);
        dfs(matrix, iStart - 1, jStart, iEnd, jEnd, result, visit);
        dfs(matrix, iStart, jStart - 1, iEnd, jEnd, result, visit);
        visit[iStart][jStart] = false;  //取消选择
    }