Leetcode Problems

May 23, 2024 1 min read

Leetcode 42. Trapping Rain Water

链接：https://leetcode-cn.com/problems/trapping-rain-water

思路

每个地方能接的水量等于左右两边的最大高度中的最小值，减去当前高度。因此，可以用双指针法来解决这个问题。

用两个指针left和right分别指向数组的两端，用maxleft和maxright分别记录左右两端的最大值。
每次比较maxleft和maxright的大小，如果maxleft小于maxright，则计算left位置的水量，否则计算right位置的水量。
每次计算完水量后，移动left或right指针。
直到left和right指针相遇。
时间复杂度为$O(n)$。
空间复杂度为$O(1)$。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        n = len(height)
        left, right = 0, n - 1
        maxleft, maxright = height[0], height[n - 1]
        ans = 0
        while left <= right:
            maxleft = max(height[left], maxleft)
            maxright = max(height[right], maxright)
            if maxleft < maxright:
                ans += maxleft - height[left]
                left += 1
            else:
                ans += maxright - height[right]
                right -= 1
        return ans

Leetcode 151. Reverse Words in a String

链接：https://leetcode-cn.com/problems/reverse-words-in-a-string

思路

先将字符串去除首尾空格，然后将字符串按空格分割。
将分割后的字符串逆序拼接。
时间复杂度为$O(n)$。
空间复杂度为$O(n)$。
注意：Python中字符串是不可变对象，因此不能直接修改字符串，需要先转换为列表。

代码

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.strip().split()))

Leetcode Problems

Leetcode 42. Trapping Rain Water

思路

代码

Leetcode 151. Reverse Words in a String

思路

代码

YuLiang Sun

Fourth-year BEng student in Computer Science