首页 > 小红书笔试
头像
雾ZJW0417
编辑于 2021-08-21 14:56
+ 关注

小红书笔试

第一题回溯超时 只过了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 +
                    '}';
        }
    }
}



全部评论

(8) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