题目描述

并查集
1.初始化并查集的数组p ，for i in n :p[i] = i;
2.合并2个数，即merge（x,y）
3.查询&压缩路径 find(x)
4.用set保存连同块的数量
5.判断set的大小 等于1说明都连起来了

样例

import java.util.*;
public class Main{
    public static int[]p;
    public static void main(String[]args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int n = in.nextInt();
            p = new int[n+1];
            for ( int i = 0; i < n; ++i ) {
                p[i+1] = i+1;
            }
            int m = in.nextInt();
                for ( int i = 0; i < m; ++i ) {
                    int x = in.nextInt();
                    int y = in.nextInt();
                    merge(x,y);
                }
                Set<Integer> set = new HashSet(); 
                for ( int i = 1; i <= n; ++i ) {
                    set.add(find(i));
                }

                if ( set.size() == 1 ) {
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
        }
    }

    public static int find(int x) {
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    public static void merge(int x ,int y ){
        int x_new = find(x);
        int y_new = find(y);
        p[x_new] = y_new;
    }

}

题目描述

满足就选不满足就不选。（算贪心？）

样例

import java.util.*;
public class Main {
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            in.nextLine();
            String line = in.nextLine();
            String[] nums = line.split(" ");
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(nums[i]);
            }
            int pre = arr[0];
            int ans = 1;
            int max = 1;
            for ( int i = 1; i < n; ++i ) {
                if (arr[i] <= 2*pre){
                    ans++;
                }else {
                    ans = 1;
                }
                max = Math.max(max,ans);
                pre = arr[i];
            }


            System.out.println(max);
        }
    }
}

题目描述

建树+遍历树对比颜色，不一样就加一

import java.util.*;

public class Main {
    public static List<List<Integer>> edges = new ArrayList();
    public static int ans = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            for ( int i = 0; i <= n; ++i ) {
                edges.add(new ArrayList());
            }
            in.nextLine();
            String line = in.nextLine();
            String[] nums = line.split(" ");

            for (int i = 0; i < n-1; i++) {
                int a = Integer.parseInt(nums[i]);
                edges.get(a).add(i+2);
            }
            int[] brr = new int[n+1];
            for (int i = 1; i <= n; i++) {
                brr[i] = in.nextInt();
               // System.out.println(brr[i]);
            }
            //return ;
            Queue<int[]> q = new ArrayDeque();
            q.offer(new int[]{1,0});
            while(!q.isEmpty()){
                int[]t = q.poll();
                int cur = t[0];
                int color = t[1];
                if (color != brr[cur]) {
                    ans++;
                }
                //System.out.println("cur:"+cur);
                List<Integer>children = edges.get(cur);
                for (int child:children){
                    int[]tmp =new int[2];
                    tmp[0] = child;
                    tmp[1] = brr[cur];
                   // System.out.println("child:"+child);
                    q.offer(tmp);
                }
                //System.out.println(ans);
                //return;
            }


            System.out.println(ans);
        }
    }

    // public static void dfs(int cur,int color,int[]brr) {
    //     List<Integer> children = edges.get(cur);
    //     if (brr[cur] == color) {
    //         for( int child:children) {
    //             dfs(child,color,brr);
    //         }
    //     }else {
    //         ans++;
    //         for(int child:children){
    //             dfs(child,brr[cur],brr);
    //         }
    //     }
    // }
}

题目描述：Given a nonnegative number set (can have duplicates), divide it into two sets so that the sum of the variances of these two sets is minimized. You can shuffle set order. The values of two sets cannot overlap. All number in the original set must appear in one of the two sets.
Finally return the value of the sum. The result include one decimal place.
The definition of variance: S^2= ∑ (X-a) ^2 / (n-1), where X is the average, a is every number in the set, and n is the size of the set.
For example: There is a set [1,3,1] . We can divide it into [1,1] and [3], Then return the result:0.0
Please simply proof the correctness of your solution.

时间复杂度要求O(nlgn)

求个解法。（目前想法是排序+前缀和枚举）但不知道咋证明，所以不知道对不对

题目描述

队列存储垃圾桶 判断那个更近一些（预处理：保证左边的垃圾桶一定是左边最近的）

样例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            in.nextLine();
            String line = in.nextLine();
            String[] tmp = line.split(" ");
            String line2 = in.nextLine();
            String[] tmp2 = line2.split(" ");
            int len = tmp.length;
            int[] arr = new int[n];
            int[] brr = new int[m];
            int index = 0;
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            for (int i = 0; i < len; ++i) {
                int a = Integer.parseInt(tmp[i]);
                int t = Integer.parseInt(tmp2[i]);
                if (t == 1) {
                    deque.offer(a);
                } else {
                    arr[index++] = a;
                }
            }
            index = 0;
            int pre = (int) deque.poll();
            for (int i = 0; i < n; ++i) {
                if (arr[i] < pre) {
                    brr[index]++;
                } else {
                    // 找到pre
                    while(!deque.isEmpty()) {
                        int next = (int)deque.peek();
                        if (arr[i] > next) {
                            pre = next;
                            index++;
                            deque.poll();
                        }else {
                            break;
                        }
                    }
                    if (!deque.isEmpty()) {
                        int next = (int)deque.peek();
                        if (Math.abs(arr[i] - pre) <= Math.abs(arr[i] - next)) {
                            brr[index]++;
                        } else {
                            index++;
                            brr[index]++;
                            pre = (int) deque.poll();
                        }
                    }else {
                        brr[index]++;
                    }
                }
            }

            StringBuffer ans = new StringBuffer();
            for (int i = 0; i < m; ++i) {
                if (i != m - 1) {
                    ans.append(brr[i] + " ");
                } else {
                    ans.append(brr[i]);
                }
            }

            System.out.println(ans.toString());
        }
    }
}

