來自太空的 X 帖子
埃隆·馬斯克（Elon Musk）旗下太空探索技術公司 SpaceX 于 2 月 26 號，從太空往社交平臺 X（前身為推特，已被馬斯克全資收購并改名）發布帖子。
這是 SpaceX 官號首次通過星鏈來發送 X 帖子，馬斯克對此表示祝賀和肯定。
對于此事，馬斯克多次強調："該帖子是由 SpaceX 從一部普通手機直接發到衛星上的，中間沒有任何特殊設備！"
...
回到主線。
來做一道和「特斯拉」相關的面試算法題。
題目描述
平臺：LeetCode
題號：777
在一個由 'L' ,'R' 和 'X' 三個字符組成的字符串（例如 "RXXLRXRXL"）中進行移動操作。
一次移動操作指用一個 "LX" 替換一個 "XL"，或者用一個 "XR" 替換一個 "RX"。
現給定起始字符串 start 和結束字符串 end，請編寫代碼，當且僅當存在一系列移動操作使得 start 可以轉換成 end 時， 返回 True。
示例 :
輸入:?start?=?"RXXLRXRXL",?end?=?"XRLXXRRLX"
輸出:?True
解釋:
我們可以通過以下幾步將start轉換成end:
RXXLRXRXL?->
XRXLRXRXL?->
XRLXRXRXL?->
XRLXXRRXL?->
XRLXXRRLX
提示：
-
-
start和end中的字符串僅限于'L','R'和'X'
雙指針
根據題意，我們每次移動要么是將 XL 變為 LX，要么是將 RX 變為 XR，而該兩者操作可分別看做將 L 越過多個 X 向左移動，將 R 越過多個 X 向右移動。
因此在 start 和 end 中序號相同的 L 和 R 必然滿足坐標性質：
-
序號相同的 L:start的下標不小于end的下標（即L不能往右移動） -
序號相同的 R:start的下標不大于end的下標（即R不能往左移動）
其中「序號」是指在 LR 字符串中出現的相對順序。
Java 代碼：
class?Solution?{
????public?boolean?canTransform(String?start,?String?end)?{
????????int?n?=?start.length(),?i?=?0,?j?=?0;
????????while?(i?<?n?||?j?<?n)?{
????????????while?(i?<?n?&&?start.charAt(i)?==?'X')?i++;
????????????while?(j?<?n?&&?end.charAt(j)?==?'X')?j++;
????????????if?(i?==?n?||?j?==?n)?return?i?==?j;
????????????if?(start.charAt(i)?!=?end.charAt(j))?return?false;
????????????if?(start.charAt(i)?==?'L'?&&?i?<?j)?return?false;
????????????if?(start.charAt(i)?==?'R'?&&?i?>?j)?return?false;
????????????i++;?j++;
????????}
????????return?i?==?j;
????}
}
C++ 代碼：
class?Solution?{
public:
????bool?canTransform(string?start,?string?end)?{
????????int?n?=?start.size();
????????int?i?=?0,?j?=?0;
????????while?(i?<?n?||?j?<?n)?{
????????????while?(i?<?n?&&?start[i]?==?'X')?i++;
????????????while?(j?<?n?&&?end[j]?==?'X')?j++;
????????????if?(i?==?n?||?j?==?n)?return?i?==?j;
????????????if?(start[i]?!=?end[j])?return?false;
????????????if?(start[i]?==?'L'?&&?i?<?j)?return?false;
????????????if?(start[i]?==?'R'?&&?i?>?j)?return?false;
????????????i++;?j++;
????????}
????????return?i?==?j;
????}
};
Python 代碼：
class?Solution:
????def?canTransform(self,?start:?str,?end:?str)?->?bool:
????????i,?j,?n?=?0,?0,?len(start)
????????while?i?<?n?or?j?<?n:
????????????while?i?<?n?and?start[i]?==?'X':?i?+=?1
????????????while?j?<?n?and?end[j]?==?'X':?j?+=?1
????????????if?i?==?n?or?j?==?n:?return?i?==?j
????????????if?start[i]?!=?end[j]:?return?False
????????????if?start[i]?==?'L'?and?i?<?j:?return?False
????????????if?start[i]?==?'R'?and?i?>?j:?return?False
????????????i,?j?=?i?+?1,?j?+?1
????????return?i?==?j
TypeScript 代碼：
function?canTransform(start:?string,?end:?string):?boolean?{
????let?n?=?start.length;
????let?i?=?0,?j?=?0;
????while?(i?<?n?||?j?<?n)?{
????????while?(i?<?n?&&?start.charAt(i)?===?'X')?i++;
????????while?(j?<?n?&&?end.charAt(j)?===?'X')?j++;
????????if?(i?===?n?||?j?===?n)?return?i?===?j;
????????if?(start.charAt(i)?!==?end.charAt(j))?return?false;
????????if?(start.charAt(i)?===?'L'?&&?i?<?j)?return?false;
????????if?(start.charAt(i)?===?'R'?&&?i?>?j)?return?false;
????????i++;?j++;
????}
????return?i?===?j;
};
-
時間復雜度： -
空間復雜度：
我是宮水三葉，每天都會分享算法知識，并和大家聊聊近期的所見所聞。
歡迎關注，明天見。
更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的 合集新基地 🎉🎉
