【LC_Lesson1】--字符串反转练习

LeetCode算法练习题目一：给定一个字符串，要求将该字符串反转后输出

努力学习，天天向上。借助LeetCode的题目，练习编码能力，数据结构，以及C++和Python的编码能力。

一. 算法实现

解法一：首尾互换位置

（重点：关注到不同方法的时间复杂度，空间复杂度，以及一种评测算法效率的实现方式）

比较好的方式，首位交换位置

C++实现方式如下：

 # include <iostream>

 using namespace std;

 class Solution{

     public:

         void reverseString(string str);

 };

 void Solution::reverseString(string str)

 {

     int i;

     int j = str.length()-;

     unsigned char temp;

     while(i < j)

     {

         temp = str[i];

         str[i] = str[j];

         str[j] = temp;

         i++;j--;

     }

     for(i=;i<str.length();i++)

         cout << str[i];

     cout << endl;

 }

 int main(void)

 {

     Solution str;

     str.reverseString("hello,wwz");

     return ;

 }

结果如下：

python实现方式：

 def ReverseSting1(list_string):

     length = len(list_string);

     i = 0;

     j = length - 1;

     while i < j:

         temp = list_string[j];

         list_string[j] = list_string[i];

         list_string[i] = temp;

         i += 1;

         j -= 1;

     print(list_string)

 string = 'abcdefghijklmn'

 list_string = list(string)

 ReverseSting1(list_string)

结果如下：

注意：python中的字符串是只读属性，因此为了方便修改，将其转换成列表是一个不错的选择。

解法二：暴力执行

最简单的方式，就是暴力执行，将整个数据包遍历一遍。如果有n个数据，因此需要执行n次，时间复杂度就是很直观的O(n)，代码就不写了，比较简答

二. 效率分析

首尾交换

假如有n个元素，由于首尾同时遍历扫描，因此将会执行n/2次运算，可算作时间复杂度为O(n/2),实际上没有这种说法，对于同等量级的运算更多都会表示为O(n)

暴力执行

前文已经描述，方案简单，逻辑简单，就是只管的O(n)

对比分析预测

针对首尾交换的n/2次运算（时间为T1），以及暴力法的n次运算(时间为T2)，按理说执行时间应该几乎一致,也就是T1 = 1/2 * T2 ，但是由于首尾交换每次执行运算量稍多一些，所以时间应为T1 > 1/2 * T2。

下面我们实际上机验证，再次也给出一种测试算法效率的方法：

（未完待续）

巴特西

【LC_Lesson1】--字符串反转练习

最新文章

热门文章