SHOW:
|
|
- or go back to the newest paste.
1 | import java.util.*; | |
2 | - | /* |
2 | + | |
3 | - | Ratkaisun idea: lähdetään rakentamaan uutta merkkijonoa |
3 | + | |
4 | - | merkki kerrallaan. Seuraava huomio on oleellinen: jos jotain |
4 | + | public static int getDoublePosStart(StringBuilder sb, int start, int startlen) { |
5 | - | merkkiä on jäljellä 1 enemmän kuin kaikkia muita merkkejä |
5 | + | for (; start < startlen; ++start) { |
6 | - | yhteensä, niin joudumme lisäämään sen. Esimerkiksi tilanteessa |
6 | + | if (sb.charAt(start) == sb.charAt(start - 1)) { |
7 | - | jossa jäljellä olevat kirjaimemme olisivat c,c,c,a,b joudumme |
7 | + | return start; |
8 | - | käyttämään merkit a ja b erottamaan merkkejä c toisistaan. |
8 | + | |
9 | - | Sijoittaisimme ne siis merkkijonoon seuraavasti: cacbc. |
9 | + | |
10 | return -1; | |
11 | - | Algoritmi toimii seuraavasti: pidetään aina muistissa edellisessä |
11 | + | |
12 | - | indeksissä olevaa kirjainta. Sen lisäksi tarkistamme aina |
12 | + | |
13 | - | onko jotain kirjainta jäljellä yksi kappale enemmän kuin muita |
13 | + | public static int getDoublePosEnd(StringBuilder sb, int limit) { |
14 | - | kirjaimia yhteensä. Jos tällainen kirjain löytyy, sijoitamme sen |
14 | + | // for (int i = sb.length() - 1; i > limit; --i) { |
15 | - | rakennettavan merkkijonon perälle. Muutoin sijoitamme merkkijonoon |
15 | + | int i = sb.length() - 1; |
16 | - | pienimmän kirjaimen, jota on jäljellä ja joka ei esiinny edellsisessä |
16 | + | if (i > limit) { |
17 | - | indeksissä. |
17 | + | if (sb.charAt(i) == sb.charAt(i - 1)) { |
18 | - | */ |
18 | + | return i; |
19 | } | |
20 | } | |
21 | - | int n=mjono.length(); |
21 | + | return -1; |
22 | } | |
23 | - | int[] merkkien_esiintyvyys=new int[256]; |
23 | + | |
24 | public static int getNonDoublePos(StringBuilder sb, char c, int oldpos) { | |
25 | - | for(int i=0; i<n; i++) |
25 | + | for (int i = oldpos; i > 0; --i) { |
26 | - | merkkien_esiintyvyys[mjono.charAt(i)]++; |
26 | + | if (sb.charAt(i) != c && sb.charAt(i - 1) != c) { |
27 | return i; | |
28 | - | StringBuilder vastaus=new StringBuilder(); |
28 | + | |
29 | } | |
30 | - | int jaljella=n; |
30 | + | return 0; |
31 | - | int kirjain_vasemmalla=-1; |
31 | + | |
32 | ||
33 | - | while(jaljella!=0){ |
33 | + | public static String xjarjestaMerkit(String mjono) { |
34 | int amin = 255; | |
35 | - | boolean pakko=false; |
35 | + | int amax = 0; |
36 | int[] amounts = new int[256]; | |
37 | - | for(int i='A'; i<='Z'; i++){ |
37 | + | for (int i = 0; i < mjono.length(); ++i) { |
38 | - | if(merkkien_esiintyvyys[i]*2==jaljella+1){ |
38 | + | char c = mjono.charAt(i); |
39 | - | merkkien_esiintyvyys[i]--; |
39 | + | ++amounts[c]; |
40 | - | pakko=true; |
40 | + | amin = Math.min(amin, c); |
41 | - | vastaus.append((char)(i)); |
41 | + | amax = Math.max(amax, c); |
42 | - | jaljella--; |
42 | + | |
43 | - | kirjain_vasemmalla=i; |
43 | + | |
44 | - | break; |
44 | + | int[] firstcharloc = new int[256]; |
45 | ||
46 | boolean first = true; | |
47 | StringBuilder result = new StringBuilder(); | |
48 | - | if(pakko) |
48 | + | int lastpos = 1; |
49 | for (char i = (char)amin; i <= amax; ++i) { | |
50 | if (amounts[i] <= 0) { | |
51 | - | for(int i='A'; i<='Z'; i++){ |
51 | + | |
52 | - | if(merkkien_esiintyvyys[i]!=0&&i!=kirjain_vasemmalla){ |
52 | + | |
53 | - | merkkien_esiintyvyys[i]--; |
53 | + | |
54 | - | vastaus.append((char)(i)); |
54 | + | // optimizaion for first |
55 | - | jaljella--; |
55 | + | if (first) { |
56 | - | kirjain_vasemmalla=i; |
56 | + | for (int j = 0; j < amounts[i]; ++j) { |
57 | - | break; |
57 | + | result.append(i); |
58 | } | |
59 | first = false; | |
60 | continue; | |
61 | - | return vastaus.toString(); |
61 | + | |
62 | ||
63 | int startlen = result.length(); | |
64 | for (int j = 0; j < amounts[i]; ++j) { | |
65 | int samepos = getDoublePosStart(result, lastpos, startlen); | |
66 | ||
67 | if (samepos >= 0) { | |
68 | - | System.out.println(jarjestaMerkit("CBAXXXX")); |
68 | + | result.insert(samepos, i); |
69 | lastpos = samepos + 1; | |
70 | ++startlen; | |
71 | } else { | |
72 | firstcharloc[i]++; | |
73 | result.append(i); | |
74 | if (i == amax) { | |
75 | int strend = result.length()-firstcharloc[i]; | |
76 | ++j; | |
77 | for (; j < amounts[i]; ++j) { | |
78 | int pos2 = getNonDoublePos(result, i, strend); | |
79 | result.insert(pos2, i); | |
80 | lastpos++; | |
81 | strend = pos2; | |
82 | } | |
83 | break; | |
84 | } | |
85 | } | |
86 | } | |
87 | } | |
88 | ||
89 | char oldchar = result.charAt(result.length() - 1); | |
90 | int oldpos = result.length() - firstcharloc[oldchar]; | |
91 | while (true) { | |
92 | int pos = getDoublePosEnd(result, lastpos); | |
93 | if (pos < 0) { | |
94 | break; | |
95 | } else { | |
96 | char c = result.charAt(pos); | |
97 | if (c != oldchar) { | |
98 | oldpos = result.length() - firstcharloc[c]; | |
99 | } | |
100 | int pos2 = getNonDoublePos(result, c, oldpos); | |
101 | result.deleteCharAt(pos); | |
102 | result.insert(pos2, c); | |
103 | lastpos++; | |
104 | } | |
105 | } | |
106 | return result.toString(); | |
107 | } | |
108 | ||
109 | ||
110 | ||
111 | static int amin = 255; | |
112 | static int amax = 0; | |
113 | static int total = 0; | |
114 | static int[] amounts = new int[256]; | |
115 | ||
116 | public static char getNextChar(char lastChar) | |
117 | { | |
118 | char next = 255; | |
119 | for (char i = (char)amin; i <= amax && total > 0; ++i) { | |
120 | if (amounts[i] <= 0) { | |
121 | continue; | |
122 | } | |
123 | if (i == lastChar) { | |
124 | continue; | |
125 | } | |
126 | if (amounts[i] > total/2) { | |
127 | next = i; | |
128 | break; | |
129 | } | |
130 | next = (char)Math.min(next, i); | |
131 | } | |
132 | --amounts[next]; | |
133 | --total; | |
134 | return next; | |
135 | } | |
136 | ||
137 | public static String jarjestaMerkit(String mjono) { | |
138 | for (int i = 0; i < mjono.length(); ++i) { | |
139 | char c = mjono.charAt(i); | |
140 | ++amounts[c]; | |
141 | ++total; | |
142 | amin = Math.min(amin, c); | |
143 | amax = Math.max(amax, c); | |
144 | } | |
145 | ||
146 | StringBuilder sb = new StringBuilder(); | |
147 | char c = 0; | |
148 | while (total > 0) | |
149 | { | |
150 | c = getNextChar(c); | |
151 | sb.append(c); | |
152 | } | |
153 | ||
154 | return sb.toString(); | |
155 | } | |
156 | ||
157 | public static void main(String[] args) { | |
158 | if (true) { | |
159 | suuri3(); | |
160 | return; | |
161 | } | |
162 | System.out.println(jarjestaMerkit("AAABBB")); | |
163 | System.out.println(jarjestaMerkit("AAABBBCCCCCCCDDDDD")); | |
164 | System.out.println(jarjestaMerkit("BAAACCC")); | |
165 | System.out.println(jarjestaMerkit("CBAED")); | |
166 | System.out.println(jarjestaMerkit("AXAXA")); | |
167 | } | |
168 | ||
169 | public static void suuriTesti(String alku, String loppu) { | |
170 | String uusi = jarjestaMerkit(alku); | |
171 | System.out.println(uusi.equals(loppu)); | |
172 | System.out.println(uusi); | |
173 | System.out.println(loppu); | |
174 | System.out.println(uusi.length()); | |
175 | System.out.println(uusi.substring(uusi.length() - 200)); | |
176 | } | |
177 | ||
178 | public static void suuri3() { | |
179 | int n = 99999; | |
180 | char[] t = new char[n]; | |
181 | char[] u = new char[n]; | |
182 | for (int i = 0; i < n; i++) { | |
183 | if (i % 2 == 0) { | |
184 | t[i] = 'X'; | |
185 | } else if (i < n / 2) { | |
186 | t[i] = 'A'; | |
187 | } else { | |
188 | t[i] = 'B'; | |
189 | } | |
190 | u[i] = t[i]; | |
191 | } | |
192 | Arrays.sort(u); | |
193 | suuriTesti(new String(u), new String(t)); | |
194 | } | |
195 | } |