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}

Leetcode-cn.com 2021-09-03
🟡 面试题 17.14.smallest-k-lcci

🏷️ Tags
#array #divide_and_conquer #quickselect #sorting #heap_priority_queue

Description
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

Example

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

Leetcode.com 2021-09-02
🟡 95.unique-binary-search-trees-ii

🏷️ Tags
#tree #binary_search_tree #dynamic_programming #backtracking #binary_tree

Description
Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Leetcode-cn.com 2021-09-04
🟢 剑指 Offer 10- I.fei-bo-na-qi-shu-lie-lcof

🏷️ Tags
#memoization #math #dynamic_programming

Description
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

 

Example

输入：n = 2
输出：1

Leetcode.com 2021-09-03
🔴 587.erect-the-fence

🏷️ Tags
#geometry #array #math

Description
You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden.

You are asked to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed.

Return the coordinates of trees that are exactly located on the fence perimeter.

Example

Input: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[3,3],[2,4],[4,2]]