贪心算法----字典序最小问题

2019/02/12 17:17
阅读数 1.3K

题目:

  字典序最小问题,给一个定长为N的字符串S,构造一个字符串T,长度也为N。起初,T是一个空串,随后反复进行下列任意操作:1. 从S的头部删除一个字符,加到T的尾部 2. 从S的尾部删除一个字符,加到T的尾部。目标是最后生成的字符串T的字典序尽可能小。1≤N≤2000。字符串S只包含大写英文字母。

  输入:字符串S
  输出:字符串T。要求每80个字符换行输出

  样例输入:

6
A
C
D
B
C
B

  样例输出:

ABCBCD

  思路分析:从题目上就可以得出这道题的解法就是循环比较首尾元素的字典序,难点就是假如两个字符相同时该如何处理,例如字符串"ACDBCB",那么第一次循环肯定是先把A加进来,然后把B加进来,下一次判断的时候发现头尾都是"C"那么继续往下看头尾两个字符发现B的字典序小于D那么肯定是先加上尾部的这个C的字符的,然后把B加进来,把C加进来,把D进来,最后形成了字典序最小的字符串"ABCBCD"。这里有一个重要的解题技巧,除了用双指针比较字符串的首尾元素之外,还可以用到翻转字符串的方法去解这道题,具体代码如下:

 1 public class 字典序最小问题 {
 2 
 3     public static void main(String[] args) {
 4         Scanner sc = new Scanner(System.in);
 5         int N = sc.nextInt();
 6         StringBuilder ss = new StringBuilder();
 7         for (int i = 0; i < N; i++) {
 8             ss.append(sc.next());
 9         }
10         // String s = sc.nextLine();
11         f(ss.toString());
12 
13     }
14 
15     private static void f(String s) {
16         String s1 = new StringBuilder(s).reverse().toString();
17         int N = s.length();
18         StringBuilder rs = new StringBuilder();
19         int cnt = 0;
20         while (rs.length() < N) {
21             if (s.compareTo(s1) <= 0) {
22                 rs.append(s.charAt(0));
23                 s = s.substring(1);
24             } else {
25                 rs.append(s1.charAt(0));
26                 s1 = s1.substring(1);
27             }
28             // 字符满80个就换行
29             if (rs.length() % 80 == 0) {
30                 System.out.println(rs.substring(cnt * 80, (cnt + 1) * 80));
31                 cnt++;
32             }
33         }
34         // 余数部分
35         if (rs.length() > cnt * 80) {
36             System.out.println(rs.substring(cnt * 80));
37         }
38     }
39 
40 }

  结果:

    

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部