Problem1
【Problem Description】
Write a program that can input a three-digit positive integer and output the corresponding number in reverse order. If the input number is not a three-digit positive integer, output -1.
【Input Format】
Input a three-digit positive integer.
【Output Format】
Output the value of the number after reversing the digits.
【Sample Input】
356【Sample Output】
653
【Explanation】
The positive integer value input is 356. Swapping the ones and hundreds digit gives the result 653. If the input positive integer is 300, then the output is 3.
解析：这个题目考察了判断数据的合法性，以及对数位的反转。
代码：
num = input()
if len(num) != 3:
print(-1)
exit()
reversed = 0
for i in range(len(num) - 1, -1, -1):
if not num[i].isdigit():
print(-1)
exit()
reversed = (reversed * 10 + (ord(num[i]) - ord('0')))
print(reversed)
省流版：
num = input()
if len(num) != 3 or not num.isdigit():
print(-1)
exit()
print(num[::-1])
这里涉及到切片的知识。
以下是常用的切片和含义：
list[起始索引,结束索引] 切片时包含起始索引位置的元素，但不包含结束索引位置的元素。索引为 0 表示第一个,1 表示第二个,-1 表示最后一个,-2 表示倒数第二个；这样的好处在于通过 list[x:] 和 list[:x] 即可将列表轻松切分为两个互补的子列表，非常流畅。
list[-1]：返回最后一个数据，list[-2] 是倒数第二个···，以此类推；
list[:1]：返回 0 到 1 的数据，故返回第一个数据；
list[1:]：返回从1到0的数据,故返回第二个到最后一个的数据（不包含结束索引位置0）；注意不要和前面的混淆
list[-1:]：返回从 -1 到 0 的数据，故返回最后一个数据，注意这里是正序的；
list[:-1]：返回从 0 到 -1 的数据，故返回第一个到倒数第二个的数据（不包含结束索引位置-1）；
list[::1]：表示步长为 1，步长大于 0 时，返回序列为原顺序；
list[::-1]: 表示从右往左以步长为 -1 进行切片。步长小于 0 时，返回序列为倒序；
list[::2]: 表示从左往右步长为 2 进行切片。
list[:]：返回整个列表（注意没有第二个冒号就都默认是正序的）。
例子：
list = [1, 2, 3, 4, 5]
print(list[-1]) # 5
print(list[:1]) # [1]
print(list[1:]) # [2, 3, 4, 5]
print(list[-1:]) # [5]
print(list[:-1]) # [1, 2, 3, 4]
print(list[::1]) # [1, 2, 3, 4, 5]
print(list[::-1]) # [5, 4, 3, 2, 1]
print(list[::2]) # [1, 3, 5]
print(list[:]) # [1, 2, 3, 4, 5]
Problem2
【Problem Description】
Implement a simple calculator: Read two integer operands (data1 and data2) and an operator (op) from the console, and calculate the expression data1 op data2. The operator op can be one of the followings: +, -, *, or /.
【Input Format】
Input the operands and operator from the console:
-
First, input two integers as the operands, separated by a space, representing data1 and data2.
-
Next, input a character as the operator op, which can be ‘+’, ‘-’, ‘*’, or ‘/’.
Leave a space between data1, data2, and op. Refer to the sample input for specific format.
【Output Format】
Output the result of the calculation to the console. If division is performed and the value is fully divisible, output the result as an integer. Otherwise, output the value rounded to two decimal places.
【Sample Input】
23 5 *【Sample Output】
115【Explanation】
In the input, the first operand is 23, the second operand is 5, and the operator is ‘*’. The calculator performs multiplication to the operands 23 and 5. The result is 115.
解析：这个题本身不难，就是实现一个基础的计算器，我用函数闭包的方法写的，也算是复习一下课上的知识。
代码：
import math
# eps = 1e-8
def calculate(op: str):
def specific(a, b):
if op == '+':
return a + b
elif op == '-':
return a - b
elif op == '*':
return a * b
elif op == '/':
if a % b == 0:
return a // b
return a / b
return 0
return specific
a, b, op = input().strip().split(' ')
a = int(a)
b = int(b)
out = calculate(op)(a, b)
if isinstance(out, int):
print(int(out))
else:
print("%.2f" %(out))
注意在除法的时候判断一下整除，如果能除尽，就返回 int 类型（// 除法），否则返回 float 类型。
Problem3
【Problem Description】
Write a program to find the longest common substring between two input strings, s and t.
【Input Format】
Read the strings s and t from the console, each on a separate line. Both s and t can consist of any arbitrary characters, with lengths not exceeding 50 characters. The input data should only have one unique longest common substring. If there is no common substring, print “No Answer”.
【Output Format】
Print the longest common substring of s and t on a separate line, followed by a newline character.
Algorithm hint: Use an integer counter to keep track of the current matching length and a character array to store the current matching substring. If a longer substring is found, update the counter and array accordingly.
【Sample Explanation】
Assume the following input is entered into the console:
aabcdababce
12abcabcdaceThe output is:
abcda解析：这个题翻译成中文就是求最长公共子串，和它很相似的还有求最长公共子序列。这可以说是动态规划模板题（不用动态规划也不好写）。
代码：
# 最长公共子序列，经典题目，复习动态规划
s1 = input()
s2 = input()
dp = [["" for _ in range(max(len(s1), len(s2)))] for _ in range(max(len(s1), len(s2)))]
x = 0 # 记录最长公共子串的信息
y = 0
max_len = 0
for i in range(1, len(s1)):
if s1[i] == s2[0]:
dp[i][0] = s1[i]
else:
dp[i][0] = ''
if len(dp[i][0]) > max_len:
max_len = len(dp[i][0])
x = i
y = 0
for j in range(1, len(s2)):
if s1[i] == s2[j]:
dp[i][j] = dp[i - 1][j - 1] + s1[i]
if len(dp[i][j]) > max_len:
max_len = len(dp[i][j])
x = i
y = j
else:
dp[i][j] = ''
if dp[x][y] == '':
print('No Answer')
else:
print(dp[x][y])
# dp[i][j]表示以i，j结尾的最大公共子串
对于最长公共子序列，求法也差不多，只是 s1[i] ！= s2[j] 子序列长度不变，不清零。
leetcode 【剑指 Offer II 095. 最长公共子序列】
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
class Solution:
def longestCommonSubsequence(self, s1: str, s2: str) -> int:
dp = [[0 for _ in range(max(len(s1), len(s2)))] for _ in range(max(len(s1), len(s2)))]
max_len = 0
for j in range(0, len(s2)):
if s1[0] == s2[j]:
dp[0][j] = 1
elif j > 0:
dp[0][j] = dp[0][j - 1]
if dp[0][j] > max_len:
max_len = dp[0][j]
for i in range(1, len(s1)):
if s1[i] == s2[0]:
dp[i][0] = 1
else:
dp[i][0] = dp[i - 1][0]
if dp[i][0] > max_len:
max_len = dp[i][0]
for j in range(1, len(s2)):
if s1[i] == s2[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
if dp[i][j] > max_len:
max_len = dp[i][j]
return max_len
# 序列化是很重要的
可以看到，初始条件的处理是很困难的，如果不合理选取初始条件，就会增大代码量。这也是动态规划的精髓之一。
Problem4
【Problem Description】
There are two rectangles, A and B, positioned arbitrarily on a plane. Write a program to calculate the area of their intersection (shaded region in the diagram). (0 ≤ a, b ≤ 1000)
【Input Format】
Read two lines from standard input, each containing four integers separated by spaces, in the following format:
Ax1 Ay1 Ax2 Ay2
Bx1 By1 Bx2 By2
Here, (x1, y1) represents the coordinates of the top-left corner of the rectangle, and (x2, y2) represents the coordinates of the bottom-right corner. All coordinate values are integers ranging from 0 to 1000.
【Output Format】
Print an integer to standard output, which represents the area of the intersection between the two rectangles (can be 0). End the output with a newline character.
【Sample Input】
0 2 2 0
1 4 3 1【Sample Output】
1【Explanation】
The intersection area of the two rectangles is 1.
解析：这个题非常巧妙。由于是求重叠部分，我们可以去两个矩形中上边高度最小的，下边高度最大的，左边位置最大的，右边位置最小的。注意特判两个矩形不相交的情况（此时重叠部分的上边小于下边，或者右边小于左边，取 max(0, val) 即可。
代码：
x11, y11, x12, y12 = map(int, input().strip().split())
x21, y21, x22, y22 = map(int, input().strip().split())
rect1 = [[min(x11, x12), max(y11, y12)], [max(x11, x12), min(y11, y12)]]
rect2 = [[min(x21, x22), max(y21, y22)], [max(x21, x22), min(y21, y22)]]
up = min(rect1[0][1], rect2[0][1])
down = max(rect1[1][1], rect2[1][1])
left = max(rect1[0][0], rect2[0][0])
right = min(rect1[1][0], rect2[1][0])
ans = (max(up - down, 0)) * (max(right - left, 0))
print(ans)
另外需要注意的是，去除两个数之间的空格应该用 input().strip().split()，这样可以去掉所有的空白字符，而 input().strip().split(' ') 是不行的！！！
Problem5
解析：后缀表达式，数据结构常考题。
代码：
expr = ''.join(input().strip().split())
stk_op = []
post = ''
def get_pri_r(c):
if c == ')':
return 0
elif c == '+' or c == '-':
return 1
elif c == '*' or c == '/':
return 2
elif c == '(':
return 3
else:
return -1
def get_pri_l(c):
if c == '(':
return 0
elif c == '+' or c == '-':
return 1
elif c == '*' or c == '/':
return 2
elif c == ')':
return 3
else:
return -1
# 其实应该有两个优先级，一个是在左的优先级，一个是在右的优先级
for c in expr:
if c.isdigit():
post = post + c
else:
if len(stk_op) and get_pri_r(c) <= get_pri_l(stk_op[-1]):
while len(stk_op) and get_pri_r(c) <= get_pri_l(stk_op[-1]):
tmp = stk_op.pop(-1)
if tmp == '(':
break
post = post + tmp
if c != ')':
stk_op.append(c)
# for sym in reversed(stk_op):
# post += sym
for sym in stk_op[::-1]: # 倒序
post += sym
print(post)
为什么要定义两种操作符顺序，参看严蔚敏老师的《数据结构》。
