Nice solution, one thing make the code neat is using:
int[] dx = {-1,-2,-2,-1,1,2, 2, 1};
int[] dy = {-2,-1, 1, 2,2,1,-1,-2};
Make it an iteration rather than write 8 lines.
Nice solution, one thing make the code neat is using:
int[] dx = {-1,-2,-2,-1,1,2, 2, 1};
int[] dy = {-2,-1, 1, 2,2,1,-1,-2};
Make it an iteration rather than write 8 lines.
int n;
double[][][] dp;
public double knightProbability(int size, int k, int r, int c) {
n=size;
dp = new double[n][n][k+1];
return helper(k,r,c);
}
int[] dx = {-1,-2,-2,-1,1,2, 2, 1};
int[] dy = {-2,-1, 1, 2,2,1,-1,-2};
public double helper(int k, int r, int c){
if(r<0||c<0||r>=n||c>=n)return 0;
if(k==0)return 1;
if(dp[r][c][k]!=0)return dp[r][c][k];
for(int i=0;i<dx.length;i++){
dp[r][c][k]+=0.125*helper(k-1,r+dx[i],c+dy[i]);
}
return dp[r][c][k];
}
The key is:
From last digit to first digit:
Find one number from four digits that can make it larger, if found, set the following digits to min, if not found, continue this on the digit before it.
When reach -1 th digit, means there is no solution bigger than input, just set all digits to min and return.
char min, max;
char[] time;
public String nextClosestTime(String s) {
time = s.toCharArray();
min=(char)Math.min(Math.min(time[0],Math.min(time[1],time[3])),time[4]);
max=(char)Math.max(Math.max(time[0],Math.max(time[1],time[3])),time[4]);
solve(4);//try looking for solution from last digits to first digits
if(time[0]=='#'){ //no solution found, turn to another day
Arrays.fill(time,min);
time[2]=':';
}
return new String(time);
}
public void solve(int i){//from the ith position, look for smallest value that is bigger than it
if(i<0){//didn't find any, mark no solution, need to turn to another day
time[0]='#';
return;
}
if(i==2){//':' sign, jump cross it
solve(1);
return;
}
char ans = max;
for(int j=0;j<5;j++){//try to find a suitable number to replace ith position
if(j!=2&&time[j]>time[i]) ans=(char)Math.min(ans,time[j]);
}
if(ans==time[i]||!isvalid(i,ans)){//didn't find a suitable one or the one found is not valid, go to i-1
solve(i-1);
return;
}
time[i]=ans;//set the number
for(int j=i+1;j<5;j++){//set the following number to smallest value possible
if(j!=2)time[j]=min;
}
}
public boolean isvalid(int i,char ans){
if(i==3)return ans<'6';
if(i==1)return time[i-1]<'2'||(time[i-1]=='2'&&ans<'4');
if(i==0)return ans<'2'||(ans=='2'&&time[i+1]<'4');
return true;
}
@zhangsikai123
But they gave parent-child relationship...it is not undirected...
I used brute force and quite confident about the correctness.
The test case: [[5,2],[3,4],[4,3],[5,3],[1,3]]
My result provide null because there is no solution.
But the expected answer is [4,3], which leaves node 3 still has two parent.
@jiayi.zhang1993
The definition is asking a tree with parents, childs well defined.
But it turned out to be remove an edge in an undirected graph to make it a tree.
All the accepted answers are wrong technically.
@wavy
The problem definition clearly defines edge[parent, child] format.
Which means the expected solution will make a child node has two parent node.
I noticed there is a test case [[5,2],[3,4],[4,3],[5,3],[1,3]]
The definition for edge is [parent, child].
Which means node 3 has THREE parent, even you remove one (expected answer is [4,3]), node 3 still has two parent...
I cannot pass this test...
They should clarify this is an undirected graph!