【華為OD題庫-032】數字游戲-java

題目

小明玩一個游戲。系統發1+n張牌，每張牌上有一個整數。第一張給小明，后n張按照發牌順序排成連續的一行。需要小明判斷，后n張牌中，是否存在連續的若干張牌，其和可以整除小明手中牌上的數字.
輸入描述:
輸入數據有多組，每組輸入數據有兩行，輸入到文件結尾結束。
第一行有兩個整數n和m，空格隔開。m代表發給小明牌上的數字
第二行有n個數，代表后續發的n張牌上的數字，以空格隔開。
輸出描述:
對每組輸入，如果存在滿足條件的連續若干張牌，則輸出1:否則，輸出0
補充說明:
1<=n<= 1000
1<=牌上的整數<= 400000輸入的組數，不多于1000
用例確保輸入都正確，不需要考慮非法情況
示例1
輸入:
6 7
2 12 6 3 5 5
10 11
1 1 1 1 1 1 1 1 1 1
輸出
0
說明:
兩組輸入。
第一組小明牌的數字為7，再發了6張牌。第1、2兩張牌數字和為14，可以整除7，輸出1。
第二組小明牌的數字為11，再發了10張牌，這10張牌數字和為10，無法整除11，輸出0。

思路

以單組數據來看，對于給定數組nums，是否存在連續和能夠被指定k整除？可以想到一下幾種方案：

暴力破解
組合思想
前綴和

思路一：暴力破解

雙層循環：
外層i表示，依次以i開始的連續數組
內存循環變量j，初始值為i。求以i開始的連續數組的和，（即nums[i]+nums[i+1]+…+nums[j]），如果存在某個和能夠被k整除，那么返回1
兩層遍歷完了都沒有找到這樣的連續數組，那么返回0

思路二：組合思想

找到nums所有的子連續數組：組合思想可參考：【JAVA-排列組合】一個套路速解排列組合題。
剪枝的關鍵在于判斷數組是否連續，path中可以存放位置，如果是連續，那么path最后一個位置應該等于當前位置-1，即：i-1=path.peekLask();
如果某個子數組的和能夠被k整除，那么返回1，否則返回0

思路三：前綴和
參考leetcode原題：974. 和可被 K 整除的子數組
leetcode的題目考慮了負數，雖然本題的牌的數字不會有正數，但這里還是對正負數都考慮進來。

設P[i]為nums數組的前i項的和
對于sum(i,j)=num[i]+num[i+1]+…+num[j]=P[j]-P[i-1]。
假設nums的i~j區間的和能夠被k整除。
即：sum(i,j)%k==0，即（P[j]-P[i-1]）%k=0，
即：(P[j]%k - P[i-1]%k)%k=0。
考慮同為正負的情況：P[j]%k == P[i-1]%k時上式成立
如果一正一負：|P[j]%k - P[i-1]%k| = k時上式成立，假設P[j]%k為正，P[i-1]%k為負，那么去掉絕對值后表達式為：P[j]%k = k+P[i-1]%k
綜合正負數的情況，表達式可以寫為：(P[j]%k+k)%k == (k+P[i-1]%k)%k，即，當前綴和為s時，考慮s可能為負數的情況，那么對k求余數可以寫為： (s%k+k)%k

上面的推導可能比較抽象，現在以具體數據來說明過程：
假設我們的nums為：4 5 -4 -2 -7 -3 1，k為5。以下3行分別為nums，前綴和，對k求余（(s%k+k)%k）的結果：

