Leetcode程式紀錄

Numbers With Equal Digit Sum

簡單說明：給定一個陣列(array)，該array裡面皆為數字組成，每個數字的位數間做總和，相同的成一組。每組至少兩個數字或以上，如果沒有，則不算成組，若全部都沒有成組，則回傳一個-1；若有成組，則將該組最大與次大的兩個數字做加總，比較其他組看誰的加總最大，便回傳該值。
example
A=[51,71,17,42], the function should return 93. There are two pairs of numbers whose digits add up to an equal sum: (51, 42) and (17,71). The first pair sums up to 93.
B=[42,33,60], the function should return 102. The digits of all numbers in A add up to the same sum, and choosing to add 42 and 60 gives the result 102.
C=[51,32,43], the function should return -1, since all numbers in A have digits that add up to different, unique sums.

在這邊我做一個code紀錄，如果有更厲害的朋友可以指教。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static int solution(int[] A) {
	long startTime = System.nanoTime(); // 測試時間
	HashMap<Integer, ArrayList<Integer>> entity = new HashMap<>();
	ArrayList<Integer> list;
	for(int i=0 ; i<A.length ; i++) {
		int total = addAllDigit(A[i]); // 每一位數字相加
		// 先找尋entity的key有沒有相同的
		if(entity.containsKey(total)) { // 有相同
			// 拿出原本map裡的list
			ArrayList<Integer> internal = entity.get(total);
			internal.add(A[i]);
			// 覆蓋存回該map裡面
			entity.put(total, internal);
		} else { // 沒有相同
			list = new ArrayList<>();
			list.add(A[i]);
			entity.put(total, list);
		}
	}
	int biggest = -1;
	for(Integer value : entity.keySet()) {
		Integer array[] = (entity.get(value)).toArray(new Integer[0]);
		int total = addTwoNumberBiggest(array);
		if(total != -1 && total>biggest) {
			biggest = total;
		}
	}
	long endTime = System.nanoTime(); // 測試時間
	System.out.println("spend Time :" + (endTime-startTime)/1000000);
	return biggest;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 每一位數字相加
public static int addAllDigit(int number) {
	int flag=1;
	int result=0;
	result += number%10;
	number = number/10;
	while(flag != -1) {
		result += number%10;
		if((number/10) != 0) {
			number = number/10;
		} else {
			flag = -1;
		}
	}
	return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
	// 一個list裡面存在的兩數相加最大 / 若只存在一個數字, 因為無法相加所以回傳-1
	public static int addTwoNumberBiggest(Integer[] A) {
		Integer copyArray[] = Arrays.copyOf(A, A.length);
		Arrays.sort(copyArray);
		if(copyArray.length < 2) {
			return -1;
		}
		return copyArray[copyArray.length-2]+copyArray[copyArray.length-1];
		// 會影響到原先的array
//		Arrays.sort(A);
//		return A[A.length-2]+A[A.length-1];
	}