力扣面试经典150 —— 16-20题

• 力扣面试经典150题
• 在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题，安装 Debug LeetCode 插件可以免费 debug
• 本文使用 python 语言解题，文中 “数组” 通常指 python 列表；文中 “指针” 通常指 python 列表索引

16. [困难] 接雨水

• 题目链接
• 标签：栈、数组、双指针、动态规划、单调栈
  

16.1 解法1：按行计算

• 按列计算水量时，必须要考虑墙壁相对高度，这带来了一些困难。更简单的做法是分层计算水量，这样就不需要考虑墙壁的绝对高度，只要考虑当前位置是否有墙壁就行了。
• 具体而言，对每一行水从左到右遍历，从找到第一个墙壁开始计数水量，到找到下一个墙壁时把水量累积起来

  class Solution:
      def trap(self, height: List[int]) -> int:
          water_sum = 0
          for h in range(max(height)):        # 按行考察
              water_cnt = 0
              get_left = False
              for i in range(len(height)):    # 考察行内墙壁的情况
                  if height[i] > h:           
                      # 当前位置被墙壁阻挡
                      if not get_left:
                          # 找到左侧墙壁，从此开始要计算水量        
                          get_left = True     
                      elif water_cnt > 0:
                          # 找到墙壁时已经有水，意味着找到右墙壁，累积水量
                          water_sum += water_cnt
                          water_cnt = 0
                  else:
                      # 当前位置无墙壁，若已经找到左墙则加一格水
                      if get_left:
                          water_cnt += 1
          return water_sum
  

• 时间复杂度 $O(m\ast n)$，其中 $m$ 是最高墙壁高度；空间复杂度 $O(1)$。这个解法现在会超时了

16.2 解法2：按列计算（动态规划）

• 如果最高墙壁高度很高，计算复杂度会到达 $O(n^2)$ 导致超时。更好的方式是通过按列计算水量，将时间负责度降低到 $O(n)$。考察每一列水量的计算方法，其实只需要该列墙壁高度、该列左侧最高墙高度和该列右侧最高墙高度三个值即可
  
  如上图所示，正在求的列水量为 $\max (0,\min (\text{leftMax},\text{rightMax})-\text{height})$

• 基于以上想法，我们可以先统计每一个位置左右最高墙壁高度，再利用上式来计算水量。注意到计算当前位置左右最高墙壁高度是一个动态规划问题，因为其满足动态规划三要素

  1. 无后效性：当前找到的墙壁不影响之前找到的墙壁
  2. 最优子结构：我们最后要构造长 $n$ 的最高墙壁高度列表，其中任意一段都是最高的，即问题最优解的结构包含其子问题的最优解。
  3. 重叠子问题：找第 $i$ 个位置左侧的最高墙高度 = 找第 $i-1$ 位置左侧最高墙高度，并取其和第 $i$ 个位置墙壁高度的最大值。其中出现了自顶向下递归过程中要重复求解的重叠子问题，这提示我们使用递推式自底向上的构造解（动态规划的自底向上形式），或使用带备忘录的递归法（动态规划的自顶向下形式）

  我们通过以下动态规划递推式来高效计算每一个位置左右最高墙壁的高度
  $$\begin{array}{rlrl}& \text{leftMax}[i]=\max (\text{leftMax}[i-1],\text{height}[i])& & 1\le i\le n-1\\ & \mathrm{rightMax}[i]=\max (\mathrm{rightMax}[i+1],\text{height}[i])& & 0\le i\le n-2\end{array}$$

• 下面给出代码

  def trap(self, height: List[int]) -> int:
  	# 通过动态规划递推式找出每个位置左右最高墙壁高度
  	n = len(height)
  	max_left = [0] * n
  	max_right = [0] * n
  	for i in range(1, n-1):
  	    max_left[i] = max(max_left[i-1], height[i-1])
  	for i in range(n-2, 0, -1):
  	    max_right[i] = max(max_right[i+1], height[i+1])
  	
  	# 基于每个位置左右最高墙壁高度中较低的那个，计算每一列的水量
  	water_sum = 0
  	for i in range(1, n-1):
  	    min_max_height = min(max_left[i], max_right[i])
  	    if min_max_height > height[i]:
  	        water_sum += min_max_height - height[i]
  	
  	return water_sum
  

• 时间复杂度 $O(n)$，空间复杂度 $O(n)$

16.3 解法3：双指针