依次遍歷nums，找到以當前nums[j]結尾的連續數組，判斷其和能夠整除k的數組有多少個？
j=0時，nums[j]=4，要滿足(P[j]%k - P[i-1]%k)%k=0，才能找到滿足條件的連續數組，現在P[j]%k=4，是否存在P[i-1]%k=4？i必須小于等于j，明顯不存在。
j=1時，P[j]%k=4，是否存在P[i-1]%k=4，即在j前面的求余結果是否有4，第一個為4，存在（i=1）。也就是說sum（1,1）能夠被5整除。
j=2時，P[j]%k=0，第三行在位置2之前是否存在0？根據上面的邏輯不存在，但是實際上此時余數都為0了，肯定是能被k整除的，可以在0的左側假設有P[-1]=0，這樣當余數為0時，就能保證一定能夠找到一個相同值，從而判斷為滿足條件。即sum(0,2)能夠被5整除
j=3,P[j]%k=3，前面找不到
j=4,P[j]%k=1，前面找不到
j=5,P[j]%k=3，找得到，當i=4時，P[3]%k=3，即sum（4,5）能夠被5整除
j=6,P[j]%k=4，在其前面能夠找到4，i分別為1和2時，P[0]%k=4，P[1]%k=4，即sum（1,6），sum（2,6）均能被5整除

綜上：我們可以用一個變量來存放前綴和%k出現的次數，比如map。然后遍歷nums，先求出當前的前綴和sum，再求余數mod=(sum%k+k)%k，然后在map中找是否存在map.get(mod)>0，如果存在，那么就找到了這樣的連續數組，如果不存在，則將map.get(mod)++后繼續查找。
前綴和%k的值域范圍剛好為：0~k-1，所以也可以用一個數組dp來代替map，它標識的含義是，mod值等于key出現了val次。考慮到要設P[-1]=0，即mod值為0在初始狀態就要出現一次，那么將dp[0]=1。

題解

給出了三種思路在本題的具體實現，前綴和確實很抽象，也不好表達，對此不理解的多看看974. 和可被 K 整除的子數組的題解

package hwod;import java.util.*;
import java.util.stream.Collectors;public class NumberGame {public static void main(String[] args) {Scanner sc = new Scanner(System.in);List<Integer> list1 = new ArrayList<>();//存放給定的牌List<List<Integer>> list2 = new ArrayList<>();//牌堆while (sc.hasNextLine()) {String firstLines = sc.nextLine();if ("".equals(firstLines)) break;list1.add(Arrays.stream(firstLines.split(" ")).mapToInt(Integer::parseInt).toArray()[1]);String secondLines = sc.nextLine();list2.add(Arrays.stream(secondLines.split(" ")).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList()));}List<Integer> res = numberGame(list1, list2);for (Integer re : res) {System.out.println(re);}}private static List<Integer> numberGame(List<Integer> list1, List<List<Integer>> list2) {List<Integer> res = new ArrayList<>();for (int i = 0; i < list1.size(); i++) {res.add(checked3(list2.get(i), list1.get(i)));}return res;}/*** 暴力破解* @param list   牌堆* @param target 被除的值* @return 如果存在連續和能夠整除target，返回1，否則返回0*/private static int checked(List<Integer> list, Integer target) {for (int i = 0; i < list.size(); i++) {int sum = 0;for (int j = i; j < list.size(); j++) {sum += list.get(j);if (sum % target == 0) return 1;}}return 0;}private static int res = 0;/*** 組合思想* @param list* @param target* @return*/private static int checked2(List<Integer> list, Integer target) {LinkedList<Integer> path = new LinkedList<>();dfs(list, 0, path, 0, target);return res;}private static void dfs(List<Integer> list, int start, LinkedList<Integer> path, int sum, int k) {if (!path.isEmpty() && sum % k == 0) {res = 1;return;}for (int i = start; i < list.size(); i++) {if (!path.isEmpty() && path.peekLast() != i - 1) continue;if (res != 0) break;path.addLast(i);dfs(list, i + 1, path, sum + list.get(i), k);path.removeLast();}}/*** 設P[i]為前i項的前綴和* sum(i,j)=num[i]+num[i+1]+...+num[j]=P[j]-p[i-1]* (P[j]-p[i])%k==0  ==>  (P[j]%k - p[i-1]%k)%k=0** @param list* @param k* @return 如果存在連續和能夠整除k，返回1，否則返回0*/private static int checked3(List<Integer> list, Integer k) {int[] dp = new int[k];dp[0] = 1;int sum = 0;for (int i = 0; i < list.size(); i++) {sum += list.get(i);int mod = (sum % k + k) % k;if (dp[mod] != 0) return 1;dp[mod]++;}return 0;}
}