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

题目描述

给你一个整数数组 numsnums 和一个正整数 kk,返回长度为 kk 且最具 竞争力numsnums 子序列。

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

在子序列 aa 和子序列 bb 第一个不相同的位置上,如果 aa 中的数字小于 bb 中对应的数字,那么我们称子序列 aa 比子序列 bb(相同长度下)更具 竞争力 。 例如,[1,3,4][1,3,5]更具竞争力,在第一个不相同的位置,也就是最后一个位置上,44 小于 55

示例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<=1051 <= nums.length <= 10^5
  • 0<=nums[i]<=1090 <= nums[i] <= 10^9
  • 1<=k<=nums.length1 <= 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. 使数组互补的最少操作次数

题目描述

给你一个长度为 偶数 nn 的整数数组 numsnums 和一个整数 limitlimit 。每一次操作,你可以将 numsnums 中的任何整数替换为 11 到 limitlimit 之间的另一个整数。

如果对于所有下标 ii(下标从 00 开始),nums[i] + nums[n - 1 - i] 都等于同一个数,则数组 numsnums互补的 。例如,数组 [1,2,3,4] 是互补的,因为对于所有下标 iinums[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][1,limit] 的数,所以 target[2,2×limit]target \in [2, 2 \times limit]

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

  • 操作 00 次: a+b=targeta+b = target
  • 操作 11 次: 1+min(a,b)targetlimit+max(a,b)1 + min(a,b) \le target \le limit + max(a,b)
  • 操作 22 次: 其他情况

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

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

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

前缀数组

考虑如果需要得知操作 00 次的组数,只需要知道 a+ba+btargettarget 的个数(这可以提前计算出所有 a+ba+b 的和,并统计个数),故可以在 O(1)O(1) 时间内计算出。

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

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

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

  • a+b=targeta+b = target 的组数
  • min(a,b)target1min(a,b) \le target-1 的组数
  • max(a,b)targetlimitmax(a,b) \ge target-limit 的组数

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

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

差分数组

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

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

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

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

相对于前缀数组,该方案省去了预处理的时间,时间复杂度为 O(n)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. 数组的最小偏移量

题目描述

给你一个由 nn 个正整数组成的数组 numsnums

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

如果元素是 偶数 ,除以 22
例如,如果数组是 [1,2,3,4][1,2,3,4],那么你可以对最后一个元素执行此操作,使其变成 [1,2,3,2][1,2,3,2]
如果元素是 奇数,乘上 22
例如,如果数组是 [1,2,3,4][1,2,3,4],那么你可以对第一个元素执行此操作,使其变成 [2,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

题解

数字变换规则为:

  • 偶数: 可以执行除以 22 的操作
  • 奇数: 可以执行乘以 22 的操作

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

根据上述规则,如果一个数 nn 原本就是奇数,那么它只会在 nn2×n2 \times n 反复横跳;而如果一个数 nn 原本是偶数,那么它将存在一个奇因子 mm,其会在所有 m×2km \times 2^k 内横跳。

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

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

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

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

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

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

需要特别注意的是,由于维护最大值和最小值要求时间复杂度为 O(n)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