代码随想录刷题题Day7

2023-12-13 14:06:08

刷题的第七天,希望自己能够不断坚持下去,迎来蜕变。😀😀😀
刷题语言:C++ / Python
Day7 任务
344.反转字符串
541. 反转字符串II
卡码网:54.替换数字
151.翻转字符串里的单词
卡码网:55.右旋转字符串

1 反转字符串

在这里插入图片描述
如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数,如果库函数仅仅是解题过程中的一小部分,并且已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。
本题考虑双指针
在这里插入图片描述
伪代码:

len = s.size();
for(i = 0, j = len - 1 ; i < len / 2; i++, j--) 
	swap(s[i], s[j]);

C++:

class Solution {
public:
    void reverseString(vector<char>& s) {
		int len = s.size();
		for (int i = 0, j = len - 1; i < len / 2; i++, j--)
		{
			swap(s[i], s[j]);
		}
    }
};

或者:

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        while (left < right)
        {
          swap(s[left], s[right]);
          left++;
          right--;
        }
    }
};

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
Python:

class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1
        while left < right:
          	s[left], s[right] = s[right], s[left]
          	left += 1
          	right -= 1

2 反转字符串II

在这里插入图片描述
在遍历字符串的过程中,只要让 i += (2 * k),i 每次移动 2 * k 就可以了,然后判断是否需要有反转的区间
当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章
伪代码:

for (i = 0; i < s.size(); i += 2k)
{
	if (i + k <= s.size()) 
	{
		reverse(s, i, i + k);
		continue;
	}
	reverse(s, i, s.size());
}

C++中的reverse()函数
C++:

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k)
        {
            if (i + k <= s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k);
                continue;
            }
            reverse(s.begin() + i, s.end());
        }
        return s;
    }
};

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
Python:

class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        def reverse_substring(text):
            left, right = 0, len(text) - 1
            while left < right:
                text[left], text[right] = text[right], text[left]
                left += 1
                right -= 1
            return text
        res = list(s)
        for i in range(0, len(s), 2 * k):
            res[i : i + k] = reverse_substring(res[i : i + k])

        return ''.join(res)

3 替换数字

在这里插入图片描述
把这道题目做到极致,就不要只用额外的辅助空间
思路:

首先扩充数组到每个数字字符替换成 “number” 之后的大小
在这里插入图片描述
然后从后向前替换数字字符,也就是双指针法,过程如下:i指向新长度的末尾,j指向旧长度的末尾
在这里插入图片描述
从前向后填充就是 O ( n 2 ) O(n^2) O(n2)的算法,因为每次添加元素都要将添加元素之后的所有元素整体向后移动
很多数组填充类的问题,其做法都是先预先给数组扩容带填充后的大小,然后在从后向前进行操作
好处:(1)不用申请新数组(2)从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题

伪代码:

while (cin >> s)
{
	count = 0;
	oldSize = s.size();
	for (i = 0; i < s.size(); i++)
	{
		if (s[i] >= '0' && s[i] <= '9')
			count++;
	}
}
s.resize(s.size() + count * 5);
newSize = s.size();
for (i = newSize - 1, j = oldSize - 1; j < i; i--, j--)
{
	if (s[i] > '9' || s[i] < '0')
		s[i] = s[j];
	else
	{
		s[i] = 'r';
		s[i - 1] = 'e';
		s[i - 2] = 'b';
		s[i - 3] = 'm';
		s[i - 4] = 'u';
		s[i - 5] = 'n';
		i -= 5;
	}
}
cout << s << endl;

C++:

#include <iostream>
using namespace std;
int main()
{
	string s;
	while (cin >> s)
	{
		int oldSize = s.size();
		int count = 0;
		for (auto i : s)
		{
			if (i >= '0' && i <= '9')
			{
				count++;
			}
		}
		s.resize(s.size() + count * 5);
		int newSize = s.size();
		for (int i = newSize - 1, j = oldSize - 1; j < i; i--, j--)
		{
			if (s[j] < '0' || s[j] > '9') s[i] = s[j];
			else
			{
				s[i] = 'r';
				s[i - 1] = 'e';
				s[i - 2] = 'b';
				s[i - 3] = 'm';
				s[i - 4] = 'u';
				s[i - 5] = 'n';
				i -= 5;
			}
		}
		cout << s << endl;
	}
}

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
拓展:

双指针方法:
(1)移除元素
(2)三数之和
(3)四数之和
(3)翻转链表
(4)环形链表II
(5)反转字符串

字符串和数组的区别:

C语言中,把一个字符串存入一个数组时,也把结束符 '\0’存入数组,并以此作为该字符串是否结束的标志

char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {}

在C++中,提供一个string类,string类会提供 size接口,可以用来判断string类字符串是否结束,就不用’\0’来判断是否结束。

string a = "asd";
for (int i = 0; i < a.size(); i++) {}

翻转字符串里的单词

