10.10 携程笔试 100 100 0 63.33

第一题暴力法解了

import java.util.Scanner;

public class first {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] arr = in.nextLine().toCharArray();
        int max = 0;
        int total = 0;
        for(int i=0;i<arr.length-2;i++){
            if(arr[i]==arr[i+2])
                total++;
        }
        for(int i=0;i<arr.length;i++){
            int num=0;
            if(i-2>=0&&arr[i-2]==arr[i])
                num++;
            if(i-1>=0&&i+1<arr.length&&arr[i-1]==arr[i+1])
                num++;
            if(i+2< arr.length&&arr[i]==arr[i+2])
                num++;
            int change_num=0;
            if(arr[i]=='1'){
                arr[i] = '0';
                if(i-2>=0&&arr[i-2]==arr[i])
                    change_num++;
                if(i-1>=0&&i+1<arr.length&&arr[i-1]==arr[i+1])
                    change_num++;
                if(i+2< arr.length&&arr[i]==arr[i+2])
                    change_num++;
                arr[i] = '1';
            }
            else{
                arr[i] = '1';
                if(i-2>=0&&arr[i-2]==arr[i])
                    change_num++;
                if(i-1>=0&&i+1<arr.length&&arr[i-1]==arr[i+1])
                    change_num++;
                if(i+2< arr.length&&arr[i]==arr[i+2])
                    change_num++;
                arr[i] = '0';
            }
            if(change_num>num)
                max=Math.max(max,change_num-num);
        }
        System.out.println(total+max);
    }
}

第二题用Comparator自定义排序规则，用flag来回切

import java.util.*;
public class second {
    static class Node extends Object{
        int x;
        int y;
        public Node(int x,int y){
            this.x=x;
            this.y=y;
        }
        @Override
        public boolean equals(Object obj){
            Node temp = (Node) obj;
            return temp.x==this.x&&temp.y==this.y;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int n = in.nextInt();
        int x = in.nextInt();
        int find_x = -1;
        int find_y = -1;
        List<Node> list=new ArrayList<>();
        for(int i=0;i<n;i++){
            int a = in.nextInt();
            int b = in.nextInt();
            Node node=new Node(a,b);
            list.add(node);
            if(x-1==i){
                find_x = a;
                find_y = b;
            }
        }
        boolean flag=true;
        boolean control=true;
        while(flag){
            if(list.size()==1)
                break;
            if(control){
                Collections.sort(list, new Comparator<Node>() {
                    @Override
                    public int compare(Node o1, Node o2) {
                        if(o1.x<o2.x)
                            return -1;
                        if(o1.x>o2.x)
                            return 1;
                        if(o1.y<o2.y)
                            return -1;
                        return 1;
                    }
                });
            }
            else{
                Collections.sort(list, new Comparator<Node>() {
                    @Override
                    public int compare(Node o1, Node o2) {
                        if(o1.y<o2.y)
                            return -1;
                        if(o1.y>o2.y)
                            return 1;
                        if(o1.x<o2.x)
                            return -1;
                        return 1;
                    }
                });
            }
            control = !control;
            int location=-1;
            for(int i=0;i<list.size();i++){
                if(list.get(i).x==find_x&&list.get(i).y==find_y)
                    location=i;
            }
            int mid=list.size()/2;
            if(location>=mid){
                sb.append("R");
                list = list.subList(mid,list.size());
            }
            else{
                sb.append("L");
                list = list.subList(0,mid);
            }
        }
        System.out.println(sb.toString()+"O");
    }
}

第三题真不会，一点分也混不到

第四题，每个节点为源做一次dfs，最后求到的路径总数/2，过了63.33%，超时了

import java.util.*;

public class test {
    public static char[] colors;
    public static boolean[] visited;
    public static int ans=0;
    public static HashMap<Integer,List<Integer>> edge;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        colors = in.nextLine().toCharArray();
        visited = new boolean[n+1];
        edge=new HashMap<>();
        for(int i=1;i<=n;i++){
            edge.put(i,new ArrayList<>());
        }
        for(int i=1;i<n;i++){
            int a=in.nextInt();
            int b=in.nextInt();
            List<Integer> nodes = edge.get(a);
            nodes.add(b);
            edge.put(a,nodes);
            nodes = edge.get(b);
            nodes.add(a);
            edge.put(b,nodes);
        }
        for(int i=1;i<=n;i++){
            Arrays.fill(visited,false);
            dfs(i,1,0,0,0);
        }
        System.out.println(ans/2);
    }
    public static void dfs(int location, int depth,int red,int green,int blue){
        visited[location] = true;
        char color = colors[location-1];
        if(color=='r')
            red++;
        if(color=='g')
            green++;
        if(color=='b')
            blue++;
        if(depth==4){
            if(red>0&&green>0&&blue>0)
                ans++;
            return;
        }
        List<Integer> nodes = edge.get(location);
        for(int node:nodes){
            if(visited[node]==false)
                dfs(node,depth+1,red,green,blue);
        }
        visited[location] = false;
        if(color=='r')
            red--;
        if(color=='g')
            green--;
        if(color=='b')
            blue--;
    }
}