user
算法刷题 6-10

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。ceshi

6

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

L C I R E T O E S I I G E D H N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"。

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

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 解释:

L D R E O E I I E C I H N T S G

6.1

比较简单的一道题,除了看规律之外,还可以用给方向变量来做。

class Solution:
    def convert(s: str, numRows: int) -> str:
        if len(s) <= numRows or numRows == 1:
            return s
                    
        ans = ""
        for row in range(0,numRows):
            start = row
            
            if (row == 0) or (row == numRows-1):
                while True:
                    ans = ans + s[start]
                    start = start + 2*(numRows-1)
                    if start > len(s)-1:
                        break
                    
            else:
                while True:
                    print("here")
                    ans = ans + s[start]
                    start = start + 2*(numRows-1-row)
                    if start <= len(s)-1:
                        ans = ans + s[start]
                        start = start+2*row
                        if start > len(s)-1:
                            break
                    else:
                        break

            
        return ans
    

s = "A"

print(Solution.convert(s,3))

7

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123 输出: 321

示例 2:

输入: -123 输出: -321

示例 3:

输入: 120 输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

7.1

简单,略过。

class Solution:
    def reverse(self, x: int) -> int:
        
        sign = ""
        if x < 0 :
            sign = "-"
            x = str(x)[1:]

        x = int(sign + str(x)[::-1])

        if x > 2**31 -1 or x < -2**31:
            return 0

        return x
	str_num = str(x)[::-1]
        if str_num.endswith('-'):
            str_num = '-' + str_num[:-1]
            return int(str_num) if int(str_num) >= -2**31 else 0
        return int(str_num) if int(str_num) <= 2**31 - 1 else 0

8

请你来实现一个 atoi 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:

如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。 假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。 该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。 注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0 。

提示:

本题中的空白字符只包括空格字符 ' ' 。 假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围,请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42" 输出: 42

示例 2:

输入: "-42" 输出: -42 解释:第一个非空白字符为 '-', 它是一个负号。   我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3:

输入: "4193 with words" 输出: 4193 解释:转换截止于数字 '3' ,因为它的下一个字符不为数字。

示例 4:

输入: "words and 987" 输出: 0 解释:第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。

示例 5:

输入: "-91283472332" 输出: -2147483648 解释:数字 "-91283472332" 超过 32 位有符号整数范围。   因此返回 INT_MIN (−231) 。

8.1

简单

lass Solution:
    def myAtoi( str: str) -> int:
        str = str.lstrip()

        sign = 0
        for index,letter in enumerate(str):
            if index == 0:
                if (letter == '-' and len(str) > 1) or (letter == '+' and len(str) > 1) or letter.isdigit():
                    sign = "-" if letter == '-' else letter
                    continue
                else:
                    break

            if letter.isdigit():
                sign += letter
            else:
                sign = sign if sign != "-" and sign != "+" else 0
                break
        
        sign = int(sign)
        sign = sign if sign <= 2**31-1 else 2**31-1
        sign = sign if sign >= -2**31 else -2**31
            
        return sign
    
    
str = '+-2'

print(Solution.myAtoi(str))

9

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121 输出: true

示例 2:

输入: -121 输出: false 解释:从左向右读,为 -121 。 从右向左读,为 121- 。因此它不是一个回文数。

示例 3:

输入: 10 输出: false 解释:从右向左读,为 01 。因此它不是一个回文数。

进阶:

你能不将整数转为字符串来解决这个问题吗?

9.1

简单,注意一下进阶问题!

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # 68 ms , 在所有 Python3 提交中击败了 84.98% 的用户
        x = str(x)
        flag = False
        if x == x[::-1]:
            flag = True

        return flag

进阶

	origin = x
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        revertedNumber = 0
        while True:
            revertedNumber = revertedNumber * 10 + x % 10
            x //= 10
            if x < 10:
                revertedNumber = revertedNumber * 10 + x % 10
                break

        return (origin == revertedNumber or origin == revertedNumber/10)

10 ❌

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。

说明:

s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。

示例 1:

输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素,在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入: s = "ab" p = "." 输出: true 解释: "." 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入: s = "aab" p = "cab" 输出: true 解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个,'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入: s = "mississippi" p = "misisp*." 输出: false

10.1

看不懂下面的算法

# 回溯
class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern:
            return not text

        first_match = bool(text) and pattern[0] in {text[0], '.'}

        if len(pattern) >= 2 and pattern[1] == '*':
            return (self.isMatch(text, pattern[2:]) or
                    first_match and self.isMatch(text[1:], pattern))
        else:
            return first_match and self.isMatch(text[1:], pattern[1:])
# 动态规划
class Solution(object):
    def isMatch(self, text, pattern):
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(pattern):
                    ans = i == len(text)
                else:
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)
微信小程序码
其他代码 都是无关网页的一些代码
——
Total Comments(Loading)
New to Old
defaultimg
Input Your Information to Comment
Loading