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. 找出最具竞争力的子序列

题目描述

给你一个整数数组 $nums$ 和一个正整数 $k$ ，返回长度为 $k$ 且最具 竞争力 的 $nums$ 子序列。

数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。

在子序列 $a$ 和子序列 $b$ 第一个不相同的位置上，如果 $a$ 中的数字小于 $b$ 中对应的数字，那么我们称子序列 $a$ 比子序列 $b$ （相同长度下）更具 竞争力 。例如，[1,3,4]比[1,3,5]更具竞争力，在第一个不相同的位置，也就是最后一个位置上， $4$ 小于 $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]

提示

$1 <= nums.length <= 10^5$
$0 <= nums[i] <= 10^9$
$1 <= k <= nums.length$

题解

等价于找出 最小子序列，使用单调栈即可

代码

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. 使数组互补的最少操作次数

题目描述

给你一个长度为偶数 $n$ 的整数数组 $nums$ 和一个整数 $limit$ 。每一次操作，你可以将 $nums$ 中的任何整数替换为 $1$ 到 $limit$ 之间的另一个整数。

如果对于所有下标 $i$ （下标从 $0$ 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 $nums$ 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 $i$ ，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的取值可能。由于两个数可以被替换为 $[1,limit]$ 的数，所以 $target \in [2, 2 \times limit]$

接下来，需要计算要把每一对数的和变成 target 需要的操作次数。记两个数分别为 $a$ 和 $b$

操作 $0$ 次： $a+b = target$
操作 $1$ 次： $1 + min(a,b) \le target \le limit + max(a,b)$
操作 $2$ 次：其他情况

同时，题目规定了 $nums[i] \le limit$ ，这意味着不存在 $limit$ 很小，而数组所有数等很大，使得 $target > 2 \times limit$ ，但又可凑出的情况。

要完成该操作，时间复杂度为 $O(limit * length)$ 根据题目要求，很显然会超时

考虑到，每次要验证的数存在 $+1$ 关系，因此如果可以根据该关系减少需要计算的数目，则会极大降低时间复杂度。

前缀数组

考虑如果需要得知操作 $0$ 次的组数，只需要知道 $a+b$ 为 $target$ 的个数（这可以提前计算出所有 $a+b$ 的和，并统计个数），故可以在 $O(1)$ 时间内计算出。

要得知操作 $1$ 次的组数，只需要知道满足 $1+min(a,b) \le target \le limit + max(a,b)$ 的个数，整理式子可得
$\begin{cases}min(a,b) \le target-1\\ target - limit \le max(a,b)\end{cases}$
要快速统计出这个个数，可以统计所有 $\le min(a, b)$ 和 $\le max(a,b)$ 的个数。将两个对应的数相减在减去重复的操作 $0$ 次的组数，即可快速得出该区间值。

对于操作 $2$ 次的组数，由于总共只有 $n/2$ 组，因此使用 $n/2-op0-op1$ ，即可快速得到该值。

也即问题转换为快速获取：

$a+b = target$ 的组数
$min(a,b) \le target-1$ 的组数
$max(a,b) \ge target-limit$ 的组数

该问题可以通过提前统计不同 $a+b$ 、 $min(a,b)$ 、 $max(a,b)$ 个数，而后计算 $\le min(a,b)$ 、 $\le max(a,b)$ 个数即可。

该操作的时间复杂度为 $O(limit + length)$

差分数组

差分数组可以看作是反向的前缀数组，可以很方便实现区间的同加同减。在这道题里，代码会更为简洁。

如果需要将区间 $[a,b]$ 同时加 $5$ ，那么在差分数组中，只需要将 $\text{diff}[a] += 5$ ， $\text{diff}[b+1] -= 5$ 即可（将原本的 $O(n)$ 操作变为 $O(1)$ 。

根据之前的分析，可以建立 $res[2\times limit]$ 数组统计不同的 $target$ 的操作个数。对于一对 $a$ 和 $b$ ， $[a+b, a+b]$ 区间操作次数为 $0$ ， $[1+min(a,b), limit+max(a,b)]$ 区间操作次数为 $1$ ，其余区间操作次数为 $2$ 。

可以将区间简化为，整个加 $2$ ， $[1+min(a,b), limit+max(a,b)]$ 区间减 $1$ ，并重置 $\text{diff}[a+b]$

相对于前缀数组，该方案省去了预处理的时间，时间复杂度为 $O(n)$

代码

前缀数组思路

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. 数组的最小偏移量

题目描述

给你一个由 $n$ 个正整数组成的数组 $nums$ 。

你可以对数组的任意元素执行任意次数的两类操作：

如果元素是偶数，除以 $2$
例如，如果数组是 $[1,2,3,4]$ ，那么你可以对最后一个元素执行此操作，使其变成 $[1,2,3,2]$
如果元素是奇数，乘上 $2$
例如，如果数组是 $[1,2,3,4]$ ，那么你可以对第一个元素执行此操作，使其变成 $[2,2,3,4]$
数组的 偏移量 是数组中任意两个元素之间的 最大差值。

返回数组在执行某些操作之后可以拥有的 最小偏移量。

示例 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

题解

数字变换规则为：

偶数: 可以执行除以 $2$ 的操作
奇数: 可以执行乘以 $2$ 的操作

最终使得整个数组的最大值和最小值差值最小。

根据上述规则，如果一个数 $n$ 原本就是奇数，那么它只会在 $n$ 和 $2 \times n$ 反复横跳；而如果一个数 $n$ 原本是偶数，那么它将存在一个奇因子 $m$ ，其会在所有 $m \times 2^k$ 内横跳。

可以看出，奇数在这里至关重要。奇数 $n$ 最终只能存在为 $n$ 和 $2n$ 。而要想使得最终结果最小，需要将其他数尽可能靠近这些“固定的数”。也即奇数将确定了最终数组元素的大致大小。

由于同时维护扩大和缩小较为复杂，考虑到扩大只有一种情况，那么可以将扩大操作转换为缩小操作，使得我们只需要维护缩小操作。

也即，将所有的奇数扩大两倍维护。问题转换为 给定一个偶数数列，通过除 $2$ 使得数列最值差最小

转换为这一步后，思路较为明显，由于只能缩小，因此根据贪心应该尝试缩小最大值。当最大值为奇数时，其无法缩小，因此操作只能缩小其他值，但无论缩小谁都会导致最值差变大。
最大值为奇数不一定就是最值差最小的解，但是最优解必然存在于这个变化过程中。

最坏情况下，数会被插入删除 $log(a_i)$ 次，采用二分法维护最大值和最小值的时间复杂度为 $O(log(n))$ 。故时间复杂度为 $O(nlog(n)log(a_{max}))$

题解中，有人提出“对于偶数数列，全部除以 $2$ 必定结果更优，因此可以根据此思路找到限定范围的那个奇数”，时间复杂度可以优化到 $O(n(log(n)+log(a_{max})))$ 。可以参考一下它的思路

需要特别注意的是，由于维护最大值和最小值要求时间复杂度为 $O(n)$ ，因此必须采用二分法来进行插入检索。同时必须采用链表维护该数据结构关系。

代码

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