• 动态规划通常可以用双指针方法优化空间复杂度。本题中注意到 max_left[i] 和 max_right[i] 都只用过一次，可以用 left, right 两个指针分别向中间移动，实时维护至此为止左右见过的最高墙壁高度 max_left, max_right 并计算列水量

  def trap(self, height: List[int]) -> int:
      # 核心在于找出每个位置左右最高墙壁高度中较低的那个
      left, right = 0, len(height) - 1
      max_left = max_right = 0
      water_sum = 0
      while left < right:
          # 用left，right两个指针分别向中间移动，实时维护至此为止左右见过的最高墙壁高度max_left, max_right
          max_left = max(max_left, height[left])
          max_right = max(max_right, height[right])
          
          # 直接根据左右最大高度判断
          if max_left < max_right:
              # 右边存在最高柱子 max_right 可以挡水，第 left 列存水量由 max_left 决定
              water_sum += max_left - height[left]
              left += 1
          else:
              # 左边存在最高柱子 max_left 可以挡水，第 right 列存水量由 max_right 决定
              water_sum += max_right - height[right]
              right -= 1
  
      return water_sum
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

16.4 解法4：栈

• 另一种解此题的思路是：计算水量 -> 找每一行水的左右墙壁 -> 括号匹配，这样就可以用栈解决了
  
• 具体而言，我们使用基于栈符号匹配的思想找出每一对墙壁，同时计算水量
  1. 栈元素：位置索引
  2. 入栈时机：当前高度小于栈顶位置高度，说明找到了积水位置，入栈成为栈顶
  3. 出栈时机：当前高度大于栈顶位置高度，说明找到了栈顶位置的那行水的右侧墙，不断出栈计算水量，直到当前高度不大于栈顶或栈空，再把当前位置入栈
  4. 栈底元素：还没有计算水量的部分的左侧最高墙壁位置
• 下面给出代码

  def trap(self, height: List[int]) -> int:
  	water_sum = 0
  	stack = []  # 用列表充当栈，stack[0] 是栈底, stack[-1] 是栈顶
  	
  	for i, h in enumerate(height):
  	    # 栈非空，且当前位置高度 > 栈顶位置高度，一直出栈计算水量
  	    while len(stack) != 0 and h > height[stack[-1]]:
  	        # 弹出栈顶，计算此位置水所在的整行水量
  	        top = stack.pop()   
  	        if len(stack) == 0: # 弹出之后栈空了，说明弹出的是最左侧的墙，不计算水量直接跳出
  	            break
  	        
  	        # 目标行水左边最高墙位置和高度
  	        left = stack[-1]
  	        max_left = height[left]
  	
  	        # 目标行水宽度
  	        water_width = i - left - 1
  	
  	        # 计算目标行水量，求和
  	        water_height = min(max_left, height[i]) - height[top]
  	        water_sum += water_width * water_height
  	    
  	    stack.append(i)
  	return water_sum
  

• 时间复杂度 $O(n)$，空间复杂度 $O(n)$

17. [简单] 罗马数字转整数

• 题目链接
• 标签：哈希表、数学、字符串
  

17.1 解法1：模拟所有组合情况

• 注意到罗马数字规则是左结合的，一种简单的想法是列出题目范围内所有可能的罗马数字组合情况，然后从左到右遍历，识别各个罗马数字相加

  def romanToInt(self, s: str) -> int:
  	char2value = {
  	     'I': 1,
  	     'V': 5,
  	     'X': 10,
  	     'L': 50,
  	     'C': 100,
  	     'D': 500,
  	     'M': 1000,
  	     'IV': 4,
  	     'IX': 9,
  	     'XL': 40,
  	     'XC': 90,
  	     'CD': 400,
  	     'CM': 900
  	 }
  	
  	 i, value = 0, 0
  	 while True:
  	     if s[i:i+2] in char2value:
  	         value += char2value[s[i:i+2]]
  	         i += 2
  	     else:
  	         value += char2value[s[i:i+1]]
  	         i += 1
  	
  	     if i >= len(s):
  	         break
  	 
  	 return value
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

17.2 解法2：根据规则模拟

• 仔细分析罗马数字的构造规则，注意到
  1. 通常情况下小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可
  2. 若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反
• 给出代码如下

  def romanToInt(self, s: str) -> int:
  	char2value = {
  	    'I': 1,
  	    'V': 5,
  	    'X': 10,
  	    'L': 50,
  	    'C': 100,
  	    'D': 500,
  	    'M': 1000,
  	}
  	
  	l = len(s)
  	value = 0
  	for i in range(l):
  	    if i < l - 1 and char2value[s[i]] < char2value[s[i+1]]:
  	        value -= char2value[s[i]]
  	    else:
  	        value += char2value[s[i]]
  	
  	return value
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

