【Algorithm】 002 算法基础

构造回文

时间限制：1秒

空间限制：32768K

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子1:

abcda google

输出例子1:

2 2

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            int[][] dp = new int[str.length() + 1][str.length() + 1];
            for (int i = 1; i < dp.length; i ++ ) {
                for (int j = 1; j < dp[0].length; j ++ ) {
                    if (str.charAt(i - 1) == str.charAt(str.length() - j)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            System.out.println(str.length() - dp[str.length()][str.length()]);
        }
    }
}

算法基础-字符移位

时间限制：1秒

空间限制：32768K

小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。 你能帮帮小Q吗？

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出移位后的字符串。

输入例子1:

AkleBiCeilD

输出例子1:

kleieilABCD

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            char[] c = str.toCharArray();
            for (int i = 0; i < c.length; i++) {
                if (c[i] > 'Z') {
                    int j = i;
                    while(j > 0) {
                        if (c[j - 1] < 'a') {
                            char temp = c[j];
                            c[j] = c[j - 1];
                            c[j - 1] = temp;
                            j--;
                        } else {
                            break;
                        }
                    }
                }
            }
            System.out.println(new String(c));
        }
    }
}

有趣的数字

时间限制：1秒

空间限制：32768K

小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？

输入描述:

输入包含多组测试数据。

对于每组测试数据：

N - 本组测试数据有n个数

a1,a2…an - 需要计算的数据

保证:

1<=N<=100000,0<=ai<=INT_MAX.

输出描述:

对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。

输入例子1:

6 45 12 45 32 5 6

输出例子1:

1 2

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] c = new int[n];
            for (int i = 0 ; i < n; i++) {
                c[i] = sc.nextInt();
            }

            Arrays.sort(c);

            if (c[0] == c[n - 1]) {
                System.out.println(((n * (n - 1)) / 2) + " " + ((n * (n - 1)) / 2));
                continue;
            }

            int minCount = 0;
            int maxCount = 0;
            int MIN = Integer.MAX_VALUE;
            int MAX = c[n - 1] - c[0];

            Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
            for (int i = 0; i < n; i++) {
                if (map.containsKey(c[i])) {
                    map.put(c[i], map.get(c[i]) + 1);
                } else {
                    map.put(c[i], 1);
                }
            }

            if (map.size() == n) {
                for (int i = 0; i < n - 1; i++) {
                    if (c[i + 1] - c[i] == MIN) {
                        minCount++;
                    } else if (c[i + 1] - c[i] < MIN) {
                        MIN = c[i + 1] - c[i];
                        minCount = 1;
                    }
                }
            } else {
                for (Integer key : map.keySet()) {
                    int val = map.get(key);
                    if (val > 1) {
                        minCount += (val * (val - 1)) / 2;
                    }
                }
            }

            int max_1 = map.get(c[0]);
            int max_2 = map.get(c[n - 1]);
            maxCount = max_1 * max_2;
            System.out.println(minCount + " " + maxCount);
        }
    }
}