【华为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;
    }
}