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]

Leetcode.com 2021-08-30
🟢 598.range-addition-ii

🏷️ Tags
#array #math

Description
You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < ai and 0 <= y < bi.

Count and return the number of maximum integers in the matrix after performing all the operations.

Example

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

Leetcode.com 2021-08-31
🟡 153.find-minimum-in-rotated-sorted-array

🏷️ Tags
#array #binary_search

Description
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:


[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.


Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Leetcode-cn.com 2021-09-02
🟢 剑指 Offer 22.lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

🏷️ Tags
#linked_list #two_pointers

Description
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

 

undefined

Leetcode.com 2021-09-01
🟡 565.array-nesting

🏷️ Tags
#depth_first_search #array

Description
You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].

You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... } subjected to the following rule:


The first element in s[k] starts with the selection of the element nums[k] of index = k.
The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on.
We stop adding right before a duplicate element occurs in s[k].


Return the longest length of a set s[k].

Example

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}