PushDominoes [source code]
public class PushDominoes {
static
/****************************************************************************/
class Solution {
public String pushDominoes(String dominoes) {
char[] chs = dominoes.toCharArray (), res = new char[dominoes.length ()];
int N = chs.length;
int[] left = new int[N], right = new int[N];
for (int i = 0; i < N; i++)
left[i] = chs[i] == 'L' || chs[i] == 'R' ? i : (i - 1 >= 0 ? left[i - 1] : -1);
for (int i = N - 1; i >= 0; i--)
right[i] = chs[i] == 'L' || chs[i] == 'R' ? i : (i + 1 < N ? right[i + 1] : N);
for (int i = 0; i < N; i++) {
int cur_left = left[i], cur_right = right[i];
if (cur_left == -1)
res[i] = (cur_right < N && chs[cur_right] == 'L') ? 'L' : '.';
else if (cur_right == N)
res[i] = (chs[cur_left] == 'R') ? 'R' : '.';
else {
if (chs[cur_left] == chs[cur_right])
res[i] = chs[cur_left];
else if (chs[cur_left] == 'L' && chs[cur_right] == 'R')
res[i] = '.';
else {
int left_dist = i - cur_left, right_dist = cur_right - i;
res[i] = left_dist == right_dist ? '.' : (left_dist < right_dist ? 'R' : 'L');
}
}
}
return new String (res);
}
}
/****************************************************************************/
public static void main(String[] args) {
PushDominoes.Solution tester = new PushDominoes.Solution();
String[] inputs = {
".L.R...LR..L..", "LL.RR.LLRRLL..",
"RR.L", "RR.L",
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String dominoes = inputs[2 * i], ans = inputs[2 * i + 1],
output = tester.pushDominoes (dominoes);
System.out.printf ("%s\n%s\n%s\n",
dominoes, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
);
}
}
}
感觉还是有点思路的, 稍微写写看;
一开始是希望针对L和R, 分别建立两个左右lookup, 这样就是有四个lookup数组;
但是后面写到主循环的时候, 发现这样的设计既不节省, 也会让最后的逻辑更复杂;
干脆只lookup最close的一个L或者R的index; 具体是L还是R, 到时候需要查询的时候再去access一下就行了;
最后还算是有惊无险的AC了, 速度是25(NA).
最后一个bug是(left_dist < right_dist ? 'R' : 'L')这个写反了, 有点粗心;
总体来说代码量也不算很大, 稍微有点啰嗦不过不算过分, 很好理解;
UNFINISHED
editorial
Approach #1: Adjacent Symbols [Accepted]
Intuition
Between every group of vertical dominoes ('.'), we have up to two non-vertical dominoes bordering this group. Since additional dominoes outside this group do not affect the outcome, we can analyze these situations individually: there are 9 of them (as the border could be empty). Actually, if we border the dominoes by 'L' and 'R', there are only 4 cases. We'll write new letters between these symbols depending on each case.
Algorithm
Continuing our explanation, we analyze cases:
- If we have say "A....B", where A = B, then we should write "AAAAAA".
- If we have "R....L", then we will write "RRRLLL", or "RRR.LLL" if we have an odd number of dots. If the initial symbols are at positions i and j, we can check our distance k-i and j-k to decide at position k whether to write 'L', 'R', or '.'.
- (If we have "L....R" we don't do anything. We can skip this case.)
看是看得懂, 非要用开花那题类似的那个思路来做; 感觉有点笨笨的;
class Solution {
public String pushDominoes(String dominoes) {
int N = dominoes.length();
int[] indexes = new int[N+2];
char[] symbols = new char[N+2];
int len = 1;
indexes[0] = -1;
symbols[0] = 'L';
for (int i = 0; i < N; ++i)
if (dominoes.charAt(i) != '.') {
indexes[len] = i;
symbols[len++] = dominoes.charAt(i);
}
indexes[len] = N;
symbols[len++] = 'R';
char[] ans = dominoes.toCharArray();
for (int index = 0; index < len - 1; ++index) {
int i = indexes[index], j = indexes[index+1];
char x = symbols[index], y = symbols[index+1];
char write;
if (x == y) {
for (int k = i+1; k < j; ++k)
ans[k] = x;
} else if (x > y) { // RL
for (int k = i+1; k < j; ++k)
ans[k] = k-i == j-k ? '.' : k-i < j-k ? 'R' : 'L';
}
}
return String.valueOf(ans);
}
}
感觉比我的啰嗦啊;
第一个for循环应该就是一个sparsify的操作, 不想用list来做, 就直接自己用数组来模拟;
两个平行数组分别存储index和value;
这个其实是有点类似我的lookup的思路的: 这题没有必要把L和R的lookup信息分开维护; 不仅浪费而且后面使用起来很麻烦;
换一个角度来说, L和R又不重合, 为什么一起维护呢?
基本就是一个主动分段的方法, 我认为其实实现起来比我的方法还复杂一些, 各种数学计算, 一不小心就算错了; 更直接的类似我的方法就是眼光针对每一个entry, 而不是强行建立这个分组的概念;
感觉这个算法肯定又是awice自己比赛的时候乱想的算法, 然后现在写editorial的时候非要加进来;
一个小技巧是他这个x > y, 用来进行一个类似char之间的的判断, 我自己实现的时候没有想到;
Approach #2: Calculate Force [Accepted]
Intuition
We can calculate the net force applied on every domino. The forces we care about are how close a domino is to a leftward 'R', and to a rightward 'L': the closer we are, the stronger the force.
Algorithm
Scanning from left to right, our force decays by 1 every iteration, and resets to N if we meet an 'R', so that force[i] is higher (than force[j]) if and only if dominoes[i] is closer (looking leftward) to 'R' (than dominoes[j]).
Similarly, scanning from right to left, we can find the force going rightward (closeness to 'L').
For some domino answer[i], if the forces are equal, then the answer is '.'. Otherwise, the answer is implied by whichever force is stronger.
class Solution {
public String pushDominoes(String S) {
char[] A = S.toCharArray();
int N = A.length;
int[] forces = new int[N];
int force = 0;
for (int i = 0; i < N; ++i) {
if (A[i] == 'R') force = N;
else if (A[i] == 'L') force = 0;
else force = Math.max(force - 1, 0);
forces[i] += force;
}
force = 0;
for (int i = N-1; i >= 0; --i) {
if (A[i] == 'L') force = N;
else if (A[i] == 'R') force = 0;
else force = Math.max(force - 1, 0);
forces[i] -= force;
}
StringBuilder ans = new StringBuilder();
for (int f: forces)
ans.append(f > 0 ? 'R' : f < 0 ? 'L' : 'V');
return ans.toString();
}
}
稍微简练了一些了;
大概看了看, 是类似我的思路, 但是不是完全一样, 他故意用一个force什么的东西, 其实代表的就是一个跟距离等价的概念, 类似这个:
最后某一个点的force到底是正还是负, 最终取决于的就是距离(到两头最近LR的距离);
大概是这么个意思, 没有特意去纠结了; 我认为他的两个方法都不如我的方法; 我的这个lookup思路是一个很熟练的routine了, 转化为熟悉的问题是我喜欢的一种做法;
uwi:
8分钟
class Solution {
public String pushDominoes(String dominoes) {
char[] s = dominoes.toCharArray();
int n = s.length;
char pre = 0;
int prepos = -1;
for(int i = 0;i < n;i++){
if(s[i] == 'L'){
if(pre == 'R'){
int K = (prepos+i+1)/2-prepos;
for(int j = 0;j < K;j++){
s[prepos+j] = 'R';
s[i-j] = 'L';
}
}else{
for(int j = prepos+1;j <= i;j++){
s[j] = 'L';
}
}
prepos = i;
pre = 'L';
}else if(s[i] == 'R'){
if(pre == 'R'){
for(int j = prepos;j < i;j++){
s[j] = 'R';
}
}
pre = 'R';
prepos = i;
}
}
if(pre == 'R'){
for(int i = prepos;i < n;i++)s[i] = 'R';
}
return new String(s);
}
}
很犀利的做法, 不过用Top-Down读代码的方法大概看了一下核心逻辑, 他是用的一个InPlace sparsify的思路去做的, 他就只关系所有的L和R, 然后走一遍, 只维护这些点的信息; 最后的思路其实跟editorial1是有点类似的, 但是他这个代码整体结构和实现细节都好很多;
反正就是维护两个相邻的LR, 然后判断中间的点应该干什么; 跟editorial1的那个开花分段思路其实是类似的;
看起来他因为有nested loop, 实际上最后worst case就是2N, 也不是说就不好, 毕竟我的做法也不是1N的;
Problem Description
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.
Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.
Return a string representing the final state.
Example 1:
Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
Example 2:
Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.
Note:
- 0 <= N <= 10^5
- String dominoes contains only 'L', 'R' and '.'
Difficulty:Medium
Total Accepted:1.6K
Total Submissions:4.3K
Contributor:lee215
Companies
google
Related Topics
two pointersdynamic programming