⌨️字符串挪移(baidu)

题目描述

1. 题目：给定一个长度为 $n$ 且只包含小写字母的字符串 $S$（下标从 1 开始）。进行 $n$ 次操作，第 $i$ 次操作将 $S[i]$ 移动到字符串的末尾。请输出经过 $n$ 次操作后的字符串。

   • 输入描述：在一行中输入一个由小写字母组成的字符串 $S$，其长度为 $n$（$1 \leq n \leq 10^6$）。

   • 输出描述：在一行中输出经过操作后的字符串。

2. 输入输出示例

   • 示例1：输入 paectc，输出 accept

   • 示例2：输入 abqde，输出 bdaeq

解题思想

常规想法 O(n^2)

基于对题目的分析，假设第 $i$ 次操作后的字符串记为 $S_i$。那么第 $i + 1$ 次操作后的字符串 $S_{i+1}$ 可以表示为：

$$S_{i+1} = S_i[0:i] + S_i[i+2:n] + S_i[i+1]$$

其中，$S_i[0:i]$ 表示字符串 $S_i$ 的前 $i$ 个字符，$S_i[i+2:n]$ 表示字符串 $S_i$ 从 $i+2$ 到 $n$ 的字符，而 $S[i+1]$ 是要移动到末尾的字符。由于题目要求进行 $n$ 次操作，而每次操作都需要按照上述公式更新字符串，因此整体的时间复杂度为 $O(n^2)$。

注意：String.slice(k1, k2) 的时间复杂度为 $O(k1-k2)$，因此一次字符串更新的时间复杂度为 $O(n)$，其中 $n$ 是字符串的长度。

以下是基于该常规想法的两个简单实现，

function rearrangeString1(S) {
  const length = S.length; // 原始字符串的长度
  let resStr = S; // 结果字符串

  for (let i = 0; i < length; i++) {
    const left = i > 0 ? resStr.slice(0, i) : ""; // 当前字符左边的子字符串
    const toBeMoved = resStr[i]; // 要移动到末尾的字符
    const right = i < length - 1 ? resStr.slice(i + 1) : ""; // 当前字符右边的子字符串
    resStr = left + right + toBeMoved; // 拼接字符串，将第 i 个字符移动到末尾
  }

  return resStr; // 返回经过 n 次操作后的最终结果
}

该实现的每次操作都基于当前字符串更新字符串。经过 $n$ 次操作后，字符串将更新 $n$ 次，第 $n$ 次更新的字符串就是最终的结果。时间复杂度为 $O(n^2)$。

function rearrangeString2(S) {
  const length = S.length; // 原始字符串的长度
  // 结果字符串和原始字符串的字符索引映射
  // resIndexMap[结果字符串字符索引] = 原始字符串字符索引
  const resIndexMap = Array.from({ length }, (_, index) => index);

  for (let i = 0; i < length; i++) {
    const toBeMoved = resIndexMap.splice(i, 1)[0]; // 获取要移动到末尾的字符对应的索引
    resIndexMap.push(toBeMoved); // 将第 i 个字符对应的索引移到映射的最后
  }

  // 根据映射关系生成结果字符串
  const resStr = resIndexMap.reduce((accu, cur) => accu + S[cur], ""); 
  return resStr; // 返回最终的结果字符串
}

该实现将每次的字符串更新修改为索引映射的更新，减少了因字符串裁切和创建带来的性能消耗。时间复杂度仍然为 $O(n^2)$。

找规律 O(nlogn)

基于对字符串操作过程的分析，从而寻找其中隐含的规律。

案例分析1

令 $s = 123456789abcdef$，对字符串 $s$ 进行 $15$ 次操作（字符串使用 1-based 表示）。同时定义：

• $s_i$ 表示第 $i$ 次操作后的字符串（$s_0$ 即原始字符串 $s$）
• $oIndex$ 表示当前要移动到末尾的字符在 “原始字符串” 中的索引
• $cIndex$ 表示当前要移动到末尾的字符在 “上一次操作后的字符串” 中的索引，即 $cIndex === i$
• $rIndex$ 表示当前要移动到末尾的字符在 “本轮参考字符串” 中的索引，其中 $s_b$ 为本轮参考字符串（第 $1$ 轮的本轮参考字符串为原始字符串 $s$；第 $i$ 轮的本轮参考字符串为第 $i - 1$ 轮最后一次操作得到的字符串）

