前言:
目前大家对“数组分组java”大体比较注意,朋友们都需要了解一些“数组分组java”的相关知识。那么小编同时在网摘上汇集了一些有关“数组分组java””的相关内容,希望各位老铁们能喜欢,你们一起来学习一下吧!本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。
大家好,我是小彭。
上周末是 LeetCode 第 337 场周赛,你参加了吗?这场周赛第三题有点放水,如果按照题目的数据量来说最多算 Easy 题,但如果按照动态规划来做可以算 Hard 题。
小彭的技术交流群 02 群来了,公众号回复 “加群” 加入我们~
周赛概览
2595. 奇偶位数(Easy)
题解一:模拟 O(lgn)题解二:位掩码 + bitCount O(1)
2596. 检查骑士巡视方案(Medium)
题解一:模拟 O(n^2)
2597. 美丽子集的数目(Medium)
题解一:回溯 O(2^n)题解二:同余分组 + 动态规划 / 打家劫舍 O(nlgn)
2598. 执行操作后的最大 MEX(Medium)
题解一:同余分组 + 贪心 O(n)2595. 奇偶位数(Easy)题目地址
题目描述
给你一个 正 整数 n 。
用 even 表示在 n 的二进制形式(下标从 0 开始)中值为 1 的偶数下标的个数。
用 odd 表示在 n 的二进制形式(下标从 0 开始)中值为 1 的奇数下标的个数。
返回整数数组 answer ,其中 answer = [even, odd] 。
题解一(模拟)
简单模拟题。
写法 1:枚举二进制位
class Solution { fun evenOddBit(n: Int): IntArray { val ret = intArrayOf(0, 0) for (index in 0..30) { if (n and (1 shl index) != 0) { ret[index % 2]++ } } return ret }}
复杂度分析:
时间复杂度:O(U) 其中 U 是整数二进制位长度;空间复杂度:O(1) 仅使用常量级别空间。
写法 2:不断取最低位,然后右移 n,当 n 为 0 时跳出:
class Solution { fun evenOddBit(n: Int): IntArray { val ret = intArrayOf(0, 0) var x = n var index = 0 while (x != 0) { ret[i] += x and 1 // 计数 x = x ushr 1 // 右移 i = i xor 1 // 0 -> 1 或 1 -> 0 } return ret }}
复杂度分析:
时间复杂度:O(lgn)空间复杂度:O(1) 仅使用常量级别空间。题解二(位掩码 + bitCount)
使用二进制掩码 01010101 取出偶数下标,再使用 Integer.bitCount() 计算位 1 的个数:
class Solution { fun evenOddBit(n: Int): IntArray { val mask = 0b0101_0101_0101_0101_0101_0101_0101_0101 return intArrayOf( Integer.bitCount(n and mask), Integer.bitCount(n) - Integer.bitCount(n and mask) ) }}
复杂度分析:
时间复杂度:O(1) Java Integer.bitCount() 库函数的时间复杂度是 O(1),如果按照常规实现是 O(lgn);空间复杂度:O(1)2596. 检查骑士巡视方案(Medium)题目地址
题目描述
骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中,骑士会从棋盘的 左上角 出发,并且访问棋盘上的每个格子 恰好一次 。
给你一个 n x n 的整数矩阵 grid ,由范围 [0, n * n - 1] 内的不同整数组成,其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。
如果 grid 表示了骑士的有效巡视方案,返回 true;否则返回 false。
注意,骑士行动时可以垂直移动两个格子且水平移动一个格子,或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。
题解(模拟)
二维简单模拟题。
class Solution { fun checkValidGrid(grid: Array<IntArray>): Boolean { if (grid[0][0] != 0) return false val directions = arrayOf( intArrayOf(1, 2), intArrayOf(2, 1), intArrayOf(2, -1), intArrayOf(1, -2), intArrayOf(-1, -2), intArrayOf(-2, -1), intArrayOf(-2, 1), intArrayOf(-1, 2) ) val n = grid.size var row = 0 var column = 0 var count = 1 outer@ while (count < n * n) { for (direction in directions) { val newRow = row + direction[0] val newColumn = column + direction[1] if (newRow < 0 || newRow >= n || newColumn < 0 || newColumn >= n) continue if (count == grid[newRow][newColumn]) { row = newRow column = newColumn count++ continue@outer } } return false } return true }}
复杂度分析:
时间复杂度:O(C·n^2) 其中 C 是骑士的行走方向,C 为常数 8;空间复杂度:O(1)2597. 美丽子集的数目(Medium)题目地址
题目描述
给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
如果 nums 的子集中,任意两个整数的绝对差均不等于 k ,则认为该子数组是一个 美丽 子集。
返回数组 nums 中 非空 且 美丽 的子集数目。
nums 的子集定义为:可以经由 nums 删除某些元素(也可能不删除)得到的一个数组。只有在删除元素时选择的索引不同的情况下,两个子集才会被视作是不同的子集。
预备知识同余性质:
如果 x % m == y % m,则称 x 和 y 对模 m 同余,即为 x ≡ (y mod m)
乘法定理:
如果某个任务有 n 个环节,每个环节分别有 {m_1, m_2, m_3, …, m_n} 种方案,那么完成任务的总方案数就是 m_1m_2m3…m_n。
题解一(暴力回溯)
由于题目的数据量非常小(数组长度只有 20),所以可以直接使用暴力算法。
算法:枚举所有子集,并且增加约束条件:如果已经选择过 x - k 或 x + k,则不能选择 x。
class Solution { private var ret = 0 fun beautifulSubsets(nums: IntArray, k: Int): Int { subsets(nums, 0, k, IntArray(k + 1001 + k)/* 左右增加 k 避免数组下标越界 */) return ret - 1 // 题目排除空集 } // 枚举子集 private fun subsets(nums: IntArray, start: Int, k: Int, cnts: IntArray) { // 记录子集数 ret++ if (start == nums.size) return for (index in start until nums.size) { val x = nums[index] + k // 偏移 k if (cnts[x - k] != 0 || cnts[x + k] != 0) continue // 不允许选择 // 选择 cnts[x]++ // 递归 subsets(nums, index + 1, k, cnts) // 回溯 cnts[x]-- } }}
复杂度分析:
时间复杂度:O(2^n) 其中 n 为 nums 数组长度,每个位置有选和不选两种状态,每个状态的时间复杂度是 O(1),因此整体时间复杂度是 O(2^n);空间复杂度:O(C) 数组空间。题解二(同余分组 + 动态规划 / 打家劫舍)
这道题如果不使用暴力解法,难度应该算 Hard。
根据同余性质,如果 x 和 y 对模 k 同余,那么 x 和 y 有可能相差 k;如果 x 和 y 对模 k 不同余,那么 x 和 y 不可能相差 k。 因此,我们可以将原数组按照模 k 分组,然后单独计算每个分组内部方案数,再根据乘法定理将不同分组的方案数相乘即得到最终结果。
那么,现在的是如何计算分组内部的方案数?
我们发现,“如果已经选择过 x - k 或 x + k,则不能选择 x ” 的语义跟经典动态规划题 198.打家劫舍 的 “如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警” 的语义非常类似,我们可以套用相同的解题思路:
1、先对分组内部排序,因为只有相邻的数才有可能不能同时选择;
2、定义 dp[i] 表示选择到 i 为止的方案数,则有递推关系:
��[�]={��[�−1]+��[�−2]if ��−��−1=���[�−1]∗2if ��−��−1≠�
如果不选 a_i,那么 a_{i-1} 一定可选,即 dp[i-1] 的方案数。
如果选择 a_i,那么需要考虑 a_{i-1} 与 a_i 的关系:
如果 a_i - a_{i-1} =k,那么 a_i 与 a_{i-1} 不能同时选择,dp[i] = dp[i-1] + dp[i-2] 表示在 a_{i-1} 和 a_{i-2} 上的方案数之和;如果 a_i - a_{i-1} \not=k,那么 a_i 与 a_{i-1} 可以同时选择 dp[i] = dp[i-1]*2
最后,还需要考虑数字重复的情况,设 c_i 表示 a_i 的出现次数:
如果不选 a_i,则只有 1 种方案,即空集;如果选择 ai_i,则有 2^{c_i} 种方案,最后在减去 1 个空集方案。
整理到递归公式中有:
��[�]={��[�−1]+��[�−2]∗(2��−1)if ��−��−1=���[�−1]∗(2��)if ��−��−1≠�
以 [2, 3, 4, 5, 10], k = 2 为例,按照模 2 分组后:
余数为 0 的分组 [2, 4, 10]:方案为 [2]、[4]、[10]、[2, 10]、[4, 10]余数为 1 的分组 [3, 5]:方案为 [3]、[5]
class Solution { fun beautifulSubsets(nums: IntArray, k: Int): Int { // 1、同余分组 // <余数 to <元素,元素计数>> val buckets = HashMap<Int, TreeMap<Int, Int>>() for (num in nums) { val cntMap = buckets.getOrPut(num % k) { TreeMap<Int, Int>() } cntMap[num] = cntMap.getOrDefault(num, 0) + 1 } // 2、枚举分组 var ret = 1 for ((_, bucket) in buckets) { // 3、动态规划 val n = bucket.size // dp[i] 表示选择到 i 位置的方案数,这里使用滚动数组写法 // val dp = IntArray(n + 1) var pre2 = 0 // dp[i-2] var pre1 = 1 // dp[i-1] var index = 1 var preNum = -1 for ((num, cnt) in bucket) { if (index > 1 && num - preNum == k) { // a_i 不可选 val temp = pre1 pre1 = pre1 + pre2 * ((1 shl cnt) - 1) pre2 = temp } else { // a_i 可选可不选 val temp = pre1 pre1 = pre1 * (1 shl cnt) pre2 = temp } preNum = num index++ } ret *= pre1 } return ret - 1 }}
复杂度分析:
时间复杂度:O(nlgn + n) 其中 n 为 nums 数组的长度,使用有序集合进行分组的时间复杂度是 O(nlgn),枚举分组的步骤每个元素最多访问一次,时间复杂度是 O(n);空间复杂度 O(n):有序集合空间 O(n),动态规划过程中使用滚动数组空间为 O(1)。
相似题目
78. 子集784. 字母大小写全排列198. 打家劫舍
近期周赛子集问题:
LeetCode 周赛 333 · 无平方子集计数(Medium)
2598. 执行操作后的最大 MEX(Medium)题目地址
题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。
在一步操作中,你可以对 nums 中的任一元素加上或减去 value 。
例如,如果 nums = [1,2,3] 且 value = 2 ,你可以选择 nums[0] 减去 value ,得到 nums = [-1,2,3] 。
数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。
例如,[-1,2,3] 的 MEX 是 0 ,而 [1,0,3] 的 MEX 是 2 。
返回在执行上述操作 任意次 后,nums **的最大 MEX 。
预备知识同余性质:
如果 x % m == y % m,则称 x 和 y 对模 m 同余,即为 x ≡ (y mod m)
负数取模技巧:
如果 x 和 y 都大于 0,则 x ≡ (y mod m) 等价于 x % m == y % m
10%3==1−4%3==1
如果 x 和 y 都小于 0,则 x ≡ (y mod m) 等价于 x % m == y % m
−10%3==−1−4%3==−1
如果 x < 0,而 y≥0,则 x ≡ (y mod m) 等价于 x % m + m == y % m
−10%3==−1+3==2−4%3==−1+3==25%3==2
可以看到,为了避免考虑正负数,可以统一使用 (x % m + m) % m 对 x 取模,如此无论 x 为正负数,余数都能转换到 [0,m) 范围内。
题解(同余分组 + 贪心)
这道题依然考同余性质。
根据同余性质,如果 x 和 y 对模 value 同余,那么经过若干次操作后 x 总能转换为 y。如果 x 和 y 对模 value 不同余,那么无论经过多少次操作 x 也无法转换为 y。
举个例子:{-10、-4、-1、2、5} 都对模 3 同余,而 1 对模 3 不同余。只要经过若干次 +value/-value,总能转换为同余的其他数;
-10 + 3 * 2 = -4-10 + 3 * 3 = -1-10 + 3 * 4 = 2-10 + 3 * 5 = 5其它同理。-10 无法转换为 1
贪心思路:继续分析题目,由于不同分组中的数不可能转换为其它分组的数,为了让目标 “确实的最小非负整数尽可能大”,应该取尽可能小的同余数,否则无法使结果更优。
举个例子,假设 value 为 3,且不同分组的个数如下:
余数为 0 的分组中有 3 个元素:应该取 0、3、6余数为 1 的分组中有 4 个元素:应该取 1、4、7、10余数为 2 的分组中有 1 个元素:应该取 2、[缺失 5]
如果余数为 0 的分组取 0、6、9,则缺失的元素会变成 4。
class Solution { fun findSmallestInteger(nums: IntArray, value: Int): Int { // 同余分组 val buckets = HashMap<Int, Int>() for (num in nums) { val mod = (num % value + value) % value buckets[mod] = buckets.getOrDefault(mod, 0) + 1 } // 试错 var mex = 0 while (true) { val mod = mex % value // mex 一定是非负数 buckets[mod] = buckets.getOrDefault(mod, 0) - 1 // 计数不足 if (buckets[mod]!! < 0) break mex++ } return mex }}
复杂度分析:
时间复杂度:O(n) 其中 n 为 nums 数组的长度,计数时间为 O(n),试错最多尝试 n 次,整体时间复杂度为 O(n);空间复杂度:O(value) 散列表最多记录 value 个分组。
相似题目:
264. 丑数 II
OK,这场周赛就讲这么多,我们下周见。
标签: #数组分组java