依照特定轨迹遍历字符串图
遍历 字符串 特定 轨迹
2023-09-11 14:14:09 时间
题目大致是这样的,
字符串“PAYPALISHIRING”的一种“之”字型路线是这样的:
假设一行一行的读写,就是PAHNAPLSIIGYIR。
所以,假设输入PAHNAPLSIIGYIR和3,就是横着的字符串和层数,输出N轨迹的字符PAYPALISHIRING。
首先想到的是怎样 将输入字符串。切割开来,比方上面是3层,分成3个字符串,这三个字符串一定是连续的
第一段+第二段+第三段
如今的难题是怎么推断每一段的长度。
将上面的图抽象化
就是这样的,每个圆代表一个字符。这事实上是有规律的。
例如以下
这样每一层的个数和这个周期之间是有关系的
base=(字符总个数/(层数+层数-2))
第一层个数=base+x
最后一层=base+x
其它层=base×2+x。
这里面的x表示(如上图)绿色的圆的补偿,比方如以下4个绿色圆,
base=20/8=2
第一层=2+1=3;
第二层=2×2+1=5。
第三层=2×2+1=5;
第四层=2×2+1=5;
最后一层=2+0=2;
假设是以下这样的情况
事实上算法也是一样的仅仅要对于补偿x值修正就能够了。本次就不讨论这样的情况了。
到达这一步时,将之前的切割成了3部分,然后进行N轨迹遍历,
初步方案是。给三个字符串编号1、2、3.然后依照12321232123的遍历直到结束
所以如今须要解决的问题是,怎样实现这样的循环的遍历。
这里想到在cpu中有个寄存器用于决定地址是加一还是减一操作,所以借用这样的思想。例如以下方案
实现函数例如以下
string convert(string text,int nRow)//text为输入字符串 nRow是层数
{
string r;
vector <string> m;
int arry[251]={0};
int len=text.size();
int s,c;
s=len/(2*nRow-2); //base数据
c=len%(2*nRow-2); //为上面绿色的个数
for(int i=1;i<=nRow;++i)
{
if(i==1) //计算第一层的个数
{
if(c>=1)
arry[i]=s+1; //arry的下标表述层数,内容为当前层的个数
else
arry[i]=s;
}
else if(i==nRow) //计算最后一层的个数
{
if(c>=nRow)
arry[i]=s+1;
else
arry[i]=s;
}
else //中间层的个数
{
if(c>=i&&)
arry[i]=2*s+1;
else
arry[i]=2*s;
}
}
m.resize(nRow+1);
int loc;
int base;
base=0;
for(int i=1;i<=nRow;++i) //依据每一层的个数,切割字符串
{
base+=arry[i-1];
for(int j=0;j<arry[i];++j)
{
loc=j+base;
m[i].push_back(text[loc]);//m[i]保存每一层的字符串。
}
}
int flag=0; //~0 addr++ 0 add--
int cnt=1;
int* num=new int[nRow+1]();
//以下是在切割完毕后的循环遍历
int x,y;
int tol=text.size();
while(1)
{
tol--;
if(tol<0)
break;
x=cnt;
y=num[cnt];
r.push_back(m[x][y]);
num[cnt]++;
if(cnt==nRow || cnt==1)
flag=~flag;
if(flag!=0)
cnt++;
else
cnt--;
}
cout<<r<<endl;
return r;
}
相关文章
- Java实现 LeetCode 530 二叉搜索树的最小绝对差(遍历树)
- python 遍历list并删除部分元素
- Atitit 循环(loop), 递归(recursion), 遍历(traversal), 迭代(iterate).
- 华为OD机试 - 二叉树层序遍历(Java & JS & Python)
- uniapp、uView——复选框的使用(使用星期为例)、三目运算、push、forEach遍历方法
- Java遍历目录下全部文件并替换指定字符串
- 695. 岛屿的最大面积-深度优先遍历
- 19. 删除链表的倒数第 N 个结点-c语言 遍历一次链表求解
- 144. 二叉树的前序遍历
- N 叉树的后序遍历-c语言递归法
- vue双向绑定的时候把遍历的数组转为了字符串,并且再转回去数组进行绑定
- 二叉树系列(一):已知先序遍历序列和中序遍历序列,求后序遍历序列
- 二叉树的遍历
- VC++获取网卡上的IP、网关及DNS信息,获取最佳路由,遍历路由表中的条目(附源码)
- 二叉排序树 bst 创建和遍历
- Python学习笔记六之字符串操作:遍历、切割、查找等
- matlab遍历图像、字符串数组等基本操作