[LeetCode题解] ZigZag Conversion

栏目: 编程工具 · 发布时间: 5年前

内容简介:第二天。今天AC掉了一道之前没AC掉的题目。。。今天的题目是

原文在这,可以来我blog翻翻哦。

第二天。今天AC掉了一道之前没AC掉的题目。。。

今天的题目是 6. ZigZag Conversion

题目描述:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

恩,又是一道“编程题“, 并不涉及到什么算法,静下心来仔细想想还是能做出来的。做这道题的思路就是 一点一点跑例子 ,找出其中的规律就好了。

我们先以输入为 s = "PAYPALISHIRING", numRows = 3 为例子,这是题目给出的例子,正确答案已经有了。

先把Z字型画出来(不难发现,题目在最开始其实已经给出了答案):

P   A   H   N
A P L S I I G
Y   I   R

观察上面的例子我们可以发现:

  • 第一行中的元素在原来的字符串中下标相差4个。
  • 第二行中的元素在原来字符串中下标相差2个。

ok,看起来好像找到了一些规律,继续跑一个例子验证一下,这次的输入是 s = "PAYPALISHIRING", numRows = 3 ,把Z字型画出来:

P     I    N
A   L S  I G
Y A   H R
P     I

可以看到第一行的元素在原来字符串中的下标相差6个,但是第二行却出现了一些不一样的情况:

  • AL 相差4个, LS 却相差2个
  • SI 相差4个, IG 却相差2个

看起来 offset 是有规律的,而且好像需要分成两种情况,继续看看第3行:

  • YA 相差2个, AH 相差4个
  • HR 相差4个,如果还有元素的话,下一个元素与 R 之间显然相差2个。

从上面的例子来看显然是要分成两种情况的,某一行中下标之间的 offset 是不断在两个数字间不断变换的。

我们尝试用两个数组来保存这些 offset ,我们把这两个数组定义为 skipDownskipUp 。其中 skipDown 表示下标在z字型中经过了一个向下的剪头,如第二个例子中,第一行的 P 移动到 I 时, P 经过了 AYPAl 组成的向下的剪头。 skipUp 同理可推。

如果我们继续跑例子的话,应该是比较容易找出规律的:

  • i 行的 skipDown2*(i-1) ,而第一行和最后一行的 skipDown 都应该为 2*(numRows)
  • skipDownskipUp 是逆序的关系。

综上,我们可以写出下面的代码:

string convert(string s, int numRows) {
    if (numRows < 2) return s;
    vector<int> skipDown(numRows);
    vector<int> skipUp(numRows);
    
    skipDown[0] = 2*(numRows-1);
    skipUp[0] = 0;
    for(int i = 1;i < numRows; i++) {
        skipDown[i] = skipDown[i-1] - 2;
        skipUp[i] = skipUp[i-1] + 2;
    }
    
    skipDown[numRows-1] = skipDown[0];
    skipUp[0] = skipUp[numRows-1];
    
    string res(s.size(), ' ');
    
    int index = 0;
    for(int i = 0;i < numRows; i++) {
        bool flag = true;
        for(int j = i;j < s.size();index++) {
            res[index] = s[j];

            if (flag) { j += skipDown[i]; }
            else { j += skipUp[i]; }
            
            flag = !flag;
        }
    }
    return res;
}

当然这肯定不是最优的代码,比如其实我们可以不用两个数组,甚至不用数组来保存的 offset ,但是这样写会比较容易理解,代码会比较简单点。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

零工经济

零工经济

Diane Mulcahy / 陈桂芳 / 中信出版集团股份有限公司 / 2017-11-1 / CNY 39.00

// 国内第一本讲述“零工经济”概念的图书! // 互联网时代,你的技能与兴趣可以与市场需求产生更佳的匹配! // 通过工作模式的转型,你的财务状况可以获得更多的灵活性与稳定性! 如果把当前的工作世界看作一把尺子,设想它一头是传统意义上由企业提供的职业阶梯,另一头是失业,那么两头之间范围广、种类多的工作选择便是零工经济。它包括咨询顾问、承接协定、兼职工作、临时工作、自由职业、个体......一起来看看 《零工经济》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

SHA 加密
SHA 加密

SHA 加密工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具