hard
3218. Minimum Cost for Cutting Cake I
#Problem There is an m x n cake that needs to be cut into 1 x 1 pieces. You are given integers m, n, and two arrays: horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i. verticalCut of …
3219. Minimum Cost for Cutting Cake II
跟 3218. Minimum Cost for Cutting Cake I 一模一样，只不过 m 和 n 的量级从 20 增加到 10⁵，因此只能用 O(n log n) 贪心解法。 https://leetcode.cn/problems/minimum-cost-for-cutting-cake-ii/
2360. Longest Cycle in a Graph
#Problem You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge. The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from …
2608. Shortest Cycle in a Graph
#Problem There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1. The edges in the graph are represented by a given 2D integer array edges, where edges[i] = [uᵢ, vᵢ] denotes an edge between vertex uᵢ …
2127. Maximum Employees to Be Invited to a Meeting
#Problem A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees. The employees are numbered from 0 to n - 1. Each …
3203. Find Minimum Diameter After Merging Two Trees
#Problem There exist two undirected trees with n and m nodes, numbered from 0 to n - 1 and from 0 to m - 1, respectively. You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [aᵢ, …
685. Redundant Connection II
#Problem In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has …
1591. Strange Printer II
#Problem There is a strange printer with the following two special requirements: On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle. Once …
664. Strange Printer
#Problem There is a strange printer with the following two special properties: The printer can only print a sequence of the same character each time. At each turn, the printer can print new characters starting from and ending at any place …
1610. Maximum Number of Visible Points
#Problem You are given an array points, an integer angle, and your location, where location = [pos_x, pos_y] and points[i] = [x_i, y_i] both denote integral coordinates on the X-Y plane. Initially, you are facing directly east from your …
2872. Maximum Number of K-Divisible Components
#Problem There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [aᵢ, bᵢ] indicates that there is an edge between nodes aᵢ and bᵢ in the …
770. Basic Calculator IV
#Problem Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as …
224. Basic Calculator
#Problem Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation. Note: You are not allowed to use any built-in function which evaluates strings as mathematical …
3389. Minimum Operations to Make Character Frequencies Equal
#Problem You are given a string s. A string t is called good if all characters of t occur the same number of times. You can perform the following operations any number of times: Delete a character from s. Insert a character in s. Change a …
188. Best Time to Buy and Sell Stock IV
#Problem You are given an integer array prices where prices[i] is the price of a given stock on the iᵗʰ day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k …
123. Best Time to Buy and Sell Stock III
#Problem You are given an array prices where prices[i] is the price of a given stock on the iᵗʰ day. Find the maximum profit you can achieve. You may complete at most two transactions. Note: You may not engage in multiple transactions …
3291. Minimum Number of Valid Strings to Form Target I
#Problem You are given an array of strings words and a string target. A string x is called valid if x is a prefix of any string in words. A prefix of a string is a substring that starts from the beginning of the string and extends to any …
3292. Minimum Number of Valid Strings to Form Target II
3291. Minimum Number of Valid Strings to Form Target I 的进阶版，题目一模一样，但 words 的长度从 5 * 10³ 增加到 5 * 10⁵，target 的长度从 5 * 10³ 增加到 5 * 10⁴。 如果按 problem 3291 中 O(n²) 复杂度的 trie 树 + 动态规划是无法 AC 的，需要用更快的 AC 自动机。
3213. Construct String with Minimum Cost
#Problem You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length. Imagine an empty string s. You can perform the following operation any number of times (including zero): Choose …
2809. Minimum Time to Make Array Sum At Most x
#Problem You are given two 0-indexed integer arrays nums1 and nums2 of equal length. Every second, for all indices 0 <= i < nums1.length, value of nums1[i] is incremented by nums2[i]. After this is done, you can do the following operation: …
3266. Final Array State After K Multiplication Operations II
#Problem You are given an integer array nums, an integer k, and an integer multiplier. You need to perform k operations on nums. In each operation: Find the minimum value x in nums. If there are multiple occurrences of the minimum value, …
2931. Maximum Spending After Buying Items
#Problem You are given a 0-indexed m * n integer matrix values, representing the values of m * n different items in m different shops. Each shop has n items where the jᵗʰ item in the iᵗʰ shop has a value of values[i][j]. Additionally, the …
2699. Modify Graph Edge Weights
#Problem You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [aᵢ, bᵢ, wᵢ] indicates that there is an edge between nodes aᵢ and bᵢ with weight wᵢ. Some …
1719. Number Of Ways To Reconstruct A Tree
#Problem You are given an array pairs, where pairs[i] = [xᵢ, yᵢ], and: There are no duplicates. xᵢ < yᵢ Let ways be the number of rooted trees that satisfy the following conditions: The tree consists of nodes whose values appeared in pairs. …
1982. Find Array Given Subset Sums
#Problem You are given an integer n representing the length of an unknown array that you are trying to recover. You are also given an array sums containing the values of all 2ⁿ subset sums of the unknown array (in no particular order). …
782. Transform to Chessboard
#Problem You are given an n x n binary grid board. In each move, you can swap any two rows with each other, or any two columns with each other. Return the minimum number of moves to transform the board into a chessboard board. If the task …
2056. Number of Valid Move Combinations On Chessboard
#Problem There is an 8 x 8 chessboard containing n pieces (rooks, queens, or bishops). You are given a string array pieces of length n, where pieces[i] describes the type (rook, queen, or bishop) of the iᵗʰ piece. In addition, you are given …
52. N-Queens II
#Problem The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. …
51. N-Queens
#Problem The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any …
1531. String Compression II
#Problem Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters …
2097. Valid Arrangement of Pairs
#Problem You are given a 0-indexed 2D integer array pairs where pairs[i] = [startᵢ, endᵢ]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have endᵢ₋₁ == startᵢ. Return any valid arrangement of pairs. …
3250. Find the Count of Monotonic Pairs I
#Problem You are given an array of positive integers nums of length n. We call a pair of non-negative integer arrays (arr1, arr2) monotonic if: The lengths of both arrays are n. arr1 is monotonically non-decreasing, in other words, arr1[0] …