剑指offer系列——剑指 Offer 58

编程入门行业动态更新时间:2024-10-22 14:33:46

剑指offer系列——剑指 Offer 58

⭐️前面的话⭐️

大家好！博主开辟了一个新的专栏——剑指offer，我要开始刷题了！这个专栏会介绍《剑指offer》书上所有的面试编程题。并且会分享一些我的刷题心得。由于博主水平有限，如有错误，欢迎指正，如果有更好的解题思路和算法可以分享给博主哦！一起加油！一起努力！

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2021年9月10日🌴
💖祝所有的老师教师节快乐！💖
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《剑指offer第1版》，📚《剑指offer第2版》
💬参考在线编程网站：🌐牛客网🌐力扣
🙏作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
博主的码云gitee，平常博主写的程序代码都在里面。

📌导航小助手📌

⭐️剑指 Offer 58 - II. 左旋转字符串⭐️
- 🔐题目详情
- 💡解题思路
- 🔑源代码
- 🌱总结

⭐️剑指 Offer 58 - II. 左旋转字符串⭐️

🔐题目详情

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例：

输入: s = "abcdefg", k = 2
输出: "cdefgab"
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

1 <= k < s.length <= 10000

来源：力扣（LeetCode）
链接：

💡解题思路

在正式对字符串进行左旋之前，首先来看看字符串左旋次数与字符串个数的规律，假设字符串长度为len，左旋次数为k。举例一个字符串str=abcdef，此时len = 6，当k=1，左旋得bcdefa，k=3，左旋得defabc，k=6，左旋得abcdef与初始时的字符串相等，所以我们可以通过规律得到左旋次数k为字符串长度len的倍数时，左旋字符串与初始时字符串相同，所以说，当左旋len+1次与左旋1次的效果是相同的，所以在对字符串进行左旋操作时不妨先对左旋次数k取len的模，这样，当k比较大时，消耗的时间比较少，提高了程序的效率！
由于力扣平台提供的字符串指针常量，不能对该指针指向的内容进行修改，需要自己申请空间进行字符串的左旋操作！
方法1： 暴力遍历。
我们最先想到的就是遍历，每次左旋，我们就将第一个字符替换到最后一个字符位置，并将后面的字符左移。

时间复杂度： O(k*N)

对于暴力模拟算法，我门可以做一点优化，那就是我们可以将两段原字符串拼在一起，不妨设原字符串长度为m, 那么下标为m+j对应的字符相当于下标为j的字符串。

那么左旋n次，等同于左旋k=n%m次，就是俩段合并字符串中的[k, k + m - 1]区间的字符串。

方法2： 巧妙拷贝。
申请好内存之后，我们可以对原字符串s进行特定位置的拷贝，比如字符串abcdefg需要左旋该字符串k次，该字符串长度为len=7，不难发现下标为k%len的字符，左旋k次后，会在数组的首位置，所以我们可以从原字符串下标为 k % l e n k\%len k%len字符开始拷贝。

但是注意要保证k的值不大于字符串长度len（先对k取len的模，即k %= len），由于访问拷贝完最后一个元素后需要访问拷贝首个元素，所以我们需要对访问的数组下标取len的模（即*(s+(k+i)%len)或s[(k+i)%len]）保证数组不越界和实现从最后一个元素过渡到首个元素，该栗子中数组下标顺序为k->k+1->...->len-1->0->...->k-1，如果k=4，进行拷贝的数组下标次序是4->5->6->0->1->2->3，得到的就是逆序的字符串efgabcd。

时间复杂度： O(N)
方法3： 逆序三部曲。
还是以字符串abcdefg需要左旋该字符串k次（保证k < len），该字符串长度为len=7,左旋次数k=4为例！
因为下标为k%len的字符，左旋k次后，会在数组的首位置，所以我以该元素为分界线，位于该元素之前的作为一组（不包括该分界字符）,下标范围为 [ 0 , k % l e n − 1 ] [0,k\%len-1] [0,k%len−1]，位于该元素之后的作为一组（包含该分界字符）,下标范围为 [ k % l e n , l e n − 1 ] [k\%len,len-1] [k%len,len−1]。
先分别对两部分进行逆序，然后在整个字符串进行逆序，就能得到左旋k次的字符串，一共进行三次字符串逆序，简称“逆序三部曲”。

