3.10深信服笔试

1.字符不重复的最小次数

题意

给你一个长度为N的字符串，你可以删除任意位置的字符，删除后，该字符的左右字符会成为新的邻居，问需要删除多少个字符，可以是的每个字符的邻居不相同。

思路

比较简单的写法是用栈模拟，从前往后依次将字符加入栈中，如果和栈顶元素不相同，则入栈。相同则出栈。

代码

import java.util.Scanner;

public class A {
    static int maxn = 50 + 10;	//数据范围
    static char[] stack = new char[maxn];
    static char[] chars;
    static int t;
    static int n;

    /*栈模拟*/
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sc.nextLine();
        chars = sc.nextLine().toCharArray();
        int ans=0;
        for (int i = 0; i < chars.length; i++) {
            while (t > 0 && stack[t - 1] == chars[i]) {
                --t;
                ans++;
            }
            stack[t++]=chars[i];
        }
        System.out.println(ans);
    }
}

2.网络是否连通

题意

先给你一堆Ip，和IP对应的序号。再给你序号与序号之间的连接关系。最后有q次询问，每次询问两个IP是否连通。

思路

很裸的并查集，套模板就行。

代码

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class B {
    /**
     * 并查集模板
     * @param args
     */
    static Map<String, String> set = new HashMap<>();
    static String[] arr;
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new String[n + 1];
        for (int i = 1; i <= n; i++) {
            String ip = sc.next();
            set.put(ip, ip);
            int id = sc.nextInt();
            arr[id] = ip;
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            union(arr[a],arr[b]);
        }
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            System.out.println(isSet(sc.next(),sc.next())?"Yes":"No");
        }
    }

    public static void union(String a, String b) {
        String pa = find(a);
        String pb = find(b);
        if (pa.equals(pb)) return;
        set.put(pa, pb);
    }

    public static String find(String o) {
        String p = set.get(o);
        if (p.equals(o)) return p;
        p = find(p);
        set.put(o, p);
        return p;
    }

    public static boolean isSet(String a, String b) {
        return find(a).equals(find(b));
    }
}

3.最长连续递减子数组

题意

给你一个数组，求最长的连续递减子数组长度。（ps：不是最长递减子序列）

思路

维护一个当前位置结尾的最长递减子序列长度。如果当前位置比上一个位置小，那么len[i]=len[i-1]+1，否之len[i]=1。len数组可以优化成一个变量。

代码

import java.util.Scanner;

public class C {
    static int maxn = (int) 1e4 + 10;
    static int n;
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] vals = sc.nextLine().split(",");
        n = vals.length;
        arr = new int[n + 1];
        for (int i = 1; i < arr.length; i++) {
            arr[i] = Integer.parseInt(vals[i - 1]);
        }
        System.out.println(dp());
    }

    public static int dp() {
        int ans = 0;
        int pre = 0;
        arr[0] = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            pre = arr[i] < arr[i - 1] ? pre + 1 : 1;
            ans = Math.max(pre, ans);
        }
        return ans;
    }
}