面试经典150

数组/字符串

合并两个有序数组

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0:
            nums1[:] = nums2
            return
        if n == 0:
            return
        result = [0] * (m + n)
        l1 = l2 = 0
        i = 0
        while l1 < m and l2 < n:
            if nums1[l1] > nums2[l2]:
                result[i] = nums2[l2]
                l2 += 1
            else:
                result[i] = nums1[l1]
                l1 += 1
            i += 1
        while l1 < m:
            result[i] = nums1[l1]
            i += 1
            l1 += 1
        while l2 < n:
            result[i] = nums2[l2]
            i += 1
            l2 += 1
        nums1[:] = result

我也没有好的思路，选择空间换时间，维护了一个临时数组，三指针移动，然后把结果赋给nums1。

灵神解法

从右往左遍历，如果nums1[i] > nums2[j]，则nums1[k] = nums1[i]，i--；否则nums1[k] = nums2[j]，j--。该做法每次可以确定一个位置，时间复杂度\(O(m+n)\)，且由于从后往前，避免了覆盖的情况发生，因为每个数字必然是在他该在的位置，且腾出了新的空位。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0:
            nums1[:] = nums2
            return
        if n == 0:
            return
        r1, r2, r = m - 1, n - 1, m + n - 1
        while r1 >= 0 and r2 >= 0:
            if nums1[r1] >= nums2[r2]:
                nums1[r] = nums1[r1]
                r1 -= 1
            else:
                nums1[r] = nums2[r2]
                r2 -= 1
            r -= 1
        if r2 >= 0:
            nums1[:r2 + 1] = nums2[:r2 + 1]

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow, fast = 0, 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

快慢指针秒了

删除有序数组中的重复项

给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。

nums 的前 k 个元素应包含排序后的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                nums[slow] = nums[i]
                slow += 1
        return slow

只看每一个发生跳跃的情况就可以了。

删除有序数组中的重复项 II

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 1
        flag = False
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                flag = False
                nums[slow] = nums[i]
                slow += 1
            else:
                if not flag:
                    nums[slow] = nums[i]
                    slow += 1
                flag = True
        return slow

我的做法是对于重复的数字，移动一次慢指针，但也只移动一次，确保只记录两次。

灵神解法

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        stack_size = 2  # 栈的大小，前两个元素默认保留
        for i in range(2, len(nums)):
            if nums[i] != nums[stack_size - 2]:  # 和栈顶下方的元素比较
                nums[stack_size] = nums[i]  # 入栈
                stack_size += 1
        return min(stack_size, len(nums))

使用栈的思想，其实也就是快慢指针，只不过比较对象从相邻两个元素变成了栈顶元素前一个元素和当前元素。

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        result = nums[0]
        count = 1
        for num in nums[1:]:
            if num != result:
                count -= 1
                if count < 0:
                    result = num
                    count = 1
            else:
                count += 1

        return result

此消彼长！

最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        i = len(s) - 1
        # 单词最右
        while s[i] == ' ':
            i -= 1

        j = i
        while s[j] != ' ':
            j -= 1
            if j < 0:
                break
        return i - j

从后往前找单词最右，再从单词最右往左找单词最左，返回长度。

最长公共前缀

给定一个字符串数组 strs ，返回本身 longest common prefix字符串。

如果不存在公共前缀，返回空字符串 ""。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i, c in enumerate(strs[0]):
            for s in strs[1:]:
                if i == len(s) or s[i] != c:
                    return strs[0][:i]
        return strs[0]

直接拿其中一个作为基准逐个字符往后比较即可。

双指针

验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            if not s[i].isalnum():
                i += 1
            elif not s[j].isalnum():
                j -= 1
            elif s[i].lower() == s[j].lower():
                i += 1
                j -= 1
            else:
                return False
        return True

isalnum() 函数判断一个字符是否是字母数字字符。s[i].isalnum() 是 Python 中字符串的内置方法，核心作用是：判断字符串 s 中索引为 i 的单个字符是否为“字母或数字”（alphanumeric）。

lower() 函数将字符转为小写。

左右指针秒了。

判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        if m > n:
            return False
        i, j = 0, 0
        while i < m and j < n:
            if s[i] == t[j]:
                i += 1
                j += 1
            else:
                j += 1
        return i == m

哈希表

同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s2t = {}
        t2s = {}
        m = len(s)
        for i in range(m):
            if s[i] in s2t and s2t[s[i]] != t[i] or t[i] in t2s and t2s[t[i]] != s[i]:
                return False
            s2t[s[i]] = t[i]
            t2s[t[i]] = s[i]
        return True

创建两个字典，分别记录 s 和 t 的映射关系。之所以需要第二个从t 到 s 的映射关系，是因为不同字符不能映射到同一个字符上，因此需要判断 t 中的字符是否已经映射过。

单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。具体来说：

pattern 中的每个字母都恰好映射到 s 中的一个唯一单词。
s 中的每个唯一单词都恰好映射到 pattern 中的一个字母。
没有两个字母映射到同一个单词，也没有两个单词映射到同一个字母。

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        s1 = s.split()
        s2t = {}
        t2s = {}
        m = len(pattern)
        n = len(s1)
        if m != n:
            return False
        for i in range(m):
            if s1[i] in s2t and s2t[s1[i]] != pattern[i] or pattern[i] in t2s and t2s[pattern[i]] != s1[i]:
                return False
            s2t[s1[i]] = pattern[i]
            t2s[pattern[i]] = s1[i]
        return True

基本思路同同构字符串。

存在重复元素

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        map1 = {}
        for i, num in enumerate(nums):
            if num in map1 and i - map1[num] <= k:
                return True
            map1[num] = i
        return False

创建一个字典，记录数字出现的索引。如果当前数字在字典中，并且索引之差小于等于 k，则返回 true 。

区间

汇总区间

给定一个无重复元素的有序整数数组 nums 。

区间 [a,b] 是从 a 到 b（包含）的所有整数的集合。

返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个区间但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result = []
        start = end = 0
        n = len(nums)
        if n == 0:
            return result
        elif n == 1:
            return [str(nums[0])]
        for i in range(1, n):
            if nums[i] - nums[i-1] != 1:
                end = i - 1
                if start == end:
                    result.append(str(nums[start]))
                else:
                    result.append(str(nums[start]) + '->' + str(nums[end]))
                start = i
        end = n - 1
        if start == end:
            result.append(str(nums[start]))
        else:
            result.append(str(nums[start]) + '->' + str(nums[end]))
        return result

创建一个结果列表，并初始化两个指针 start 和 end，指向区间的开始和结束位置。按照题意模拟即可。