65. Valid Number

 

難度: Hard

類型:String

CPP程式下載: 65.cpp

前情題要:

判斷字串是否為完整的一個數。

Given a string s, return whether s is a valid number.

For example, all the following are valid numbers: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789", while the following are not valid numbers: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".

Formally, a valid number is defined using one of the following definitions:

1. An integer number followed by an optional exponent.
2. A decimal number followed by an optional exponent.

An integer number is defined with an optional sign '-' or '+' followed by digits.

A decimal number is defined with an optional sign '-' or '+' followed by one of the following definitions:

1. Digits followed by a dot '.'.
2. Digits followed by a dot '.' followed by digits.
3. A dot '.' followed by digits.

An exponent is defined with an exponent notation 'e' or 'E' followed by an integer number.

The digits are defined as one or more digits.

 

Example 1:

Input: s = "0"

Output: true

Example 2:

Input: s = "e"

Output: false

Example 3:

Input: s = "."

Output: false

 

Constraints:

• 1 <= s.length <= 20
• s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

思考方式:

1. 將數字切成第一個數字, 第二個數字,  小數點後的(第三)數字, 第一個正負符號, 第二個正負符號, exp, 以及 小數點(dot), 這七個部分。

2. 每個字元進來, 就根據目前各個部分是否存在來判斷合不合理。

3. 用邏輯的思維判斷這些數字存在與否能不能成為一個合理的數字。

複雜度思考:

Time Complexity: Worst case: O( N )

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 7.98 MB, Beats: 98.61%

Accepted

1498 / 1498 testcases passed

tendchen

submitted at Oct 08, 2025 00:26

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

7.98MB

Beats98.61%

Analyze Complexity

Code

C++

class Solution {
public:
    bool isNumber(string s) {
        //int length=s.size();
        bool sign1=false;
        bool sign2=false;
        bool exp=false;
        bool dot=false;
        int num1=false;
        int num2=false;
        int num3=false;
        int leng=s.length();
        for (int i=0;i<leng;i++)
        {
            switch (s[i])
            {
                case '+':
                case '-':
                    if (sign2) return false;
                    else if (sign1)
                    {
                        if (!exp) return false;
                        else {
                            if (num2) return false;
                            else {
                                if (sign2) return false;
                                else
                                {
                                    sign2=true;
                                    continue;
                                }
                            }
                        }
                    }
                    else {
                        if (dot|num1)
                        {
                            return false;
                        }
                        else
                        {
                            sign1=true;
                            continue;
                        }
                    }
                    break;
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    if (num2)
                    {
                        num2++;
                        continue;
                    }
                    else
                    {
                        if (exp)
                        {
                            num2++;
                            sign2=true;
                            continue;
                        }
                        else
                        {
                            if (num1)
                            {
                                if (!dot)
                                {
                                    num1++;
                                    continue;
                                }
                                else
                                {
                                    num3++;
                                    continue;
                                }
                            }
                            else
                            {
                                num1++;
                                sign1=true;
                                if (dot) num3++;
                                continue;
                            }
                        }
                    }
                    break;
                case '.':
                    if (num2) return false;
                    else if (exp) return false;
                    else if (dot) return false;
                    else if (num1)
                    {
                        num1++;
                        dot=true;
                        continue;
                    }
                    else
                    {
                        sign1=true;
                        dot=true;
                        continue;
                    }
                    break;
                case 'e':
                case 'E':
                    if (exp) return false;
                    else
                    {
                        if (num1)
                        {
                            exp=true;
                            continue;
                        }
                        else
                        {
                            return false;
                        }
                    }
                    break;
                default:
                    return false;
                    break;
            }
        }
        if (num2)   return true;
        if (exp)    return false;
        if (dot)
        {
            if (num3) return true;
            else 
            {
                if (num1) return true;
                else return false;
            }
        }
        if (num1) return true;
        else return false;
    }
};

20. Valid Parentheses Solved

20. Valid Parentheses

難度: Easy

類型: String, Stack

CPP程式下載: 20.cpp

前情題要:

檢查字串是否括弧對稱正確。

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

思考方式:

後進先出, 用 Stack 實作

複雜度思考:

Time Complexity: O( N ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.56 MB, Beats: 96.45%

Accepted

100 / 100 testcases passed

tendchen

submitted at Jul 10, 2025 20:59

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

8.56MB

Beats96.45%

Analyze Complexity

Code

C++

class Solution {
public:
    bool isValid(string s) {
        int i;
        int len=s.size();
        stack<char> sc_symbol;
        //cout << len;
        for (i=0;i<len;i++)
        {
            switch(s[i])
            {
                case '(':
                case '[':
                case '{':
                    sc_symbol.push(s[i]);
                    break;
                case ')':
                    if (sc_symbol.empty()) return false;
                    //cout << sc_symbol.pop();
                    //printf("char=%c\n",sc_symbol.top());
                    if (sc_symbol.top()!='(') return false;
                    sc_symbol.pop();
                    break;
                case ']':
                    if (sc_symbol.empty()) return false;
                    //printf("char=%c\n",sc_symbol.top());
                    if (sc_symbol.top()!='[') return false;
                    sc_symbol.pop();
                    break;
                case '}':
                    if (sc_symbol.empty()) return false;
                    //printf("char=%c\n",sc_symbol.top());
                    if (sc_symbol.top()!='{') return false;
                    sc_symbol.pop();
                    break;

            }
        }
        if (sc_symbol.empty()) return true;
        return false;
    }
};