Hot 100 题解🔥

前言

最近打算开个新坑，也就是这个Hot 100。

做完这份题解后，我会对我做过的所有题里有意思的，值得一说的再写一份题解。

这份题解并不按照顺序进行，而是根据🏷️进行排序。不定期更新，平均一天1~2T，有空的话会加更。

一、数组

1.1 两数之和

题干：

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

示例：

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

思路：

介个题本身考察的是对数组的理解和对数据结构的应用，我们可以想到一种最简单的方式：暴力。

借助暴力搜索+集合去重的方式，很快就能得到需要的答案。但这样的时间复杂度为O(n2)O(n^2)，远远超出预期。

亦或是思路二：先排好序，接着通过二分的方式找到另一个。这种方式有个好处，那就是不需要数组去重，遇到重复的跳过就行了。时间复杂度为O(logn)+O(logn)O(logn)+O(logn)排序+二分。

但是还是不够快，思路三可以通过hash表的方式进行，为什么能想到hash表呢？首先，这个数组本身是无序的，排序需要花费一定的时间复杂度。而对于某一个数i来说，他的配对为target-i，我们关注的，如何在后一次遇到target-i时及时找到我们的i？hash表可以很快的实现这一点。而且不需要担心重复问题。

实现：

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}
        res=[]
        for i,num in enumerate(nums):
            if (j:=target-num) in hashmap.keys():
                return [hashmap[j],i]
            hashmap[num]=i
        return []

二、链表

2.1 Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

image-20220905223717946

思路

链表的逆序相加，需要同时遍历两个链表，而且重点是进位。

我们可以用一个哨兵carryBit存放。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 关键词 逆序 相加
        cur,carryBit=ListNode(0),0
        dummy=cur
        while l1 or l2:
            carryBit=(val:=(l1.val if l1 else 0)+(l2.val if l2 else 0)+carryBit)//10
            cur.next=ListNode(val%10)
            cur=cur.next
            if l1: l1=l1.next
            if l2: l2=l2.next
        if carryBit:cur.next=ListNode(1)
        return dummy.next

总体来说，这题考察的就是对链表的理解和对进位的理解，并没有什么难度。