算法题练习——NC52 有效括号序列、NC22 合并两个有序的数组

淩亂°似流年 2024-04-07 12:23 53阅读 0赞

**目录**

NC52 有效括号序列

NC22 合并两个有序的数组

--------------------

### NC52 有效括号序列 ###

**描述**

> 给出一个仅包含字符'(',')','\{','\}','\['和'\]',的字符串，判断给出的字符串是否是合法的括号序列  
> 括号必须以正确的顺序关闭，"()"和"()\[\]\{\}"都是合法的括号序列，但"(\]"和"(\[)\]"不合法。

> 数据范围：字符串长度 0\\le n \\le 100000≤n≤10000
> 
> 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

**示例1**

> 输入："()\[\]\{\}"
> 
> 返回值：true

**示例2**

> 输入："\[\]"
> 
> 返回值：true

**示例3**

> 输入："(\[)\]"
> 
> 返回值：false

**python代码解：**

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param s string字符串 
    # @return bool布尔型
    #
    class Solution:
        def isValid(self , s: str) -> bool:
            # write code here
            st = []
            for i, char in enumerate(s):
                if char == '(':
                    st.append(')')
                elif char == '[':
                    st.append(']')
                elif char == '{':
                    st.append('}')
                elif(len(st)==0):
                    return False
                elif(st[-1]==char):
                    st.pop()
            return len(st) == 0

--------------------

### NC22 合并两个有序的数组 ###

**描述**

> 给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

> 数据范围： 0 \\le n,m \\le 1000≤n,m≤100，|A\_i| <=100∣Ai∣<=100， |B\_i| <= 100∣Bi∣<=100

**注意：**

> 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
> 
> 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印
> 
> 3. A 数组在\[0,m-1\]的范围也是有序的

**示例1**

> 输入：\[4,5,6\],\[1,2,3\]
> 
> 返回值：\[1,2,3,4,5,6\]
> 
> 说明：A数组为\[4,5,6\]，B数组为\[1,2,3\]，后台程序会预先将A扩容为\[4,5,6,0,0,0\]，B还是为\[1,2,3\]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组

**示例2**

> 输入：\[1,2,3\],\[2,5,6\]
> 
> 返回值：\[1,2,2,3,5,6\]

**python代码解：**

# @param A int整型一维数组 
    # @param B int整型一维数组 
    # @return void
    #
    class Solution:
        def merge(self , A, m, B, n):
            # write code here
            for i in range(n):
                A[m+i] = B[i]
            A.sort()
            return A