第 $i$ 次	移动 $s[oIndex] = s_i[cIndex] = s_b[rIndex]?$	到 $s_{i-1}$ 末尾得到 $s_i=?$
1	$s[1] = s_0[1] = s_0[1] = 1$	$s_1 = 23456789abcdef1$
2	$s[3] = s_1[2] = s_0[3] = 3$	$s_2 = 2456789abcdef13$
3	$s[5] = s_2[3] = s_0[5] = 5$	$s_3 = 246789abcdef135$
4	$s[7] = s_3[4] = s_0[7] = 7$	$s_4 = 24689abcdef1357$
5	$s[9] = s_4[5] = s_0[9] = 9$	$s_5 = 2468abcdef13579$
6	$s[11] = s_5[6] = s_0[11] = b$	$s_6 = 2468acdef13579b$
7	$s[13] = s_6[7] = s_0[13] = d$	$s_7 = 2468acef13579bd$
8	$s[15] = s_7[8] = s_0[15] = f$	$s_8 = 2468ace13579bdf$
9	$s[3] = s_8[9] = s_8[9] = 3$	$s_9 = 2468ace1579bdf3$
10	$s[7] = s_9[10] = s_8[11] = 7$	$s_{10} = 2468ace159bdf37$
11	$s[11] = s_{10}[11] = s_8[13] = b$	$s_{11} = 2468ace159df37b$
12	$s[15] = s_{11}[12] = s_8[15] = f$	$s_{12} = 2468ace159d37bf$
13	$s[7] = s_{12}[13] = s_{12}[13] = 7$	$s_{13} = 2468ace159d3bf7$
14	$s[15] = s_{13}[14] = s_{12}[15] = f$	$s_{14} = 2468ace159d3b7f$
15	$s[15] = s_{14}[15] = s_{14}[15] = f$	$s_{15} = 2468ace159d3b7f$

15 次操作可以抽象为 4 轮移动

第一轮：参考 $s_0$，从 $1$ 开始，每隔一位字符就要移动，即需要移动 $s_0$ 的第 $1、3、5、7、9、11、13、15$ 共 $8$ 个字符

第二轮：参考 $s_8$，从 $9$ 开始，每隔一位字符就要移动，即需要移动 $s_8$ 的第 $9、11、13、15$ 共 $4$ 个字符

第三轮：参考 $s_{12}$，从 $13$ 开始，每隔一位字符就要移动，即需要移动 $s_9$ 的第 $13、15$ 共 $2$ 个字符

第四轮：参考 $s_{15}$，从 $15$ 开始，每隔一位字符就要移动，即需要移动 $s_{14}$ 的第 $15$ 共 $1$ 个字符

经过四轮，操作次数为 $15$，终止操作！

案例分析2

令 $s = paectc$ 现对字符串 $s$ 进行 $6$ 次操作，（字符串使用 1-based 表示）。同时如上定义 $s_i$、$oIndex$、$cIndex$、$rIndex$、$s_b$。

第 $i$ 次	移动 $s[oIndex] = s_i[cIndex] = s_b[rIndex]?$	到 $s_{i-1}$ 末尾得到 $s_i=?$
1	$s[1] = s_0[1] = s_0[1] = p$	$s_1 = aectcp$
2	$s[3] = s_1[2] = s_0[3] = e$	$s_2 = actcpe$
3	$s[5] = s_2[3] = s_0[5] = t$	$s_3 = accpet$
4	$s[1] = s_3[4] = s_3[4] = p$	$s_4 = accetp$
5	$s[5] = s_4[5] = s_3[6] = t$	$s_5 = accept$
6	$s[6] = s_5[6] = s_5[6] = t$	$s_6 = accept$

6 次操作可以抽象为 3 轮移动

第一轮：参考 $s_0$，从 $1$ 开始，每隔一位字符就要移动，即需要移动 $s_0$ 的第 $1、3、5$ 共 $3$ 个字符

第二轮：参考 $s_3$，从 $4$ 开始，每隔一位字符就要移动，即需要移动 $s_3$ 的第 $4、6$ 共 $2$ 个字符

第三轮：参考 $s_5$，从 $6$ 开始，每隔一位字符就要移动，即需要移动 $s_5$ 的第 $6$ 共 $1$ 个字符

经过三轮，操作次数为 $6$，终止操作！

规律抽象：基于上述案例分析，我们可以抽象出用于解题的一般性规律。

对于字符串 $S$，假设其长度为 $length$，同时定义以下变量：

