首页 > 其他分享 >leetcode 65. 有效数字 66. 寻找两个正序数组的中位数

leetcode 65. 有效数字 66. 寻找两个正序数组的中位数

时间：2023-06-02 12:07:21浏览次数：51  
标签：False State 有效数字 STATE flag 65 66 return patten


leetcode 65. 有效数字 66. 寻找两个正序数组的中位数

65. 有效数字

难度困难295

有效数字（按顺序）可以分成以下几个部分：

  1. 一个 小数 或者 整数
  2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 下述格式之一：
  1. 至少一位数字，后面跟着一个点 '.'
  2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
  3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 至少一位数字

部分有效数字列举如下：

  • ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：

  • ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

示例 1：

输入：s = "0"
输出：true

示例 2：

输入：s = "e"
输出：false

示例 3：

输入：s = "."
输出：false

示例 4：

输入：s = ".1"
输出：true

提示：

  • 1 <= s.length <= 20
  • s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# @Time    : 2022/1/14 14:52 
# @Author  : mtl
# @Desc    : ***
# @File    : 65.py
# @Software: PyCharm
import traceback
from typing import List
from enum import Enum

class Solution:
    def isNumber(self, s: str) -> bool:
        if s == ".":
            return False
        def find(patten: str, s: str):
            plen, slen = len(patten), len(s)
            if slen == 0 or s == ".":
                return False
            i, j = 0, 0
            # jump = True
            arr_num = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]
            while i < plen:
                pstr = patten[i]
                if patten[i] == "(":
                    i2 = i + 1
                    while i2 < plen:
                        if patten[i2] == ")":
                            pstr = patten[i+1:i2].split("|")
                            break
                        i2+=1
                    i = i2
                elif patten[i] == "\\":
                    i += 1
                    pstr = patten[i]
                    if pstr == "d":
                        pstr = arr_num
                elif patten[i] not in arr_num:
                    pstr = patten[i]
                i += 1
                flag = False
                while j < slen:
                    flag = False
                    if isinstance(pstr, List):
                        if s[j] in pstr:
                            flag = True
                            j += 1
                    if isinstance(pstr, str):
                        if s[j] == pstr:
                            flag = True
                            j += 1
                    if patten[i] == "?":
                        flag = True
                        i += 1
                    elif patten[i] != "*" and not flag:
                        return False
                    if i >= plen or patten[i] != "*":
                        break
                    if not flag:
                        i += 1
                        break
                if j >= slen:
                    if str(patten[i]) in ["*", "?"]:
                        i += 1
                    elif not flag:
                        break
            if i != plen or j != slen:
                return False
            return True
        s = s.upper()
        if "e" in s or "E" in s:
            sarr = s.split("E")
            if len(sarr) > 2:
                return False
            if "." in sarr[0]:
                f1 = find("(+|-)?\d\d*.?\d*", sarr[0]) or find("(+|-)?\d*.?\d\d*", sarr[0])
            else:
                f1 = find("(+|-)?\d\d*", sarr[0])
            f2 = find("(+|-)?\d\d*", sarr[1])
            return f1 and f2
        else:
            if "." in s:
                return find("(+|-)?\d\d*.?\d*", s) or find("(+|-)?\d*.?\d\d*", s)
            return find("(+|-)?\d\d*", s)

    def isNumber(self, s: str):
        arr_num = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]

        def getTask(patten: str):
            i, plen = 0, len(patten)
            while i < plen:
                if patten[i] == "(":
                    i2 = i + 1
                    while i2 < plen:
                        if patten[i2] == ")":
                            return i2 + 1, patten[i + 1:i2].split("|")
                        i2 += 1
                if patten[i] == "\\":
                    i += 1
                    pstr = patten[i]
                    if pstr == "d":
                        return i + 1, arr_num
                return i + 1, patten[i]

        def search(s: str, patten):
            if s == "" or s == ".":
                return False
            l, flag = "*", True
            while flag and len(patten) > 0:
                i, p = getTask(patten)
                l = patten[i] if len(patten) > i else ""
                flag = False
                if len(s) > 0:
                    if isinstance(p, str):
                        if s[0] == p:
                            flag = True
                    elif isinstance(p, List):
                        if s[0] in p:
                            flag = True
                    else:
                        flag = False
                    if flag:
                        s = s[1:]
                if i >= len(patten) and len(s) > 0:
                    flag = False
                    break
                if l == "?":
                    flag = True
                    patten = patten[i + 1:]
                elif l != "*":
                    patten = patten[i:]
                elif l == "*" and not flag:
                    flag = True
                    patten = patten[i + 1:]
                if flag and len(s) > 0 and patten == "":
                    flag = False
                    break
            return flag
        pattens = ["(+|-)?\d\d*.", "(+|-)?\d\d*.\d\d*", "(+|-)?.\d\d*", "(+|-)?\d\d*"]
        flag = False
        sarr = s.upper().split("E")
        if len(sarr) > 2:
            return False
        for patten in pattens:
            s2 = sarr[0]
            flag = search(s2, patten)
            if flag:
                break
        if len(sarr) > 1 and flag:
            flag = search(sarr[1], "(+|-)?\d\d*")
        return flag

    def isNumber(self, s: str):
        if s == "":
            return False
        i, slen = 0, len(s)
        add_flag, num_flag, point_flag, has_point, e_flag, flag = False, False, False, False, False, True
        num_arr = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "."]
        symbol_arr = ["+", "-", "e", "E"]
        while i < slen:
            if s[i] in symbol_arr[:-2] and not add_flag:
                if (i > 0 and not e_flag) or (e_flag and s[i - 1] not in symbol_arr[2:]):
                    flag = False
                    break
                add_flag = True
            elif add_flag:
                if s[i] in num_arr[:-1]:
                    add_flag = False
                    num_flag = True
                elif s[i] == ".":
                    add_flag = False
                    continue
                else:
                    flag = False
                if e_flag and not add_flag:
                    flag = True
            elif e_flag:
                if s[i] not in num_arr[:-1]:
                    flag = False
                    break
                elif s[i - 1] in symbol_arr[2:] and not flag:
                    flag = True
            elif s[i] == ".":
                if point_flag or has_point:
                    flag = False
                    break
                if not num_flag:
                    point_flag = True
                    flag = False
                has_point = True
            elif point_flag:
                if s[i] in num_arr:
                    num_flag = True
                else:
                    break
                if num_flag:
                    point_flag = False
                    flag = True
            elif s[i] in num_arr[:-1]:
                num_flag = True
                if e_flag:
                    flag = True
            elif s[i] in symbol_arr[2:] and not e_flag:
                e_flag = True
                flag = False
                if i == 0:
                    break
            if s[i] not in num_arr[:-1]:
                num_flag = False
            if s[i] not in num_arr and s[i] not in symbol_arr:
                flag = False
            if not flag and not e_flag and not point_flag:
                break
            i += 1
        return flag

    def isNumber(self, s: str) -> bool:
        State = Enum("State", [
            "STATE_INITIAL",
            "STATE_INT_SIGN",
            "STATE_INTEGER",
            "STATE_POINT",
            "STATE_POINT_WITHOUT_INT",
            "STATE_FRACTION",
            "STATE_EXP",
            "STATE_EXP_SIGN",
            "STATE_EXP_NUMBER",
            "STATE_END"
        ])
        Chartype = Enum("Chartype", [
            "CHAR_NUMBER",
            "CHAR_EXP",
            "CHAR_POINT",
            "CHAR_SIGN",
            "CHAR_ILLEGAL"
        ])

        def toChartype(ch: str) -> Chartype:
            if ch.isdigit():
                return Chartype.CHAR_NUMBER
            elif ch.lower() == "e":
                return Chartype.CHAR_EXP
            elif ch == ".":
                return Chartype.CHAR_POINT
            elif ch == "+" or ch == "-":
                return Chartype.CHAR_SIGN
            else:
                return Chartype.CHAR_ILLEGAL

        transfer = {
            State.STATE_INITIAL: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
                Chartype.CHAR_SIGN: State.STATE_INT_SIGN
            },
            State.STATE_INT_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT
            },
            State.STATE_INTEGER: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_EXP: State.STATE_EXP,
                Chartype.CHAR_POINT: State.STATE_POINT
            },
            State.STATE_POINT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_POINT_WITHOUT_INT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION
            },
            State.STATE_FRACTION: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_EXP: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
                Chartype.CHAR_SIGN: State.STATE_EXP_SIGN
            },
            State.STATE_EXP_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
            State.STATE_EXP_NUMBER: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
        }

        st = State.STATE_INITIAL
        for ch in s:
            typ = toChartype(ch)
            if typ not in transfer[st]:
                return False
            st = transfer[st][typ]

        return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER,
                      State.STATE_END]

