标签：12 17 int mid students sandwiches 数组 2023 c1

LeetCode 每日一题

746. 使用最小花费爬楼梯

问题

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

解答

本体是很显然的 DP 问题。

对于某一台阶 i，可以从两种状态转移而来，要么是 i - 1，要么是 i - 2。故而可以得到状态转移方程：\(f_i = min(f_{i - 1}, f_{i - 2}) + cost_i, i > 1; f_1 = f_0 = 0\)

正常来说，要使用 DP 需要先证明，一般性的证明可以参考2023-12-15 每天一练的 2789. 合并后数组中的最大元素解答。不过若是做题的话可以不用证明，但是在没有思路怎么选择 DP 参数（一般而言，其参数为 位置 + 属性）时，不妨证明一下，证明过程可能会带给你新的感悟

最优子结构的证明：
设 \(f = f_n\) 是该问题中台阶为 n 的最优解且 \(f_{n - 1}\)，不是台阶为 n - 1 时的最优解，假设台阶为 n - 1 时的最优解为 \(f'_{n - 1}\)，那可以将 \(f_{n - 1}\) 替换成 \(f'_{n - 1}\)，则有 \(f' = f'_n = min(f'_{n - 1}, f_{n - 2} + cost_n\)，若 \(f'_{n - 1} < f_{n - 2}\)，则 \(f'\) 变成最优解，这与假设矛盾，故而该问题拥有最优子结构，可以使用 DP

代码：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        prev = curr = 0
        for i in range(2, n + 1):
            nxt = min(curr + cost[i - 1], prev + cost[i - 2])
            prev, curr = curr, nxt
        return curr

拓展

关于动态规划与贪心的证明，笔者建议读者可以阅读算法导论

依据灵神的网站题目顺序

1508. 子数组和排序后的区间和

问题

给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

提示：

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

解答

对于区间求和，首先想到前缀和、线段树、树状数组

对于排序，首先想到二分算法、二叉搜索树结构，二叉搜索树结构包括：堆、AVL 树、红黑树、B 树等

最朴素的思想是，先求出前缀和（\(O(n)\)），再遍历求出 n * (n + 1) / 2 数组（\(O(n^2)\)），对其排序（\(O(n^2\log n)\)），再求和得到解（\(O(right - left + 1)\)），显然该算法的时间复杂度为（\(O(n^2\log n)\)），需要进行优化
可以不对其进行排序，直接求 n * (n + 1) / 2 数组中第 k 大的数（\(O(n^2)\)），但是显然该算法的时间复杂度为 \(O(n^2 \cdot (right - left + 1))\)，若区间较小还好，如果较大，甚至不如算法1
可以先对 n 数组进行排序（\(O(n \log n)\)），基本没用，可以放弃
由算法 2 中的直接求 n * (n + 1) / 2 数组中第 k 大的数（\(O(n^2)\)），此后可以优化成求 n * (n + 1) / 2 数组的前缀和（\(O(n^2)\)），然后求一次第 left 大的值，和求一次第 right 大的值，但是由于 n * (n + 1) / 2 数组未排序，所以此法也不可用
观察到前缀的递增性质，可以使用二分法来求第 k 大的子数组和，只不过由于前缀和数组中的值并不是各个子数组的和，前缀和数组中的元素之差才是子数组的和，所以二分的区间并不是 [0, n]，而是 [0, prefixSum[-1]]，prefixSum[-1] 即为数组的和，即数组的最大子数组之和。那么什么用作二分的判断呢，即如何决定下一步将 mid 赋值给 left 还是 right 呢？当然是当前小于等于 mid 的子数组和的个数与 k 的大小关系决定。怎么获得当前小于等于 mid 的子数组和的个数呢？遍历前缀和数组即可（最好情况\(O(n)\)，最坏情况 \(O(n^2)\)，此处可以稍作优化，当 j == n 时，即可直接停止整个循环，计算结果了），所以该算法的时间复杂度为最好情况\(O(n \log prefixSum[-1])\)，最坏情况 \(O(n^2 \log prefixSum[-1])\)

代码：

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        MODULO = 10**9 + 7
        prefixSums = [0]
		# nums 前缀和，注意 它的长度为 n + 1
        for i in range(n):
            prefixSums.append(prefixSums[-1] + nums[i])
        # prefixSums 前缀和，注意 它的长度为 n + 1
        prefixPrefixSums = [0]
        for i in range(n):
            prefixPrefixSums.append(prefixPrefixSums[-1] + prefixSums[i + 1])
		# 计算 和小于等于 x 的数量
        def getCount(x: int) -> int:
            count = 0
            j = 1
            for i in range(n):
                while j <= n and prefixSums[j] - prefixSums[i] <= x:
                    j += 1
                j -= 1
                count += j - i
            return count
		# 计算第 k 大的和
		# 可以思考一下为什么这个方法得到的值一定是 nums 某个子数组的和？
		# 设第 k 大的子数组和为 kth
		# 若 mid < kth，则因为函数 count 求的是小于 等于 x 的数量(重点是等于)，有 count < k
		# 此时，有 low = mid + 1，用来靠近 kth
		# 若 mid > kth，则因为函数 count 求的是小于 等于 x 的数量，有 count >= k
		# 此时，有 high = mid，用来靠近 kth
		# 若mid = kth，则有 high = kth，那么此后永远有 low = mid + 1，直到 low = high = kth
        def getKth(k: int) -> int:
            low, high = 0, prefixSums[n]
            while low < high:
                mid = (low + high) // 2
                count = getCount(mid)
                if count < k:
                    low = mid + 1
                else:
                    high = mid
            return low
		# 获取 前 k 个最小子数组和的和
        def getSum(k: int) -> int:
			# 第 k 个最小子数组和
            num = getKth(k)
            total, count = 0, 0
            j = 1
            for i in range(n):
				# 求 严格小于 kth 的子数组和
                while j <= n and prefixSums[j] - prefixSums[i] < num:
                    j += 1
                j -= 1
				# prefixPrefixSums[j] - prefixPrefixSums[i] = prefixSums[i + 1] + ··· + prefixSums[j]
				# 原式即为求区间[i + 1]，[i + 1, i + 2]，···，[i + 1, j]的和的和
				# 为什么是 i + 1 呢，因为prefixSums和prefixPrefixSums数组长度是 n + 1，第 0 位初始化用
                total += prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)
                count += j - i
			# 等于 kth 的子数组和的和
            total += num * (k - count)
            return total

        return (getSum(right) - getSum(left - 1)) % MODULO

拓展

	区间求和	区间最大值	区间修改	单点修改
前缀和	\(\checkmark\)	\(\times\)	\(\times\)	\(\times\)
树状数组	\(\checkmark\)	\(\checkmark\)	\(\times\)	\(\checkmark\)
线段树	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)

