《剑指 Offer》字符串"左旋"、"右旋"里的数学秘密

为什么要写本篇文章?看上去这是 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'。这个共识、前提成立,我们再进行后续的推导:

1. 原始字符串通过 k 为分割,可以拆分为: A + B。题目求的是什么? B + A
2. 思考:根据上面的2个特性,通过什么变化可以从 A + B,得到 B + A 呢?
   不难得出结论,有2个方案:
3. 先整体逆序,逆序 (A + B) = 逆序(B) + 逆序(A) = B' + A'
4. 再局部逆序,逆序(B') + 逆序(A') = B + A

结论:我们发现这时候的结果刚好满足题目要求。所以这些方法都是有迹可循的,符合数学群论中的 "逆运算" 和 "运算律" 的思想

方法1:先整体逆序,再局部逆序

1. 原始字符串通过 k 拆分为: A + B 的结构,左旋后变为 B + A
2. 先整体逆序。逆序(A) = A' 逆序(B) = B'。大的结构还是逆序(A + B) = B' + A'
3. 再局部逆序:逆序(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:先部分逆序,再整体逆序

思考:能不能先局部逆序,再整体逆序?
分析:继续用上面的思路推导下

1. 原始字符串通过 k 拆分为: A + B 的结构,左旋后变为 B + A
2. 先局部逆序:逆序(A) + 逆序(B) = A' + B'
3. 再整体逆序。逆序(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('')
 }