dw做网站简单首页,天价索赔背后的平台版权对垒,h5在线网站建设,网络上哪里可以做推广题目 小明玩一个游戏。系统发1n张牌#xff0c;每张牌上有一个整数。第一张给小明#xff0c;后n张按照发牌顺序排成连续的一行。需要小明判断#xff0c;后n张牌中#xff0c;是否存在连续的若干张牌#xff0c;其和可以整除小明手中牌上的数字. 输入描述: 输入数据有多组…题目 小明玩一个游戏。系统发1n张牌每张牌上有一个整数。第一张给小明后n张按照发牌顺序排成连续的一行。需要小明判断后n张牌中是否存在连续的若干张牌其和可以整除小明手中牌上的数字. 输入描述: 输入数据有多组每组输入数据有两行输入到文件结尾结束。 第一行有两个整数n和m空格隔开。m代表发给小明牌上的数字 第二行有n个数代表后续发的n张牌上的数字以空格隔开。 输出描述: 对每组输入如果存在满足条件的连续若干张牌则输出1:否则输出0 补充说明: 1n 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[i1]…nums[j]如果存在某个和能够被k整除那么返回1 两层遍历完了都没有找到这样的连续数组那么返回0 思路二组合思想 找到nums所有的子连续数组组合思想可参考【JAVA-排列组合】一个套路速解排列组合题。 剪枝的关键在于判断数组是否连续path中可以存放位置如果是连续那么path最后一个位置应该等于当前位置-1即i-1path.peekLask(); 如果某个子数组的和能够被k整除那么返回1否则返回0 思路三前缀和 参考leetcode原题974. 和可被 K 整除的子数组 leetcode的题目考虑了负数虽然本题的牌的数字不会有正数但这里还是对正负数都考虑进来。 设P[i]为nums数组的前i项的和 对于sum(i,j)num[i]num[i1]…num[j]P[j]-P[i-1]。 假设nums的i~j区间的和能够被k整除。 即sum(i,j)%k0即P[j]-P[i-1]%k0 即(P[j]%k - P[i-1]%k)%k0。 考虑同为正负的情况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 kP[i-1]%k 综合正负数的情况表达式可以写为(P[j]%kk)%k (kP[i-1]%k)%k即当前缀和为s时考虑s可能为负数的情况那么对k求余数可以写为 (s%kk)%k 上面的推导可能比较抽象现在以具体数据来说明过程 假设我们的nums为4 5 -4 -2 -7 -3 1k为5。以下3行分别为nums前缀和对k求余(s%kk)%k的结果 依次遍历nums找到以当前nums[j]结尾的连续数组判断其和能够整除k的数组有多少个 j0时nums[j]4要满足(P[j]%k - P[i-1]%k)%k0才能找到满足条件的连续数组现在P[j]%k4是否存在P[i-1]%k4i必须小于等于j 明显不存在。 j1时P[j]%k4是否存在P[i-1]%k4即在j前面的求余结果是否有4第一个为4存在i1。也就是说sum1,1能够被5整除。 j2时P[j]%k0第三行在位置2之前是否存在0根据上面的逻辑不存在但是实际上此时余数都为0了肯定是能被k整除的可以在0的左侧假设有P[-1]0这样当余数为0时就能保证一定能够找到一个相同值从而判断为满足条件。即sum(0,2)能够被5整除 j3,P[j]%k3前面找不到 j4,P[j]%k1前面找不到 j5,P[j]%k3找得到当i4时P[3]%k3即sum4,5能够被5整除 j6,P[j]%k4在其前面能够找到4i分别为1和2时P[0]%k4P[1]%k4即sum1,6sum2,6均能被5整除 综上我们可以用一个变量来存放前缀和%k出现的次数比如map。然后遍历nums先求出当前的前缀和sum再求余数mod(sum%kk)%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);ListInteger list1 new ArrayList();//存放给定的牌ListListInteger 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()));}ListInteger res numberGame(list1, list2);for (Integer re : res) {System.out.println(re);}}private static ListInteger numberGame(ListInteger list1, ListListInteger list2) {ListInteger 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(ListInteger 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(ListInteger list, Integer target) {LinkedListInteger path new LinkedList();dfs(list, 0, path, 0, target);return res;}private static void dfs(ListInteger list, int start, LinkedListInteger 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[i1]...num[j]P[j]-p[i-1]* (P[j]-p[i])%k0 (P[j]%k - p[i-1]%k)%k0** param list* param k* return 如果存在连续和能够整除k返回1否则返回0*/private static int checked3(ListInteger 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;}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
