Python|每日一练|栈|数组|字典树|数组|树|广度优先搜索|单选记录：逆波兰表达式求值|回文对|二叉树的层序遍历

1、逆波兰表达式求值（栈，数组）

根据 逆波兰表示法(https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437)，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

 

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

 

示例 1：

输入：tokens = ["2","1","+","3","*"]

输出：9

解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]

输出：6

解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

输出：22

解释：

该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5

= ((10 * (6 / (12 * -11))) + 17) + 5

= ((10 * (6 / -132)) + 17) + 5

= ((10 * 0) + 17) + 5

= (0 + 17) + 5

= 17 + 5

= 22

 

提示：

• 1 <= tokens.length <= 104
• tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

 

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

选项代码：

class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""stack = []for token in tokens:if token not in ["+", "%", "*", "/"]:stack.append(int(token))else:num1 = stack.pop()num2 = stack.pop()if token == "+":stack.append(num1 + num2)elif token == "-":stack.append(num2 - num1)elif token == "*":stack.append(num1 * num2)elif token == "/":if num1 * num2 < 0:result = -((-num2) // num1)stack.append(result)else:stack.append(num2 // num1)print(stack)return stack.pop()
# %%
if __name__ == "__main__":tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]sol = Solution()result = sol.evalRPN(tokens)print(result)

PS:逆波兰式

（Reverse Polish Notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）。

算法定义

一个表达式E的后缀形式可以如下定义：

（1）如果E是一个变量或常量，则E的后缀式是E本身。

（2）如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1'E2' op，这里E1'和E2'分别为E1和E2的后缀式。

（3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。

如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+

(a+b)*c-(a+b)/e的后缀表达式为：

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

算法作用

实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

2、回文对（字典树，数组）

给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

 

示例 1：

输入：words = ["abcd","dcba","lls","s","sssll"]

输出：[[0,1],[1,0],[3,2],[2,4]]

解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2：

输入：words = ["bat","tab","cat"]

输出：[[0,1],[1,0]]

解释：可拼接成的回文串为 ["battab","tabbat"]

示例 3：

输入：words = ["a",""]

输出：[[0,1],[1,0]]

提示：

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] 由小写英文字母组成

选项代码：

from typing import  List
class Solution:def palindromePairs(self, words: List[str]) -> List[List[int]]:def is_palindrome(str, start, end):"""检查子串是否是回文串"""part_word = str[start : end + 1]return part_word == part_word[::-1]def find_reversed_word(str, start, end):"""查找子串是否在哈希表中Return:不在哈希表中，返回 -1否则返回对应的索引"""part_word = str[start : end + 1]ret = hash_map.get(part_word, -1)return rethash_map = {}for i in range(len(words)):word = words[i][::-1]hash_map[word] = ires = []for i in range(len(words)):word = words[i]word_len = len(word)if is_palindrome(word, 0, word_len - 1) and "" in hash_map and word != "":res.append([hash_map.get(""), i])for j in range(word_len):if is_palindrome(word, j, word_len - 1):left_part_index = find_reversed_word(word, 0, j - 1)if left_part_index != -1 and left_part_index != i:res.append([i, left_part_index])if is_palindrome(word, 0, j - 1):right_part_index = find_reversed_word(word, j, word_len - 1)if right_part_index != -1 and right_part_index != i:res.append([right_part_index, i])return res
# %%
if __name__ == "__main__":words = ["a",""]sol = Solution()result = sol.palindromePairs(words)print(result)

3、二叉树的层序遍历（树，广度优先搜索）

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

 

示例：
二叉树：[3,9,20,null,null,15,7], #！python中用None

3

/ \

9  20

/  \

15   7

返回其层序遍历结果：

[

[3],

[9,20],

[15,7]

]

选项代码：

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:return []queue, res = [root], []while queue:size = len(queue)temp = []for i in range(size):data = queue.pop(0)temp.append(data.val)if data.left:queue.append(data.left)if data.right:queue.append(data.right)res.append(temp)return res