测试开发面试题解

Criss@陈磊

发布于 2020-01-22 09:52:10

5220

发布于 2020-01-22 09:52:10

文章被收录于专栏：测试技术圈

新书

速递

吴老的java版《selenium webdriver3 实战宝典》和python版《selenium Webdriver 3.0 自动化测试框架实战指南》出版了，代码拿来就能用。

文｜李兴

题目描述

给定一个由括号元素'('， ')'，'[':，']'， '{'， '}'组成的字符串，判断该字符串中的所有类型的括号是否是闭合的。

判断条件：

（1）左括号必须用相同类型的右括号闭合

（2）左括号必须以相同的顺序闭合

示例：

输入：() 输出：true

输入：()[]{} 输出：true

输入：(] 输出：false

输入：([)] 输出：false

输入：([{}]) 输出：true

输入：((())) 输出：true

输入：([[()()]{}]){}[] 输出：true

解题分析一

通过观察示例中的字符串发现，一个符合括号闭合要求的字符串有如下特点：

（1）合理的嵌套关系

（2）嵌套的最内层是一对闭合的括号类型（相邻两个元素），如()

首先将字符串string转换成列表string_list，然后判断列表string_list当中是否存在相邻字符为闭合括号的情况，如果存在就删除这两个字符，然后继续判列表string_list当中是否存在相邻字符为闭合括号的情况。直到string_list为空，或者没有可以删除的元素为止。

如果string_list能够删除为空，为真，否则为假

此题的解法类似于我们玩的消消乐，如果能够全部消除，则通关

算法

def isClosedParentheses(string):
   '''
    判断一个由括号组成的字符串是否是闭合的
   '''
    d= {'(': ')', '[': ']', '{': '}'}
   string_list = list(string)
   while string_list:
       for i in range(len(string_list)-1): # 获取所有列表的下标
           if string_list[i] in d.keys() and d[string_list[i]] == string_list[i +1]:# 找到闭合的括号
                string_list.pop(i) # 先删除闭合括号的左边，然后该下标右边，下标左移
                string_list.pop(i) # 左移完成后，闭合括号的右边，左移到该下标继续删除
                break # 找到闭合括号后退出本次循环
       else:
           break # for循环完成后退出while循环
            #验证列表是否全部删除
   if string_list:
       return False
   else:
       return True

考点

1、列表元素删除

2、for…else…语法结构

解题分析二

给出的括号字符串，一定存在一对正确的括号，如：(),[],{}
将这一对有效括号清除掉，这对括号外的括号就成为中间成对出现的括号，
这样一直清除下去，这个字符串如果清除完毕就是True，否则为False

算法

def isClosedParentheses(string):
   '''
    判断一个由括号组成的字符串是否是闭合的
   '''
   while '{}' in s or '()' in s or '[]' in s:
           s = s.replace('{}', '')
           s = s.replace('[]', '')
           s = s.replace('()', '')
       return s == ''