由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 新人刚刚开始认真找工作,问个简单的题(1)
相关主题
面试问题,最长翻转整数问题帮我看看这两个题目回答
问一个题,求相同元素最多的两个数组fb电面第一轮
一朋友被Google的电面干掉了 (转载)Bloomberg面试题
寻找子序列/子段落问一下dynamic programming的常见问题
Facebook interview 面经Linkedin 工资不高啊
Amazon Summer Intern Offer, 发面经贡献F家Onsite一题
nlogn for longest increasing subsequence被简单题给虐了。
请教道算法题DP通项公式
相关话题的讨论汇总
话题: int话题: ds话题: input话题: vector话题: node
进入JobHunting版参与讨论
1 (共1页)
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
4
数据还可以重复输出,最快也就o(n^2)了吧
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 的大作中提到】
: 为什么只用算一次呢?
: 每个点为起点的可能有多个符合条件的序列啊
: 展开烁烁?

1 (共1页)
进入JobHunting版参与讨论
相关主题
DP通项公式Facebook interview 面经
新手请教:C++ decrement loop (转载)Amazon Summer Intern Offer, 发面经
问个算法题5nlogn for longest increasing subsequence
BB的面试题-只用&和| 如何reverse a bit string?请教道算法题
面试问题,最长翻转整数问题帮我看看这两个题目回答
问一个题,求相同元素最多的两个数组fb电面第一轮
一朋友被Google的电面干掉了 (转载)Bloomberg面试题
寻找子序列/子段落问一下dynamic programming的常见问题
相关话题的讨论汇总
话题: int话题: ds话题: input话题: vector话题: node