程序员常见的基础算法（一线互联网算法面试常用算法）

忙族 2023-07-13 12:53:19 734

程序员常见的基础算法（一线互联网算法面试常用算法）void LeftRotateString(char* s int n int m) { 　　while (m--) 　　{ 　　　　LeftShiftOne(s n); 　　} } 这样就完成了将若干个字符移到字符串尾部的要求。void LeftShiftOne(char* s int n) { 　　// 保存第一个字符　　char t = s[0]; 　　for (int i = 1; i < n; i ) 　　{ 　　　　s[i - 1] = s[i]; 　　} 　　s[n - 1] = t; } 然后再调用m次LeftShiftOne函数，使得字符串开头的m个字符移到字符串的尾部：解法一：蛮力移位初看此题，可能最先想到的方法是将需要移动的字符一个一个地移到字符串的尾部。如果定义指向该字符串的一个指针s，然后设该字符串的长度为n，那么，可以先编

与字符串相关的问题在各大互联网公司的笔试和面试中出现的频率极高。例如，网上广为流传的一道单词翻转题：输入“I am a student.”，要求输出“student. a am I”。

6个典型的字符串问题，分别是字符串的旋转、字符串的包含、字符串的全排列、字符串转换成整数、回文判断、最长回文子串。这6个问题中，除了“将字符串转换成整数”这个问题需要特别注意细节之外，其他5个问题都有多种思路和多种解法，比如先从蛮力解法入手，然后考虑是否能逐步优化。

程序员常见的基础算法（一线互联网算法面试常用算法）(1)

今天我们首先介绍字符串的旋转：

1.1　字符串的旋转题目描述

给定一个字符串，要求将字符串前面的若干个字符移到字符串的尾部。例如，将字符串"abcdef"的前3个字符'a'、'b'和'c'移到字符串的尾部，那么原字符串将变成"defabc"。请写一个函数实现此功能。

分析与解法

解法一：蛮力移位

初看此题，可能最先想到的方法是将需要移动的字符一个一个地移到字符串的尾部。

如果定义指向该字符串的一个指针s，然后设该字符串的长度为n，那么，可以先编写一个函数LeftShiftOne (char* s int n)，以完成将一个字符移到字符串尾部的功能：

void LeftShiftOne(char* s int n) { 　　// 保存第一个字符　　char t = s[0]; 　　for (int i = 1; i < n; i ) 　　{ 　　　　s[i - 1] = s[i]; 　　} 　　s[n - 1] = t; }

然后再调用m次LeftShiftOne函数，使得字符串开头的m个字符移到字符串的尾部：

void LeftRotateString(char* s int n int m) { 　　while (m--) 　　{ 　　　　LeftShiftOne(s n); 　　} }

这样就完成了将若干个字符移到字符串尾部的要求。

下面来分析一下这种方法的时间复杂度和空间复杂度。针对长度为n的字符串来说，假设需要移动m个字符到字符串的尾部，那么总共需要m×n次操作。同时设立一个变量保存第一个字符。因此，时间复杂度为O (mn)，空间复杂度为O (1)。

有没有更好的办法来降低时间复杂度呢？

解法二：三步反转

对于这个问题，换一个角度思考一下。既然题目要求将字符串前面的那部分原封不动地移到字符串的尾部，那么是否可以把需要移动的部分跟不需要移动的部分分开处理呢？例如，可以先将一个字符串分割成两个部分，然后将这两个部分的字符串分别反转，最后再对整个字符串进行整体反转，即可解决字符串旋转的问题。

拿题目中的例子来说，给定字符串"abcdef"，若要将"def"移动到"abc"的前面，只需要按照下述3个步骤操作即可。

（1）将原字符串分为X和Y两个部分，其中X为"abc"，Y为"def"。

（2）将X的所有字符反转，即相当于反转"abc"得到"cba"；再将Y的所有字符也反转，即相当于反转"def"得到"fed"。

（3）最后，将上述步骤得到的结果再给予整体反转，即整体反转"cbafed"得到"defabc"，这样，就实现了字符串的反转。

参考代码如下：

void ReverseString(char* s int from int to) { 　　while (from < to) 　　{ 　　　　char t = s[from]; 　　　　s[from ] = s[to]; 　　　　s[to--] = t; 　　} } void LeftRotateString(char* s int n int m) { 　　// 若要左移动大于n位，那么与%n是等价的　　m %= n; 　　ReverseString(s 0 m - 1); 　　ReverseString(s m n - 1); 　　ReverseString(s 0 n - 1); }

这种把字符串先分为两个部分，各自反转，最后整体反转的方法，俗称“三步反转”法，其时间复杂度为O(n)，空间复杂度为O(1)。

程序员常见的基础算法（一线互联网算法面试常用算法）(2)