給定一個(gè)數(shù)字字符串?dāng)?shù)組弯囊，要求選取其中任意兩個(gè)字符串兩兩組合痰哨，選取的字符串中包含0-9的所有數(shù)字，找出符合要求的組合的總數(shù)
例如：
123456匾嘱，112233445566斤斧，123789，546821奄毡，025975折欠，15840911115600，5454545454522222211111
說(shuō)明：
該問(wèn)題的難點(diǎn)在于當(dāng)給定數(shù)字字符串較多時(shí)，例如10萬(wàn)個(gè)字符串锐秦，判斷時(shí)間容易較長(zhǎng)咪奖，必須進(jìn)行優(yōu)化，短時(shí)間內(nèi)給出結(jié)果
解決思路：
將給定字符串?dāng)?shù)組全部轉(zhuǎn)換為數(shù)字組合的數(shù)組
例如：字符串123456酱床，可以轉(zhuǎn)換為1羊赵，2，3扇谣，4昧捷，5，6的集合
字符串罐寨，112233445566也可以轉(zhuǎn)換為1靡挥，2，3鸯绿，4跋破，5，6的集合
這樣我們只需對(duì)1瓶蝴，2毒返，3，4舷手，5拧簸，6的集合進(jìn)行判斷，這樣會(huì)大大降低運(yùn)算的數(shù)量
// Complete the winningLotteryTicket function below.
//數(shù)字字符串?dāng)?shù)組，兩兩組合，包含0-9的所有數(shù)字翼虫，找出符合要求的組合的總數(shù)
static long winningLotteryTicket(String[] tickets) {
Map, Integer> map =new HashMap<>();
//解析所有字符串為數(shù)字集合并計(jì)數(shù)凝危，這么處理會(huì)極大的降低需要處理的集合的數(shù)量
//此方法在數(shù)據(jù)量極大時(shí)，會(huì)大幅度降低需要處理的數(shù)據(jù)的數(shù)量
Arrays.stream(tickets)
.forEach(ticket -> {
List numList =strToInt(ticket);
Integer cnt =map.get(numList);
cnt =null == cnt ?0 : cnt;
cnt++;
map.put(numList, cnt);
});
List> list =new ArrayList<>(map.keySet());
//集合中數(shù)字兩兩判斷，是否包含0-9的所有數(shù)字
//注:若單個(gè)結(jié)合本身就包含0-9的所有數(shù)字，需要做特殊處理
long totalSum = IntStream.range(0, list.size())
.mapToLong(i -> {
List listA =list.get(i);
long
countA =map.get(listA);
if
(isHasAll(listA)) {
long sum = IntStream.range(i +1, list.size())
.mapToLong(a ->map.get(list.get(a)))
.sum();
long
total = countA * sum;
total += LongStream.range(1, countA)
.sum();
return
total;
}
long sum = IntStream.range(i +1, list.size())
.filter(j ->isHasAll(listA, list.get(j)))
.mapToLong(j ->map.get(list.get(j)))
.sum();
return
countA * sum;
})
.sum();
return
totalSum;
}
/**
* 字符串轉(zhuǎn)換為數(shù)字集合，需去重兔乞，排序
*@param numStr
* @return
*/
private static List<Integer> strToInt(String numStr) {
return IntStream.range(0, numStr.length())
.map(i -> Integer.
parseInt(numStr.substring(i, i + 1)))
.distinct()
.sorted()
.boxed()
.collect(Collectors.
toList());
}
/**
* 判斷兩個(gè)數(shù)字結(jié)合是否包含0-9的所有數(shù)字
* @paramintsI
* @param intsJ
* @return
*/
public static boolean isHasAll(List<Integer> intsI, List intsJ) {
int[] buffer = IntStream.rangeClosed(0, 9)
.filter(i -> !
intsI.contains(i))
.toArray()
;
int[] result = Arrays.stream(buffer)
.filter(i -> !
intsJ.contains(i))
.toArray()
;
return null== result || result.length == 0;
}
/**
* 判斷單個(gè)數(shù)字結(jié)合是否包含0-9的所有數(shù)字
* @paramintsI
* @return
*/
public static boolean isHasAll(List intsI) {
int[] result = IntStream.rangeClosed(0, 9)
.filter(i -> !
intsI.contains(i))
.toArray()
;
return null== result || result.length == 0;
}
