1. import java.io.*;
2.
3. // Problem Description:
4. // Get the least number after deleting k digits of a number
5. // Supposing the number is represented as a string
6.
7. class DecreasingResult {
8. public int firstDecreasing;
9. public int nextStart;
10. }
11.
12. class Ideone
13. {
14. // Solution 1: O(n*k)
15. public static String getLeastNumberDeletingDigits_1(String number, int k) {
16. String leastNumber = number;
17. while(k > 0 && leastNumber.length() > 0) {
18. int firstDecreasingDigit = getFirstDecreasing(leastNumber);
19. if(firstDecreasingDigit >= 0) {
20. leastNumber = removeDigit(leastNumber, firstDecreasingDigit);
21. }
22. else {
23. leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
24. }
25.
26. --k;
27. }
28.
29. return leastNumber;
30. }
31.
32. private static int getFirstDecreasing(String number) {
33. for(int i = 0; i < number.length() - 1; ++i) {
34. int curDigit = number.charAt(i) - '0';
35. int nextDigit = number.charAt(i + 1) - '0';
36. if(curDigit > nextDigit) {
37. return i;
38. }
39. }
40.
41. return -1;
42. }
43.
44. private static String removeDigit(String number, int digitIndex) {
45. String result = "";
46. if(digitIndex > 0) {
47. result = number.substring(0, digitIndex);
48. }
49. if(digitIndex < number.length() - 1) {
50. result += number.substring(digitIndex + 1);
51. }
52.
53. return result;
54. }
55.
56. // Solution 2: O(n)
57. public static String getLeastNumberDeletingDigits_2(String number, int k) {
58. String leastNumber = number;
59. int start = 0;
60. while(k > 0 && leastNumber.length() > 0) {
61. DecreasingResult result = getNextDecreasing(leastNumber, start);
62. if(result.firstDecreasing >= 0) {
63. leastNumber = removeDigit(leastNumber, result.firstDecreasing);
64. }
65. else {
66. leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
67. }
68.
69. start = result.nextStart;
70. --k;
71. }
72.
73. return leastNumber;
74. }
75.
76. private static DecreasingResult getNextDecreasing(String number, int start) {
77. int firstDecreasing = -1;
78. int nextStart;
79.
80. for(int i = start; i < number.length() - 1; ++i) {
81. int curDigit = number.charAt(i) - '0';
82. int nextDigit = number.charAt(i + 1) - '0';
83. if(curDigit > nextDigit) {
84. firstDecreasing = i;
85. break;
86. }
87. }
88.
89. if(firstDecreasing == 0) {
90. nextStart = 0;
91. }
92. else if (firstDecreasing > 0) {
93. nextStart = firstDecreasing - 1;
94. }
95. else {
96. nextStart = number.length();
97. }
98.
99. DecreasingResult result = new DecreasingResult();
100. result.firstDecreasing = firstDecreasing;
101. result.nextStart = nextStart;
102.
103. return result;
104. }
105.
106. //////////////////////////////////////////////////////////////
107. // Test Code Begins:
108. //////////////////////////////////////////////////////////////
109. private static void testSolution1(String number, int k, String expected) {
110. String result = getLeastNumberDeletingDigits_1(number, k);
111. if(result.equals(expected)) {
112. System.out.println("Solution 1 passed, with number " + number + ", k: " + k);
113. }
114. else {
115. System.out.println("Solution 1 FAILED, with number " + number + ", k: " + k);
116. }
117. }
118.
119. private static void testSolution2(String number, int k, String expected) {
120. String result = getLeastNumberDeletingDigits_2(number, k);
121. if(result.equals(expected)) {
122. System.out.println("Solution 2 passed, with number " + number + ", k: " + k);
123. }
124. else {
125. System.out.println("Solution 2 FAILED, with number " + number + ", k: " + k);
126. }
127. }
128.
129. private static void test(String number, int k, String expected) {
130. testSolution1(number, k, expected);
131. testSolution2(number, k, expected);
132. }
133.
134. private static void test1() {
135. String number = "13243221";
136. int k = 5;
137. String expected = "121";
138.
139. test(number, k, expected);
140. }
141.
142. private static void test2() {
143. String number = "1234567";
144. int k = 3;
145. String expected = "1234";
146.
147. test(number, k, expected);
148. }
149.
150. private static void test3() {
151. String number = "7654321";
152. int k = 3;
153. String expected = "4321";
154.
155. test(number, k, expected);
156. }
157.
158. private static void test4() {
159. String number = "66666666";
160. int k = 3;
161. String expected = "66666";
162.
163. test(number, k, expected);
164. }
165.
166. private static void test5() {
167. String number = "12345";
168. int k = 5;
169. String expected = "";
170.
171. test(number, k, expected);
172. }
173.
174. private static void test6() {
175. String number = "12345";
176. int k = 6;
177. String expected = "";
178.
179. test(number, k, expected);
180. }
181.
182. private static void test7() {
183. String number = "12345";
184. int k = 0;
185. String expected = "12345";
186.
187. test(number, k, expected);
188. }
189.
190. private static void test8() {
191. String number = "24635";
192. int k = 3;
193. String expected = "23";
194.
195. test(number, k, expected);
196. }
197.
198. public static void main (String[] args) {
199. test1();
200. test2();
201. test3();
202. test4();
203. test5();
204. test6();
205. test7();
206. test8();
207. }
208. }
Success #stdin #stdout 0.07s 380160KB
stdin
Standard input is empty
stdout
Solution 1 passed, with number 13243221, k: 5
Solution 2 passed, with number 13243221, k: 5
Solution 1 passed, with number 1234567, k: 3
Solution 2 passed, with number 1234567, k: 3
Solution 1 passed, with number 7654321, k: 3
Solution 2 passed, with number 7654321, k: 3
Solution 1 passed, with number 66666666, k: 3
Solution 2 passed, with number 66666666, k: 3
Solution 1 passed, with number 12345, k: 5
Solution 2 passed, with number 12345, k: 5
Solution 1 passed, with number 12345, k: 6
Solution 2 passed, with number 12345, k: 6
Solution 1 passed, with number 12345, k: 0
Solution 2 passed, with number 12345, k: 0
Solution 1 passed, with number 24635, k: 3
Solution 2 passed, with number 24635, k: 3