Od练习的第三天

package com.od202305;

import java.util.Scanner;

/**
 * 对称字符串
 */
public class Od007 {

    public static void main(String[] args) {
        //解法1
        getStr();
        //解法二
        getStr2();

    }

    /**
     * 解法一：常规解法，递归拼接后取值，注意：容易出现越界，使用charAt()中int类型的范围有限
     * @return
     */
    public static void getStr(){
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        for (int j = 0; j < i; j++) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            String s = doProcess(n);
            System.out.println(s.charAt(k) == 'R' ? "red" : "blue");
        }
    }

    public static String doProcess(int n) {
        if (n == 1) { //当 n 为 1 时输出 R
            return "R";
        }
        String str = doProcess(n - 1); //当 n 大于等于 2 时需要对字符进行反转处理
        String reverseStr = "";
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == 'R') {
                reverseStr += 'B';
            } else {
                reverseStr += 'R';
            }
        }
        return reverseStr + str;
    }

    /**
     * 解法二
     *
     * @return
     */
    public static void getStr2() {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            long k = sc.nextLong();
            long charNum = (long) Math.pow(2, n - 1); //第 n 行的总字符个数
            int re = doProcess(charNum, k, 0);
            if (re % 2 == 0) {
                System.out.println("red"); //翻转次数为 2 的倍数
            } else {
                System.out.println("blue");
            }
        }
    }

    /**
     * 思路：字符索引如果在翻转的右侧则翻转次数不加一为单，除以一半层层递归判断
     *
     * @param count   字符数量
     * @param cur     字符的索引
     * @param reverse 翻转的次数
     * @return
     */
    public static int doProcess(long count, long cur, int reverse) {
        if (count == 1) {
            return reverse;
        }
        long half = count / 2;
        if (cur < half) { //小于半数说明是经过翻转的部分
            reverse++;
            return doProcess(half, cur, reverse);
        } else {
            return doProcess(half, cur - half, reverse);//2 0 0
        }
    }
}

package com.od202305;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 分界线
 */
public class Od008 {
    public static void main(String[] args) {
        System.out.println(getResult1("ab cd", "ab"));
    }

    /**
     * 解法一
     *
     * @param s1 相当于报纸（newspaper）
     * @param s2 匿名信代表 （anonymousLetter）
     * @return
     */
    public static boolean getResult1(String s1, String s2) {
        String[] s3 = s1.split(" ");
        String[] s4 = s2.split(" ");
        List<String> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        Arrays.stream(s3).forEach(e1 -> {
            char[] chars = e1.toCharArray();
            Arrays.sort(chars);
            String sortStr = new String(chars);
            list1.add(sortStr);
        });
        Arrays.stream(s4).forEach(e1 -> {
            char[] chars = e1.toCharArray();
            Arrays.sort(chars);
            String sortStr = new String(chars);
            list2.add(sortStr);
        });

        return list1.containsAll(list2);
    }

    public void getResult2() {
        Scanner sc = new Scanner(System.in);
        String[] newspaper = sc.nextLine().split(" ");
        String[] anonymousLetter = sc.nextLine().split(" ");
        boolean res = true;
        for (String anony : anonymousLetter) {
            for (int i = 0; i < newspaper.length; i++) {
                String news = newspaper[i];
                if (anony.length() == news.length() && handle(news, anony)) { //长度相等才有资格匹配
                    newspaper[i] = " "; //使用过的字符串之后就不能使用了
                    break;
                }
                if (i == newspaper.length - 1) { //遍历到最后都没有匹配的，直接 false
                    res = false;
                }
            }
            if (!res) { //已经失败了，跳出循环
                break;
            }
        }
        System.out.println(res);
    }

    /**
     * 通过 char 字符的排序，然后判断是否一一匹配，只要一个不匹配，直接 false * @param news 报纸上的字符串
     *
     * @param anony 匿名信上的字符串
     * @return
     */
    public static boolean handle(String news, String anony) {
        char[] newsChar = news.toCharArray();
        char[] anonyChar = anony.toCharArray();
        Arrays.sort(newsChar);
        Arrays.sort(anonyChar);
        boolean isTrue = true;
        for (int i = 0; i < newsChar.length; i++) {
            if (newsChar[i] != anonyChar[i]) {
                isTrue = false;
            }
        }
        return isTrue;
    }

}

package com.od202305;

import java.util.*;

public class Od009 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        if (M > 10) {
            System.out.println("[[]]");
        } else {
            List<Set<String>> list = new ArrayList<>();
            sc.nextLine();
            for (int i = 0; i < M; i++) {
                String[] strings = sc.nextLine().split(",");
                Set<String> set = new HashSet<>();
                if (strings.length == 1) { //只有一个元素直接添加
                    set.add(strings[0]);
                    list.add(set);
                } else {
                    for (String str : strings) {
                        set.add(str); //数组转化为 set 集合
                    }
                    list.add(set);
                    merge(set, list, list.size() - 1);
                }
            }
            System.out.println(list);
        }

    }

    public static void merge(Set<String> set, List<Set<String>> list, int index) {
        for (int i = 0; i < list.size(); i++) {
            //保证不和自己进行对比
            if (i == index) {
                continue;
            }
            Set<String> setIndex = list.get(i); //当前索引的 set 集合
            Set<String> setTemp = new HashSet<>();
            setTemp.addAll(set);
            setTemp.retainAll(setIndex); //求出 set 和 setIndex 的交集
            if (setTemp.size() >= 2) { //交集大于等于 2 则合并
                set.addAll(setIndex); //set 与 setIndex 合并
//                int beforeIndex = index > i ? i : index; //求出排在前面的 index
//                int afterIndex = beforeIndex == index ? i : index; //靠后的位置
                list.remove(index); //合并的两个 set 进行删除，先删除后面的一个
                list.remove(i);
                list.add(i, set); //将新的 set 放在前面位置
                merge(set, list, i); //将新建的组合再进行判断合并
            }
        }
    }
}
//第二种
/**
     * 合并关联端口组合
     *
     * @param set   进行合并的端口组合
     * @param list  端口组合集合
     * @param index 需要进行合并的组合索引
     */
    public static void merge2(Set<String> set, List<Set<String>> list, int index) {
        for (int i = 0; i < list.size(); i++) {
            if (i == index) {
                continue;
            }
            Set<String> setIndex = list.get(i); //当前索引的 set 集合
            Set<String> setTemp = new HashSet<>();
            setTemp.addAll(set);
            setTemp.retainAll(setIndex); //求出 set 和 setIndex 的交集
            if (setTemp.size() >= 2) { //交集大于等于 2 则合并
                set.addAll(setIndex); //set 与 setIndex 合并
                int beforeIndex = index > i ? i : index; //求出排在前面的 index
                int afterIndex = beforeIndex == index ? i : index; //靠后的位置
                list.remove(afterIndex); //合并的两个 set 进行删除，先删除后面的一
                个
                list.remove(beforeIndex);
                list.add(beforeIndex, set); //将新的 set 放在前面位置
                merge(set, list, beforeIndex); //将新建的组合再进行判断合并
            }
        }
    }