LeetCode 周赛 217
LeetCode 1672. 最富有客户的资产总量
题目描述
给你一个m x n
的整数网格accounts
,其中accounts[i][j]
是第i
位客户在第j
家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。
客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
题解
先求每个数组的和,而后返回和中的最大值
代码
class Solution: def maximumWealth(self, accounts: List[List[int]]) -> int: return max([sum(a) for a in accounts])
LeetCode 1673. 找出最具竞争力的子序列
题目描述
给你一个整数数组 和一个正整数 ,返回长度为 且最具 竞争力 的 子序列。
数组的子序列是从数组中删除一些元素(可能不删除元素)得到的序列。
在子序列 和子序列 第一个不相同的位置上,如果 中的数字小于 中对应的数字,那么我们称子序列 比子序列 (相同长度下)更具 竞争力 。 例如,[1,3,4]
比[1,3,5]
更具竞争力,在第一个不相同的位置,也就是最后一个位置上, 小于 。
示例1
输入:nums = [3,5,2,6], k = 2
输出:[2,6]
解释:在所有可能的子序列集合{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}
中,[2,6]
最具竞争力。
示例2
输入:nums = [2,4,3,3,5,4,9,6], k = 4
输出:[2,3,3,4]
提示
题解
等价于找出 最小子序列,使用单调栈即可
代码
class Solution: def mostCompetitive(self, nums: List[int], k: int) -> List[int]: unused = len(nums) - k top = 0 stack = [] for num in nums: while len(stack) > 0 and num < stack[-1] and unused > 0: unused -= 1 stack.pop() if len(stack) < k: stack.append(num) else: unused -= 1 return stack
LeetCode 1674. 使数组互补的最少操作次数
题目描述
给你一个长度为 偶数 的整数数组 和一个整数 。每一次操作,你可以将 中的任何整数替换为 到 之间的另一个整数。
如果对于所有下标 (下标从 开始),nums[i] + nums[n - 1 - i]
都等于同一个数,则数组 是 互补的 。例如,数组 [1,2,3,4]
是互补的,因为对于所有下标 ,nums[i] + nums[n - 1 - i] = 5
。
返回使数组 互补 的 最少 操作次数。
示例1
输入:nums = [1,2,4,3], limit = 4
输出:1
解释:
经过 1 次操作,你可以将数组 nums 变成 [1,2,2,3](加粗元素是变更的数字): nums[0] + nums[3] = 1 + 3 = 4. nums[1] + nums[2] = 2 + 2 = 4. nums[2] + nums[1] = 2 + 2 = 4. nums[3] + nums[0] = 3 + 1 = 4. 对于每个 i ,nums[i] + nums[n-1-i] = 4 ,所以 nums 是互补的。
示例2
输入:nums = [1,2,2,1], limit = 2
输出:2
解释:
经过 2 次操作,你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ,因为 3 > limit 。
示例3
输入:nums = [1,2,1,2], limit = 2
输出:0
解释:
nums 已经是互补的。
题解
要确保 互补,首先需要确定每一对数的和,记为target
。
来看target
的取值可能。由于两个数可以被替换为 的数,所以
接下来,需要计算要把每一对数的和变成 target
需要的操作次数。记两个数分别为 和
- 操作 次:
- 操作 次:
- 操作 次: 其他情况
同时,题目规定了 ,这意味着不存在 很小,而数组所有数等很大,使得 ,但又可凑出的情况。
要完成该操作,时间复杂度为 根据题目要求,很显然会超时
考虑到,每次要验证的数存在 关系,因此如果可以根据该关系减少需要计算的数目,则会极大降低时间复杂度。
前缀数组
考虑如果需要得知操作 次的组数,只需要知道 为 的个数(这可以提前计算出所有 的和,并统计个数),故可以在 时间内计算出。
要得知操作 次的组数,只需要知道满足 的个数,整理式子可得
要快速统计出这个个数,可以统计所有 和 的个数。将两个对应的数相减在减去重复的操作 次的组数,即可快速得出该区间值。
对于操作 次的组数,由于总共只有 组,因此使用 ,即可快速得到该值。
也即问题转换为快速获取:
- 的组数
- 的组数
- 的组数
该问题可以通过提前统计不同 、、 个数,而后计算 、 个数即可。
该操作的时间复杂度为
差分数组
差分数组可以看作是反向的前缀数组,可以很方便实现区间的同加同减。在这道题里,代码会更为简洁。
如果需要将区间 同时加 ,那么在差分数组中,只需要将 , 即可(将原本的 操作变为 。
根据之前的分析,可以建立 数组统计不同的 的操作个数。对于一对 和 , 区间操作次数为 , 区间操作次数为 ,其余区间操作次数为 。
可以将区间简化为,整个加 , 区间减 ,并重置
相对于前缀数组,该方案省去了预处理的时间,时间复杂度为
代码
前缀数组思路
class Solution: def minMoves(self, nums: List[int], limit: int) -> int: n = len(nums) l = int(n / 2) sumab = {} # a + b 的个数 minab = {} # min(a, b) 的个数 maxab = {} # max(a, b) 的个数 for i in range(l): a = nums[i] b = nums[-i-1] a, b = min(a, b), max(a, b) sumab[a+b] = sumab.get(a+b, 0) + 1 minab[a] = minab.get(a, 0) + 1 maxab[b] = maxab.get(b, 0) + 1 maxpossible = 2*limit+1 leminab = [0] * maxpossible # <= min(a, b) 的个数 lemaxab = [0] * maxpossible # <= max(a, b) 的个数 for i in range(1, maxpossible): leminab[i] = leminab[i-1] + minab.get(i, 0) lemaxab[i] = lemaxab[i-1] + maxab.get(i, 0) # print(sumab) # print(minab) # print(maxab) # print(leminab) # print(lemaxab) res = n for target in range(2, maxpossible): op0 = sumab.get(target, 0) op1 = leminab[target - 1] - (lemaxab[target - limit - 1] if target - limit - 1 > 0 else 0) - op0 op2 = l - op0 - op1 # print(target, op0, op1, op2) res = min(res, op1+2*op2) return res
#define MAXN 100010 #define MAXN2 200020 int sumab[MAXN2]; int minab[MAXN]; int maxab[MAXN]; int leminab[MAXN]; int lemaxab[MAXN]; int minMoves(int* nums, int numsSize, int limit){ int l = numsSize / 2; memset(sumab, 0, sizeof(int)*MAXN2); memset(minab, 0, sizeof(int)*MAXN); memset(maxab, 0, sizeof(int)*MAXN); memset(leminab, 0, sizeof(int)*MAXN); memset(lemaxab, 0, sizeof(int)*MAXN); for (int i=0; i<l; ++i) { int a = nums[i]<nums[numsSize-i-1] ? nums[i] : nums[numsSize-i-1]; int b = nums[i]<nums[numsSize-i-1] ? nums[numsSize-i-1] : nums[i]; ++sumab[a+b]; ++minab[a]; ++maxab[b]; } int maxpossible = 2*limit+1; for (int i=1; i<=limit; ++i) { leminab[i] = leminab[i-1] + minab[i]; lemaxab[i] = lemaxab[i-1] + maxab[i]; } // for (int i=0; i<maxpossible; ++i) { // printf("%d %d %d %d %d %d\n", i, sumab[i], minab[i], maxab[i], leminab[i], lemaxab[i]); // } int res = numsSize; for (int target=2; target<maxpossible; ++target) { int op0 = sumab[target]; int op1 = (target-1 <= limit ? leminab[target-1] : leminab[limit]) - (target-limit-1>0 ? lemaxab[target-limit-1] : 0) - op0; int op2 = l - op0 - op1; res = op1+2*op2<res ? op1+2*op2 : res; // printf("%d %d %d %d\n", target, op0, op1, op2); } return res; }
差分数组思路
int minMoves(int* nums, int numsSize, int limit){ int l = numsSize / 2; int maxm = 2 * limit + 1; int *diff = malloc(sizeof(int) * (maxm + 1)); memset(diff, 0, sizeof(int) * (maxm + 1)); for (int i=0; i<l; ++i) { int a = fmin(nums[i], nums[numsSize-i-1]); int b = fmax(nums[i], nums[numsSize-i-1]); int sum = fmin(maxm, a + b); int temp = diff[sum]; // 所有 +2 diff[2] += 2; // [1+a, limit+b] -1 diff[1+a < maxm ? 1+a : maxm] -= 1; diff[limit+b+1 < maxm ? limit+b+1 : maxm] += 1; // a+b 保持不变 int t = 1+a <= sum && sum <= limit+b? 1 :2; diff[sum] -= t; diff[sum+1 < maxm ? sum+1 : maxm] += t; } int res = numsSize; for (int i=2; i<maxm; ++i) { diff[i] += diff[i-1]; res = fmin(res, diff[i]); } return res; }
LeetCode 1675. 数组的最小偏移量
题目描述
给你一个由 个正整数组成的数组 。
你可以对数组的任意元素执行任意次数的两类操作:
如果元素是 偶数 ,除以
例如,如果数组是 ,那么你可以对最后一个元素执行此操作,使其变成
如果元素是 奇数,乘上
例如,如果数组是 ,那么你可以对第一个元素执行此操作,使其变成
数组的 偏移量 是数组中任意两个元素之间的 最大差值。
返回数组在执行某些操作之后可以拥有的 最小偏移量。
示例 1
输入:nums = [1,2,3,4]
输出:1
解释:
你可以将数组转换为 [1,2,3,2],然后转换成 [2,2,3,2],偏移量是 3 - 2 = 1
示例 2
输入:nums = [4,1,5,20,3]
输出:3
解释:
两次操作后,你可以将数组转换为 [4,2,5,5,3],偏移量是 5 - 2 = 3
示例 3
输入:nums = [2,10,8]
输出:3
题解
数字变换规则为:
- 偶数: 可以执行除以 的操作
- 奇数: 可以执行乘以 的操作
最终使得整个数组的最大值和最小值差值最小。
根据上述规则,如果一个数 原本就是奇数,那么它只会在 和 反复横跳;而如果一个数 原本是偶数,那么它将存在一个奇因子 ,其会在所有 内横跳。
可以看出,奇数在这里至关重要。奇数 最终只能存在为 和 。而要想使得最终结果最小,需要将其他数尽可能靠近这些“固定的数”。也即奇数将确定了最终数组元素的大致大小。
由于同时维护扩大和缩小较为复杂,考虑到扩大只有一种情况,那么可以将扩大操作转换为缩小操作,使得我们只需要维护缩小操作。
也即,将所有的奇数扩大两倍维护。问题转换为 给定一个偶数数列,通过除 使得数列最值差最小
转换为这一步后,思路较为明显,由于只能缩小,因此根据贪心应该尝试缩小最大值。当最大值为奇数时,其无法缩小,因此操作只能缩小其他值,但无论缩小谁都会导致最值差变大。
最大值为奇数不一定就是最值差最小的解,但是最优解必然存在于这个变化过程中。
最坏情况下,数会被插入删除 次,采用二分法维护最大值和最小值的时间复杂度为 。故时间复杂度为
题解中,有人提出“对于偶数数列,全部除以 必定结果更优,因此可以根据此思路找到限定范围的那个奇数”,时间复杂度可以优化到 。可以参考一下它的思路
需要特别注意的是,由于维护最大值和最小值要求时间复杂度为 ,因此必须采用二分法来进行插入检索。同时必须采用链表维护该数据结构关系。
代码
func minimumDeviation(nums []int) int { root := NewTree() for _, num := range nums { if num & 1 == 1{ root = root.Insert(num << 1) } else { root = root.Insert(num) } } max, _ := root.Max() min, _ := root.Min() res := max - min for { if max & 1 == 1 { break } root, _ = root.Remove(max) root = root.Insert(max >> 1) max, _ = root.Max() min, _ = root.Min() if max - min < res { res = max - min } } return res } // Tree 平衡二叉树结构 type Tree struct { number int count int left *Tree right *Tree depth int } // NewTree 生成一个平衡二叉树 func NewTree() *Tree { return nil } // NewTreeNode 新建一个二叉树节点 func NewTreeNode(number int) *Tree { return &Tree{ number: number, count: 1, left: nil, right: nil, depth: 1, } } // Insert 向树内插入一个数 func (t *Tree) Insert(n int) *Tree { if t == nil { return NewTreeNode(n) } if n == t.number { // 就是当前值 t.count++ t.updateNode() return t } else if n > t.number { // 插到右边 t.right = t.right.Insert(n) } else { // 插到左边 t.left = t.left.Insert(n) } t.updateNode() return t.rotate() } // Remove 删除一个指定的元素(个数减一) func (t *Tree) Remove(n int) (*Tree, error) { if t == nil { return nil, fmt.Errorf("Can not find number %d in AVL Tree", n) } if n == t.number { t.count-- if t.count <= 0 { if t.left != nil && t.right != nil { minLeaf, tmp := t.right.removeLeft() minLeaf.left = t.left minLeaf.right = tmp minLeaf.updateNode() return minLeaf.rotate(), nil } else if t.left != nil { return t.left, nil } else { return t.right, nil } } return t, nil } else if n > t.number { var err error t.right, err = t.right.Remove(n) t.right.updateNode() return t.rotate(), err } else { var err error t.left, err = t.left.Remove(n) t.left.updateNode() return t.rotate(), err } } func (t *Tree) removeLeft() (minLeaf *Tree, newRoot *Tree) { if t.left == nil { minLeaf = t newRoot = t.right return } minLeaf, t.left = t.left.removeLeft() t.updateNode() newRoot = t.rotate() return } // Min 获取平衡二叉树的最小值 func (t *Tree) Min() (int, error) { if t == nil { return 0, fmt.Errorf("Can not get the min number in an empty AVL Tree") } tmp := t for tmp.left != nil { tmp = tmp.left } return tmp.number, nil } // Max 获取平衡二叉树的最大值 func (t *Tree) Max() (int, error) { if t == nil { return 0, fmt.Errorf("Can not get the max number in an empty AVL Tree") } tmp := t for tmp.right != nil { tmp = tmp.right } return tmp.number, nil } // Depth 获取平衡二叉树节点的深度 func (t *Tree) Depth() int { if t == nil { return 0 } return t.depth } // updateDepth 更新子树深度(左右子树深度必须已更新) func (t *Tree) updateDepth() { if t != nil { leftDepth := t.left.Depth() rightDepth := t.right.Depth() if leftDepth < rightDepth { t.depth = rightDepth + 1 } else { t.depth = leftDepth + 1 } } } func (t *Tree) updateNode() { if t != nil { t.updateDepth() } } // Rotate 尝试旋转树(如果需要) func (t *Tree) rotate() *Tree { if t == nil { return t } leftDepth := t.left.Depth() rightDepth := t.right.Depth() if leftDepth-rightDepth > 1 { // 左子树深度大于右子树深度 // 右旋 return t.rotateRight() } else if rightDepth-leftDepth > 1 { // 左子树深度小于右子树深度 // 左旋 return t.rotateLeft() } return t } // RotateRight 平衡二叉树右旋 func (t *Tree) rotateRight() *Tree { a := t b := a.left c := b.right a.left = c b.right = a a.updateNode() b.updateNode() return b } // RotateLeft 平衡二叉树左旋 func (t *Tree) rotateLeft() *Tree { a := t b := a.right c := b.left a.right = c b.left = a a.updateNode() b.updateNode() return b } // Count 获取指定节点存储的数字个数 func (t *Tree) Count() int { if t == nil { return 0 } return t.count } // Number 获取指定节点存储的数字内容 func (t *Tree) Number() int { if t == nil { return 0 } return t.number } // Print 打印二叉树 func (t *Tree) Print() { if t != nil { fmt.Printf("%d [%d %d] %d\n", t.Number(), t.left.Number(), t.right.Number(), t.Count()) t.left.Print() t.right.Print() } }
import queue class Solution: def minimumDeviation(self, nums: List[int]) -> int: nums = [num << 1 if num & 1 else num for num in nums] nums.sort() q = queue.PriorityQueue() for num in nums: q.put(-num) min_number, max_number = min(nums), max(nums) res = max_number - min_number while 1: max_number = -q.get() res = min(res, max_number - min_number) if max_number & 1: break max_number = int(max_number / 2) q.put(-max_number) min_number = min(max_number, min_number) return res