时间复杂度： O(N)

🔑源代码

编程语言：C语言/C++/Java
在线编程平台：力扣

C语言：

//方法1
char* reverseLeftWords(char* s, int n){int len = strlen(s);int k = 0;k = n % len;//当左旋位数为字符串长度整数倍时，左旋后与初始相同int i = 0;char* str = (char*)malloc(sizeof(char) * len + 1) ;//申请合适空间strcpy(str,s);for (i = 0; i < k; i++)//每次左旋一位，需要左旋几次，就循环几次{int j = 0;char tmp = *str;for (j = 0; j < len - 1; j++){*(str + j) = *(str + j + 1);//左旋一位}*(str + j) = tmp;}return str;
}

//方法2
char* reverseLeftWords(char* s, int n){int len = strlen(s);char* str = (char*)malloc(sizeof(char) * len +1);int i = 0;int k = 0;k = n % len;for(i = 0; i < len; i++){*(str + i) = *(s + (k + i) % len);}*(str + i) = '\0';return str;
}

//方法3
void reverse(char* str, int i, int j)
{int left = i;int right = j;while (left < right){char tmp = str[left];str[left] = str[right];str[right] = tmp;right--;left++;}
}
char* reverseLeftWords(char* s, int n){int len = strlen(s);char* str = (char*)malloc(sizeof(char) * len + 1);int k = n % len;strcpy(str,s);reverse(str, 0, k-1);reverse(str, k, len-1);reverse(str, 0, len-1);str[len] = '\0';return str;
}

C++语言：

//方法1：模拟
class Solution {
public:void left(string& s) {char tmp = s[0];int n = s.length();for (int i = 0; i < n - 1; i++) {s[i] = s[i + 1];}s[n - 1] = tmp;}string reverseLeftWords(string s, int n) {int m = s.length();n %= m;while (n-- > 0) {left(s);}return s;}
};//方法1优化：字符串截取
class Solution {
public:string reverseLeftWords(string s, int n) {string ss = s + s;int m = s.length();n %= m;return ss.substr(n, m);}
};

//方法2：偏移拷贝
class Solution {
public:string reverseLeftWords(string s, int n) {int m = s.length();n %= m;string ans(m, ' ');int index = 0;int cnt = m;while (cnt-- > 0) {ans[index++] = s[n++ % m];}return ans;}
};

//方法3：字符串逆序
class Solution {
public:void reverse(string& s, int left, int right) {while (left < right) {char tmp = s[left];s[left] = s[right];s[right] = tmp;left++; right--;}}string reverseLeftWords(string s, int n) {int m = s.length();n %= m;reverse(s, 0, n - 1);reverse(s, n, m - 1);reverse(s, 0, m - 1);return s;}
};

Java语言：

//方法1：模拟
class Solution {public static void leftMove(char[] cs) {char tmp = cs[0];int n = cs.length;for(int i = 0; i < n - 1; i++) {cs[i] = cs[i + 1];}cs[n - 1] = tmp;}public String reverseLeftWords(String s, int n) {char[] cs = s.toCharArray();int m = s.length();n %= m;for (int i = 0; i < n; i++) {leftMove(cs);}return new String(cs);}
}//方法1优化：字符串偏移
class Solution {public String reverseLeftWords(String s, int n) {StringBuilder ss = new StringBuilder(s);ss.append(s);int m = s.length();n %= m;return ss.toString().substring(n, n + m);}
}

//方法2：偏移拷贝
class Solution {public String reverseLeftWords(String s, int n) {char[] cs = s.toCharArray();int m = s.length();n %= m;char[] ans = new char[m];int index = 0;int cnt = m;while (cnt-- > 0) {ans[index++] = cs[n++ % m];}return new String(ans);}
}

//方法3：多次逆序
class Solution {public static void reverse(char[] cs, int left, int right) {while (left < right) {char tmp = cs[left];cs[left] = cs[right];cs[right] = tmp;left++;right--;}}public String reverseLeftWords(String s, int n) {char[] cs = s.toCharArray();int m = s.length();n %= m;reverse(cs, 0, n - 1);reverse(cs, n, m - 1);reverse(cs, 0, m - 1);return new String(cs);}
}