838. Push Dominoes
難度: Medium
類型: Two Pointers, String, Dynamic Programming
前情題要:
給每個骨牌受到的推力, 計算出最後每個骨牌是倒左, 倒右, 或是直立。
There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.
After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.
When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.
For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.
You are given a string dominoes representing the initial state where:
dominoes[i] = 'L', if the ith domino has been pushed to the left,dominoes[i] = 'R', if the ith domino has been pushed to the right, anddominoes[i] = '.', if the ith domino has not been pushed.
Return a string representing the final state.
Example 1:
Input: dominoes = "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.
Example 2:
Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
Constraints:
n == dominoes.length1 <= n <= 105dominoes[i] is either 'L', 'R', or '.'.
思考方式:
1. 如果目前位置是 R (往右推), 那麼前面 first_R 到目前的位置都會是 R。同時把 first_R 更新為目前位置。
2. 如果目前位置是 L (往左推), 那麼前面 first_L或是從一開始到目前的位置都會是 L。同時把 first_L 更新為目前位置。如果沒有 first_L, 而有 first_R, 那麼正中間那個位置會是直立 '.', 中間偏左的位置是R, 中間偏右的位置是 L。
3. 最後檢查如果只有一個R, 沒有第二個R, 直到最後, 那麼從第一個R到最後都是 R。
複雜度思考:
Time Complexity: O( N + N )
Space Complexity: O( x )
結果:
Runtime: 2 ms, Beats: 92.24%
Memory: 11.99 MB, Beats: 42.15%
Accepted45 / 45 testcases passed
tendchen
submitted at Jun 17, 2025 14:36char* pushDominoes(char* dominoes) {
int size,i,j;
char *return_array=0;
int first_L=-1, first_R=-1;
size = strlen(dominoes);
//printf("size=%d\n",size);
return_array=malloc(size*sizeof(char)+1);
memset(return_array,'.',size);
return_array[size]='\0';
for (i=0;i<size;i++)
{
if (dominoes[i]=='R')
{
//printf("R at location(%d), first_R=%d, first_L=%d\n",i,first_R,first_L);
if (first_R==-1)
{
first_R=i;
}
else
{
for (j=first_R;j<=i;j++)
return_array[j]='R';
first_R=i;
}
}
else if (dominoes[i]=='L')
{
//printf("L at location(%d), first_R=%d, first_L=%d\n",i,first_R,first_L);
if (first_R==-1)
{
if (first_L==-1) first_L=0;
for (j=first_L;j<=i;j++)
return_array[j]='L';
first_L=i;
}
else //first_R >=0; first_L
{
if ((i-first_R)%2)
{
//left side:R, right side:L
for (j=first_R;j<=((first_R+i)/2);j++)
{
return_array[j]='R';
}
for (j=((first_R+i+1)/2);j<=i;j++)
{
return_array[j]='L';
}
}
else
{
//left side:R, right side:L, middle:'.'
for (j=first_R;j<((first_R+i)/2);j++)
{
return_array[j]='R';
}
for (j=(((first_R+i)/2)+1);j<=i;j++)
{
return_array[j]='L';
}
return_array[((first_R+i)/2)]='.';
}
first_R=-1;
first_L=i;
}
//return_array[i]=dominoes[i];
}
else
{
//do nothing
}
}
//printf("Deal with the rest parts! first_R=%d, first_L=%d\n",first_R,first_L);
if (first_R!=-1)
{
for (j=first_R;j<size;j++)
{
return_array[j]='R';
}
}
/*
printf("return_array=0x%X\n",return_array);
for (i=0;i<size;i++)
{
printf("%c",return_array[i]);
}
printf("\n");
printf("return_array=%s\n",return_array);
*/
return return_array;
}
