竹与剑 發表於 2025-11-27 09:00:00

剑指offer-43、左旋转字符串

<h2 id="题描述">题⽬描述</h2>
<p>汇编语⾔中有⼀种移位指令叫做循环左移（ ROL ），现在有个简单的任务，就是⽤字符串模拟这个指令的运算结果。对于⼀个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列S=”abcXYZdef” ,要求输出循环左移3位后的结果，即“ XYZdefabc ”。是不是很简单？OK，搞定它！</p>
<h2 id="思路及解答">思路及解答</h2>
<p>这道题⽬的意思就是将前⾯ n 位，移动到后⾯，那么我们可以直接从第 n+1 位开始，遍历到最后⼀个，再拼接上前⾯ n 个。</p>
<h3 id="暴力移位">暴力移位</h3>
<p>通过k次单步左移实现循环左移。将第一个字符保存，其余字符前移，最后字符放到末尾</p>
<pre><code class="language-java">public class Solution {

    public String leftRotateString(String str, int n) {
      if (str == null || str.length() == 0 || n &lt;= 0) {
            return str;
      }
      
      char[] chars = str.toCharArray();
      int len = chars.length;
      n %= len; // 处理n大于字符串长度的情况
      
      // 执行n次单步左移
      for (int k = 0; k &lt; n; k++) {
            // 单步左移：保存首字符，其余前移，最后放回首字符
            char firstChar = chars;
            for (int i = 0; i &lt; len - 1; i++) {
                chars = chars;
            }
            chars = firstChar;
      }
      
      return new String(chars);
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(k×n)，其中k为移动次数，n为字符串长度</li>
<li><strong>空间复杂度</strong>：O(1)，只使用固定额外空间</li>
</ul>
<h3 id="字符串切片法推荐">字符串切片法（推荐）</h3>
<p>值得注意的是， n 可能⼤于 str 的⻓度，那么这种情况下我们应该先对 str 的⻓度取余，保持严谨。即是： n = n % str.length(); 。</p>
<pre><code class="language-java">public class Solution {

        public String LeftRotateString(String str, int n) {
                if (str == null || str.length() == 0 || n &lt;= 0) {
            return str;
      }
                String ret = "";
                n = n % str.length();
                for (int i = n; i &lt; str.length(); ++i) {
                        ret += str.charAt(i);
                }
               
                for (int i = 0; i &lt; n; ++i) {
                        ret += str.charAt(i);
                }
                return ret;
        }

}
</code></pre>
<ul>
<li>时间复杂度 O(n)</li>
<li>空间复杂度 O(n) 。</li>
</ul>
<p>或者可以用substring 的API</p>
<pre><code class="language-java">public class Solution {
    public String leftRotateString(String str, int n) {
      if (str == null || str.length() == 0 || n &lt;= 0) {
            return str;
      }
      
      int len = str.length();
      n %= len; // 处理n大于字符串长度的情况
      
      // 直接截取并拼接：后部分 + 前部分
      return str.substring(n) + str.substring(0, n);
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，substring操作需要线性时间</li>
<li><strong>空间复杂度</strong>：O(n)，创建新的字符串对象</li>
</ul>
<h3 id="三次反转数学优美">三次反转（数学优美）</h3>
<p>利用数学规律：BA = (A'B')'，通过三次反转实现循环左移。</p>
<p>分别反转前n位、剩余部分，最后整体反转</p>
<pre><code class="language-java">public class Solution {

    public String leftRotateString(String str, int n) {
      if (str == null || str.length() == 0 || n &lt;= 0) {
            return str;
      }
      
      char[] chars = str.toCharArray();
      int len = chars.length;
      n %= len;
      
      if (n == 0) return str; // 移动0位直接返回
      
      // 第一步：反转前n个字符
      reverse(chars, 0, n - 1);
      // 第二步：反转剩余字符
      reverse(chars, n, len - 1);
      // 第三步：整体反转
      reverse(chars, 0, len - 1);
      
      return new String(chars);
    }
   
    /**
   * 反转字符数组中指定范围的字符
   * @param chars 字符数组
   * @param start 起始索引
   * @param end 结束索引
   */
    private void reverse(char[] chars, int start, int end) {
      while (start &lt; end) {
            // 交换首尾字符
            char temp = chars;
            chars = chars;
            chars = temp;
            start++;
            end--;
      }
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个字符被访问两次</li>
<li><strong>空间复杂度</strong>：O(1)，原地操作，只使用常数空间</li>
</ul>


</div>
<div id="MySignature" role="contentinfo">
    <p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19257019
頁: [1]
查看完整版本: 剑指offer-43、左旋转字符串