fork(6) download
  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