tag:blogger.com,1999:blog-8522573717713847738.post6005007939506251893..comments2024-03-28T00:14:29.070-07:00Comments on Yu's Coding Garden : leetcode Question 39: Jump Game IIAnonymoushttp://www.blogger.com/profile/00263085222060621782noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-8522573717713847738.post-70233418623315032352016-07-18T08:45:48.870-07:002016-07-18T08:45:48.870-07:00If no solution exits, adding this line inside whi...If no solution exits, adding this line inside while loop solves the issue.<br /><br />if(m==0) return -1;<br /><br />BTW Yu Zhu, you're Awesome :)Jagannadhhttps://www.blogger.com/profile/00503358527209597473noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-43164594484798643702015-03-09T07:17:36.337-07:002015-03-09T07:17:36.337-07:00will this DP solution be accepted on leetcode judg...will this DP solution be accepted on leetcode judge... I think it will give TLE. Please explain the time complexity.. Rockhttps://www.blogger.com/profile/00523101884887779302noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-77090951976015734002014-06-01T18:27:35.786-07:002014-06-01T18:27:35.786-07:00Do you mean I should check if there exist the solu...Do you mean I should check if there exist the solution or not ?<br /><br />I assume that the problem has at least one solution. <br /><br />To check the solution, I think simply check "if previous i == j" after the inner loop will perform well.<br /><br /><br />Thanks.Anonymoushttps://www.blogger.com/profile/00263085222060621782noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-40553364610126927252014-05-27T18:59:48.981-07:002014-05-27T18:59:48.981-07:00Have you considered such a case: whether you can r...Have you considered such a case: whether you can reach the last index as the case in Jump Game I?Anonymoushttps://www.blogger.com/profile/01694795219406772425noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-36327915431227314352014-02-02T08:30:39.980-08:002014-02-02T08:30:39.980-08:00I think the time complexity of your code is the sa...I think the time complexity of your code is the same as the aboveAnonymoushttps://www.blogger.com/profile/00263085222060621782noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-29712495164447091252014-01-31T13:36:28.315-08:002014-01-31T13:36:28.315-08:00But this solution may exceed the time limit. Here ...But this solution may exceed the time limit. Here I provide a solution using DP<br />int jump(int A[], int n) {<br /> int *jumps=new int[n];<br /> int i,j;<br /><br /> if(n==0 || A[0]==0)<br /> return 0;<br /><br /> jumps[0]=0;<br /><br /> for(i=1;i<n;i++)<br /> {<br /> jumps[i]=INT_MAX;<br /> for(j=0;j<i;j++)<br /> {<br /> if(i<=j+A[j] && jumps[j]!=INT_MAX)<br /> {<br /> jumps[i]=jumps[j]+1;<br /> break;<br /> }<br /> }<br /> }<br /> return jumps[n-1];<br /> }fyDenghttps://www.blogger.com/profile/15837125503408486714noreply@blogger.com