LeetCode 第186场周赛

良心周赛 四题代码总共不超过50行🥺

第一题:分割字符串的最大得分

难度简单

题目描述

给你一个由若干 0 和 1 组成的字符串 s ,请你计算并返回将该字符串分割成两个 非空 子字符串(即 子字符串和 子字符串)所能获得的最大得分。

「分割字符串的得分」为 子字符串中 0 的数量加上 子字符串中 1 的数量。

示例 1:

示例 2:

示例 3:

提示:

  • 2 <= s.length <= 500
  • 字符串 s 仅由字符 '0''1' 组成。

题目链接

https://leetcode-cn.com/problems/maximum-score-after-splitting-a-string/

思路:

  遍历每一个分割位置。

代码:

第二题:可获得的最大点数

难度中等

题目描述

几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k,请你返回可以获得的最大点数。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

题目链接

https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/

思路:

  因为拿掉的牌固定为k张,因此剩下的就是中间的n-k张,维护一个滑动窗口,求中间n-k张的最小值即可。

代码:

第三题:对角线遍历 II

难度中等

题目描述

给你一个列表 nums ,里面每一个元素都是一个整数列表。请你依照下面各图的规则,按顺序返回 nums 中对角线上的整数。

示例 1:

img

示例 2:

img

示例 3:

示例 4:

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i].length <= 10^5
  • 1 <= nums[i][j] <= 10^9
  • nums 中最多有 10^5 个数字。

题目链接

https://leetcode-cn.com/problems/diagonal-traverse-ii/

思路:

  在同一条对角线上的元素,横纵坐标之和是相等的,也就是i+j是一样的。

  计算所有元素的横纵坐标,然后按照(横纵坐标之和,纵坐标,元素值)的关键字顺序来排序,排序后的结果就是对角线遍历的顺序。

代码:

第四题:带限制的子序列和

难度困难

题目描述

给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个 相邻 的整数 nums[i]nums[j] ,它们在原数组中的下标 ij 满足 i < jj - i <= k

数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

题目链接

https://leetcode-cn.com/problems/constrained-subset-sum/

思路:

  动态规划。令dp[i]表示选择下标为i的元素时能选择的最大子序和,因为选择的两个元素下标之差不能大于k,因此有状态转移方程dp[i] = max(0, max(dp[i-k: i])) + nums[i]

  由于题目的范围较大,不能暴力计算max(dp[i-k: i]),因此使用一个最大堆来保存dp[i-k: i]的最大值。

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注