Leetcode.com 2021-08-21
🔴 37.sudoku-solver

🏷️ Tags
#array #backtracking #matrix

Description
Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:


Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.


The '.' character indicates empty cells.

Example

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Leetcode.com 2021-08-22
🔴 850.rectangle-area-ii

🏷️ Tags
#segment_tree #array #ordered_set #line_sweep

Description
We are given a list of (axis-aligned) rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] , where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner of the ith rectangle.

Find the total area covered by all rectangles in the plane. Since the answer may be too large, return it modulo 109 + 7.

Example

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: As illustrated in the picture.

Leetcode.com 2021-08-23
🟢 653.two-sum-iv-input-is-a-bst

🏷️ Tags
#tree #depth_first_search #breadth_first_search #binary_search_tree #hash_table #two_pointers #binary_tree

Description
Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Leetcode-cn.com 2021-08-24
🟡 787.cheapest-flights-within-k-stops

🏷️ Tags
#depth_first_search #breadth_first_search #graph #dynamic_programming #shortest_path #heap_priority_queue

Description
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 toi 抵达 pricei。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

Example

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下


从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

Leetcode-cn.com 2021-08-25
🟡 797.all-paths-from-source-to-target

🏷️ Tags
#depth_first_search #breadth_first_search #graph #backtracking

Description
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。

译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。

Example

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

Leetcode.com 2021-08-24
🟡 537.complex-number-multiplication

🏷️ Tags
#math #string #simulation

Description
A complex number can be represented as a string on the form "real+imaginaryi" where:


real is the real part and is an integer in the range [-100, 100].
imaginary is the imaginary part and is an integer in the range [-100, 100].
i2 == -1.


Given two complex numbers num1 and num2 as strings, return a string of the complex number that represents their multiplications.

Example

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Leetcode-cn.com 2021-08-26
🟡 881.boats-to-save-people

🏷️ Tags
#greedy #array #two_pointers #sorting

Description
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

Example

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

Leetcode.com 2021-08-25
🟡 633.sum-of-square-numbers

🏷️ Tags
#math #two_pointers #binary_search

Description
Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Leetcode.com 2021-08-25
🟡 633.sum-of-square-numbers

🏷️ Tags
#math #two_pointers #binary_search

Description
Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Leetcode.com 2021-08-25
🟡 633.sum-of-square-numbers

🏷️ Tags
#math #two_pointers #binary_search

Description
Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Leetcode.com 2021-08-25
🟡 633.sum-of-square-numbers

🏷️ Tags
#math #two_pointers #binary_search

Description
Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Leetcode-cn.com 2021-08-27
🔴 295.find-median-from-data-stream

🏷️ Tags
#design #two_pointers #data_stream #sorting #heap_priority_queue

Description
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：


void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。


undefined

Leetcode.com 2021-08-26
🟡 331.verify-preorder-serialization-of-a-binary-tree

🏷️ Tags
#stack #tree #string #binary_tree

Description
One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'.

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid.


For example, it could never contain two consecutive commas, such as "1,,3".


Note: You are not allowed to reconstruct the tree.

Example

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Leetcode-cn.com 2021-08-28
🟢 1480.running-sum-of-1d-array

🏷️ Tags
#array #prefix_sum

Description
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

Example

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

Leetcode.com 2021-08-27
🟡 522.longest-uncommon-subsequence-ii

🏷️ Tags
#array #hash_table #two_pointers #string #sorting

Description
Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.


For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).


Example

Input: strs = ["aba","cdc","eae"]
Output: 3

Leetcode-cn.com 2021-08-29
🟢 1588.sum-of-all-odd-length-subarrays

🏷️ Tags
#array #prefix_sum

Description
给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

Example

输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Leetcode.com 2021-08-28
🔴 1235.maximum-profit-in-job-scheduling

🏷️ Tags
#array #binary_search #dynamic_programming #sorting

Description
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Leetcode-cn.com 2021-08-30
🟡 528.random-pick-with-weight

🏷️ Tags
#math #binary_search #prefix_sum #randomized

Description
给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。




例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

Example

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

Leetcode.com 2021-08-29
🔴 330.patching-array

🏷️ Tags
#greedy #array

Description
Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

Example

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Leetcode-cn.com 2021-08-31
🟡 1109.corporate-flight-bookings

🏷️ Tags
#array #prefix_sum

Description
这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

 

Example

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]