TopCoder SRM 405 Level 2 1000
一個(gè)理想的字符串，其中每個(gè)字母第一次出現(xiàn)的位置N，與這個(gè)字母在字符串中出現(xiàn)的次數(shù)M是相等的，求給定長度的字符串中最小的一個(gè)理想字符串
字符串長度小于100
相當(dāng)于去搜索1～100中的一組不同的數(shù)
加起來等于長度L
同時(shí)每個(gè)數(shù)字都要小于等于比自己小的所有數(shù)的和加一
因?yàn)長比較小
所以用深搜就可以了
在這個(gè)過程中要注意深搜時(shí)候需要從大往小搜
這樣才能滿足“最小的”結(jié)果
搜索完之后的字符串構(gòu)建的步驟因?yàn)镾tringBuffer用的不熟練
反而調(diào)試了很久
1 import java.util.*;
2 import java.util.regex.*;
3 import java.text.*;
4 import java.math.*;
5 import java.awt.geom.*;
6
7 public class IdealString
8 {
9 int[] table = new int[26];
10 int finalindex = 0;
11 int L;
12
13 public String construct(int length)
14 {
15 Arrays.fill(table, 0);
16 L = length;
17 if(dfs(1, 0, 0)){
18 StringBuffer sb = new StringBuffer();
19 char c = 'A';
20 int i , j = 0;
21 for(i = 0 ; i < L; ++ i)
22 sb.append(' ');
23 for(i = 0 ; i < finalindex; ++i){
24 sb.setCharAt(table[i] - 1, c ++);
25 table[i]--;
26 }
27 for(i = 0 ; i < L; ++ i){
28 if(sb.charAt(i) != ' ')
29 continue;
30 while(table[j] == 0) j++;
31 sb.setCharAt(i, (char)('A' + j));
32 table[j]--;
33 }
34 return sb.toString();
35 }
36 return new String();
37 }
38
39 boolean dfs(int num, int index, int sum){
40 table[index] = num;
41 int base = num + sum;
42 if(base == L){
43 table[index] = num;
44 finalindex = index + 1;
45 return true;
46 }
47 if(base > L)
48 return false;
49 int total = 0;
50 for(int i = 0 ; i <= index ; ++ i)
51 total += table[i];
52 for(int i = total + 1; i >= num + 1; -- i){
53 if(base + i <= L && dfs(i, index +1, base))
54 return true;
55 }
56 return false;
57 }
58 }