150. 逆波兰表达式求值

解法一：将计算部分抽象成一个函数，使代码更加简洁，避免了很多冗余操作。对比下面解法二（我自己写的），此解法（参考别人的）的代码更加精简。核心思想都是利用栈解决问题，遇到字符数字，则入栈，遇到运算符则将栈顶两元素退出来进行运算。那么如何判断是否是字符数字呢？这里用到了int()函数和try-except语句。如果是字符数字，用int()可以将其转换为数字，如果是运算符，使用int()则会报错，从而进入excep语句中。另外值得注意的是python的 b / a 会向下取整， 比如 -1 / 132 = -1。 题目要求是取整数部分，那么负数的时候，实际应该是向上取整， 解决方法： int(b / float(a))。python3 b / a 会转为小数计算，所以直接 int(b / a)， 不能 b // a。

class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""def calculate(num1, num2, op):if op == '+':return num1 + num2elif op == '-':return num2 - num1elif op == '*':return num1 * num2else:return int(num2 / float(num1))stack = []for token in tokens:try:stack.append(int(token))except:num1 = stack.pop()num2 = stack.pop()stack.append(calculate(num1, num2, token))return stack[0]

解法二：直接去判断i是何种运算符，反正就四种，其余情况都是数字呗。

class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""stack = []ans = 0for i in tokens:if i == '+':ans = int(stack[-2]) + int(stack[-1])stack.pop()stack.pop()stack.append(ans)elif i == '-':ans = int(stack[-2]) - int(stack[-1])stack.pop()stack.pop()stack.append(ans)elif i == '*':ans = int(stack[-2]) * int(stack[-1])stack.pop()stack.pop()stack.append(ans)elif i == '/':ans = int(stack[-2]) / float(stack[-1])stack.pop()stack.pop()stack.append(ans)else:stack.append(i)return int(stack[0])

347. 前 K 个高频元素

解法一：用字典做哈希表，统计各个元素出现的频率，并根据出现的频率由高到低将字典排序。接着创建一个数组，将排好序的元素添加进数组，然后利用切片取出前k个元素。

如何让字典按值排序呢？这里回顾sorted函数的用法。（参考）

1. sorted高阶函数语法格式： sorted(可迭代对象,key=函数名,reverse=False/True)

 作用：从可迭代对象中，依次取出一个元素，该元素再按照key规定的排列依据排序。可迭代对象：即可依次取值的对象，例如：集合，序列（列表，字符串，元组），字典等。key : 是列表排列的依据，一般可以自定义一个函数返回排序的依据，再把函数名绑定给key。reverse : 译为反转，reverse默认等于False，从小到大排序。等于True时，从大到小排序。

2. 匿名函数lambda的格式： 函数名 = lambda [形参1,形参2,…] : ，返回操作语句块产生的结果并绑定给函数名。

例如： key=lambda x : x[1]       x：相当于字典集合中的一个元组， 例：dict_items([(3, 1), (1, 3), (2, 2)])中的(3, 1), (1, 3), (2, 2)x[1]: 返回x中的第二个元素，即键值对元组中的值。dict_items([(3, 1), (1, 3), (2, 2)])中的1或2或3

注意：

（1） sorted函数中的可迭代对象不要用字典dic，那样只能迭代出的字典dic的键。要用dic.items()才可迭代出字典的键值对。

例：不能用 dic_order=sorted(dic,key=lambda x:x[1],reverse=False)要用 dic_order=sorted(dic.items(),key=lambda x:x[1],reverse=False)

（2） sorted函数排好序后，要绑定一个对象(赋值)，例：dic_order=sorted(dic.items(),key=lambda x:x[1],reverse=False).

 因为字典是无序类型，用sorted函数排好序后不绑定dic_order，字典会自动打乱顺序。

dic={3:1,1:3,2:2}    # 首先建一个字典dic#dic.items()返回的是： dict_items([(3, 1), (1, 3), (2, 2)])dic_order=sorted(dic.items(),key=lambda x:x[1],reverse=True)  # 按字典集合中，每一个元组的第二个元素排列。x相当于字典集合中遍历出来的一个元组。print(dic_order)     # 得到:  [(1, 3), (2, 2), (3, 1)]

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""record = {}for i in nums:if record.get(i):record[i] += 1else:record[i] = 1record1 = sorted(record.items(), key=lambda x: x[1], reverse=True)print(record1)ans = []for item in record1:ans.append(item[0])return ans[:k]

解法二：堆队列算法-heapq模块以及其定义的函数。代码随想录中卡哥的讲解。

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""import heapq# 统计每个元素出现的频率mapping = {}for i in nums:mapping[i] = mapping.get(i, 0) + 1# 定义一个小根堆对频率进行排序priority_que = []for key, freq in mapping.items():heapq.heappush(priority_que, (freq, key))if len(priority_que) > k: # 如果堆的大小大于k 则弹出 保证堆的大小为kheapq.heappop(priority_que)# 找出前k个高频元素 因为小根堆弹出最小的 所以倒序输出到数组res = [0] * kfor i in range(k-1, -1, -1):res[i] = heapq.heappop(priority_que)[1]return res