• $crStr$ 表示当前轮次的字符串（current round string），初始时 $crStr = S$
• $crIndex$ 表示当前轮次的起始索引（current round index），初始时 $crIndex = 1$
• $armCount$ 表示已移动的字符数量（all rounds moved count），初始时 $armCount = 0$

使用 while 循环，循环的终止条件为 $armCount \ge length$。每次循环的内容如下：

1. 根据 $crIndex$ 和 $length$ 确定本轮要移动的所有字符索引：$crIndex, crIndex + 2, crIndex + 4, \dots$（不超过 $length$ 的索引）。
2. 根据确定的要移动字符的索引：
   • 生成下一轮的 $crStr$，将这些字符移动到字符串的末尾。
   • 更新 $armCount$，即 $armCount += \text{移动字符的数量}$。
   • 更新下一轮的 $crIndex$，即 $crIndex += \text{本轮移动字符的数量}$。

时间复杂度分析

• 外部循环次数：观察上述案例分析可知，对于长度为 $n$ 的字符串，第一轮进行 $\lceil n/2 \rceil$ 次操作，第二轮进行 $\lceil n - \lceil n/2 \rceil \rceil$ 次操作，依次递减，最后一轮进行 $1$ 次操作。总轮次就是 while 循环的次数，记总轮次为 $x$，则有：

  $$n \cdot 2^{-x} < 1 \Rightarrow x > \log_2 n$$

  因此，外部循环的时间复杂度为 $O(\log n)$。

• 内部操作次数：每轮操作涉及字符的移动，初始时的时间复杂度为 $O(n)$，但随着轮次的增加，移动的字符数量逐渐减少。因此，虽然最坏情况下的内部操作为 $O(n)$，但实际移动的元素会逐渐减少。

综合来看，外部循环的次数为 $O(\log n)$，而每次循环中的操作为 $O(n)$，因此总体时间复杂度为 $O(n \log n)$。然而，考虑到后续操作中的移动字符数量逐渐减少，实际的时间复杂度可能会更小。

单向链表 O(n)

在题目中，对字符串的操作描述为：第 $i$ 次将当前字符串的第 $i$ 个字符移动到字符串末尾。由于数组中元素移动的时间复杂度较高，因此我们可以考虑使用单向链表来优化操作。

通过对任意字符串的操作过程的分析，我们需要定义至少四个指针：head：指向链表的头节点；current：指向当前要移动到末尾的节点；prev：指向当前要移动节点的前一个节点；tail：指向链表的尾节点。

解题步骤

Step1. 初始化链表：

• 使用给定字符串初始化一个单向链表，记为 linkedList。
• 初始化时，head、prev 和 current 指向链表的第一个节点，而 tail 指向链表的最后一个节点。

Step2. 执行移动操作：

• 在每次移动操作中，我们首先需要将 prev 指向 current 节点的下一个节点。这样可以方便我们处理 current 节点的移动。
• 将 current 节点移动到链表的末尾：将 current 指向的节点添加到 tail 的后面，并更新 tail 指针。
• 更新 current 为 prev 指向的节点的下一个节点，这样在下一轮中我们可以继续处理下一个要移动的节点。
• 当 current 指向 tail 时，表示已经完成 $n$ 次操作，循环终止。

