LeetCode

LeetCode-6-Z字形变换

Posted by 刘知安 on 2018-11-15
文章目录
  1. 题目内容
    1. 描述
    2. 示例：
  • 解法 —— 逐行追加+方向控制
    1. 要注意的地方

    • 题目内容

    描述

    将字符串 "PAYPALISHIRING"以Z字形排列成给定的行数：

    1
    2
    3
    P   A   H   N
    A P L S I I G
    Y   I   R

    之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"

    实现一个将字符串进行指定行数变换的函数:

    1
    string convert(string s, int numRows);

    示例：

    • 示例1
    1
    2
    输入: s = "PAYPALISHIRING", numRows = 3
    输出: "PAHNAPLSIIGYIR"
    • 示例2
    1
    2
    3
    4
    5
    6
    7
    8
    输入: s = "PAYPALISHIRING", numRows = 4
    输出: "PINALSIGYAHRPI"
    解释:

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

    解法 —— 逐行追加+方向控制

    开始我死活没看出来这怎么是个Z，原来是N字型，倒着的Z

    看上去好像要开个二维数组，然后一个一个字符放进去，然后再读出来，其实只要把“N“字型从左右两边同时向中间压扁，这样就只需要开一个高度为“|”的字符串数组，然后每到第一行和最后一行，就改变寻找下一次放字符所在行的方向。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    def longestPalindrome(self, s):
           """
           :type s: str
           :rtype: str
           """
           maxPalindromeLen = 0
           maxPalindrome = ""

           n = len(s)
           if n == 1:
               maxPalindromeLen = 1
               maxPalindrome = s
               return maxPalindrome

           for i in range(n):
               for j in range(i, n):
                   sub_str=s[i:j+1]
                   if self.isPalindrome(sub_str):
                       if j - i + 1 > maxPalindromeLen:
                           maxPalindromeLen = j - i + 1
                           maxPalindrome = sub_str
           return maxPalindrome

       def isPalindrome(self, s):
           n = len(s)
           # 根据回文的对称性，两个指针往中间靠拢
           head = 0
           tail = n - 1
           while (head <= tail):
               if s[head] != s[tail]:
                   return False
               head += 1
               tail -= 1

           return True

    要注意的地方

    • “数组”的创建（“预占位”的方式）
    FEATURED TAGS
    LeetCode
    FRIENDS