|
| 1 | +/** |
| 2 | + * 838. Push Dominoes |
| 3 | + * ----------------------- |
| 4 | + * link: https://leetcode.com/problems/push-dominoes/ |
| 5 | + * |
| 6 | + * description: follow the rules of dominoes falling physics after one sec. |
| 7 | + * |
| 8 | + * time: O(n^2) |
| 9 | + * space: O(n) |
| 10 | + */ |
| 11 | + |
| 12 | +/** |
| 13 | + *@param {string} dominoes |
| 14 | + *@return {string} |
| 15 | + */ |
| 16 | +varpushDominoes=function(dominoes){ |
| 17 | +if(dominoes.length===1)returndominoes; |
| 18 | + |
| 19 | +letdominoesArr=[...dominoes]; |
| 20 | + |
| 21 | +for(leti=0;i<dominoesArr.length;i++){ |
| 22 | +if(dominoesArr[i]!=='.')continue; |
| 23 | + |
| 24 | +let[left,right]=nearestMove(dominoesArr,i); |
| 25 | + |
| 26 | +if(left===-1&&right===-1)continue; |
| 27 | + |
| 28 | +if(left===-1&&dominoesArr[right]==='L'){ |
| 29 | +dominoesArr[i]='L'; |
| 30 | +}elseif(right===-1&&dominoesArr[left]==='R'){ |
| 31 | +dominoesArr[i]='R'; |
| 32 | +}elseif(i-left!==right-i){ |
| 33 | +if(i-left<right-i&&dominoesArr[left]==='R'){ |
| 34 | +dominoesArr[i]='R'; |
| 35 | +dominoesArr[right-1]=dominoesArr[right]; |
| 36 | +}elseif(i-left>right-i&&dominoesArr[right]==='L'){ |
| 37 | +dominoesArr[i]='L'; |
| 38 | +dominoesArr[left+1]=dominoesArr[left]; |
| 39 | +}elseif(dominoesArr[left]===dominoesArr[right]){ |
| 40 | +dominoesArr[i]=dominoesArr[right]; |
| 41 | +} |
| 42 | +}elseif(dominoesArr[left]===dominoesArr[right]){ |
| 43 | +dominoesArr[i]=dominoesArr[right]; |
| 44 | +} |
| 45 | +} |
| 46 | + |
| 47 | +returndominoesArr.join(''); |
| 48 | +}; |
| 49 | + |
| 50 | +/** |
| 51 | + *@param {string[]} dominoes |
| 52 | + *@param {number} index |
| 53 | + *@returns {number[]} |
| 54 | + */ |
| 55 | +varnearestMove=function(dominoes,index){ |
| 56 | +letans=[-1,-1]; |
| 57 | + |
| 58 | +for(leti=index-1;i>-1;i--){ |
| 59 | +if(ans[0]===-1&&(dominoes[i]==='L'||dominoes[i]==='R')){ |
| 60 | +ans[0]=i; |
| 61 | +break; |
| 62 | +} |
| 63 | +} |
| 64 | + |
| 65 | +for(leti=index+1;i<dominoes.length;i++){ |
| 66 | +if(ans[1]===-1&&(dominoes[i]==='L'||dominoes[i]==='R')){ |
| 67 | +ans[1]=i; |
| 68 | +break; |
| 69 | +} |
| 70 | +} |
| 71 | + |
| 72 | +returnans; |
| 73 | +}; |