代码随想录算法训练营第八天 | 344.反转字符串,541.反转字符串II,卡码网:54.替换数字,151.翻转字符串里的单词,卡码网:55.右旋转字符串

发布时间 2023-12-20 22:12:54作者: amulet

一、344.反转字符串

题目链接:

LeetCode 344.反转字符串

学习前:

思路:

相向指针。left=0,right=length-1,不停交换left和right的值

时间复杂度:O(n)

空间复杂度:O(1)

学习后:

了解swap函数通过位运算实现的方式

二、541.反转字符串II

题目链接:

LeetCode 541.反转字符串II

学习前:

思路:

new一个char数组,存放反转后的字符串。运用双向指针反转每2k个字符的前k个,最后将char数组转成字符串输出

时间复杂度:O(n)

空间复杂度:O(n)

学习后:

  • 思路基本一致,抓住第k个和第2k个,但是我采用是char数组而不是StringBuffer,最后还要进行转换
  • 代码还能进一步优化,使得逻辑更加清晰

三、卡码网:54.替换数字

题目链接:

LeetCode 卡码网:54.替换数字

学习前:

思路:

创建StringBuffer对象,遍历字符串,是字母则直接追加,是数字则追加number

时间复杂度:O(n)

空间复杂度:O(1)

学习后:

复习

四、151.翻转字符串里的单词

题目链接:

LeetCode 151.翻转字符串里的单词

学习前:

思路:

在一个for循环中,从后往前遍历,在遇到非空格字符后遇到的第一个空格处,进行append操作,

但是对于边界处的判断总是出现问题

时间复杂度:O(n)

空间复杂度:O(1)

学习后:

  • 原本试图在一个循环里面解决问题,但是很容易有错误;并且对于边界处,需要在循环外面多进行一次判断
  • 采用分3步的思路,整体翻转+局部翻转,不仅简化了每一步的操作,还对前面所学的进行复习,层层递进

五、卡码网:55.右旋转字符串

题目链接:

LeetCode 卡码网:55.右旋转字符串

学习前:

思路:

  1. 首先整体翻转
  2. 前k个局部翻转
  3. 余下的局部翻转

时间复杂度:O(n)

空间复杂度:O(1)

学习后:

进一步掌握 整体翻转+局部翻转 的巧妙

六、学习总结

  1. 时间:3.5h
  2. 初步了解StringBuffer以及字符串的就地翻转
  3. 熟悉 整体先翻转再局部翻转 的思路