C语言怎么实现Z字形变换排列

发布时间:2022-04-24 14:12:16 作者:iii
来源:亿速云 阅读:143

本篇内容介绍了“C语言怎么实现Z字形变换排列”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

题目链接:Z 字形变换

C语言怎么实现Z字形变换排列

方法一

——找规律模拟数组

题目要求构造一个从左到右的Z型矩阵。

通过分析,可以看出这个Z型矩阵的特点

C语言怎么实现Z字形变换排列

Z型矩阵就是如图中的橙色,绿色这样部分组合在一起的,Z型矩阵就是由一个个这样相同周期组成的。

这里有一种情况需要特殊讨论,当矩阵只有一行时,直接返回原字符。

其余情况均可满足。

其周期的构成满足这样一个规律:

在第一列向下填写矩阵行数r个字符,接着向其右上部分共(r-2)列分别填写一个字符。Z型矩阵的周期t=r+r-2=2*r-2,每个周期会占用矩阵的r-1列,总共有 字符长度len/t个周期(将最后一个周期视作完整周期)。

因此创建一个具有r行c列的的二维矩阵,(这里在计算列的时候需要多+一个周期,因为除法的计算会舍去余数)。一开始从(0,0)这个位置开始填写字符,通过判断i%t与r-1的大小决定向上移动还是向下移动。

共两种情况:

i%t<r-1 :说明这时矩阵正在填写第一列的数字,这时只需要向下移动

i%t>=r-1:说明第一列已经填写好了,这时需要向右上方进行填写字符,所以需要向右移动一位,向上移动一位。

当一个周期运行完时,又会回到新周期的第一列。

再次遍历矩阵,将存储有字符的位置加入到一个新的字符串中。

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1||numRows>=s.size())//特殊情况进行排除
        return s;
      int r=numRows;//矩阵的行数
      int t=2*r-2;//周期所含字符个数
      int len=s.size();//字符串的长度
      int c=(len+t)/t*(r-1);//二维矩阵列数
      vector<string> v1 (r,string(c,0));
    for(int i=0, x=0,y=0;i<len;i++){
        v1[x][y]=s[i];
        
        if(i%t<r-1){
            x++;//向下移动
        }
        else{
            x--;//向上移动
            y++;//向右移动
        }  
    }
    string ans;
    for(int i=0;i<r;i++){//遍历矩阵,扫描字符并添加
        for(int j=0;j<c;j++){
            if(v1[i][j])
            ans+=v1[i][j];
        }
    }
    return ans;
    }
};

时间复杂度=o(nr)

空间复杂度=o(nr)

方法二

&mdash;&mdash;压缩矩阵

在第一种方法,需要构造一个二维矩阵,但是其实只使用了其中的部分空间,这样就导致浪费了许多空间,因此可以对矩阵进行压缩。

依旧是将矩阵只有一行的情况进行额外讨论,若成立,直接返回原字符串。 反之,创建一个r行1列的的string数组,通过判断字符i的位置(与第一种方法的判断方式一样),直接将字符填写到数组的对应行。 举例说明:

C语言怎么实现Z字形变换排列

这个Z型字符在模拟数组是这样呈现的:

C语言怎么实现Z字形变换排列

class Solution {
public:
    string convert(string s, int numRows) {
    int len=s.size();//字符串长度
    int r=numRows;//矩阵行数
    int t=2*r-2;//周期所含字符个数
     if (r == 1) {
            return s;
        }
    vector<string> v1(r);
    int x=0;
        for(int i=0;i<len;i++){
            v1[x]+=s[i];
            if(i%t<r-1)
            x++;//向下移动
            else
            x--;//向上移动
        }
        string ans;
        for (auto &row : v1) {//遍历矩阵,扫描字符并添加
            ans += row;
        }
    return ans;
    }
};

时间复杂度:o(n)

空间复杂度:o(n)

“C语言怎么实现Z字形变换排列”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

推荐阅读:
  1. css如何实现凸字形状
  2. Opencv实现傅里叶变换

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c语言

上一篇:vue怎么使用el-table实现循环轮播数据列表

下一篇:Android用SharedPreferences怎么实现登录注册注销功能

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》