【剑指offer】学习计划day3

这篇具有很好参考价值的文章主要介绍了【剑指offer】学习计划day3。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 【剑指offer】学习计划day3,剑指offer,算法,c语言,c++,数据结构,剑指offer

【剑指offer】学习计划day3,剑指offer,算法,c语言,c++,数据结构,剑指offer

目录

一. 前言 

二.替换空格

        a.题目

         b.题解分析

          c.AC代码

三. 左旋转字符串

         a.题目

        b.题解分析

        c.AC代码 


一. 前言 

 本系列是针对Leetcode中剑指offer学习计划的记录与思路讲解。详情查看以下链接:

剑指offer-学习计划https://leetcode.cn/study-plan/lcof/?progress=x56gvoct

    本期是本系列的day3,今天的主题是----》字符串(简单)

    题目编号:JZ05,JZ58

二.替换空格

        a.题目

【剑指offer】学习计划day3,剑指offer,算法,c语言,c++,数据结构,剑指offer

         b.题解分析

        由于针对不同语言,字符串被设计成可变不可变两种,因此我们需要进行分类讨论【剑指offer】学习计划day3,剑指offer,算法,c语言,c++,数据结构,剑指offer 

        情景1字符串不可变

        假如我们使用的是C语言,题目传入的是一个字符串常量,是不可变的,即无法直接修改字符串的某一位字符。因此我们需要额外新建一个足够大的字符数组,然后遍历1次原字符串对字符数组进行填充即可。时间复杂度为O(N),空间复杂度也为O(N)。

        情景2字符串可变

        而假如我们使用了C++,题目传入的是一个string类型的变量,是可变的。当然你依旧可以使用一个足够大的辅助空间解决本题。但如果你想把这道题目做到极致,就要充分利用string可变的特性,对字符串进行原地修改

        第一步:显然我们需要扩充字符串到每个空格替换成"%20"之后的大小。

        第二步:使用双指针法,一个指针从后往前遍历原字符串,一个指针从后往前填充新字符串。在这个过程中,如果遇到空格,则将其替换为"%20"。过程如下:

【剑指offer】学习计划day3,剑指offer,算法,c语言,c++,数据结构,剑指offer        额外补充:时间复杂度为O(N),空间复杂度为O(1)。可能有小伙伴会有疑问:为什么要从后往前遍历,从前往后不行吗?答案显然是可以的,但是从前往后遍历替换空格时无可避免的要将后面的所有字符进行向后移动,移动字符需要O(N)的时间,整个过程的时间复杂度就为,时间开销较大。一般很多数组填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作。


          c.AC代码

//字符串不可变,采用额外空间
char* replaceSpace(char* s) 
{
	char* cur = s;
	int spaceNum = 0;
	//遍历字符串记录有多少空格
	while (*cur)
	{
		if (*cur == ' ')
		{
			spaceNum++;
		}
		cur++;
	}
	cur = s;
	//分配合适的空间,这里求原字符串大小不能用sizeof(),s是指针
	char* ret= (char*)malloc(strlen(s)+1 + spaceNum * 2);
	int retSize = 0;
	//遍历字符串对数组进行赋值
	while (*cur)
	{
		if (*cur == ' ')
		{
            //替换空格
			strcpy(ret + retSize, "%20");
			retSize += 3;
		}
		else
		{
			ret[retSize] = *cur;
			retSize++;
		}
		cur++; //指向下一字符
	}
	ret[retSize] = '\0'; //不要忘记添加字符串结束标志
	return ret;
}
//字符串可变,双指针法

class Solution {
public:
	string replaceSpace(string s)
	{
		int spaceNum = 0; // 统计空格的个数
		int pOld = s.size() - 1; //原字符串最后一个元素下标
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == ' ')
			{
				spaceNum++;
			}
		}
		s.resize(s.size() + spaceNum * 2); //扩容
		int pNew = s.size() - 1; //新字符串最后一个元素下标
		//双指针进行赋值,遇到空格进行替换
		while (pOld > pNew) //当pOld = pNew时说明前面已经没有空格了
		{
			if (s[pOld] != ' ')
			{
				s[pNew] = s[pOld];
			}
			else
			{
				s[pNew--] = '0';
				s[pNew--] = '2';
				s[pNew] = '%';
			}
			pNew--;
			pOld--;
		}
		return s;
	}
};

三. 左旋转字符串

         a.题目

【剑指offer】学习计划day3,剑指offer,算法,c语言,c++,数据结构,剑指offer

        b.题解分析

       法1. 辅助空间法

       第一种方法最简单明了:首先建立一个辅助字符数组,然后遍历字符串,将前n个字符放入数组的后n个位置,剩下的字符放入数组前端即可。时间复杂度为O(N),空间复杂度为O(N)

       法2. 三步翻转法 

       此方法非常巧妙,思路如下:先翻转前n个字符,再翻转剩下的字符,最后翻转整个字符串。通过这三次翻转,我们便可以完成左旋n个字符的目的。具体过程如下:【剑指offer】学习计划day3,剑指offer,算法,c语言,c++,数据结构,剑指offer

        但是由于涉及到字符串的修改,因此像C语言这些字符串不可修改的语言还是要建立辅助空间,时间复杂度为O(N),空间复杂度为O(N);而像C++这些语言就没有这种顾虑,直接原地修改即可,时间复杂度为O(N),空间复杂度为O(1)

        c.AC代码 