类似题目：

378. 有序矩阵中第 K 小的元素

1700. 无法吃午餐的学生数量

问题

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里，每一轮：

如果队列最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队列。
否则，这名学生会放弃这个三明治并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

解答

很显然的自动机，那么先确定终止状态：所有学生都不喜欢栈顶三明治。即此时，students中的元素全部相同，且与 sandwiches[0] 相反，所以可以记录 students 中 0、1的个数，当 0/1 个数为 0 时，找到 sandwiches 中第一个与其相反的元素的位置即可，但是该算法可能需要 \(O(n^2)\) 的时间复杂度，需要优化
要达到终止状态，必然要先消耗完 students 中所有 0 或 1，计算 sandwiches 中 0 或 1的数量：若 students0 < sandwiches0，则 0 先消耗完，我们找到 sandwiches 中第 students0 + 1 个 0 的位置即可

class Solution:
	# 由于对 python 掌握得不好，所以写了一坨。。。
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
		n = len(sandwiches)
		c1 = {}
        c2 = {}
        c1[1], c2[1] = sum(students), sum(sandwiches)
        c1[0], c2[0] = n - c1[1], n - c2[1]

		def getCount(f: int) -> int:
			f0 = 0
            index = 0
            for s in sandwiches:
                if s == f:
                    f0 += 1
                if f0 > c1[f]:
                    break
                index += 1
            return n - index

        if c1[0] == c2[0]:
            return 0
        if c1[0] < c2[0]:
            return getCount(0)
        if c1[1] <c2[1]:
            return getCount(1)

# LeetCode排名中最快的算法，但是我想不通它哪里快
class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        while len(students) != 0 and not (len(set(students)) == 1 and students[0] != sandwiches[0]):
            if students[0] == sandwiches[0]:
                students = students[1:]
                sandwiches = sandwiches[1:]
            else:
                students = students[1:] + [students[0]]
        return len(students)

拓展

1864. 构成交替字符串需要的最小交换次数

问题

给你一个二进制字符串 s ，现需要将其转化为一个交替字符串。请你计算并返回转化所需的最小字符交换次数，如果无法完成转化，返回 -1 。

交替字符串是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。

任意两个字符都可以进行交换，不必相邻。

解答

该自动机的终止状态为 101··· 或 010···，所以我们只需要关注现在的字符串和终止字符串的差距即可，每次替换最多可以减少两个差距，所以求出现在的字符串和终止字符串的相同位置上不同的位的个数再除2即可。

其本质还是贪心

代码：

class Solution:
    def minSwaps(self, s: str) -> int:
        # 这个列表的第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量
        cnt = [0, 0]    
        c1 = 0
        for i, c in enumerate(s):
            # 偶数为1，给1加; 偶数为0，给0加
            # 奇数为1，给0加; 奇数为0，给1加
            cnt[i & 1 ^ int(c)] += 1
            if c == '1':
                c1 += 1

        c0 = len(s) - c1
        if abs(c1 - c0) > 1:
            return -1

        if c1 > c0:
            diff = cnt[0]
        elif c1 == c0:
            diff = min(cnt)
        else:
            diff = cnt[1]
        return (diff + 1) >> 1

拓展

本体类似于八皇后问题，即为找到启发式搜索，在 BFS 或 DFS 的基础上增加了贪心

标签：12,17,int,mid,students,sandwiches,数组,2023,c1
From： https://www.cnblogs.com/SpiritiualWander/p/17909446.html

2023-12-17 每天一练