时间复杂度：该分析流程与[找规律](#找规律 O(nlogn))类似。由于在循环内部的操作涉及到链表节点的删除和追加，而这些操作在单向链表中可以在常数时间内完成，因此它们的时间复杂度为 $O(1)$。因此，整个算法的总时间复杂度为 $O(n)$，其中 $n$ 是链表中节点的数量。

感触：使用单向链表实现还是蛮复杂的！

代码实现

找规律

function rearrangeString3(S) {
  const length = S.length; // 字符串的总长度

  let currentStr = S, // 当前处理的字符串，对应 crStr
    startIndex = 1, // 当前轮次的起始索引，对应 crIndex
    movedCount = 0; // 已移动的字符数量，对应 armCount

  while (movedCount < length) {
    // 1. 计算要移动到末尾的字符索引和剩余保持顺序的字符索引
    const [moveToEndIndices, remainIndices] = [[], []];
    for (let i = startIndex; i <= length; i++) {
      (i - startIndex) % 2 === 0 ? moveToEndIndices.push(i) : remainIndices.push(i);
    }

    // 2. 根据计算的索引重新构建当前轮次的字符串
    const moveToEndChars = moveToEndIndices.reduce(
      (result, index) => result + currentStr[index - 1], ""
    );
    const remainChars =
      currentStr.slice(0, startIndex - 1) +
      remainIndices.reduce((result, index) => result + currentStr[index - 1], "");

    currentStr = remainChars + moveToEndChars;

    // 3. 更新已移动字符数量
    movedCount += moveToEndIndices.length;
    // 4. 更新起始索引
    startIndex += moveToEndIndices.length;
  }

  return currentStr;
}

单向链表

class LinkedList {
  constructor() {
    this.head = null; // 头指针
    this.tail = null; // 尾指针
    this.length = 0; // 节点数量
  }

  append(value) {
    const newNode = new Node(value);
    if (this.length === 0) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  static fromString(str) {
    const linkedList = new LinkedList();
    for (let ele of str) linkedList.append(ele);
    return linkedList;
  }

  toString() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    return values.join("");
  }
}

class Node {
  constructor(value) {
    this.value = value; // 节点值
    this.next = null; // 节点指向
  }
}

function rearrangeString4(S) {
  const linkedList = LinkedList.fromString(S);
  if (!linkedList.head || linkedList.head === linkedList.tail) return S;

  let current = linkedList.head;
  let prev = null;

  for (let i = 0; i < S.length - 1; i++) {
    if (current === null) {
      // 如果已经到达链表末尾，重新从头开始
      current = linkedList.head;
      prev = null;
    }

    if (prev === null) {
      // 移动头节点
      linkedList.head = current.next;
      linkedList.tail.next = current;
      current.next = null;
      linkedList.tail = current;
      current = linkedList.head;
    } else {
      // 移动非头节点
      let temp = current.next;
      prev.next = temp;
      linkedList.tail.next = current;
      current.next = null;
      linkedList.tail = current;
      current = temp;
    }

    if (current !== null) {
      prev = current;
      current = current.next;
    }
  }

  return linkedList.toString();
}

代码测试

单元测试

import { describe, test } from "node:test";
import { strict as assert } from "node:assert";
import {
  rearrangeString1,
  rearrangeString2,
  rearrangeString3,
  rearrangeString4,
} from "./LinkedList.mjs";

describe("字符串挪移", () => {
  test("常规想法1", () => {
    assert.equal(rearrangeString1("paectc"), "accept");
    assert.equal(rearrangeString1("abqde"), "bdaeq");
  });
  test("常规想法2", () => {
    assert.equal(rearrangeString2("paectc"), "accept");
    assert.equal(rearrangeString2("abqde"), "bdaeq");
  });
  test("找规律", () => {
    assert.equal(rearrangeString3("paectc"), "accept");
    assert.equal(rearrangeString3("abqde"), "bdaeq");
  });
  test("单向链表", () => {
    assert.equal(rearrangeString4("paectc"), "accept");
    assert.equal(rearrangeString4("abqde"), "bdaeq");
  });
});

时间复杂度测试

import {
  rearrangeString1,
  rearrangeString2,
  rearrangeString3,
  rearrangeString4,
} from "./LinkedList.mjs";

function generateRandomString(length) {
  let result = "";
  const characters = "abcdefghijklmnopqrstuvwxyz";
  const charactersLength = characters.length;
  for (let i = 0; i < length; i++) {
    result += characters.charAt(Math.floor(Math.random() * charactersLength));
  }
  return result;
}

const longRandomString = generateRandomString(100000);

console.time("常规想法1");
const res1 = rearrangeString1(longRandomString);
console.timeEnd("常规想法1");

console.time("常规想法2");
const res2 = rearrangeString2(longRandomString);
console.timeEnd("常规想法2");

console.time("找规律");
const res3 = rearrangeString3(longRandomString);
console.timeEnd("找规律");

console.time("单向链表");
rearrangeString4(longRandomString);
console.timeEnd("单向链表");

• length = 100000 时，

  常规想法1: 2.471s
  常规想法2: 1.068s
  找规律: 25.164ms
  单向链表: 30.162ms

• length = 1000 时，

  常规想法1: 3.128ms
  常规想法2: 0.955ms
  找规律: 1.301ms
  单向链表: 2.247ms

• length = 10 时，

  常规想法1: 0.366ms
  常规想法2: 0.456ms
  找规律: 0.454ms
  单向链表: 0.629ms

综合上述分析，当字符串足够大时，找规律的方法优于单向链表实现，单向链表又优于常规想法2，而常规想法2则优于常规想法1。