算法面试冲刺|Leetcode 算法面试冲刺热题 HOT 100 刷题（337 338 347 394 399）（六十八）面试|leetcode|算法

文章目录

337. 打家劫舍 III
338. 比特位计数
347. 前 K 个高频元素
394. 字符串解码
399. 除法求值

337. 打家劫舍 III

算法面试冲刺|Leetcode 算法面试冲刺热题 HOT 100 刷题（337 338 347 394 399）（六十八）

文章图片

文章图片

直接上答案：

文章图片

看了b站一个小姐姐的讲解，写出来的：
https://www.bilibili.com/video/BV1XL411w7oM/?spm_id_from=333.788

# Definition for a binary tree node. # class TreeNode: #def __init__(self, val=0, left=None, right=None): #self.val = val #self.left = left #self.right = right# [0, 0] # [0]代表不偷，[1]代表偷 # root 不偷，那么就取left的[0][1]中的最大值 + right[0][1]中的最大值 # root 偷，root.val + left[0] + right[0] class Solution: def rob(self, root: Optional[TreeNode]) -> int: def helper(root): if not root: return [0, 0] l = helper(root.left) r = helper(root.right) no_rob = max(l) + max(r) rob = root.val + l[0] + r[0] return [no_rob, rob] return max(helper(root))

338. 比特位计数

文章图片

看了如何计算二进制的1，就是和自己的i-1的数字去&，一直&到i=0.

class Solution: def countBits(self, n: int) -> List[int]: ans = [0] for i in range(1, n + 1): count = 0 while i != 0: i &= i - 1 count += 1 ans.append(count) return ans

347. 前 K 个高频元素

文章图片

看了答案知道是小顶堆，然后自己写出来的：

import heapq class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: dic = {} for num in nums: if num in dic: dic[num] += 1 else: dic[num] = 1heap = [] for num, cnt in dic.items(): if len(heap) < k: heapq.heappush(heap, [cnt, num]) else: tmp = heapq.heappop(heap) if cnt > tmp[0]: heapq.heappush(heap, [cnt, num]) else: heapq.heappush(heap, tmp)return [i[1] for i in heap]

394. 字符串解码

文章图片

文章图片

想了用栈的方法，但是觉得过程有点复杂，看了K神答案：

文章图片

文章图片

K神代码

class Solution: def decodeString(self, s: str) -> str: stack, res, multi = [], "", 0 for c in s: if c == '[': stack.append([multi, res]) res, multi = "", 0 elif c == ']': cur_multi, last_res = stack.pop() res = last_res + cur_multi * res elif '0' <= c <= '9': multi = multi * 10 + int(c) else: res += c return res

按照K神思路，写的，基本一样，命名比我的好：

class Solution: def decodeString(self, s: str) -> str: stack, res, multi = [], "", 0 for c in s: if c == "[": stack.append([multi, res]) res, multi = "", 0 elif c == "]": tmp_multi, tmp_r = stack.pop() res = tmp_r + tmp_multi * reselif '0' <= c <= '9': multi = multi * 10 + int(c) else: res += c return res

399. 除法求值 【算法面试冲刺|Leetcode 算法面试冲刺热题 HOT 100 刷题（337 338 347 394 399）（六十八）】