為什麼要寫本篇文章？看上去這是 easy 級別的題目。但“點是面的縮影，面是點的抽象”，單獨一道題似乎很簡單，我們可以比較輕鬆做出來。但是這一類題目的本質是什麼？不要處於混沌的狀態解決了題目，但下次遇到類似的，還是要遲疑思考一會兒。本篇文章帶你吃透問題的本質和背後的數學推導。
題目描述
字符串的左旋轉操作是把字符串前面的若干個字符轉移到字符串的尾部。
請定義一個函數實現字符串左旋轉操作的功能。比如：
- 輸入字符串 "abcdefg" 和數字 2
- 該函數將返回左旋轉 2 位後的結果 "cdefgab"
請實現該函數
結論
只要是字符串的左旋、右旋，都用整體逆序 + 部分逆序的方法，也可以是部分逆序 + 整體逆序。
分析
關於反轉（也就是逆序），有2個 feature：
-
反轉的可逆性：反轉(反轉(x)) = x
- 類似負負得正。比如：'123' 經過一次反轉後為 '321', '321' 再經過一次反轉為 '123'
-
反轉的可組合性：反轉 (A + B) = 反轉(B) + 反轉(A)
- '123456' 按照長度為3進行拆分為2部分，s1 + s2。s1 = '123', s2 = '456
- 先對後面的 s2，也就是'456' 反轉得到 '654'，即 s2' = '654'
- 再對前面的 s1，也就是'123' 反轉得到 '321'，即 s1' = '321'
- 再對 s1' 和 s2' 進行拼接， s1' + s2' = '654321'
- 觀察發現 s1' + s2' 就等於對整體 s1 + s2 逆序後的結果。
再來觀察看看：左旋、右旋題目要求的是什麼？
前提：假設一個逆序函數，可以將 x 作為輸入，輸出是 x'。這個共識、前提成立，我們再進行後續的推導：
- 原始字符串通過 k 為分割，可以拆分為： A + B。題目求的是什麼？ B + A
- 思考：根據上面的2個特性，通過什麼變化可以從 A + B，得到 B + A 呢？
不難得出結論，有2個方案： - 先整體逆序，
逆序 (A + B) = 逆序(B) + 逆序(A) = B' + A' - 再局部逆序，
逆序(B') + 逆序(A') = B + A
結論：我們發現這時候的結果剛好滿足題目要求。所以這些方法都是有跡可循的，符合數學羣論中的 “逆運算” 和 “運算律” 的思想
方法1：先整體逆序，再局部逆序
- 原始字符串通過 k 拆分為： A + B 的結構，左旋後變為 B + A
- 先整體逆序。
逆序(A) = A' 逆序(B) = B'。大的結構還是逆序(A + B) = B' + A' - 再局部逆序：
逆序(B') + 逆序(A') = B + A
結論：我們發現這時候的結果剛好滿足題目要求，不管是先局部再整體，還是先整體再局部，效果是等價的。
// 方法1: 先整體，再部分
const rotateLeft = (message, k) => {
const length = message.length
let datasource = Array.from(message)
const reverse = (datasource, fromIndex, toIndex) => {
for (; fromIndex < toIndex; fromIndex++, toIndex--) {
let temp = datasource[fromIndex]
datasource[fromIndex] = datasource[toIndex]
datasource[toIndex] = temp
}
}
// 1. 先整體逆序
reverse(datasource, 0, length - 1)
// 2. 再局部逆序
// 先對左半部分逆序
/*
已知：leftTo = k，leftLength = fullLength - k，求 leftTo？
注意：此時的 length 不等於 k，因為左旋的前半段為 k，剩餘的後半段 length 為完整的 length - k
leftTo - leftFrom + 1 = leftLength
leftTo = leftLength + leftFrom - 1
代入得到：
leftTo = (fullLength - k) + 0 - 1 = length - k - 1
*/
reverse(datasource, 0, length - k - 1)
// 再對右半部分逆序
/*
已知：rightTo = fullLength - 1，rightLength = k，求 rightFrom？
rightTo - rightFrom + 1 = rightLength
rightFrom = rightTo - rightLength + 1
代入得到：
rightFrom = (length - 1) - k + 1 = length - k
*/
reverse(datasource, length - k, length - 1)
// 3. 字符串數組拼接為結果
return datasource.join('')
}方法2：先部分逆序，再整體逆序
思考：能不能先局部逆序，再整體逆序？
分析：繼續用上面的思路推導下
- 原始字符串通過 k 拆分為： A + B 的結構，左旋後變為 B + A
- 先局部逆序：
逆序(A) + 逆序(B) = A' + B' - 再整體逆序。
逆序(A + B) = 逆序(B) + 逆序(A)。但是此刻我們的輸入為： A' + B'，
所以等價於：逆序(A' + B') = 逆序(B') + 逆序(A') = B + A
結論：我們發現這時候的結果剛好滿足題目要求，不管是先局部再整體，還是先整體再局部，效果是等價的。
// 方法2: 先部分，再整體
const rotateLeft1 = (message, k) => {
const length = message.length
let datasource = Array.from(message)
const reverse = (datasource, fromIndex, toIndex) => {
for (; fromIndex < toIndex; fromIndex++, toIndex--) {
let temp = datasource[fromIndex]
datasource[fromIndex] = datasource[toIndex]
datasource[toIndex] = temp
}
}
// 1. 再局部逆序
// abcdefg -> gfedc ba ->
// 先對左半部分逆序
/*
已知：leftTo = k，leftLength = fullLength - k，求 leftTo？
注意：此時的 length 不等於 k，因為左旋的前半段為 k，剩餘的後半段 length 為完整的 length - k
leftTo - leftFrom + 1 = leftLength
leftTo = leftLength + leftFrom - 1
代入得到：
leftTo = (fullLength - k) + 0 - 1 = length - k - 1
*/
reverse(datasource, 0, k - 1)
// 再對右半部分逆序
/*
已知：rightTo = fullLength - 1，rightLength = k，求 rightFrom？
rightTo - rightFrom + 1 = rightLength
rightFrom = rightTo - rightLength + 1
代入得到：
rightFrom = (length - 1) - k + 1 = length - k
*/
reverse(datasource, k, length - 1)
// 2. 先整體逆序
reverse(datasource, 0, length - 1)
// 3. 字符串數組拼接為結果
return datasource.join('')
}
