logo
Redian新闻
>未名空间
>Biology - 生物学
>
bioinformatics job opportunity
avatar
bioinformatics job opportunity# Biology - 生物学
h*i
1 楼
Given an array of non-negative integers, you are initially positioned at the
first index of the array.
Each element in the array represents your maximum jump length at that
position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from
index 0 to 1, then 3 steps to the last index.)
我用greedy algorithm解的 但是超时了。
int jump(int A[], int n)
{
if(n<=1)
return 0;
int ret = 0;
int i = 0;
int index = -1;
while (i < n-1)
{
int maxDis = 0;
for(int j = 0; j<=A[i];++j)
{
if(j+A[i+j]>maxDis)
{
maxDis=j+A[i+j];
index = j;
}
}
i+=index;
++ret;
}
return ret;
}
avatar
g*e
3 楼
我前几天做出过 从后往前dp O(n）
avatar
a*a
4 楼
分子和细胞生物学的博士后，
比较熟悉java， linux，和sql，人在国内可以考虑不？
coding经验大概2万行的样子。
avatar
p*2
5 楼
这题是greedy不是dp吗？
avatar
b*r
6 楼
感兴趣。 美国毕业的统计博士， 有5年Perl programming experience (data
processing, Dynamic algorithm, simulation, FDR test), 3年 python programming
(Natural language process, Next generation sequencing analysis),
Bioinformatics 方法一作一篇，Cancer Research NGS analysis 共同一作一篇. 三年
分子生物学实验经验， JBC 一坐一篇。 发表一个R package. 有SAS advanced
certificate. 目前使用OPT.
谢谢
avatar
s*n
7 楼
恩，从后往前dp应该可以

【在 g*********e 的大作中提到】
: 我前几天做出过 从后往前dp O(n）
avatar
s*s
8 楼
有兴趣来芝加哥大学大数据科学中心么？
https://cdis.uchicago.edu/careers

programming

【在 b*******r 的大作中提到】
: 感兴趣。 美国毕业的统计博士， 有5年Perl programming experience (data
: processing, Dynamic algorithm, simulation, FDR test), 3年 python programming
: (Natural language process, Next generation sequencing analysis),
: Bioinformatics 方法一作一篇，Cancer Research NGS analysis 共同一作一篇. 三年
: 分子生物学实验经验， JBC 一坐一篇。 发表一个R package. 有SAS advanced
: certificate. 目前使用OPT.
: 谢谢
avatar
s*e
9 楼
from front to back
O(n).
each time select the max reachable postion to jump.
public static int jump(int [] A) {
if(A.length<=1)
return 0;
int jumpcount =0;
int i =0;
int currentmaxEnd =0;
while(icurrentmaxEnd = A[i]+i;
if(A[i]>0)
jumpcount++;
else
return 0;
if(currentmaxEnd>=A.length-1 )
return jumpcount;
int max = 0;
for(int j=i+1;j<=currentmaxEnd;j++){
if(A[j]+j >= max) {
max = A[j]+j;
i = j;
}
}

}
return jumpcount;
}

the
from

【在 h******i 的大作中提到】
: Given an array of non-negative integers, you are initially positioned at the
: first index of the array.
: Each element in the array represents your maximum jump length at that
: position.
: Your goal is to reach the last index in the minimum number of jumps.
: For example:
: Given array A = [2,3,1,1,4]
: The minimum number of jumps to reach the last index is 2. (Jump 1 step from
: index 0 to 1, then 3 steps to the last index.)
: 我用greedy algorithm解的 但是超时了。
avatar
f*n
10 楼
Dynamic algorithm
如果DP题做的很顺畅的话，为何不去google？

programming

【在 b*******r 的大作中提到】
: 感兴趣。 美国毕业的统计博士， 有5年Perl programming experience (data
: processing, Dynamic algorithm, simulation, FDR test), 3年 python programming
: (Natural language process, Next generation sequencing analysis),
: Bioinformatics 方法一作一篇，Cancer Research NGS analysis 共同一作一篇. 三年
: 分子生物学实验经验， JBC 一坐一篇。 发表一个R package. 有SAS advanced
: certificate. 目前使用OPT.
: 谢谢
avatar
g*y
11 楼
前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。
avatar
w*e
12 楼
薪水如何？

【在 s******s 的大作中提到】
: 有兴趣来芝加哥大学大数据科学中心么？
: https://cdis.uchicago.edu/careers
:
: programming
avatar
s*n
13 楼
在哪里? 去学习一下

【在 g**********y 的大作中提到】
: 前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。
avatar
p*2
16 楼
是

题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
★ Sent from iPhone App: iReader Mitbbs Lite 7.51

【在 s******n 的大作中提到】
: 题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
avatar
s*e
17 楼
a more concise version
public static int jump (int [] A) {
int jumpcount =0;
int startPos =0;
int max = 0;
int newmax = 0;
while(maxjumpcount++;
for(int i=startPos; i<=max;i++){
newmax = Math.max(newmax, A[i]+i);
}
startPos = max+1;
if(newmax<=max)
return -1;
max=newmax;
}
return jumpcount;
}



【在 s******e 的大作中提到】
: from front to back
: O(n).
: each time select the max reachable postion to jump.
: public static int jump(int [] A) {
: if(A.length<=1)
: return 0;
: int jumpcount =0;
: int i =0;
: int currentmaxEnd =0;
: while(i
avatar
h*f
18 楼
smalleye's solution is better...
in case anyone wants a dp version (from front to back):
int compute(int a[], int length) {
int b[length];
int max = std::numeric_limits::max();
for (int i = 0; i < length; i++) b[i] = -1; // not reachable
b[0] = 0; // first one is alway reachable
for (int i = 0; i < length; i++) {
if (b[i] >= 0) {
// only try if the current index is reachable
for (int j = i + 1; j <= i + a[i] && j < length; j++) {
if (1 + b[i] < b[j] || -1 == b[j]) {
b[j] = 1 + b[i];
if (b[j] < max && j == length - 1) max = b[j];
}
}
}
}
if (std::numeric_limits::max() == max) return -1;
return max;
}
O(n^2)
avatar
e*s
19 楼
这题DP O(n^2)好像是逃不了了，不知道有没有大牛有更牛B解法。

【在 h*****f 的大作中提到】
: smalleye's solution is better...
: in case anyone wants a dp version (from front to back):
: int compute(int a[], int length) {
: int b[length];
: int max = std::numeric_limits::max();
: for (int i = 0; i < length; i++) b[i] = -1; // not reachable
: b[0] = 0; // first one is alway reachable
: for (int i = 0; i < length; i++) {
: if (b[i] >= 0) {
: // only try if the current index is reachable
avatar
l*c
20 楼
lz,
你的方法有没有可能有一次最远跳的地方却是一个0啊，
那样greedy不work了啊, 0的时候如何操作是不是也要写下呢

the
from

【在 h******i 的大作中提到】
: Given an array of non-negative integers, you are initially positioned at the
: first index of the array.
: Each element in the array represents your maximum jump length at that
: position.
: Your goal is to reach the last index in the minimum number of jumps.
: For example:
: Given array A = [2,3,1,1,4]
: The minimum number of jumps to reach the last index is 2. (Jump 1 step from
: index 0 to 1, then 3 steps to the last index.)
: 我用greedy algorithm解的 但是超时了。
avatar
e*s
21 楼
public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.Min(Min, MinJumps[j] + 1);
}
MinJumps[i] = Min;
}
return MinJumps[MinJumps.Length - 1];
}
avatar
C*n
23 楼
Think like this: if A[i] = x, then A[i] has an edge (with weight all equal
to 1) to all A[i+1...i+x].
Then the problem is just a BFS to count the shortest path from A[0] to A[n-
1].

public int jump(int[] A) {
int count = 0;
int start=0, end=0, newend;
while (end < A.length-1){
count++;
newend = 0;
for (int i=start; i<=end; i++)
newend = i+A[i]>newend ? (i+A[i]) : newend;
start = end+1;
end = newend;
}
return count;h
}
avatar
D*d
24 楼
这个不是 shortest path algorithm 吗？而且是很特殊的，
复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
让 S[n] 表示到达每数的最小步数，
for(i = 1; i < LenArray; ++i){
S[i] = INF;
}
for(S[0]=0,i=1; i < LenArray; ++i){
for(j=0; j < min(Array[i],LenArray); ++j){
S[i+j] = min(S[i+j],S[i]+1);
}
}
最后的答案是 S[LenArray-1]
avatar
C*U
25 楼
你这个想法不错！！
jump game 1和2都能用这个办法解决 都变成tree transverse了
用bfs就可以了吧
而且是O(n)时间的

【在 D**********d 的大作中提到】
: 这个不是 shortest path algorithm 吗？而且是很特殊的，
: 复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
: 让 S[n] 表示到达每数的最小步数，
: for(i = 1; i < LenArray; ++i){
: S[i] = INF;
: }
: for(S[0]=0,i=1; i < LenArray; ++i){
: for(j=0; j < min(Array[i],LenArray); ++j){
: S[i+j] = min(S[i+j],S[i]+1);
: }
avatar
h*i
26 楼
Given an array of non-negative integers, you are initially positioned at the
first index of the array.
Each element in the array represents your maximum jump length at that
position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from
index 0 to 1, then 3 steps to the last index.)
我用greedy algorithm解的 但是超时了。
int jump(int A[], int n)
{
if(n<=1)
return 0;
int ret = 0;
int i = 0;
int index = -1;
while (i < n-1)
{
int maxDis = 0;
for(int j = 0; j<=A[i];++j)
{
if(j+A[i+j]>maxDis)
{
maxDis=j+A[i+j];
index = j;
}
}
i+=index;
++ret;
}
return ret;
}
avatar
g*e
27 楼
我前几天做出过 从后往前dp O(n）
avatar
p*2
28 楼
这题是greedy不是dp吗？
avatar
s*n
29 楼
恩，从后往前dp应该可以

【在 g*********e 的大作中提到】
: 我前几天做出过 从后往前dp O(n）
avatar
s*e
30 楼
from front to back
O(n).
each time select the max reachable postion to jump.
public static int jump(int [] A) {
if(A.length<=1)
return 0;
int jumpcount =0;
int i =0;
int currentmaxEnd =0;
while(icurrentmaxEnd = A[i]+i;
if(A[i]>0)
jumpcount++;
else
return 0;
if(currentmaxEnd>=A.length-1 )
return jumpcount;
int max = 0;
for(int j=i+1;j<=currentmaxEnd;j++){
if(A[j]+j >= max) {
max = A[j]+j;
i = j;
}
}

}
return jumpcount;
}

the
from

【在 h******i 的大作中提到】
: Given an array of non-negative integers, you are initially positioned at the
: first index of the array.
: Each element in the array represents your maximum jump length at that
: position.
: Your goal is to reach the last index in the minimum number of jumps.
: For example:
: Given array A = [2,3,1,1,4]
: The minimum number of jumps to reach the last index is 2. (Jump 1 step from
: index 0 to 1, then 3 steps to the last index.)
: 我用greedy algorithm解的 但是超时了。
avatar
g*y
31 楼
前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。
avatar
s*n
32 楼
在哪里? 去学习一下

【在 g**********y 的大作中提到】
: 前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。
avatar
p*2
35 楼
是

题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
★ Sent from iPhone App: iReader Mitbbs Lite 7.51

【在 s******n 的大作中提到】
: 题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
avatar
s*e
36 楼
a more concise version
public static int jump (int [] A) {
int jumpcount =0;
int startPos =0;
int max = 0;
int newmax = 0;
while(maxjumpcount++;
for(int i=startPos; i<=max;i++){
newmax = Math.max(newmax, A[i]+i);
}
startPos = max+1;
if(newmax<=max)
return -1;
max=newmax;
}
return jumpcount;
}



【在 s******e 的大作中提到】
: from front to back
: O(n).
: each time select the max reachable postion to jump.
: public static int jump(int [] A) {
: if(A.length<=1)
: return 0;
: int jumpcount =0;
: int i =0;
: int currentmaxEnd =0;
: while(i
avatar
h*f
37 楼
smalleye's solution is better...
in case anyone wants a dp version (from front to back):
int compute(int a[], int length) {
int b[length];
int max = std::numeric_limits::max();
for (int i = 0; i < length; i++) b[i] = -1; // not reachable
b[0] = 0; // first one is alway reachable
for (int i = 0; i < length; i++) {
if (b[i] >= 0) {
// only try if the current index is reachable
for (int j = i + 1; j <= i + a[i] && j < length; j++) {
if (1 + b[i] < b[j] || -1 == b[j]) {
b[j] = 1 + b[i];
if (b[j] < max && j == length - 1) max = b[j];
}
}
}
}
if (std::numeric_limits::max() == max) return -1;
return max;
}
O(n^2)
avatar
e*s
38 楼
这题DP O(n^2)好像是逃不了了，不知道有没有大牛有更牛B解法。

【在 h*****f 的大作中提到】
: smalleye's solution is better...
: in case anyone wants a dp version (from front to back):
: int compute(int a[], int length) {
: int b[length];
: int max = std::numeric_limits::max();
: for (int i = 0; i < length; i++) b[i] = -1; // not reachable
: b[0] = 0; // first one is alway reachable
: for (int i = 0; i < length; i++) {
: if (b[i] >= 0) {
: // only try if the current index is reachable
avatar
l*c
39 楼
lz,
你的方法有没有可能有一次最远跳的地方却是一个0啊，
那样greedy不work了啊, 0的时候如何操作是不是也要写下呢

the
from

【在 h******i 的大作中提到】
: Given an array of non-negative integers, you are initially positioned at the
: first index of the array.
: Each element in the array represents your maximum jump length at that
: position.
: Your goal is to reach the last index in the minimum number of jumps.
: For example:
: Given array A = [2,3,1,1,4]
: The minimum number of jumps to reach the last index is 2. (Jump 1 step from
: index 0 to 1, then 3 steps to the last index.)
: 我用greedy algorithm解的 但是超时了。
avatar
e*s
40 楼
public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.Min(Min, MinJumps[j] + 1);
}
MinJumps[i] = Min;
}
return MinJumps[MinJumps.Length - 1];
}
avatar
C*n
42 楼
Think like this: if A[i] = x, then A[i] has an edge (with weight all equal
to 1) to all A[i+1...i+x].
Then the problem is just a BFS to count the shortest path from A[0] to A[n-
1].

public int jump(int[] A) {
int count = 0;
int start=0, end=0, newend;
while (end < A.length-1){
count++;
newend = 0;
for (int i=start; i<=end; i++)
newend = i+A[i]>newend ? (i+A[i]) : newend;
start = end+1;
end = newend;
}
return count;h
}
avatar
D*d
43 楼
这个不是 shortest path algorithm 吗？而且是很特殊的，
复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
让 S[n] 表示到达每数的最小步数，
for(i = 1; i < LenArray; ++i){
S[i] = INF;
}
for(S[0]=0,i=1; i < LenArray; ++i){
for(j=0; j < min(Array[i],LenArray); ++j){
S[i+j] = min(S[i+j],S[i]+1);
}
}
最后的答案是 S[LenArray-1]
avatar
C*U
44 楼
你这个想法不错！！
jump game 1和2都能用这个办法解决 都变成tree transverse了
用bfs就可以了吧
而且是O(n)时间的

【在 D**********d 的大作中提到】
: 这个不是 shortest path algorithm 吗？而且是很特殊的，
: 复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
: 让 S[n] 表示到达每数的最小步数，
: for(i = 1; i < LenArray; ++i){
: S[i] = INF;
: }
: for(S[0]=0,i=1; i < LenArray; ++i){
: for(j=0; j < min(Array[i],LenArray); ++j){
: S[i+j] = min(S[i+j],S[i]+1);
: }
avatar
I*7
45 楼

这个方法 TLE，我开始就这么做的。结果大测试的最后一个数据是
[1800, 1799, 1798, ... 3, 2, 1, 1, 0],就是说前1800个都是最多能到 倒数第三个
数。

【在 D**********d 的大作中提到】
: 这个不是 shortest path algorithm 吗？而且是很特殊的，
: 复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
: 让 S[n] 表示到达每数的最小步数，
: for(i = 1; i < LenArray; ++i){
: S[i] = INF;
: }
: for(S[0]=0,i=1; i < LenArray; ++i){
: for(j=0; j < min(Array[i],LenArray); ++j){
: S[i+j] = min(S[i+j],S[i]+1);
: }
avatar
b*i
46 楼
应该使用广度优先
先设from数组，储存出发的下标，初始时只有0这个下标，然后设立到过数组，逻辑，
表示以前到过这里，
然后在from里面遍历，看是否到达最后一个下标，否则每一个可能的目标如果没到过，
则存到目标数组。完成后，把目标数组作为from无限循环。
这样，用有限的存储空间和BFS完成这个任务。其中注意，超时可以这样解决，生成目
标数组的时候，把远的目标先放进去。这只是因为测试的数据都是从大到小的。

the
from

【在 h******i 的大作中提到】
: Given an array of non-negative integers, you are initially positioned at the
: first index of the array.
: Each element in the array represents your maximum jump length at that
: position.
: Your goal is to reach the last index in the minimum number of jumps.
: For example:
: Given array A = [2,3,1,1,4]
: The minimum number of jumps to reach the last index is 2. (Jump 1 step from
: index 0 to 1, then 3 steps to the last index.)
: 我用greedy algorithm解的 但是超时了。
avatar
b*i
47 楼
TLE啥意思？

【在 I*********7 的大作中提到】
:
: 这个方法 TLE，我开始就这么做的。结果大测试的最后一个数据是
: [1800, 1799, 1798, ... 3, 2, 1, 1, 0],就是说前1800个都是最多能到 倒数第三个
: 数。
avatar
l*o
48 楼
public class Solution {
public int jump(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int curMax = 0; int nextMax = 0; int ans = 0;
for (int i = 0; i < A.length; i++) {
if (i <= curMax) {
if (A[i] + i > nextMax)
nextMax = A[i] + i;
} else {
curMax = nextMax;
ans++;
i--;
}
}
return ans;
}
}
avatar
t*r
49 楼
这题目如果有a[i] = 0的case
很多前面的算法就不成力了把
avatar
T*7
50 楼
this is a clear and good idea :)

【在 b***i 的大作中提到】
: 应该使用广度优先
: 先设from数组，储存出发的下标，初始时只有0这个下标，然后设立到过数组，逻辑，
: 表示以前到过这里，
: 然后在from里面遍历，看是否到达最后一个下标，否则每一个可能的目标如果没到过，
: 则存到目标数组。完成后，把目标数组作为from无限循环。
: 这样，用有限的存储空间和BFS完成这个任务。其中注意，超时可以这样解决，生成目
: 标数组的时候，把远的目标先放进去。这只是因为测试的数据都是从大到小的。
:
: the
: from
avatar
T*7
51 楼
temporary load expensive?

【在 b***i 的大作中提到】
: TLE啥意思？
avatar
l*b
52 楼
int jump(int A[], int n) {
int p = 0, q = 0, i = 0;
while(q < n-1) {
int m = q;
for(; p <= q; ++p)
m = max(m, p + A[p]);
if(m == q) return -1; // in case cannot reach end
q = m;
++i;
}
return i;
}
挺好做得这个，哈哈
avatar
h*6
53 楼
构造一个n顶点的有向图，把能到达的顶点连起来，然后用dijkstra求最短路径。
avatar
j*e
54 楼
前后都可以做出来的吧。
avatar
l*b
55 楼
time limit exceeded

【在 T******7 的大作中提到】
: temporary load expensive?
相关阅读
学术圈搞科研不要自我感觉良好了薄后们文献求助 (Science) 收到！非常感谢！求paper抗体工程方向--招聘--associate director/director请教： how to tag floxed gene in mice?没人讨论Varmus辞职么？广大钱老的衣食父母啊转发：2015年国际青年学者东湖论坛—生命科学分论坛【小白求救】有谁知道怎么分析q-pcr的raw reading啊？施一公忆父文观感Database Principal 101视频教程 (转载)糖尿病实验室招技术员施一公：父亲是我最崇拜的人这个同事想干什么？找工作，求内推求推荐precast polyacrylamide gels求文献一篇求文未来规划真诚求指点生物相关工作越来越难找了
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。