当前位置: 首页 > article >正文

算法学习之三步翻转法

🍍个人主页🍍:🔜勇敢的小牛儿🚩

🔱推荐专栏🔱:C语言知识点

⚠️座右铭⚠️:敢于尝试才有机会

🐒今日鸡汤🐒:道阻且长,行则降至

目录

题目:

示意图: 

​编辑 

 解法一:

我的思路:

图解:

代码:

2,代码优化:三步翻转法

2.1:三步翻转法的逻辑——以翻转两次ABCDE变成CDEAB为例:

2.2,代码:

总结:

1.三步翻转法的步骤有三:

💥注意💥:

这里一定要传地址!!!小牛儿我就在这里错了,搞了好久。


 

题目:

写一个函数实现以下功能:

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

示意图: 

 

 解法一:

我的思路:

题目的翻转方法是将第一个字母放到最后一位,所以我就可以这样实现:

1.那现在我们可以先创建一个变量来将第一个字符先存起来。

2.然后让第二个字符以及后面的字符往前移覆盖掉原来每一个字符前面一位原本的数据。

3.将临时变量接收到的值放到最后一位。

图解:

 

 

在知道了第一步如何做以后,我们就可以开始如法炮制了:

代码:

#include<stdio.h>
#include<assert.h>
void left_reverse(char* s, int k) {
	assert(s);
	int len = strlen(s);
	int  i = 0;
	k = k % len;//这里是为了减少移动的次数,
                //因为当你要旋转18次时其实和旋转3次没有什么区别。
	while (k) {
		char temp = s[0];
		for (i = 0;i < len - 1;i++) {
			s[i] = s[i + 1];
		}
		s[len - 1] = temp;
		k--;
	}
	
}
int main() {
	char s[] = "AABCD";
	int k = 0;
	scanf("%d", &k);
	left_reverse(s, k);
	printf("%s\n", s);
	return 0;
}

2,代码优化:三步翻转法

第一种解题方法其实就相当于一种暴力解法。虽然这种方法也可以让我们很好的解决问题。但是我们都知道时间就是生命,效率就是金钱。所以我们必须要找到一个更好的解决方法来优化,提高效率。在这里我们就找到了一种更好的方法来对这个问题来进行解决,这种方法就是三步翻转法。

2.1:三步翻转法的逻辑——以翻转两次ABCDE变成CDEAB为例:

第一步:翻转前两个字符AB变成BA,现在字符变成BACDE

第二步:以第二个字符为界翻转后面三个字符CDE变成EDC,现在字符串变成BAEDC

第三步:翻转整个字符变成CDEAB

这便是逆序两个字符串的做法,当我们要逆序k个时就可以如法炮制了。

2.2,代码:

#include<stdio.h>
#include<assert.h>
void reverse(char* left,char* right) {
	assert(left && right);
	while (left < right) {
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}
void left_reverse(char* s, int k) {
	assert(s);
	int len = strlen(s);
	reverse(s, s+k-1);//左边
	reverse(s+k, s+len-1);//右边
	reverse(s, s+len-1);//整个
}
int main() {
	char s[] = "AABCD";
	int k = 0;
	scanf("%d", &k);
	left_reverse(s, k);
	printf("%s\n", s);
	return 0;
}

这个三步翻转法的效率就显然提高了。因为不管你的字符串有多长你只要进行三次翻转就可以完成你想要的翻转了。

总结:

1.三步翻转法的步骤有三:

1.翻转前k个字符。

2.翻转后k个字符。

3.翻转整个字符串。

💥注意💥:

void left_reverse(char* s, int k) {
	assert(s);
	int len = strlen(s);
	reverse(s, s+k-1);//左边
	reverse(s+k, s+len-1);//右边
	reverse(s, s+len-1);//整个
}

这里一定要传地址!!!小牛儿我就在这里错了,搞了好久。

小牛儿我今天的分享就到这里了,感谢你的阅读。如果能给个三连那就更好了,哈哈!

 


http://www.kler.cn/a/1894.html

相关文章:

  • Linux文件目录 --- 移动和改名命令MV、强制移动、试探性移动过、按时间移动
  • 羊城杯2020 easycon
  • 再服务器上建立新的编译环境
  • Ajax中的axios
  • 多功能护照阅读器港澳通行证阅读机RS232串口主动输出协议,支持和单片机/Linux对接使用
  • 本机如何连接虚拟机MYSQL
  • 51单片机入门 -驱动 8x8 LED 点阵屏
  • 高速PCB设计指南(十五)
  • 【js】多分支语句练习(2)
  • Docker入门到放弃笔记之容器
  • Android绘制——自定义view之onLayout
  • 前缀和 及其优化技巧Ⅱ
  • SAP 发出商品业务配置
  • 蓝桥杯备赛 [day01]|python|迷宫问题|乘积尾零|平方和|切面条|付账问题
  • 数据可视化
  • 数据库:mysql的主从复制实战
  • 版本管理工具git 与 svn 的区别具体有哪些?
  • UE实现地面动态交互效果
  • 大数据框架保姆级安装教程——Kafka(3.0.0)
  • 小白学Pytorch系列--Torch API (7)
  • Java单例模式写法
  • 差分运放公式推导-运算放大器
  • 初阶C语言:冒泡排序
  • typescript(元组、枚举、类、泛型)
  • mysql数据库常问面试题
  • 我的 System Verilog 学习记录(10)