PeterQwQ
0%

发表于

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

将其中一个链表遍历过的部分存起来，然后遍历另一个链表，如果遇到了存起来的节点，那么就是相交的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        seen = set()
        while headA is not None:
            seen.add(headA)
            headA = headA.next
            
        while headB is not None:
            if headB in seen:
                return headB
            headB = headB.next
        return None

发表于

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

有递归和迭代两种解法，这里给出迭代解法。CS61A 中也有类似的题目，可以参考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        ans = 0
        while head:
            if ans == 0:
                ans = ListNode(head.val)
            else:
                ans = ListNode(head.val, ans)
            head = head.next
        return ans

发表于 更新于

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

对于这样性质的矩阵，我们从右上角开始搜索，如果当前元素比目标值大，那么向左移动一列，如果当前元素比目标值小，那么向下移动一行。这样可以保证每次移动都能够排除一行或者一列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        if target < matrix[0][0]:
            return False
        if target > matrix[m-1][n-1]:
            return False
        
        i, j = 0, n-1
        while i < m and j >= 0:
            right_top = matrix[i][j]
            if target == right_top:
                return True
            if target < right_top:
                j -= 1
            else:
                i += 1
        return False

发表于

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像 顺时针 旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

仔细想了一下，沿着对角线翻转，然后对于每一行，再反转一下就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n):
            for j in range(i+1, n):
                    matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
                    
        for i in range(n):
            for j in range(n//2):
                 matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]

发表于

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

还是直接模拟，写就完事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        first, second, third, forth = 0, n-1, m-1, 0
        flag_matrix = [[False for i in range(n)] for j in range(m)]
        
        area, count, switch = m*n, 0, 0
        ans = []

        while count != area:
            if switch == 0:
                for j in range(n):
                    if flag_matrix[first][j] == False:
                        ans.append(matrix[first][j])
                        flag_matrix[first][j] = True
                        count += 1
                    else:
                        continue
                
                first += 1
                switch = (switch+1)%4
                continue
            
            if switch == 1:
                for i in range(m):
                    if flag_matrix[i][second] == False:
                        ans.append(matrix[i][second])
                        flag_matrix[i][second] = True
                        count += 1
                    else:
                        continue
                
                second -= 1
                switch = (switch+1)%4
                continue

            if switch == 2:
                for j in range(n-1, -1, -1):
                    if flag_matrix[third][j] == False:
                        ans.append(matrix[third][j])
                        flag_matrix[third][j] = True
                        count += 1
                    else:
                        continue

                third -= 1
                switch = (switch+1)%4
                continue

            if switch == 3:
                for i in range(m-1, -1, -1):
                    if flag_matrix[i][forth] == False:
                        ans.append(matrix[i][forth])
                        flag_matrix[i][forth] = True
                        count += 1
                    else:
                        continue

                forth += 1
                switch = (switch+1)%4
                continue
                
        return ans

发表于

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

直接模拟，写完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        zero_row = []
        zero_col = []
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zero_row.append(i)
                    zero_col.append(j)
        
        for i in range(m):
            for j in range(n):
                if i in zero_row or j in zero_col:
                    matrix[i][j] = 0

发表于

给你一个整数数组 nums ，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用 除法，且在 O(n) 时间复杂度内完成此题。

用双指针的思路可以很快的写完这个问题，用两个指针分别从左右两边开始遍历，每次遍历都更新当前数字左边的乘积和右边的乘积，最后返回结果即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums)-1
        answer = [1] * len(nums)
        left_product, right_product = 1, 1
        while right >= 0 and left < len(nums):
            answer[left] *= left_product
            answer[right] *= right_product
            left_product *= nums[left]
            right_product *= nums[right]
            left += 1
            right -= 1
        return answer

发表于

给定一个整数数组 nums ，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

一开始没有考虑到 k 可能比整个数组长度长的情况，后来改了一下就过了：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k%n
        tmp = nums[n-k:n]
        for i in range(n-k-1, -1, -1):
            nums[i+k] = nums[i]
        for j in range(len(tmp)):
            nums[j] = tmp[j]

发表于

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

感觉看起来是个板子题。先用暴力写了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        if n == 1:
            return [intervals[0]]
        intervals.sort(key=lambda x: x[0])
        ans = []
        merged_list = []
        i = 0
        while i < n:
            merged_list = intervals[i]
            for j in range(i+1, n+1):
                if j == n:
                    ans.append(merged_list)
                    return ans
                now_start, now_end = merged_list[0], merged_list[1]
                next_list = intervals[j]
                next_start, next_end = next_list[0], next_list[1]
                if now_end >= next_start and now_end <= next_end:
                    merged_list = [now_start, next_end]
                elif now_end >= next_start and now_end >= next_end:
                    merged_list = [now_start, now_end]
                else:
                    i = j-1
                    ans.append(merged_list)
                    break
            i += 1
        return ans

然后发现题解就是这样写的，我上面写了一坨 if 直接用一个 max 就完事了…
1
2
3
4
5
6
7
8
9
10
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

发表于 更新于

给你一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一段连续部分。

拿到这个一开始的思路是前缀和，只需要遍历一遍数组，算出当前的前缀和，然后找到之前的最小前缀和，然后用当前的前缀和减去最小前缀和，就是当前的最大和。

同时注意，我们这里的前缀和是从0开始的，所以我们要把前缀和的最小值设为0，这样才能保证我们的最大和是正确的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:
            return nums[0]
        ans = -inf
        prefix = [0]*(len(nums)+1)
        for i in range(len(nums)):
            if i != 0:
                prefix_now = nums[i] + prefix[i-1]
            else:
                prefix_now = nums[i]
            prefix_min = min(prefix[:i+1])
            prefix[i] = prefix_now
            ans = max(prefix_now - prefix_min, ans)
        return ans

但是这个写法TLE了，感觉是 min 和 max 遍历了整个数组导致的。所以只需要用一个变量来记录而不是数组来记录，应该就不会TLE了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:
            return nums[0]
        ans = -inf
        prefix_min = 0
        prefix = 0
        for i in range(len(nums)):
            if i != 0:
                prefix = nums[i] + prefix
            else:
                prefix = nums[i]
            ans = max(prefix - prefix_min, ans)
            prefix_min = min(prefix, prefix_min)
        return ans

看题解还可以动态规划写，具体的思路就是对于我们需要得到的最大数组和 f[i] ，无非就是两种途径：f[i] = f[i-1] + nums[i] 或者 f[i] = nums[i] 。很好理解，如果加上前一个数的和比当前数还小，那么就不如直接从当前数开始。所以我们可以写出动态规划的代码：
1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        '''
        f[i] = max(f[i-1] + nums[i], nums[i])
        '''
        f = [0]*len(nums)
        for i in range(len(nums)):
            f[i] = max(f[i-1]+nums[i], nums[i])
        return max(f)