LeetCode Weekly Contest 56
##Maximum Length of Repeated Subarray
Given two integer arrays A
and B
, return the maximum length of an subarray that appears in both arrays.
Example 1:
1 | Input: |
Note:
- 1 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100
题意: 求最长连续子序列,类 LCS,转移条件换一下
1 | /** |
Find K-th Smallest Pair Distance
Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.
Example 1:
1 | Input: |
Note:
2 <= len(nums) <= 10000
.0 <= nums[i] < 1000000
.1 <= k <= len(nums) * (len(nums) - 1) / 2
.
题意:任意两个数之间的差,求第 k 大的差是多少。
题解:原本以为利用排列组合知识可以解,后来发现太麻烦。因为求 k 大,感觉可以二分答案,于是二分答案然后 check 复杂度$O(log1000000*len(Set(nums)))$
1 | /** |