fork(7) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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
https://ideone.com/0Mdfcf
Least number after deleting some digits
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!