网易伏羲4.22笔试

1.宝石分数，给定行囊为k，宝石数组price，从i到j一定要装在同一个行囊里，并且每个行囊的分数为price[i]+price[j]，全都放进行囊里且分数为所有行囊价值和。求最大和最小之间的差值。用例：[2,3,5,4] k=2,输出：（15-11=）4

2.永劫无间两个玩家分别在不同坐标上，互相找到对方最小用时，其中二维数组地图map为1表示可达，为0不可达，找不到对方输出-1。

本来以为都是动态规划，所以浪费了很长时间，最后半小时用回溯法，做出来第二题【100%】，然后继续用回溯法做第一题【50%】，刚用了15分钟又做了一下，自己测试几个都能通过，不知道这实际上对不对【回溯法真好用啊，腾讯音乐回溯法一个没做出来给我打击得不轻】。下面贴出代码：

import java.util.*;
public class Solution {
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static int tempScore = 0;

    public static int putGems (int[] price, int k) {
        if(price.length<=k){
            return 0;
        }
        helper(price, 0, k, 0);
        return max-min;
    }
    public static void main(String[] args) {
        System.out.println("----------" + putGems(new int[]{2,3,5, 4}, 2));
    }
        public static void helper(int[] price, int start, int k, int lap){
            //System.out.println(start + " "+ lap + " Score: " + tempScore);
            if(k==lap||price.length-start<k-lap){
                if(k == lap&&start==price.length){
                    max = Math.max(max, tempScore);
                    min = Math.min(min, tempScore);
                }
                return;
            }
            tempScore+=price[start];
            for(int i=start; i<price.length; i++){
                tempScore+=price[i];
                helper(price, i+1, k, lap+1);
                tempScore-=price[i];
            }
            tempScore-=price[start];
        }

    }

import java.util.*;
public class Solution {
    static int res = Integer.MAX_VALUE;
    public static int getEstTime (int[][] map, int a_x, int a_y, int b_x, int b_y) {

        helper(map, a_x, a_y,b_x, b_y, 0, new int[map.length][map[0].length]);
        return res==Integer.MAX_VALUE?-1:res%2==1?res/2+1:res/2;
    }

    private static void helper(int[][] map, int a_x, int a_y, int b_x, int b_y, int step, int[][] used) {
        if(b_x==a_x&&b_y==a_y){
            res = Math.min(res, step);
        }
        used[a_x][a_y] = 1;
        List<int[]> temp = new ArrayList<>();
        if(a_x+1<map[0].length&&map[a_x+1][a_y]==1&&used[a_x+1][a_y]==0)
            temp.add(new int[]{a_x+1, a_y});
        if(a_x-1>=0&&map[a_x-1][a_y]==1&&used[a_x-1][a_y]==0)
            temp.add(new int[]{a_x-1, a_y});
        if(a_y+1<map.length&&map[a_x][a_y+1]==1&&used[a_x][a_y+1]==0)
            temp.add(new int[]{a_x, a_y+1});
        if(a_y-1>=0&&map[a_x][a_y-1]==1&&used[a_x][a_y-1]==0)
            temp.add(new int[]{a_x, a_y-1});

        for(int i=0; i<temp.size(); i++){
            helper(map, temp.get(i)[0], temp.get(i)[1], b_x, b_y, step+1, used);
        }
    }

    public static void main(String[] args) {
        int[][] map = new int[][]{{1, 1, 1, 0, 1},{1, 0, 1, 1, 1}, {1, 1, 1, 0, 1},{0, 0, 1, 1, 1},{1, 0, 0, 0, 1}};
        System.out.println(getEstTime(map, 0,0,4,4));
    }
}

1.