//辅助空间的方式
char* reverseLeftWords(char* s, int n) 
{
	//防止输入的n过大,模上字符串的长度。因为长度为n的字符串左旋n个字符相当于没变
	n %= strlen(s);
	int resSize = 0;
	char* res = (char*)malloc(strlen(s) + 1);//申请辅助空间
	//后面的字符放到前面
	for (int i = n; i < strlen(s); i++)
	{
		res[resSize] = s[i];
		resSize++;
	}
	//前面n个字符放到后面
	for (int i = 0; i < n; i++)
	{
		res[resSize] = s[i];
		resSize++;
	}
	res[resSize] = '\0';
	return res;
}
//逆置的方式

//C语言写法
void reverse(char* s, int left, int right) 
{
	assert(s);
    //逆置字符串
	while (left < right)
	{
		char tmp = s[left];
		s[left] = s[right];
		s[right] = tmp;
		left++;
		right--;

	}
}
char* reverseLeftWords(char* s, int n)
{
	//防止输入的n过大,我们模上字符串的长度。因为长度为n的字符串左旋n个字符相当于没变
	n %= strlen(s);
    //申请辅助空间
	char* res = (char*)malloc(strlen(s) + 1);
    //拷贝到新空间
	strcpy(res, s);
    //三步逆置
	reverse(res, 0, n - 1);
	reverse(res, n, strlen(s)-1);
	reverse(res, 0, strlen(s) - 1);
	return res;
}



//C++写法
class Solution {
public:
	string reverseLeftWords(string s, int n) 
	{
		//防止输入的n过大,模上字符串的长度。因为长度为n的字符串左旋n个字符相当于没变
		n %= s.size();
		//逆置前n个字符,reverse函数在algorithm头文件中
		reverse(s.begin(), s.begin() + n);
		//逆置后续字符
		reverse(s.begin() + n, s.end());
		//整体逆置
		reverse(s.begin(), s.end());
		return s;
	}
};

以上,就是本期的全部内容啦🌸

制作不易,能否点个赞再走呢🙏文章来源地址https://www.toymoban.com/news/detail-543181.html

到了这里,关于【剑指offer】学习计划day3的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(41)
  • 深度学习DAY3:神经网络训练常见算法概述

    这是最常见的神经网络训练方法之一。它通过计算损失函数对权重的梯度,并沿着梯度的反方向更新权重,从而逐步减小损失函数的值。梯度下降有多个变种,包括随机梯度下降(SGD)和小批量梯度下降。 反向传播是一种基于链式法则的方法,用于计算神经网络中每个神经元

    2024年02月07日
    浏览(45)
  • 新星计划Day6【数据结构与算法】 链表Part2

    👩‍💻博客主页:京与旧铺的博客主页 ✨欢迎关注🖱点赞🎀收藏⭐留言✒ 🔮本文由京与旧铺原创,csdn首发! 😘系列专栏:java学习 💻首发时间:🎞2022年4月30日🎠 🎨你做三四月的事,八九月就会有答案,一起加油吧 🀄如果觉得博主的文章还不错的话,请三连支持一

    2023年04月08日
    浏览(60)
  • 【剑指offer】数据结构——数组

    【剑指offer】03.数组中重复的数字 //03. 数组中重复的数字 // 找出数组中重复的数字。 // 力扣 // 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。 // 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每 // 个数字重复了几次。请找出数组中任意一

    2024年02月08日
    浏览(40)
  • 剑指offer题解合集——Week3day4

    题目链接:二叉树的镜像 AC代码 思路: 整体思路 题目链接:对称的二叉树 AC代码 思路: 整体思路

    2024年02月02日
    浏览(40)
  • 剑指offer题解合集——Week3day6

    题目链接:栈的压入、弹出序列 AC代码 思路: 整体思路 题目链接:不分行从上往下打印二叉树 AC代码 思路: 整体思路

    2024年01月19日
    浏览(48)
  • 剑指offer题解合集——Week4day2

    题目链接:二叉树中和为某一值的路径 AC代码 思路: 整体思路

    2024年01月15日
    浏览(45)
  • 《剑指offer》(3)排序算法篇

    class Solution:     def duplicate(self , numbers: List[int]) - int:         if len(numbers) = 1:             return -1         import collections         num_dict = collections.Counter(numbers)         res = [key for (key,value) in num_dict.items() if value 1]         return res[0] class Solution:     def sort(self,num): #快排

    2024年02月13日
    浏览(37)
  • 剑指 offer 动态规划算法题:丑数

    题目描述 :我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。 分析:         枚举法, 从 1 开始判断遍历,判断是否丑数(只有 2, 3, 5 作为因子),若是丑数 n 自减,直到 n 等于 1,返回即可。         动态规划法,

    2024年02月16日
    浏览(46)
  • 从零学算法(剑指 Offer 45)

    输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 我的原始人解法:直接冒泡排序,把最先应该拼接的那个数不断后移,然后拼接即可。关键就

    2024年02月10日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包