年纪大了，玩不了刺激的题目，只做LeetCode简单题和Codeforces弱智题，当作休闲爱好 所以这里也没啥好看的，没事还是逛点别的网站吧 主站：记录工业垃圾 旧站：记录学业垃圾
Codeforces-1690A Print a Pedestal (Codeforces logo?)
Description 给定\(n\)，求构造\(x + y + z = n\)，其中\(x \gt y \gt z \gt 0\)，要求\(x\)尽可能小，答案输出\(y, x, z\)。 Constraints \(6 \le n \le 10^5\) Solution 很显然要将三个数往\(n/3\)靠拢。观察\(n \% 3 = m\)的情况，在总和上补齐\(m\)即可，解法不唯一。 Code #include <bits/stdc++.h> using namespace std; int main() { int t; cin >&g...
LeetCode-935 Knight Dialer
Description 国际象棋中的马放在一个拨号器的任意位置，求走\(n\)步后能生成多少个电话号码。 1 2 3 4 5 6 7 8 9 * 0 # 拨号器如上表所示（其中*和#不可用）。 另外补充马的走法，如上图所示。 Constraints \(1 \le n \le 5000\) Solution 没啥意思的题目，思路见LeetCode-688，仅需消除后效性。 我本以为需要做一个转换表，比如\(convert[nums][8]\)表示数字\(nums\)能跳到哪里。其实是不需要的，因为电话上每个数字都是唯一的。 偶尔用点离谱的写法当题解吧。 Cod...
LeetCode-907 Sum of Subarray Minimums
Description 给定一个长度为\(n\)的数组\(a\)，求该数组中所有子数组的最小值之和。 Constraints \(1 \le n \le 3 \cdot 10^4\) \(1 \le a_i \le 3 \cdot 10^4\) Solution 假设你知道每个最小值\(a_i = min\_v\)所覆盖的区间范围\([lo, hi]\)，那么可以通过组合数得知子答案：\(sub\_ans_i = (i - lo + 1) * (hi - i + 1) * min\_v\)。 然后通过子答案之和就可以得到答案：\(ans = \sum_{i=0}^...
LeetCode-638 Shopping Offers
Description 你需要买\(n\)个商品，商品\(i\)需要的数目为\(needs_i\)，单价为\(price_i\)。同时有\(m\)个打包优惠，每个优惠\(special_i\)均为一个长度\(n+1\)的数组，其中前\(n\)个元素对应商品\(i\)的数目，最后一个元素对应打包优惠价格。求最低买入价格。 Constraints \(1 \le n \le 6\) \(0 \le price_i \le 10\) \(0 \le needs_i \le 10\) \(1 \le m \le 100\) \(0 \le special_{ij} \...
LeetCode-149 Max Points on a Line
Description 给定\(n\)个整数点的二维坐标\((x_i, y_i)\)，求最多的连在同一直线上的点数目。 Constraints \(1 \le n \le 300\) \(-10^4 \le x_i, y_i \le 10^4\) 不存在重复的点 Solution 计算几何就从来没做过，还好这题思路简单。 哈希表配合gcd记录斜率即可。需要注意的是横竖两种情况要特殊维护。 Code class Solution { public: int maxPoints(vector<vector<int>>& ...
LeetCode-678 Valid Parenthesis String
Description 给定一个长度为\(n\)的字符串\(s\)。每个字符只可能是：(、)或者*。其中*可以表示为(、)或者是空字符。问字符串\(s\)是否满足括号匹配。 Constraints \(1 \le n \le 100\) Solution 一眼区间DP。除了要求细心以外没啥特别的，只是个人想复习一下区间DP。 Code class Solution { public: bool checkValidString(string s) { bool dp[103][103] {}; bool vis[103][103] {...
LeetCode-446 Arithmetic Slices II - Subsequence
Description 给定一个长度为\(n\)的数组\(a\)，求具有公差的子序列的方案数，子序列要求长度大于等于3。 Constraints \(1 \le n \le 1000\) \(-2^{31} \le a_i \le 2^{31}-1\) Solution 想到一个不好做的递推公式：设\(dp[i][j]\)，表示以\(i\)结尾且公差为\(nums[i]-nums[j]\)的子序列方案数。设想美好但是推不动，似乎没法在\(dp[i-1][?]\)反推\(nums[j]\)…… 那改一改：设\(dp[i][d]\)，表示以\(i\)结尾的公差为\(d...
LeetCode-312 Burst Balloons
Description 给定\(n\)个元素，值为\(a_i\)。每取出一个元素\(i\)可以得到贡献\(a_{i-1} * a_i * a_{i+1}\)，注意这里\(i-1\)和\(i+1\)指的是当前相邻的元素，如果没有相邻元素则当作1。求取出所有元素的最大贡献。 Constraints \(1 \le n \le 300\) \(0 \le a_i \le 100\) Solution 一眼区间DP。 设\(dp[l][r]\)为区间\((l, r)\)的最大贡献，枚举区间中最后一个取出的元素\(i\)，那么递推公式为\(dp[l][r] = max_{i...
LeetCode-632 Smallest Range Covering Elements from K Lists
Description 给定\(k\)个数组，从每个数组中各取最少一个数，使得取的数当中最大值与最小值之差最小 Constraints \(1 \le k \le 3500\) \(1 \le nums[i].length \le 50\) Solution 将所有数都放到一个数组中，标好归属的原数组编号并排序，然后跑一遍滑动窗口即可 Code class Solution { public: vector<int> smallestRange(vector<vector<int>>& nums) { ...
LeetCode-621 Task Scheduler
Description 给你一个用字符数组\(tasks\)表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在\(1\)个单位时间内执行完。在任何一个单位时间，CPU可以完成一个任务，或者处于待命状态。 然而，两个相同种类的任务之间必须有长度为整数\(n\)的冷却时间，因此至少有连续\(n\)个单位时间内CPU在执行不同的任务，或者在待命状态。 你需要计算完成所有任务所需要的最短时间。 Constraints \(1 \le task.length \le 10^4\) \(0 \le n \le 100\...
LeetCode-646 Maximum Length of Pair Chain
Description 给定\(n\)个区间\([lo_i, hi_i]\)，求最长不重叠区间个数 Constraints \(1 \le n \le 1000\) \(-1000 \le lo_i \lt hi_i \le 1000\) Solution 解释同435 Code class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { ranges::sort(pairs, [](auto &a, aut...
LeetCode-629 K Inverse Pairs Array
Description 给定\(n\)和\(k\)，求包含数字\(1 \ldots n\)且恰好有\(k\)个逆序对的数组方案数。答案对\(10^9+7\)取模 Constraints \(1 \le n \le 1000\) \(0 \le k \le 1000\) Solution 设\(dp[i][j]\)为使用\(1 \ldots i\)构成长度\(i\)的数组，且恰有\(j\)个逆序对的方案数。这里下标从1开始算起 问题在于怎么做状态转移 如果算出\(dp[i-1]\)的答案，把数字\(i\)插入到原\(1 \ldots i-1\)中，则得到\(dp[...
LeetCode-526 Beautiful Arrangement
Description 假设有从 \(1\) 到 \(n\) 的 \(n\) 个整数。用这些整数构造一个数组 \(perm\)（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ： \(perm[i]\) 能够被 \(i\) 整除 \(i\) 能够被 \(perm[i]\) 整除 给你一个整数 \(n\) ，返回可以构造的 优美排列 的 数量 。 Constraints \(1 \le n \le 15\) Solution 状压DP，用\(dp[S]\)表示数字的选取情况 就凭感觉写的方案数，我也不知道为啥能AC Code clas...
LeetCode-1131 Maximum of Absolute Value Expression
Description 给定两个数组\(arr1\)和\(arr2\)，求\(max\{ \ \mid arr1_i - arr1_j \mid + \mid arr2_i - arr2_j \mid + \mid i - j \mid \ \}\) Constraints 时间复杂度不超过\(O(n)\) Solution 这道题就是求三维的曼哈顿距离，每一个点\(i\)的坐标是\((x_i, y_i, z_i) \to (arr1_i, arr2_i, i)\)的形式 计算公式在未展开时为\(\mid \Delta x \mid + \mid \Delta y \mi...
LeetCode-354 Russian Doll Envelopes
Description 俄罗斯套信封问题，给定\(n\)封信，每一封信\(i\)有长宽\(h_i, w_i\)，每一封信嵌套要求长宽均满足严格递增关系，问最多能嵌套多少封信 Constraints 时间复杂度不超过\(O(nlogn)\) Solution 二维LIS，使用排序降低维度，后面就是LIS模板 \(O(nlogn)\)的LIS忘记怎么写了，翻了下书 它的定义是比较特殊的：设\(dp[i]\)为长度为\(i+1\)的上升子序列中末尾元素的最小值 Code class Solution { public: int maxEnvelopes(vector&...
LeetCode-456 132 Pattern
Description Given an array of \(n\) integers nums, a 132 pattern is a subsequence of three integers \(nums[i]\), \(nums[j]\) and \(nums[k]\) such that \(i < j < k\) and \(nums[i] < nums[k] < nums[j]\). Return true if there is a 132 pattern in nums, otherwise, return false. Constrai...
LeetCode-1235 Maximum Profit in Job Scheduling
Description 有\(n\)个任务，每个任务需要在\([lo_i, hi_i]\)时间区间内调度并占用时间，可以从中获得\(p_i\)利润。求不重叠的任务调度能获得的最大利润 Constraints 时间复杂度不得超过\(O(nlogn)\) Solution 这题和630有点像，但是时间是固定的不能自由安排，固定的区间可以考虑dp 设\(dp[i]\)：前\(i\)个区间子集合的最大利润。\(dp[i]\)需要找到某个\(j \in [0, i-1]\)，使得\(dp[i] = max(dp[j] + p_i, dp[i-1])\) 为了能找到\(j\)，原区间先...
LeetCode-315 Count of Smaller Numbers After Self
Description Given an integer array nums, return an integer array counts where \(counts[i]\) is the number of smaller elements to the right of \(nums[i]\). Constraints \(1 \le nums.length \le 10^5\) \(-10^4 \le nums[i] \le 10^4\) Solution 模板题，回顾一下也好 Code class Solution { public: v...
51NOD-1364 最大字典序排列
Description 给出一个\(1-N\)的排列，允许不超过\(k\)次操作，每次操作交换相邻两个数，求最大字典序排列 Constraints \(1 \le N \le 10^5\) \(0 \le k \le 10^9\) Solution 贪心局部解，先决定第一大的数尽量大，处理好后继续决定第二大。只需维护每步操作在\(O(logn)\)内 Code 忘记线段树怎么写了唉 Link 51NOD-1364 最大字典序排列
LeetCode-1673 Find the Most Competitive Subsequence
Description 给定字符串\(s\)以及常数\(k\)，移除\(\mid s \mid - k\)个字符使得字典序最小 Constraints \(\mid s \mid\)不超过\(10^5\) Solution 单调栈秒了 Code class Solution { public: vector<int> mostCompetitive(vector<int>& nums, int k) { stack<int> stk; int max_delete = nums.size()...
LeetCode-122 Best Time to Buy and Sell Stock II
Description 炒股，每天股票有不同价格\(p_i\)，你每天可以买卖股票，求最大利润 Constraints 要求时间复杂度不超过\(O(nlogn)\)，\(n\)为交易日期长度 Solution 我不想说得太失礼，但这道题只看样例都知道答案了啊 但是重点还是学会证明 这道题等于算若干不重叠区间的两端差值，设第\(i\)个区间范围是\([L_i, R_i]\)，即：\(\sum_{i=1}^{n}(p_{Li} - p_{Ri})\) 这里每个区间\(i\)的起点\(L_i\)、长度\(R_i - L_i + 1\)以及区间个数\(n\)均没有限制，目标是\(...
LeetCode-698 Partition to K Equal Sum Subsets
Description Given an integer array \(nums\) and an integer \(k\), return true if it is possible to divide this array into \(k\) non-empty subsets whose sums are all equal. Constraints \(1 \le k \le nums.length \le 16\) \(1 \le nums_i \le 10^4\) The frequency of each element is in the ra...
LeetCode-688 Knight Probability in Chessboard
Description 给定\(n \times n\)大小的棋盘，以及马的起始坐标\((row, column)\)（坐标是从0算起），求\(k\)次移动后马仍在棋盘上的概率 补充国际象棋中马的移动方式，见上图 Constraints \(1 \le n \le 25\) \(0 \le k \le 100\) \(0 \le row, column \le n - 1\) Solution 可以定义一个\(step\)来消除后效性 设\(dp[step][i][j]\): 从\((i, j)\)出发，走了\(step\)步仍在chessboard的概...
LeetCode-436 Find Right Interval
Description 给定\(n\)个区间\([lo_i, hi_i]\)，每个区间的\(lo_i\)互不重复，求每一个区间的右侧区间下标。某区间\(i\)的右侧区间\(j\)指的是\(lo_j \ge hi_i\)且\(lo_j\)是所有可选答案中最小的那位 Constraints 时间复杂度不超过\(O(nlogn)\) Solution 不知道要说什么，总之排序就对了 Code class Solution { public: vector<int> findRightInterval(vector<vector<int>>...
POJ-1456 Supermarket
Description 给定长度为\(n\)的数组\(a[]\)，每个元素\(a_i\)为\(\{p_i, d_i\}\)，其中\(p_i\)表示贡献值，\(d_i\)表示期限，每个元素的贡献需要花费\(1\)时间单位，超过期限则无法贡献。求期限内最大的总贡献值 Constraints \(n\)不超过\(10^4\) Solution 这道题适合作为反悔贪心的第一题 从直觉来看，按照期限\(d_i\)进行排序。维护一个小根堆，堆上按照贡献\(p_i\)作为关键字，并且假设当前时间为\(x\)，则堆大小也为\(x\) 维护反悔的过程：如果在\(d = 1\)选好了\(a_i...
LeetCode-435 Non-overlapping Intervals
Description 给定\(n\)个区间\([lo_i, hi_i]\)，求最少移除区间数，使得剩余区间互不重叠 Constraints 要求时间复杂度不超过\(O(nlogn)\) Solution 很多年前做过的题，就是反过来求的最多不重叠区间，结论就是按右端点排序。但是为什么呢？ 如果不介意看我用Microsoft Paint 11.2205.9.0画出来的玩意，那应该可以解释一下 首先假设从左到右处理，最左端的若干区间并没有重叠部分，那我们自然是选择最左边的区间开始；但是如果有重叠部分呢？比如我们现在选取了最左边的左端点\(L_i\)对应的区间，现在存在重叠了，...
LeetCode-316 Remove Duplicate Letters
Description 给定一个字符串\(s\)，移除相同的字符使得每个字符只保留一份，且要求输出最小字典序 Constraints \(s\)的长度不超过\(10^4\) Solution 我讨厌字典序，用单调栈糊弄过去吧。意思很简单，就是看后面还有大字典序的话就pop() Code class Solution { public: string removeDuplicateLetters(string s) { stack<char> stk; int cnt[256] {}; bool in[256...
LeetCode-373 Find K Pairs with Smallest Sums
Description 给定两个已排序的数组\(nums1[]\)和\(nums2[]\)，和一个常数\(k\)。设元组\(p(u, v)\)为从\(nums1[]\)拿取\(u\)，且从\(nums2[]\)拿取\(v\) 返回\(k\)个元组\(p(u_i, v_j)\)使得它们的和最小 Constraints \(nums1[]\)和\(nums2[]\)长度不超过\(10^5\) \(nums1[i]\)和\(nums2[i]\)都在int范围内 \(k\)不超过\(10^4\) Solution 假设你拿了\(u_i\)和\(v_j\)，那么可以确定...
LeetCode-719 Find K-th Smallest Pair Distance
Description 给出数组\(a[0, n)\)，设距离\(d(i, j) = \mid a_i - a_j\mid\)，求第\(k\)大距离 Constraints \(n\)不超过\(10^4\) Solution 排序然后二分答案，每次猜一个距离 Code class Solution { public: int smallestDistancePair(vector<int>& nums, int k) { std::sort(nums.begin(), nums.end()); int lo = 0...
LeetCode-1363 Largest Multiple of Three
Description 给出\(digits[]\)数组，每个元素范围\([1, 9]\)，让它拼接出最长的能被3整除的字符串 Constraints \(digits[]\)长度不超过\(10^4\) Solution 首先，一个非负整数被3整除的性质是数位之和也被3整除；其次，可以用桶按\(%3\)进行分类讨论，这里筛除最小的无法拼凑的数位，剩下的只需按从大到小排列即可 Code class Solution { public: string largestMultipleOfThree(vector<int>& digits) { ...
LeetCode-201 Bitwise AND of Numbers Range
Description 给定两个整数\(lo\)和\(hi\)，表示一个区间\([lo, hi]\)，求该区间内AND操作后的结果 Constraints \(0 \le lo \le hi \le 2^{31} - 1\) Solution 拆成32位看，只要高位不一致，从\(hi\)到\(lo\)是要经历0-bit的 Code class Solution { public: int rangeBitwiseAnd(int left, int right) { int ans = 0; auto highFunc = [](int...
LeetCode-134 Gas Station
Description 在一条环路上有 \(n\) 个加油站，其中第 \(i\) 个加油站有汽油 \(gas[i]\) 升。 你有一辆油箱容量无限的的汽车，从第 \(i\) 个加油站开往第 \(i+1\) 个加油站需要消耗汽油 \(cost[i]\) 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 \(gas\) 和 \(cost\) ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 \(-1\) 。如果存在解，则 保证 它是 唯一 的。 Constraints \(1 \le n \le 10^5\) \(0 \le gas[i...
LeetCode-630 Course Schedule III
Description 给定一个数组\(a[1, n]\)，每个元素\(a_i\)具有2种属性\(\{d_i, l_i\}\)，其中\(d_i\)表示消耗时长，\(l_i\)表示最后期限（含）。每单位时长只能同时消费\(1\)个元素。求最多能消耗的元素个数 Constraints \(1 \le n \le 10^4\) \(1 \le d_i, l_i \le 10^4\) Solution 这道题适合作为反悔贪心的第二题。关联：第一题 数组按\(l_i\)排序，大根堆按\(d_i\)排序。这样保证了堆内操作时任意元素都是合法的 维护\(sum\)表示总时长，...
LeetCode-664 Strange Printer
Description TL;DR 粉刷匠 给定一个字符串\(s\)和空串\(t\)，每次操作可以覆盖任意连续长度的字符，但必须是相同字符。求从\(t\)串到\(s\)串的最少操作次数 Constraints \(s\)长度不超过\(100\) Solution 区间DP即可 Code class Solution { public: int strangePrinter(string s) { int dp[102][102]; memset(dp, 0x3f, sizeof dp); for(int i = 0;...
LeetCode-546 Remove Boxes
Description TL;DR 消消乐 给出一个数组\(boxes[0, n)\)，数组每个元素均为正整数。每一次操作可以从中消掉一些相同数值的元素，直至数组为空。每消除\(k\)个元素得到的贡献是\(k^2\)，求最大贡献 Constraints \(1 \le boxes.length \le 100\) \(1 \le boxes[i] \le 100\) Solution 关键在于定义\(dp\)的含义：设\(dp[l][r][x]\)为区间\([l,r]\)且\(r\)右侧拥有与\(boxes[r]\)相同数值的\(x\)个元素 定义好就可以递推了...
LeetCode-502 IPO
Description 有\(n\)个项目，每个项目可以获得利润\(p_i\)，但需要前提资本\(c_i\)才能启动。初始时你有资本\(w\)，求最多\(k\)个项目的最大利润 Constraints 时间复杂度不超过\(O(nlogn)\) Solution 这种一眼是排序+堆操作的贪心，最近品鉴得有点多了。排序按能合法操作的来，堆按所求最优的做关键字，因此是按资本排序，并用利润作为大根堆关键字 剩下的就是一个模拟过程（这点有别于反悔操作） Code class Solution { public: int findMaximizedCapital(int k,...
LeetCode-480 Sliding Window Median
Description 给出数组\(nums[]\)，窗口大小\(k\)，求滑动窗口中的（排序后）中值。具体见下面样例： Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3...
LeetCode-352 Data Stream as Disjoint Intervals
Description 给出数据流\(a[1...n]\)，要求实现SummaryRanges类以提供三种操作： SummaryRanges()：初始化流 void addNum(int value)：添加value到流中 int[][] getIntervals()：查询返回若干不相交的区间\([lo_i, hi_i]\)（按照\(lo_i\)排序） Constraints 最多\(3 \times 10^4\)次addNum(int value)和getIntervals()操作 最多\(10^2\)次getIntervals()操作 Soluti...
LeetCode-239 Sliding Window Maximum
Description 给出数组\(nums[]\)，滑动窗口大小\(k\)，求每个滑动窗口的最大值 Constraints \(nums[]\)长度不超过\(10^5\) \(nums[i]\)可以是负数 Solution 单调队列即可，维护单调最大值 Code class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { if(nums.size() <= k) return {*std::max...