从0开始学算法——第四天（题目参考答案）

写在开头的话

以下是我对于这四道题目的解答（python版），其中代码部分有一部分借助了AI（我说思路AI写的代码哈，因为这样子还不用手打注释），肯定不是最优解，有更好的方法欢迎大家留言，我们共同进步！

第一题解答——字符串

import sys

def count_different_strings():
"""
统计不同字符串的数量

主要思想：
1. 使用Python的内置集合(set)数据结构来存储不同的字符串
2. 集合会自动去重，相同字符串只会保留一个
3. 遍历所有输入字符串，将它们添加到集合中
4. 集合的大小就是不同字符串的数量
"""
# 读取所有输入数据
data = sys.stdin.read().split()

# 第一个元素是字符串数量N
n = int(data[0])

# 从第二个元素开始是N个字符串
strings = data[1:n+1]

# 使用集合来去重
# 集合(set)是Python中的一种数据结构，它只存储不重复的元素
# 当我们向集合中添加元素时，如果元素已经存在，集合不会重复添加
unique_strings = set()

# 遍历所有字符串并添加到集合中
for s in strings:
unique_strings.add(s)
# 集合会自动处理重复的字符串

# 输出不同字符串的数量，即集合的大小
print(len(unique_strings))

if __name__ == "__main__":
count_different_strings()

第二题解答——括号串

def is_valid_parentheses(n, s):
# 如果长度是奇数，不可能是合法的括号序列（空串除外）
if n % 2 != 0:
return "No"

stack = []
for ch in s:
if ch == '(':
stack.append(ch)
elif ch == ')':
if not stack: # 栈为空，无法匹配
return "No"
stack.pop() # 匹配一个左括号
else:
# 题目保证只包含括号，所以这里不会执行，但为了完整性可以加上
return "No"

# 遍历结束后，栈为空则说明全部匹配
return "Yes" if not stack else "No"

if __name__ == "__main__":
n = int(input())
s = input().strip()
print(is_valid_parentheses(n, s))

第三题解答——情景

import sys

def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
a = list(map(int, data[1:1 + n]))
stack = []
for x in a:
if x != 0:
stack.append(x)
else:
if stack:
stack.pop()
# 逆序输出栈中元素
for i in range(len(stack) – 1, -1, -1):
sys.stdout.write(str(stack[i]) + '\\n')

if __name__ == "__main__":
main()

第四题解答——哈希

def main():
import sys
input = sys.stdin.read
data = input().split()

q = int(data[0])
s = set()
idx = 1
results = []

for _ in range(q):
op = data[idx]
x = int(data[idx + 1])
idx += 2

if op == 'I':
s.add(x)
elif op == 'Q':
if x in s:
results.append("Yes")
else:
results.append("No")

sys.stdout.write("\\n".join(results))

if __name__ == "__main__":
main()