18. [中等] 整数转罗马数字

• 题目链接
• 标签：哈希表、数学、字符串
  

18.1 解法1：枚举

• 分析罗马数字的构造规则，发现其在个十百千位的构成规则是一样的，取值可以分成五种情况
  1. 取值 “1，2，3”：直接重复对应次取值 “1” 的符号（I/X/C）
  2. 取值 “4”：由取值 “5” 的符号加-1前缀构成（IV/XL/CD）
  3. 取值 “5”：有特殊符号（V/L/D）
  4. 取值 “6，7，8”：由取值 “5” 的符号加重复对应次取值 “1” 的符号构成
  5. 取值 “9”：由更高一位取值 “1” 的符号和-1前缀构成（IX/XC/CM）
• 可以先拆分个十百千位取值，然后通过以上枚举关系转换

  def intToRoman(self, num: int) -> str:
  	s = ''
  	
  	# 千位
  	thousands = num // 1000
  	s += 'M' * thousands
  	
  	# 百位
  	num -= thousands * 1000
  	hundreds = num // 100
  	if hundreds == 9:
  	    s += 'CM'
  	elif hundreds > 5:
  	    s += 'D' + 'C' * (hundreds-5)
  	elif hundreds == 5:
  	    s += 'D'
  	elif hundreds == 4:
  	    s += 'CD'
  	else:
  	    s += 'C' * hundreds
  	
  	# 十位
  	num -= hundreds * 100
  	tens = num // 10
  	if tens == 9:
  	    s += 'XC'
  	elif tens > 5:
  	    s += 'L' + 'X' * (tens-5)
  	elif tens == 5:
  	    s += 'L'
  	elif tens == 4:
  	    s += 'XL'
  	else:
  	    s += 'X' * tens
  	
  	# 个位
  	num -= tens * 10
  	ones = num
  	if ones == 9:
  	    s += 'IX'
  	elif ones > 5:
  	    s += 'V' + 'I' * (ones-5)
  	elif ones == 5:
  	    s += 'V'
  	elif ones == 4:
  	    s += 'IV'
  	else:
  	    s += 'I' * ones
  	
  	return s
  

• 时间复杂度 $O(1)$，空间复杂度 $O(1)$

18.2 解法2：硬编码

• 以上枚举过程写起来比较麻烦，可以将其全部整理成如下硬编码表，然后直接根据各位数据取值组合出结果
  
• 代码如下

  class Solution:
  
      THOUSANDS = ["", "M", "MM", "MMM"]
      HUNDREDS = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
      TENS = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
      ONES = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
  
      def intToRoman(self, num: int) -> str:
          return Solution.THOUSANDS[num // 1000] + \
              Solution.HUNDREDS[num % 1000 // 100] + \
              Solution.TENS[num % 100 // 10] + \
              Solution.ONES[num % 10]
  

• 时间复杂度 $O(1)$，空间复杂度 $O(1)$

19. [简单] 最后一个单词的长度

• 题目链接
• 标签：字符串
  

19.1 解法1：反向遍历

• 虽然这个可以直接用python字符串的 split 语法切分，然后反向遍历找到最后一个单词，但作为算法题还是不用这些语法了。首先我们去除字符串最右边的空格，然后反向遍历计数至第一个空格即可

  def lengthOfLastWord(self, s: str) -> int:
      # 去掉最右边的空格
      right = len(s) - 1
      while s[right] == ' ':
          right -= 1
      s = s[:right+1]
      
      # 从后往前遍历直到出现空格或遍历完成，同时计数
      l = 0
      for i in range(len(s)-1,-1,-1):
          if s[i] != ' ':
              l += 1
          else:
              break
      
      return l    
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

20. [简单] 最长公共前缀

• 题目链接
• 标签：字典树、字符串
  

20.1 解法1：纵向扫描

• 遍历第一个字符串，同时检查其他每一个字符串前缀是否和第一个的相同，遇到不同时即返回
  
• 代码如下

  def longestCommonPrefix(self, strs: List[str]) -> str:
  	prefix = ''
  	for i in range(len(strs[0])):
  	    char = strs[0][i]
  	    for str in strs[1:]:
  	        if i >= len(str) or str[i] != char:
  	            return prefix
  	    prefix += char
  	    i += 1
  	return prefix
  

• 时间复杂度 $O(mn)$，其中 $m$ 是字符串数组中的字符串的平均长度，$n$ 是字符串的数量；空间复杂度 $O(1)$