if __name__ == '__main__':
    # s = "0"
    sa = ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
    sa = ["12345.", "123.312", "1.1", "1.123123213213123"]
    sa = ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
    # sa = ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
    # sa = ["."]
    # sa = ["0.."]
    # sa = ["3."]
    # sa = [".e1"]
    # sa = ["11234.1."]
    # sa = ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
    # sa = ["2e0", ".e1", "+.", "+E3", "7e69e"]
    # sa = ["7e69e"]

    num_arr = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "."]

    sa = ["7e3+"]

    # print(num_arr[:-1])
    for s in sa:
        print(Solution().isNumber(s))
    # search("(\d{1,}.|\d{1,}.\d{1,}|.\d{1,}|\d{1,})", "123.123")
    # # s = " 123 "
    # # print(s[1:-1])
    #
    # str = "   hello word  "
    #
    # print(str[1:])
    #
    # left, right = 0,  len(str) - 1
    # while left < len(str) and str[left] == " ":
    #     left += 1
    # while right > 0 and str[right] == " ":
    #     right -= 1
    # print(str[left:right + 1])

66. 加一

难度简单904

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

提示：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

通过次数426,939

提交次数923,900

# -*- coding: utf-8 -*-
# !/usr/bin/env python
# @Time    : 2022/1/20 16:49 
# @Author  : mtl
# @Desc    : ***
# @File    : 66.py
# @Software: PyCharm
from typing import List


