小红书笔试

第一题回溯超时只过了27% 最后改成动态规划来不及交了麻烦大佬帮忙看看修改后的代码对不对

public class XHSMain1 {
    static int res = Integer.MAX_VALUE;
    static List<Entry> energy = new ArrayList<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int black=0,white=0,empty=0;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int color = sc.nextInt();
            arr[i] = color;
            if(color == 0){
                empty++;
                energy.add(new Entry(sc.nextInt(),sc.nextInt()));
            }else if(color == 1){
                white++;
            }else{
                black++;
            }
        }
        if(Math.abs(black-white)>empty || (black+white+empty)%2!=0){
            System.out.println(-1);
            return;
        }
        int needBlack = 0,needWhite = 0;
        if(black>white){
            needWhite = black-white;
        }else{
            needBlack = white-black;
        }
        empty-=(Math.abs(white-black));
        needBlack+=(empty/2);
        needWhite+=(empty/2);
        int[][] dp= new int[needWhite+1][needBlack+1];
        for (int i = 1; i <= needBlack; i++) {
            dp[0][i]=energy.get(i-1).black+dp[0][i-1];
        }
        for (int i = 1; i <= needWhite; i++) {
            dp[i][0]=energy.get(i-1).white+dp[i-1][0];
        }
        for(int i=1;i<=needWhite;i++){
            for (int j = 1; j <= needBlack; j++) {
                dp[i][j]=Math.min(dp[i-1][j]+energy.get(i+j-1).white,
                        dp[i][j-1]+energy.get(i+j-1).black);
            }
        }
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println(dp[needWhite][needBlack]);
    }

    static class Entry{
        int white;
        int black;

        public Entry(int white,int black) {
            this.black = black;
            this.white = white;
        } @Override public String toString() {
            return "Entry{" +
                    "white=" + white +
                    ", black=" + black +
                    '}';
        }
    }
}

第二题超时了过了81%那个代码没保存手上只有这个64%的了

public class XHSMain2 {
    static char[][] board;
    static int res = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            String s =sc.nextLine();
            board[i] = s.toCharArray();
        }
        for (int i = 0; i < n; i++) {
            backtrack(n-1,i);
        }
        System.out.println(res);
    }

    public static void backtrack(int r, int c) {
        if(r==0 && c==0){
            board[r][c]='#';
            if(isValid()){
                res++;
            }
            board[r][c]='.';
            return;
        }
        board[r][c]='#';
        int[][] directions = new int[4][2];
        directions[0] = new int[]{1,0};
        directions[1] = new int[]{-1,0};
        directions[2] = new int[]{0,1};
        directions[3] = new int[]{0,-1};
        for (int i = 0; i < directions.length; i++) {
            int newR = r+directions[i][0];
            int newC = c+directions[i][1];
            if(newR>=0 && newC>=0 && newR<board.length && newC<board[0].length && board[newR][newC]!='#')
                backtrack(newR,newC);
        }
        board[r][c]='.';
    }

    private static boolean isValid() {
//        System.out.println("isValid");
        for (char[] chars : board) {
//            System.out.println(Arrays.toString(chars));
            for (char aChar : chars) {
                if(aChar!='#') return false;
            }
        }
        return true;
    }
}

附第三题代码比较笨重的回溯运气好过了

public class XHSMain3 {
    static int res = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =Integer.parseInt(sc.nextLine());
        Film[] films = new Film[n];
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            String[] strs1=s.split("-");
            String[] start = strs1[0].split(":");
            String[] end = strs1[1].split(":");
            films[i] = new Film(Integer.parseInt(start[0])*60+Integer.parseInt(start[1]),
                    Integer.parseInt(end[0])*60+Integer.parseInt(end[1]));
            films[i].time=films[i].end-films[i].start;
        }
        Arrays.sort(films, new Comparator<Film>() {
            @Override
            public int compare(Film o1, Film o2) {
                if(o1.start!=o2.start)
                    return o1.start-o2.start;
                return o1.end-o2.end;
            }
        });
        backTrack(films,0,0,0,0);
        System.out.println(res);
    }

    private static void backTrack(Film[] films,int index,int end,int now,int count) {
        if(index==films.length){
            if(count==3)
                res = Math.max(res,now);
            return;
        }
        if(films[index].start>=end) {
            backTrack(films, index + 1, films[index].end, now + films[index].time, count + 1);
        }
        backTrack(films,index+1,end,now,count);
    }

    static class Film{
        int start;
        int end;
        int time;

        public Film(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Film{" +
                    "start=" + start +
                    ", end=" + end +
                    ", time=" + time +
                    '}';
        }
    }
}

#笔试##笔经##小红书#