C语言详解Z字形变换排列的实现

目录
  • 方法一
  • 方法二

题目链接:Z 字形变换

方法一

——找规律模拟数组

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

通过分析,可以看出这个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)

方法二

——压缩矩阵

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

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

这个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字形变换排列的实现的文章就介绍到这了,更多相关C语言Z字形变换内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言数据结构算法之实现快速傅立叶变换

    C语言数据结构算法之实现快速傅立叶变换 本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作.复数的基本掾作,复习所学过的动态内存分配.文件操作.结构指针的函数调用等内容. 很久以来,傅立叶变换一直是许多领域,如线性系统.光学.概率论.量子物理.天线.数字图像处理和信号分析等的一个基本分析工具,但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的,因此导致了快速傅立叶变换(FFT)的产生. 本实例将对一个二维数组进行正.反快速傅立叶变换.正傅

  • C语言详解Z字形变换排列的实现

    目录 方法一 方法二 题目链接:Z 字形变换 方法一 ——找规律模拟数组 题目要求构造一个从左到右的Z型矩阵. 通过分析,可以看出这个Z型矩阵的特点 Z型矩阵就是如图中的橙色,绿色这样部分组合在一起的,Z型矩阵就是由一个个这样相同周期组成的. 这里有一种情况需要特殊讨论,当矩阵只有一行时,直接返回原字符. 其余情况均可满足. 其周期的构成满足这样一个规律: 在第一列向下填写矩阵行数r个字符,接着向其右上部分共(r-2)列分别填写一个字符.Z型矩阵的周期t=r+r-2=2*r-2,每个周期会占用矩

  • C语言详解数据结构与算法中枚举和模拟及排序

    目录 枚举 连号区间数 递增三元组 二分 双指针 前缀和 模拟 特别数的和 错误票据 排序 快速排序 归并排序 枚举 连号区间数 来源:第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间. 当 N 很小的时候,小明可以

  • C++中的Z字形变换问题

    目录 Z字形变换 描述 Z字形变换 描述 将一个给定字符串 s 根据给定的行数 numRows ,以从上往下.从左到右进行 Z 字形排列. 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下: P A H N A P L S I I G Y I R 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:“PAHNAPLSIIGYIR”. 请你实现这个将字符串进行指定行数变换的函数: string convert(string s, int numRows);

  • C语言详解如何应用模拟字符串和内存函数

    目录 1.strlen 求字符串长度 使用案例: 1.计数法 2.不创建临时变量计数器-递归 3.指针-指针的方式 2.长度不受限制的字符串函数 1.strcpy 使用案例: 模拟实现: 2.strcat 使用案例: 模拟实现: 3.strcmp-比较字符串首字母的大小 使用案例: 模拟实现: 3.长度受限制的字符串函数  1.strncpy 使用案例: 2.strncat  使用案例: 3.strncmp 使用案例: 4.strstr-找子串  使用案例: 模拟实现: 5.strtok 用法:

  • C语言 详解如何删除有序数组中的重复项

    目录 删除有序数组中的重复项Ⅰ a.思路 b.图解 c.代码 d.思考 删除有序数组中的重复项Ⅱ a.思路 b.图解 c.代码 d.思考 删除有序数组中的重复项Ⅰ a.思路 定义变量 int dest=0,cur=1,nums[cur]与nums[dest]逐一比较. nums[cur]!=nums[dest],将nums[cur]放入dest下一个位置,更新dest. nums[cur]!=nums[dest],cur移动. cur==numsSize,结束.返回dest+1. b.图解 c.

  • C语言详解float类型在内存中的存储方式

    目录 1.例子 2.浮点数存储规则 1.例子 int main() { int n = 9; float *pFloat = (float *)&n; printf("n的值为:%d\n",n); printf("*pFloat的值为:%f\n",*pFloat); *pFloat = 9.0; printf("num的值为:%d\n",n); printf("*pFloat的值为:%f\n",*pFloat); re

  • C语言详解如何实现带头双向循环链表

    目录 创建链表存储结构 创建结点 链表的初始化 双向链表的打印 双向链表尾插 双向链表尾删 双向链表头插 双向链表头删 双向链表查找 双向链表pos前插入结点 双向链表删除pos位置的结点 双向链表的销毁 顺序表和链表的区别 2022042311415360.{C}{C}png" /> 创建链表存储结构 我们需要创建一个结构体来存储一个链表结点的相关信息. typedef int ListDataType;//将ListDataType先定义为int类型,根据需要可以改为不同的类型 //创

  • C语言详解冒泡排序实现

    目录 前言 一.冒泡排序是什么 二.具体步骤 1.代码解释 2.读入数据 总结 前言 在排序中,有各种各样的排序方式,今天我们将要来介绍<冒泡排序>.今天会从冒泡排序的具体意义和他的操作来展开. 一.冒泡排序是什么 从左到右,相邻元素进行比较.每次比较一轮,就会找到序列中最大的一个或最小的一个.这个数就会从序列的最右边冒出来. 以从小到大排序为例,第一轮比较后,所有数中最大的那个数就会浮到最右边:第二轮比较后,所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较,最后实现从小到

  • C语言详解结构体的内存对齐与大小计算

    目录 结构体的内存对齐 1.计算结构体的大小 2.结构体的对齐规则 3.为什么存在内存对齐? 4.总结 结构体的内存对齐 1.计算结构体的大小 struct S1 { char c1; // 1 byte,默认对齐数为8,所以c1的对齐数是1,第一个成员变量放在与结构体变量偏移量为0的地址处 int i; // 4 byte,默认对齐数为8,所以i的对齐数是4,所以i要放到偏移量为 4的整数倍 的地址处 char c2; // 1 byte,默认对齐数为8,所以c2的对齐数是1,所以c2要放到偏

  • C语言详解实现字符菱形的方法

    目录 前言 1.定义stdio.h头文件 2.定义主函数 3.定义行数-单数 4.得出分割行数 5.定义字符 6.初始化打印字符数与打印空白数 7.循环打印菱形 8.打印上部分 9.打印剩下部分 10.完整代码 11.完整效果 前言 好,今天就来讲一下如何解这道题. #include<stdio.h> main() { char ch = getchar(); printf(" %c \n %c%c%c \n%c%c%c%c%c\n %c%c%c \n %c \n",ch,

随机推荐