题目描述

一元二次不等式求根

样例

import java.util.*;
public class Main {
    public static void main(String[]args) {
        Scanner in = new Scanner(System.in);
        while( in.hasNext()) {
            int T = in.nextInt();
            for ( int i = 0; i < T; ++i ) {
                int t = in.nextInt();
                if( t > 0 && t < 4) {
                    System.out.println("N");
                }else{
                    int m = t*t -4*t;
                    double a = (Math.sqrt(m)+t)/2;
                    double b = (t-Math.sqrt(m))/2;
                    System.out.println("Y "+String.format("%.10f",a)+" "+String.format("%.10f",b));
                }
            }


        }
    }
}

题目描述

队列存储0的位置，遍历一次(和arr[i]的值无关)

样例

import java.util.*;
public class Main {
    public static void main(String[]args) {
        Scanner in = new Scanner(System.in);
        while( in.hasNext()) {
            int n = in.nextInt();
            //int[]arr = new int[n+1];
            ArrayDeque<Integer> d = new ArrayDeque();
            for ( int i = 1; i <= n; ++i ) {
               // arr[i] = in.nextInt();
                int t = in.nextInt();
                if(t == 0){
                    d.offer(i);
                }
            }
            StringBuffer ans = new StringBuffer();
            int zero = (int)d.poll();
            for( int i = 1; i <= n; ++i ) {
                int a = Math.abs(i - zero);
                if(!d.isEmpty()) {
                    int sec = (int)d.peek();
                    a = Math.min(a,Math.abs(sec-i));
                    if(i== zero) {
                        zero = sec;
                        d.poll();
                    }
                }
                if(i == n) {
                    ans.append(a);
                }else{
                    ans.append(a+" ");
                }
            }

            System.out.println(ans.toString());
        }
    }
}

// package test;

import java.util.*;
public class Main {
    public static int[]dx = {-1,0,1,0};
    public static int[]dy = {0,-1,0,1};
    public static void main(String[]args) {
        Scanner in = new Scanner(System.in);
        while( in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            char[][]arr = new char[n][m];
            //int ans = 0;
            for ( int i = 0; i < n; ++i ) {
                String a = in.next();
                for ( int j = 0; j < m; ++j ) {
                    arr[i][j] = a.charAt(j);
                }
            }
            for(int i = 0; i < n; ++i) {
                StringBuffer sb = new StringBuffer();
                for (int j = 0; j < m;++j ) {
                    if(arr[i][j] == '.') {
                        sb.append('.');
                    }else {
                        sb.append(find(arr,i,j));
                    }
                }
                System.out.println(sb.toString());
            }


        }
    }

    public static int find(char[][]arr,int x,int y){
        int n = arr.length;
        int m = arr[0].length;
        ArrayDeque<int[]> d = new ArrayDeque();
        d.offer(new int[]{x,y});
        int ans = 0;
        int[][]visit =  new int[n][m];
        visit[x][y] = 1;
        while(!d.isEmpty()) {
            int[] tmp = d.poll();
            // if (x == 2&& y == 1) {
            //     System.out.println(Arrays.toString(tmp));
            // }

            ans++;
           // ans %= 10;
            for ( int i = 0; i < 4; ++i ) {
                int x_new = tmp[0]+dx[i];
                int y_new = tmp[1]+dy[i];
                if (x_new <0 || y_new < 0 || x_new >=n || y_new>=m) {
                    continue;
                }
                if (arr[x_new][y_new] == '*') {
                    continue;
                }
                if(visit[x_new][y_new] == 1) {
                    continue;
                }
                d.offer(new int[]{x_new,y_new});
                visit[x_new][y_new] = 1;
            }

        }
        return ans % 10 ;
    }
}

蹲一个大佬～

题目：求s的子串中出现最多字符-最少字符的最大值
例子1：s=”aab” a:2 b ：1 最大差值是1
例子2 : s=”bbcaaac” 返回2 子串”caaa” 和“aaac” 差值最大是 2
例子3: s=“aaa” 返回0
数据范围: 1=<s.length<=10^4

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int n = in.nextInt();
            long []sum = new long[n+1];
            for ( int i = 0; i < n; ++i ) {
                    sum[i+1] = sum[i] + in.nextLong();
            }
            int l = 0;
            int r = n;
            long max = 0;
           // 寻找1～n范围的区间数据
           while ( l <= r) {
               long sum1 = sum[l] - sum[0];
               long sum3 = sum[n] - sum[r];
               if (sum1 == sum3) {
                   max = Math.max(max,sum1);
                   l++;
                   r--;
               }else if (sum1 < sum3) {
                   l++;
               }else if (sum1 > sum3) {
                   r--;
               }
           }
           System.out.println(max);
        }
    }

}