在这里插入图片描述
思路:

  1. 移除多余空格
  2. 将整个字符串反转
  3. 将每个单词反转

例子:
源字符串为:"the sky is blue "
(1)移除多余空格:“the sky is blue”
(2)将整个字符串反转:“eulb si yks eht”
(3)单词反转:“blue is sky the”

使用双指针法来去移除空格,最后resize(重新设置)一下字符串的大小,就可以做到O(n)的时间复杂度

伪代码:

// 去除所有空格并在相邻单词之间添加空格, 快慢指针
slow = 0;
for (fast = 0; fast < s.size(); fast++)
{
	if (s[fast] != ' ') // 遇到非空格就处理,即删除所有空格
	{
		if (slow != 0) s[slow++] = ' ';//手动控制空格,给单词之间添加空格。slow != 0说明不是第一个单词,需要在单词前添加空格
		while (fast < s.size() && s[fast] != ' ')// 补上该单词,遇到空格说明单词结束
		{
			s[slow++] = s[fast++];
		}
	}
}
s.resize(slow);//slow的大小即为去除多余空格后的大小
reverse(s, 0, s.size() - 1);
int start = 0;//removeExtraSpaces后保证第一个单词的开始下标一定是0
for (i = 0; i <= s.size(); i++)
{
	if (i == s.size || s[i] == ' ')// 到达空格或者串尾,说明一个单词结束。进行翻转
	{
		reverse(s, start, i - 1);// 翻转,注意是左闭右闭 []的翻转
		start = i + 1;// 更新下一个单词的开始下标start
	}
}
return s;

C++:

class Solution {
public:
	void reverse(string& s, int start, int end)// 翻转,区间写法:左闭右闭 []
	{
		for (int i = start, j = end; i < j; i++, j--)
		{
			swap(s[i], s[j]);
		}
	}
	// 去除所有空格并在相邻单词之间添加空格, 快慢指针
	void removeExtraSpace(string& s)
	{
		int slow = 0;
		for (int fast = 0; fast < s.size(); fast++)
		{
			if (s[fast] != ' ') //遇到非空格就处理,即删除所有空格
			{
				if (slow != 0) s[slow++] = ' ';// 手动控制空格,给单词之间添加空格
				while (fast < s.size() && s[fast] != ' ')
				{// 补上该单词,遇到空格说明单词结束
					s[slow++] = s[fast++];
				}
			}
		}
		s.resize(slow);// slow的大小即为去除多余空格后的大小
	}
    string reverseWords(string s) {
		removeExtraSpace(s);// 去除多余空格,保证单词之间之只有一个空格,且字符串首尾没空格
		reverse(s, 0, s.size() - 1); // 翻转s
		int start = 0;//removeExtraSpaces后保证第一个单词的开始下标一定是0
		for (int i = 0; i <= s.size(); i++)
		{
			if (i == s.size || s[i] == ' ')// 到达空格或者串尾,说明一个单词结束。进行翻转
			{
				reverse(s, start, i - 1);// 翻转,注意是左闭右闭 []的翻转
				start = i + 1;// 更新下一个单词的开始下标start
			}
		}
		return s;
    }
};

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1) O ( n ) O(n) O(n)

class Solution {
public:
	void removeExtraSpace(string& s)
	{
		int slow = 0;
		for (int fast = 0; fast < s.size(); fast++)
		{
			if (s[fast] != ' ') 
			{
				if (slow != 0) s[slow++] = ' ';
				while (fast < s.size() && s[fast] != ' ')
				{
					s[slow++] = s[fast++];
				}
			}
		}
		s.resize(slow);
	}
    string reverseWords(string s) {
		removeExtraSpace(s);
		reverse(s.begin(), s.end());
		int start = 0;
		for (int i = 0; i <= s.size(); i++)
		{
			if (i == s.size() || s[i] == ' ')
			{
          reverse(s.begin() + start, s.begin() + i);
				  start = i + 1;
			}
		}
		return s;
    }
};

Python:

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 将字符串拆分为单词,即转换成列表类型
        words = s.split()
        left, right = 0, len(words) - 1
        # 反转单词
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1
        # 将列表转换成字符串
        return " ".join(words)

5 右旋转字符串

在这里插入图片描述
思路:

在这里插入图片描述

通过整体倒序,在将两段子串顺序颠倒
C++:

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    string s;
    int k;
    cin >> k >> s;
    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin() + k);
    reverse(s.begin() + k, s.end());
    cout << s << endl;
    return 0;
}

在这里插入图片描述

先局部反转,再整体反转
C++:

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    string s;
    int k;
    cin >> k >> s;
    int len = s.size();
    reverse(s.begin(), s.begin() + len - k);
    reverse(s.begin() + len - k, s.end());
    reverse(s.begin(), s.end());
    cout << s << endl;
    return 0;
}

鼓励坚持八天的自己😀😀😀

文章来源:https://blog.csdn.net/BigDavid123/article/details/134823398
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。