a****a
发帖数: 186 | 1 Print all the increasing subsequence from the given range 54782369862345 ..
ex: 5,7,8,9; 4,7,8,9; 2,3,6,9 ..
这个题除了brute forth解法外，还有什么巧妙的解法吗？欢迎大家赐教~ | a********m
发帖数: 15480 | 2 不算简单题吧。。。。
问清楚一下，需要从头到尾么？或者从中间到尾，还是任何起止点都可以？ | g**********y
发帖数: 14569 | 3 这个题我感觉不是想考你巧妙解，就是考基本coding的技能。
每个点为起点的increasing sequence只用算一次，算完可以存在数组里。
.
【在 a****a 的大作中提到】
: Print all the increasing subsequence from the given range 54782369862345 ..
: ex: 5,7,8,9; 4,7,8,9; 2,3,6,9 ..
: 这个题除了brute forth解法外，还有什么巧妙的解法吗？欢迎大家赐教~
| d***o
发帖数: 181 | | y*****n
发帖数: 243 | 5 I've see a similar question before, just cannot figure it out. come from http://blog.csdn.net/v_july_v/article/details/6870251
求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，
5，
4，3，2}
ANSWER:
Scan from left to right, maintain a decreasing sequence. For each number,
binary search in the decreasing sequence to see whether it can be
substituted.
int[] findDecreasing(int[] a) {
int[] ds = new int[a.length];
Arrays.fill(ds, 0);
int dsl = 0;
int lastdsl = 0;
for (int i=0; i
// binary search in ds to find the first element ds[j] smaller than a[i]
. set ds[j] = a[i], or append a[i] at the end of ds
int s=0, t=dsl-1;
while (s<=t) {
int m = s+(t-s)/2;
if (ds[m] < a[i]) {
t = m - 1;
} else {
s = m + 1;
}
}
// now s must be at the first ds[j]
ds[s] = a[i];
if (s > dsl) { dsl = s; lastdsl = i; }
}
// now trace back.
for (int i=lastdsl-1, j=dsl-1; i>=0 && j >= 0; i--) {
if (a[i] == ds[j]) { j --; }
else if (a[i] < ds[j]) { ds[j--] = a[i]; }
}
return Arrays.copyOfRange(ds, 0, dsl+1);
} | a****a
发帖数: 186 | 6 从任何起点都可以
【在 a********m 的大作中提到】
: 不算简单题吧。。。。
: 问清楚一下，需要从头到尾么？或者从中间到尾，还是任何起止点都可以？
| a****a
发帖数: 186 | 7 你这个题是求最长降序子序列，我第一反应就是用DP求9-0和给定数组的LCS
你给的解法有空研究一下看看时间复杂度是多少。给的链接收藏了..好资源
【在 y*****n 的大作中提到】
: I've see a similar question before, just cannot figure it out. come from http://blog.csdn.net/v_july_v/article/details/6870251
: 求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，
: 5，
: 4，3，2}
: ANSWER:
: Scan from left to right, maintain a decreasing sequence. For each number,
: binary search in the decreasing sequence to see whether it can be
: substituted.
: int[] findDecreasing(int[] a) {
: int[] ds = new int[a.length];
| H***e
发帖数: 476 | 8 为什么只用算一次呢？
每个点为起点的可能有多个符合条件的序列啊
展开烁烁？
【在 g**********y 的大作中提到】
: 这个题我感觉不是想考你巧妙解，就是考基本coding的技能。
: 每个点为起点的increasing sequence只用算一次，算完可以存在数组里。
:
: .
| a*****g
发帖数: 13 | 9 My solution:
1. build a graph by storing "possible next digits" for each digit.
2. dfs each digit in the graph.
#include
#include
using std::vector;
using std::string;
struct Node {
int value;
vector next;
Node(int v) {
value = v;
}
};
void build_tree(vector &input) {
for (unsigned i=0;i
for (unsigned j=i+1;j
if (input[i].value < input[j].value) {
input[i].next.push_back(j);
}
}
}
}
void traverse_tree(const vector &input, int index, vector values)
{
values.push_back(input[index].value);
if (input[index].next.size() == 0) {
for (unsigned i=0;i
printf("%d ", values[i]);
}
printf("\n");
}
for (unsigned i=0; i
traverse_tree(input, input[index].next[i], values);
}
}
int main(int argc, char* argv[])
{
vector input;
string s="54782369862345";
for (unsigned i=0; i
input.push_back(s[i]-'0');
}
build_tree(input);
vector values;
for (unsigned i=0; i
traverse_tree(input, i, values);
}
return 0;
}
【在 H***e 的大作中提到】
: 为什么只用算一次呢？
: 每个点为起点的可能有多个符合条件的序列啊
: 展开烁烁？
|
|
