S*******C
发帖数: 822 | 1 Google面试题
Given a sequence S of integers, a subsequence is any selection of numbers of
S in the same order as S. For example, if S = 1,1,2,3,5,8,13 then 2,3,8 is
a subsequence of S and so is 1,1,5,13 and so is 1,2,3. However, 5,6,7 is not
a subsequence, 8,5,2 is also not a subsequence.
A subsequence T is increasing is T[i] < T[i+1] for all i.
Given a sequence S = 4, 9, 3, 8, 6, 7, 10 .... : we can have 3, 8, 10 or 4,
9, 10 or 4, 6,7,10 as its increasing subsequences.
Our task is : given a sequence S of n numbers, count the number of
increasing subsequences of S. Given an O( n log n) algorithm to accomplish
this task. | S*******C
发帖数: 822 | 2 我这里有一个查找最长递增子序列的O(nlogn)动态规划算法可以作为参考
public class LongestIncreasingSubseq {
static int min_last_element[];// 记录长度为i的递增子序列中最大元素的最小
值, min_last_element is an sorted array
static int lengthOfLIS;
public static void main(String args[]) {
int a1[] = new int[] { 12, 11, 13, 10, 14, 11, 15, 12, 17, 20, 11,
22 };
min_last_element= new int[a1.length];
System.out.println(findLongestIncreasingSubseq(a1, a1.length));
}
// 返回min_last_element[i]中刚刚大于x的那个元素的下标
static int binarySearch(int[] min_last_element, int lengthOfLIS, int x) {
int left = 0, right = lengthOfLIS, mid;
while (left <= right) {
mid = (left + right) / 2;
if (x > min_last_element[mid])
left = mid + 1;
else if (x < min_last_element[mid])
right = mid - 1;
else
return mid;
}
return left;
}
static int findLongestIncreasingSubseq(int[] A, int size) {
min_last_element[0] = A[0];
lengthOfLIS = 1;
for (int i = 1; i < size; i++) {
if (A[i] > min_last_element[lengthOfLIS - 1]) {//case 1
min_last_element[lengthOfLIS] = A[i];
lengthOfLIS++;
} else {//case 2
int pos = binarySearch(min_last_element, lengthOfLIS, A[i]);
min_last_element[pos] = A[i];
}
}
return lengthOfLIS;
}
} | j**7
发帖数: 143 | 3 我感觉这题类似Counting Inversions. Algorithm Design Section 5.3 | S*******C
发帖数: 822 | 4 能说具体一点吗？
【在 j**7 的大作中提到】
: 我感觉这题类似Counting Inversions. Algorithm Design Section 5.3
| l*n
发帖数: 529 | 5 应该跟你后来贴的longest increasing subsequence 是类似的，毕竟复杂度都告诉你
了，明显是binary search。
思路应该大致是这样的，4(0) >> 4(0) 9(1) >> 3(0) 4(0) 9(1) >> 3(0) 4(0) 8(2)
9(1) >> 3(0) 4(0) 6(2) 8(2) 9(1) >> 3(0) 4(0) 6(2) 7(3+2) 8(2) 9(1) >> 3(0)
4(0) 6(2) 7(5) 8(2) 9(1) 10(6+2+5+2+1)
新进来一个数，binary search之后包含新数的序列数量是左边的数字个数加上他们的
序列数之和。
of
is
not
4,
【在 S*******C 的大作中提到】
: Google面试题
: Given a sequence S of integers, a subsequence is any selection of numbers of
: S in the same order as S. For example, if S = 1,1,2,3,5,8,13 then 2,3,8 is
: a subsequence of S and so is 1,1,5,13 and so is 1,2,3. However, 5,6,7 is not
: a subsequence, 8,5,2 is also not a subsequence.
: A subsequence T is increasing is T[i] < T[i+1] for all i.
: Given a sequence S = 4, 9, 3, 8, 6, 7, 10 .... : we can have 3, 8, 10 or 4,
: 9, 10 or 4, 6,7,10 as its increasing subsequences.
: Our task is : given a sequence S of n numbers, count the number of
: increasing subsequences of S. Given an O( n log n) algorithm to accomplish
| S*******C
发帖数: 822 | 6 What is the number in each parenthesis?
How to you calculate the answer in the end?
)
)
【在 l*n 的大作中提到】
: 应该跟你后来贴的longest increasing subsequence 是类似的，毕竟复杂度都告诉你
: 了，明显是binary search。
: 思路应该大致是这样的，4(0) >> 4(0) 9(1) >> 3(0) 4(0) 9(1) >> 3(0) 4(0) 8(2)
: 9(1) >> 3(0) 4(0) 6(2) 8(2) 9(1) >> 3(0) 4(0) 6(2) 7(3+2) 8(2) 9(1) >> 3(0)
: 4(0) 6(2) 7(5) 8(2) 9(1) 10(6+2+5+2+1)
: 新进来一个数，binary search之后包含新数的序列数量是左边的数字个数加上他们的
: 序列数之和。
:
: of
: is
| S*******C
发帖数: 822 | 7 Anybody else who can help? | w*******s
发帖数: 96 | | w*******s
发帖数: 138 | 9 这道题有两种理解方式。当输入是[1, 1]的时候，有两个sequence满足条件，可是他们
都是[1]，所以根据理解的不同，答案可以是1，或者是2。有一种O(nlogn)的方法，不过
是针对答案是2的情形。
首先得将数组中的元素排序，并按数值大小编号，此时我们将原数组变换为新数组，新
数组中的元素值是原数组中数值大小的编号，新数组中的值是从1到n（n为原数组中不同
数值的个数），长度与原数组相同，对于新数组求解等同与对于原数组求解。
举例，原数组是[9,3,6,3]，变换为新数组为[3,1,2,1]
此变换需要排序，故时间复杂度为O(nlogn)
对于此数组（设为A)，我们可以用等同与求LIS的方法来计算个数(DP)，此方法的复杂度
为O(n^2)，DP的状态是对于每一个数组中的元素，我们记录以其为结尾的不同的subseq
uence的个数，设此数组为D。
在求D中每一个元素D[i]的过程中，我们需要对每一个在此元素之前 j < i，并且A[j]
< A[i]的D[j]求和，此操作可以用树状数组（或类似结构）优化为log n，故总时间复杂
度为O(n log n)，空间复杂度为O(n)用于保存树状数组。
树状数组介绍可以参见：http://hawstein.com/posts/binary-indexed-trees.html
【在 S*******C 的大作中提到】
: Anybody else who can help?
|
|
