郑州网站建设那家好,网址源码在线查看,广东建设信息网成绩查询,网站建设的认识1、逆波兰表达式求值#xff08;栈#xff0c;数组#xff09;
根据 逆波兰表示法(https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437)#xff0c;求表达式的值。
有效的算符包括 、-、*、/ 。每个运算对象可以是整数#xff0c;也可以是另一个…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 104tokens[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: intstack []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 NotationRPN或逆波兰记法也叫后缀表达式将运算符写在操作数之后。
算法定义
一个表达式E的后缀形式可以如下定义
1如果E是一个变量或常量则E的后缀式是E本身。
2如果E是E1 op E2形式的表达式这里op是任何二元操作符则E的后缀式为E1E2 op这里E1和E2分别为E1和E2的后缀式。
3)如果E是E1形式的表达式则E1的后缀式就是E的后缀式。
如我们平时写ab这是中缀表达式写成后缀表达式就是ab
(ab)*c-(ab)/e的后缀表达式为
(ab)*c-(ab)/e
→((ab)*c)((ab)/e)-
→((ab)c*)((ab)e/)-
→(abc*)(abe/)-
→abc*abe/-
算法作用
实现逆波兰式的算法难度并不大但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式原因就在于这个简单是相对人类的思维结构来说的对计算机而言中序表达式是非常复杂的结构。相对的逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构它执行先进后出的顺序。
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 50000 words[i].length 300words[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
