AcWing 137. 【Java】雪花雪花雪花    原题链接    简单

作者： 作者的头像   tt2767 ,  2019-12-11 23:36:34 ,  所有人可见 ,  阅读 933

0 


// 虽然TLE了，16/20，手动跑了下后面的数据是OK的，本题时间卡了常数，java是原罪啊, 有兴趣的同学再优化下吧
import java.util.*;
import java.util.stream.*;

public class Main{

    void run(){
        int n = jin.nextInt();
        for (int i = 0 ; i < n ; i++){
            List<Integer> snow = new ArrayList<>();
            for (int j = 0 ; j < 6 ;j++){
                snow.add(jin.nextInt());
            }
            snows.add(snow);
        }

        boolean isContain = false;
        for (int i = 0 ; i < n; i++){
            String note = getMinNote(snows.get(i));
            if (visit.contains(note)){
                isContain = true;
                break;
            }
            visit.add(note);
        }

        String res = isContain ? "Twin snowflakes found." : "No two snowflakes are alike.";
        System.out.println(res);

    }

    String getMinNote(List<Integer> snow){
        String flag1 = getMinFlag(snow);
        Collections.reverse(snow);
        String flag2 = getMinFlag(snow);
        return flag1.compareTo(flag2) < 0 ? flag1 : flag2;
    }

    String getMinFlag(List<Integer> snow){
        int i = 0, j = 1, k = 0, m = 6;
        while (i < m && j <m && k < m){
            if (snow.get((i+k) % m) == snow.get((j+k)%m)) k++;
            else {
                if (snow.get((i+k) % m) > snow.get((j+k) % m)) i += k+1;
                else j += k+1;
                if (i == j) i++;
                k = 0;
            }
        }
        int pos = Math.min(i,j);
        buffer.setLength(0);

        for (int u = 0 ;u < m ;u++){
            int value = snow.get((pos+u)%m);
            buffer.append(String.valueOf(value));
        }
        return buffer.toString();
    }

    private StringBuilder buffer = new StringBuilder();
    private Set<String> visit = new HashSet<>();
    private List<List<Integer>> snows = new ArrayList<>();
    private Scanner jin = new Scanner(System.in);
    public static void main(String[] args) throws Exception {new Main().run();}
}

4 评论

用户头像
Sonata_   2021-02-02 17:44         踩      回复

输入数据量为$10^5$，建议使用BufferedReader读取数据
这道题，我AC了

import java.util.*;
import java.io.*;

class Main {
    public static int toInt(String s) {
        return Integer.parseInt(s);
    }

    // less equal
    public static int cmp(int[] l, int[] r) {
        for (int i = 0; i < l.length; i++) {
            if (l[i] < r[i]) {
                return -1;
            } else if (l[i] > r[i]) {
                return 1;
            }
        }
        return 0;
    }

    public static int[] getMin(int[] arr) {
        int i = 0;
        int j = 1;
        int k = 0;
        int n = arr.length;
        while (i < n && j < n && k < n) {
            if (arr[(i + k) % n] < arr[(j + k) % n]) {
                j = j + k + 1;
                k = 0;
            } else if (arr[(i + k) % n] > arr[(j + k) % n]) {
                i = i + k + 1;
                k = 0;
            } else {
                k++;
            }
            if (i == j) {
                j++;
            }
        }
        i = Math.min(i, j);
        int[] res = new int[arr.length];
        for(k = 0; k < arr.length; k++) {
            res[k] = arr[(i + k) % n];
        }
        return res;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = toInt(br.readLine());
        int[][] snows = new int[n][6];
        int[] l = new int[6];
        int[] r = new int[6];
        for (int i = 0; i < n; i++) {
            String[] ws = br.readLine().split(" ");
            for (int j = 0; j < 6; j++) {
                l[j] = toInt(ws[j]);
                r[5 - j] = l[j];
            }
            l = getMin(l);
            r = getMin(r);
            if (cmp(l, r) >= 0) {
                System.arraycopy(l, 0, snows[i], 0, 6);
            } else {
                System.arraycopy(r, 0, snows[i], 0, 6);
            }

        }
        Arrays.sort(snows, Main::cmp);
        boolean flag = false;
        for(int i = 0; i < n - 1; i++) {
            if (cmp(snows[i], snows[i + 1]) == 0) {
                flag = true;
                break;
            }
        }
        if (flag) {
            System.out.println("Twin snowflakes found.");
        } else {
            System.out.println("No two snowflakes are alike.");
        }
    }
}
用户头像
tt2767   2021-03-03 22:28         踩      回复

👍

用户头像
xwmwr   2019-12-12 13:48         踩      回复

消灭java邪教，世界属于C++ ！
（纯属恶搞，不代表本人观点）

用户头像
tt2767   2019-12-12 23:39         踩      回复

😂