class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        dlen = len(digits)
        def add(i):
            if -i > dlen:
                digits.insert(0, 1)
            elif digits[i] + 1 == 10:
                digits[i] = 0
                add(i - 1)
            else:
                digits[i] += 1
            return digits
        return add(-1)

    def plusOne2(self, digits: List[int]) -> List[int]:
        right = len(digits) - 1
        while right >= -1:
            if right == -1:
                digits.insert(0, 1)
                break
            digits[right] += 1
            if digits[right] == 10:
                digits[right] = 0
            else:
                break
            right -= 1
        return digits

    def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1
        for d in range(len(digits) - 1, -1, -1):
            if digits[d] == 10:
                digits[d] = 0
                if d - 1 < 0:
                    digits.insert(0, 1)
                else:
                    digits[d - 1] += 1
            else:
                break
        return digits

if __name__ == '__main__':
    digits = [9, 9, 8]
    # print(digits[:-1])
    print(Solution().plusOne(digits))


标签：False,State,有效数字,STATE,flag,65,66,return,patten
From： https://blog.51cto.com/u_16015778/6401413

相关文章

  • 代码随想录算法训练营第二十三天|669. 修剪二叉搜索树
    [参考链接]669.修剪二叉搜索树 [代码]1#Definitionforabinarytreenode.2#classTreeNode(object):3#def__init__(self,val=0,left=None,right=None):4#self.val=val5#self.left=left6#self.right=right......
  • GDB021BE05 HIEE300766R0005确保保护电气装置和人员免受直接和间接接触
    GDB021BE05HIEE300766R0005确保保护电气装置和人员免受直接和间接接触GDB021BE05HIEE300766R0005GDB021BE05HIEE300766R0005 面板保护继电器-漏电继电器(ELR)、接地故障继电器(EFR)和缺相继电器(PFR)在制造配电板时，必须有除断路器以外的一些保护方法，这些保护方法可......
  • 卫星定位北斗芯片AT6558一款高性能BDS/GNSS多模卫星导航接收机SOC单芯片
    1芯片简介AT6558R是一款高性能BDS/GNSS多模卫星导航接收机SOC单芯片,片上集成射频前端，数字基带处理器，32位的RISCCPU，电源管理功能。芯片支持多种卫星导航系统，包括中国的北斗卫星导航系统BDS，美国的GPS,俄罗斯GLONASS，并实现多系统联合定位。1.2主要特征■功能规范●支持BDS/GPS/GLO......
  • 剑指 Offer 65. 不用加减乘除做加法
    题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用“+”、“-”、“*”、“/”四则运算符号。    classSolution{publicintadd(inta,intb){while(b!=0){//当进位为0时跳出intc=(a&b)<<1;//c=进位a^=......
  • 界面控件DevExpress ASP.NET新主题——Office 365暗黑主题的应用
    DevExpressASP.NET WebFormsControls拥有针对Web表单（包括报表）的110+种UI控件，DevExpressASP.NETMVCExtensions是服务器端MVC扩展或客户端控件，由轻量级JavaScript小部件提供支持的70+个高性能DevExpressASP.NETCoreControls，包含功能完善的报表平台。在之前发布的v22.1版......
  • 6567: 清点人数 树状数组
    描述 NK中学组织同学们去五云山寨参加社会实践活动，按惯例要乘坐火车去。由于NK中学的学生很多，在火车开之前必须清点好人数。初始时，火车上没有学生。当同学们开始上火车时，年级主任从第一节车厢出发走到最后一节车厢，每节车厢随时都有可能有同学上下。年级主任走到第m节车......
  • 6566: 校门外的树2 树状数组
    描述  校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：K=1，读入l,r表示在l到r之间种上一种树，每次操作种的树的种类都不同；K=2，读入l,r表示询问l到r之间有多少种树。注意：每个位置都可以重复种树。  ......
  • 为什么 Microsoft Office 365 那么贵，还有那么多人用Microsoft 365？
    随着数字化办公的普及，越来越多的人开始使用各种办公软件来提高工作效率和便捷性。而Microsoft365作为全球领先的办公软件套件，拥有着丰富的功能和服务，深受全球用户的欢迎。下面将详细介绍Microsoft365的功能、版本、软件和适用人群等信息。Office365直装版：https://souurl.cn/FDa......
  • HDU3662(求三维凸包表面的多边形个数，表面三角形个数，体积，表面积,凸包重心，凸包中点到面
    题目：3DConvexHull题意：给定空间中的n个点，求这n个点形成的凸包的表面的多边形个数。增量法求解:首先任选4个点形成的一个四面体,然后每次新加一个点,分两种情况:1>在凸包内,则可以跳过2>在凸包外,找到从这个点可以"看见"的面S(看不看得见可以用法向量，看点是否在面外侧),删除这些......
  • HDU3966(树链剖分)
    题目：Aragorn'sStory 题意：给一棵树，并给定各个点权的值，然后有3种操作：IC1C2K:把C1与C2的路径上的所有点权值加上KDC1C2K：把C1与C2的路径上的所有点权值减去KQC：查询节点编号为C的权值 分析：典型的树链剖分题目，先进行剖分，然后用线段树去维护即可，注意HDU的OJ采用Windows系统，容易......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99