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. 	public static void main(String[] args) {
  23.  
  24. //		long A = 3355798521L;
  25. //		int k = 10;
  26. //		long A = 262004L;
  27. //		int k = 2;
  28. //		long A = 8000L;
  29. //		int k = 1;
  30. //		long A = 1000L;
  31. //		int k = 1;
  32. //		long A = 2243L;
  33. //		int k = 2;
  34. 		long A = 88449L;
  35. 		int k = 2;
  36. //		long A = 123456789L;
  37. //		int k = 1;
  38. 		out.println(input(A, k));
  39. 	}
  40.  
  41. 	private static long input(long A, int k) {
  42. 		List<Long> listCandidates = new ArrayList<Long>();
  43. 		String strA = "" + A;
  44. 		int len = strA.codePointCount(0, strA.length());
  45. 		for(int i = len - 1; i >= 0; --i) {
  46. 			List<Integer> listHead = new ArrayList<Integer>();
  47. 			List<Integer> listTail = new ArrayList<Integer>();
  48. 			for(int j = 0; j < i; ++j) {
  49. 				listHead.add(new Integer(strA.codePointAt(j) - '0'));
  50. 			}
  51. 			for(int j = i; j < len; ++j) {
  52. 				listTail.add(new Integer(strA.codePointAt(j) - '0'));
  53. 			}
  54. 			//int lenTail = listTail.size();
  55. 			long mid = listIntegerToLong(listTail).longValue();
  56. 			for(long lower = mid; lower >= 0L; --lower) {
  57. 				List<Integer> listLower = longConnectToList(listHead, lower, len);
  58. 				if(countDigits(listLower).size() <= k) {
  59. 					listCandidates.add(listIntegerToLong(listLower));
  60. 					break;
  61. 				}
  62. 			}
  63. 			StringBuffer sb = new StringBuffer("");
  64. 			for(int j = 0; j < listTail.size(); ++j) {
  65. 				sb.append("9");
  66. 			}
  67. 			long mask = 0L;
  68. 			if(sb.length() > 0) {
  69. 				mask = Long.parseLong(sb.toString());
  70. 			}
  71. 			for(long higher = mid + 1; higher <= mask; ++higher) {
  72. 				List<Integer> listLower = longConnectToList(listHead, higher, len);
  73. 				if(countDigits(listLower).size() <= k) {
  74. 					listCandidates.add(listIntegerToLong(listLower));
  75. 					break;
  76. 				}
  77. 			}
  78. 		}
  79.  
  80. 		long answer = -1L;
  81. 		if(listCandidates.size() > 0) {
  82. 			answer = listCandidates.get(0);
  83. 			long distance = Math.abs(answer - A);
  84. 			for(int i = 1; i < listCandidates.size(); ++i) {
  85. 				long tmp = Math.abs(listCandidates.get(i) - A);
  86. 				if(tmp < distance) {
  87. 					distance = tmp;
  88. 					answer = listCandidates.get(i);
  89. 				}
  90. 			}
  91. 		}
  92.  
  93. 		return answer;
  94. 	}
  95.  
  96. 	/**
  97. 	 * 回傳listOrig用到的數字List
  98. 	 * 
  99. 	 * @param List<Integer>
  100. 	 * @return List<Integer>
  101. 	 */
  102. 	private static List<Integer> countDigits(List<Integer> listOrig) {
  103. 		boolean ary[] = new boolean[10];
  104. 		List<Integer> list = new ArrayList<Integer>();
  105. 		for(Integer i : listOrig) {
  106. 			int x = i.intValue();
  107. 			if(x < 10 && false == ary[x]) {
  108. 				ary[x] = true;
  109. 				list.add(new Integer(x));
  110. 			}
  111. 		}
  112. 		return list;
  113. 	}
  114.  
  115.  
  116. 	/**
  117. 	 * 將List<Integer>轉換成Long
  118. 	 * 
  119. 	 * @param listI
  120. 	 * @return
  121. 	 */
  122. 	private static Long listIntegerToLong(List<Integer> listI) {
  123. 		long ret = 0L;
  124. 		long t = 1L;
  125. 		for(int i = listI.size() - 1; i >= 0; --i) {
  126. 			ret += t * listI.get(i).longValue();
  127. 			t *= 10L;
  128. 		}
  129. 		return new Long(ret);
  130. 	}
  131.  
  132. 	/**
  133. 	 * 把尾數串接到List後
  134. 	 * 
  135. 	 * @param listI
  136. 	 * @param value
  137. 	 * @param sz
  138. 	 * @return
  139. 	 */
  140. 	private static List<Integer> longConnectToList(List<Integer> listI, long value, int sz) {
  141. 		List<Integer> list = new ArrayList<Integer>();
  142. 		if(sz > 0) {
  143. 			for(int i = 0; i < sz; ++i) {
  144. 				list.add(new Integer(0));
  145. 			}
  146. 			while(sz > 0) {
  147. 				if(value > 0) {
  148. 					long mod = value % 10;
  149. 					list.set(sz - 1, new Integer((int)mod));
  150. 					value /= 10;
  151. 				} else if(sz - 1 < listI.size()) {
  152. 					list.set(sz - 1, new Integer(listI.get(sz - 1).intValue()));
  153. 				}
  154. 				--sz;
  155. 			}
  156. 			while(list.size() > 1 && list.get(0).intValue() == 0) {
  157. 				list.remove(0);
  158. 			}
  159. 		}
  160. 		return list;
  161. 	}
  162.  
  163. }
  164.  
Success #stdin #stdout 0.08s 380352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
88448
https://ideone.com/W6yVee
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!