fork download
copy 
  1. /**
  2.  * 
  3.  */
  4.  
  5. import static java.lang.System.out;
  6.  
  7. import java.util.ArrayList;
  8. import java.util.List;
  9.  
  10. /**
  11.  * @description 0～9 挑k個數字, 組出最接近 A 的數字
  12.  * 				input(A, k)
  13.  * 				1 <= A <= 10^15, 1<=k<=10
  14.  * 
  15.  *
  16.  */
  17. public class Main {
  18.  
  19. 	/**
  20. 	 * @param args
  21. 	 */
  22.  
  23. 	private static String strOrigA;
  24.  
  25. 	private static int origK;
  26.  
  27. 	private static List<Integer> listCandidateDigits;
  28.  
  29. 	private static List<Long> listCandidateA;
  30.  
  31. 	public static void main(String[] args) {
  32.  
  33. 		long A = 3355798521L;
  34. 		int k = 5;
  35. //		long A = 3355798521L;
  36. //		int k = 10;
  37. //		long A = 262004L;
  38. //		int k = 2;
  39. //		long A = 8000L;
  40. //		int k = 1;
  41. //		long A = 1000L;
  42. //		int k = 1;
  43. //		long A = 2243L;
  44. //		int k = 2;
  45. //		long A = 88449L;
  46. //		int k = 2;
  47. //		long A = 123456789L;
  48. //		int k = 1;
  49. 		out.println(input(A, k));
  50. 	}
  51.  
  52. 	private static void recur(StringBuffer sbHead, int x, int k, boolean flag) {
  53. 		if(flag) {
  54. 			if(x == strOrigA.length()) {
  55. 				if(countDigits(sbHead.toString()) <= origK) {
  56. 					listCandidateA.add(Long.parseLong(sbHead.toString()));
  57. 				}
  58. 			} else {
  59. 				for(Integer i : listCandidateDigits) {
  60. 					recur((new StringBuffer(sbHead)).append(new Integer(i)), x + 1, 0, true);
  61. 				}
  62. 			}
  63. 		} else {
  64. 			if(k == 0) {
  65. 				if(x == strOrigA.length()) {
  66. 					listCandidateA.add(Long.parseLong(sbHead.toString()));
  67. 				} else {
  68. 					if(listCandidateDigits.contains(new Integer(strOrigA.charAt(x)))) {
  69. 						 recur((new StringBuffer(sbHead)).append(strOrigA.charAt(x)), x + 1, 0, false);
  70. 					} else {
  71. 						for(Integer i : listCandidateDigits) {
  72. 							recur((new StringBuffer(sbHead)).append(new Integer(i)), x + 1, 0, true);
  73. 						}
  74. 					}
  75. 				}
  76. 			} else if(k == 1) {
  77. 				int iLeftmost = strOrigA.charAt(x) - '0';
  78.  
  79. 				//	for special case
  80. 				if(sbHead.length() == 0 && iLeftmost - 1 == 0) {
  81. 					int iBorrowDigit = strOrigA.charAt(x + 1) - '0';
  82. 					if(iLeftmost * 10 + iBorrowDigit == 10) {
  83. 						for(int i = x + 1; i < strOrigA.length(); ++i) {
  84. 							sbHead.append("9");
  85. 						}
  86. 						listCandidateA.add(Long.parseLong(sbHead.toString()));
  87. 						return;
  88. 					} else {
  89. 						listCandidateDigits.add(new Integer(iLeftmost));
  90. 						recur((new StringBuffer(sbHead)).append(iLeftmost), x + 1, 0, false);
  91.  
  92. 						listCandidateDigits.add(new Integer(9));
  93. 						recur((new StringBuffer(sbHead)).append(9), x + 2, 0, false);
  94. 					}
  95. 				}
  96.  
  97. 				if(listCandidateDigits.contains(new Integer(iLeftmost))) {
  98. 					recur((new StringBuffer(sbHead)).append(iLeftmost), x + 1, 1, false);
  99. 				} else {
  100. 					listCandidateDigits.add(new Integer(iLeftmost));
  101. 					recur((new StringBuffer(sbHead)).append(iLeftmost), x + 1, 0, false);
  102. 					if(iLeftmost - 1 >= 0) {
  103. 						listCandidateDigits.add(new Integer(iLeftmost - 1));
  104. 						recur((new StringBuffer(sbHead)).append(iLeftmost - 1), x + 1, 0, false);
  105. 					}
  106. 				}
  107. 			} else {
  108. 				int iLeftmost = strOrigA.charAt(x) - '0';
  109. 				if(listCandidateDigits.contains(new Integer(iLeftmost))) {
  110. 					recur((new StringBuffer(sbHead)).append(iLeftmost), x + 1, k, false);
  111. 				} else {
  112. 					listCandidateDigits.add(new Integer(iLeftmost));
  113. 					recur((new StringBuffer(sbHead)).append(iLeftmost), x + 1, k - 1, false);
  114. 				}
  115. 			}
  116. 		}
  117. 	}
  118.  
  119.  
  120.  
  121. 	private static long input(long A, int k) {
  122. 		strOrigA = "" + A;
  123. 		if(countDigits(strOrigA) <= k) {
  124. 			return A;
  125. 		}
  126. 		origK = k;
  127. 		listCandidateA = new ArrayList<Long>();
  128. 		listCandidateDigits = new ArrayList<Integer>();
  129. 		recur(new StringBuffer(), 0, k, false);
  130.  
  131.  
  132. 		long answer = -1L;
  133. 		if(listCandidateA.size() > 0) {
  134. 			answer = listCandidateA.get(0);
  135. 			long distance = Math.abs(answer - A);
  136. 			for(int i = 1; i < listCandidateA.size(); ++i) {
  137. 				long tmp = Math.abs(listCandidateA.get(i) - A);
  138. 				if(tmp < distance) {
  139. 					distance = tmp;
  140. 					answer = listCandidateA.get(i);
  141. 				}
  142. 			}
  143. 		}
  144.  
  145. 		return answer;
  146. 	}
  147.  
  148. 	/**
  149. 	 * 回傳listOrig用到的數字List
  150. 	 * 
  151. 	 * @param List<Integer>
  152. 	 * @return List<Integer>
  153. 	 */
  154. 	private static int countDigits(String strOrig) {
  155. 		boolean ary[] = new boolean[10];
  156. 		StringBuffer sb = new StringBuffer();
  157. 		int len = strOrig.codePointCount(0, strOrig.length());
  158. 		for(int i = 0; i < len; ++i) {
  159. 			int x = strOrig.codePointAt(i) - '0';
  160. 			if(x < 10 && false == ary[x]) {
  161. 				ary[x] = true;
  162. 				sb.append(x);
  163. 			}
  164. 		}
  165. 		return sb.length();
  166. 	}
  167. }
  168.  
Success #stdin #stdout 0.08s 380352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3355798533
https://ideone.com/nOsGRz
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!