[数据结构与算法]LeetCode 热题 HOT 100笔记（简单篇）

🔥 LeetCode 热题 HOT 100

简单篇

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那两个整数，
并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()		# 哈希表解法 python
        for i, num in enumerate(nums):
            if target-num in hashtable:
                return [hashtable[target-num], i]
            else:
                hashtable[nums[i]] = i
        return []

解题思路：创建一个哈希表，对于每一个 num，我们首先查询哈希表中是否存在 target - num，
然后将 num 插入到哈希表中，即可保证不会让 x 和自己匹配。
扩展：dict() 字典相当于 Java常用的哈希表Hashtable
Dict是一个键值对元素的集：
1.键必须是唯一的，值可以是任意的；
2.键必须是不可变对象，比如数字、字符串或元组(纯元组，没有嵌套可变对象)；
3.Dict内部元素的存放顺序与元素的添加顺序无关。

dict()详情可见：Python之dict操作

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
输入：s = "()"
输出：true

class Solution: 
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:   # Python 栈方法
            return False
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        '''
        创建栈stack，对于字符串s的每个字符，是)]} 在Hashtable中的，
若栈为空（没匹配）或栈顶元素不匹配（定义在了Hashtable中了），就返回false，否则就出栈表示匹配。
        对于字符串s的每个字符，若不是)]}，即为([{，那么就进栈，等待匹配。
        '''
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1]!=pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)
        return not stack

解题思路：当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。
此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。
如果不是相同的类型，或者栈中并没有左括号，那么字符串s无效，返回 False。
为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
1. 遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，
返回True，否则返回False。
2. 意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，
我们可以直接返回False，省去后续的遍历判断过程。

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

# 递归
1. 如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
2. 判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。
如果两个链表有一个为空，递归结束。

53. 最大子数组和

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

动态规划解法。先设置maxAns=num[0]为初始最大值打擂台选出最大。
加强for循环内，pre表示前序最大的连续子数组和，因此只需比较 pre+x 和 x 即可。

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

class Solution {
    public int climbStairs(int n) {
        int p=0,q=0,r=1;
        for(int i=0;i<n;i++){
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
}

动态规划。f(x)=f(x-1)+f(x-2). 
f(1)=1，f(2)=2，f(3)=3，f(4)=5……

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。
    1
     \
      2
     / 
    3

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

递归。定义 inorder(root) 表示当前遍历到 root 节点的答案，
那么按照定义，我们只要递归调用 inorder(root.left) 来遍历root 节点的左子树，
然后将 root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，
递归终止的条件为碰到空节点。

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    '''
    1. p q都为空，则对称
    2. p q有一为空，则不对称
    3. 检查节点值相等 && 递归检查 p q 的左右子树
    '''
    public boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        return p.val==q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
给定二叉树 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        // 为空则深度为0
        // 递归，每递归一次+1，即为深度
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

# 此方法会超时   
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                ans = max(ans, prices[j] - prices[i])
        return ans

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        inf = int(1e9)
        minprice = inf
        maxprofit = 0
        # 技巧：设置比较，max就设置为0，min就设置为最大1e9
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            minprice = min(price, minprice)
        return maxprofit

暴力法：即找出最大差值。设置两个循环，后循环和前面的数字对着减，比较即可。
一次遍历法：找出最低价格，for循环轮着减而比较。
技巧：设置比较，max就设置为0，min就设置为最大1e9

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
找出那个只出现了一次的元素。
输入: [2,2,1]
输出: 1

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;  // 异或运算
        }
        // single = nums[0]⊕nums[1]⊕……⊕nums[n]   原理见下解析（其他元素出现两次）
        return single;
    }
}

位运算。异或运算。
异或运算有以下三个性质。
1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
2. 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
3. 异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
假设数组中有2m+1 个数，其中有 m 个数各出现两次，一个数出现一次。
令a1、a2、……、am为出现两次的 m 个数，am+1?为出现一次的数。
根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：
(a1⊕a1)⊕(a2⊕a2)⊕……(am⊕am)⊕am+1 = 性质1,2= am+1
因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        seen = set()	# set() 创建集合，集合不允许重复元素，没有顺序不能用索引。
        while head:
            if head in seen:	# 头节点在集合中，说明出现了环。
                return True
            else:	# 头节点没在集合中，就加入集合
	            seen.add(head)
	            head=head.next
        return False

哈希表。用哈希表来存储所有已经访问过的节点。
1. 每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，
2. 否则就将该节点加入哈希表中。
3. 重复这一过程，直到我们遍历完整个链表即可。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        
        slow = head			# 预定义快慢指针
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next			# 定义慢指针，快指针速度快一步。
            fast = fast.next.next		# 龟兔赛跑，迟早会相遇
        return True

快慢指针。定义慢指针，快指针速度快一步。龟兔赛跑，若是有环则迟早会相遇

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

class MinStack:
    def __init__(self):
        self.stack = []			# 定义辅助栈 min_stack 同步stack栈的操作。
        self.min_stack = [math.inf]   # 老规矩，设置最小就预赋值为最大

    def push(self, x: int) -> None:
        self.stack.append(x)
        self.min_stack.append(min(x, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

示例图像，请点击

辅助栈。
使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
1. 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，
将这个最小值插入辅助栈中；
2. 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
3. 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>(); // 创建哈希集合
        ListNode temp = headA;
        while (temp != null) {	// headA 全部放入哈希集合中
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;	// 若temp在哈希集合中，则表示相交点出现。
            }
            temp = temp.next;
        }
        return null;
    }
}

哈希集合。
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链 headA，并将链表 headA  中的每个节点加入哈希集合中。
然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
1. 如果当前节点不在哈希集合中，则继续遍历下一个节点；
2. 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，
因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。
3. 如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
输入：[3,2,3]
输出：3

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()		# 排序，由于多数元素出现一半次数以上，故中间元素必为多数元素。
        return(nums[len(nums)//2])

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next); // 循环递归这一步至链表翻转
        head.next.next = head;  // next指针改为指向前一个节点
        head.next = null;		// 将原头节点的next指针指为空
        return newHead;
    }
}

n1 → n2 → …… → nm → ?   翻转为 ? → nm →……→ n2 → n1
nk+1 的下一节点指向 nk
所以 nk.next.next = nk
需要注意的是 n1 的下一个节点必须指向 ? 。如果忽略了这一点，链表中可能会产生环。

226. 翻转二叉树

翻转一棵二叉树。
     4			         4
   /   \			   /   \
  2     7 	          7     2
 / \   / \		     / \   / \
1   3 6   9			9   6 3   1

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        left = self.invertTree(root.right)	# 递归右儿子节点为左节点
        right = self.invertTree(root.left)	# 递归左儿子节点为右节点
        root.left, root.right = left, right	
        # 简化为一步
        # root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

递归。从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。
如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，
即可完成以  root 为根节点的整棵子树的翻转。

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
如果是，返回 true ；否则，返回 false 。
输入：head = [1,2,2,1]
输出：true

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        val = []
        current_node = head
        while current_node is not None:
            val.append(current_node.val)
            current_node = current_node.next
        return val == val[::-1]

将值复制到数组中后用双指针法。
1. 遍历，复制链表值到数组列表中。
2. 判断数组val[] 是否相等于 val[::-1].
3.  val[::-1] 为数组翻转。

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left=right=0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

双指针。使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
注意到以下性质：
1. 左指针左边均为非零数；
2. 右指针左边直到左指针处均为零。
因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，
返回一个长度为 n + 1 的数组 ans 作为答案。
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

class Solution:
    def countBits(self, n: int) -> List[int]:
    # 动态规划——最低设置位
        bits = [0]
        for i in range(1, n+1):
            bits.append(bits[i & (i - 1)] + 1)
        return bits

448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            x = (num - 1)%n
            nums[x] += n
        ret = [i+1 for i, num in enumerate(nums) if num <= n]
        return ret
        # 13, 19, 18, 15, 8, 2, 11, 9

原地修改。 由于整数有n个，数组里数值也为[1, n]，那么令 nums[x] += n，则数组小于n的索引就没出现过。
动手模拟试试

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
          ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

内置位计数功能。汉明距离即为 异或运算 的二进制表达中 1 的数量。
 JAVA中 Integer.bitCount(x ^ y) 计算二进制表达中 1 的数量的函数

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
这条路径可能穿过也可能不穿过根结点。
示例：    1
         / \
        2   3
       / \     
      4   5   
 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 1		# 求最大则预设置个最小
        def depth(node):
            if not node:
                return 0
            L = depth(node.left)	# 递归左子树
            R = depth(node.right)	# 递归右子树
            self.ans = max(self.ans, L + R + 1)		# L+R+1为路径经过节点数
            return max(L, R) + 1	# 递归求二叉树最大深度
        depth(root)		# 函数调用
        return self.ans - 1		# 直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一

深度优先搜索。直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。

617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，
那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        if not root2:
            return root1
        
        merged = TreeNode(root1.val + root2.val)
        merged.left = self.mergeTrees(root1.left, root2.left)
        merged.right = self.mergeTrees(root1.right, root2.right)
        
        return merged

深度优先搜索。
从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
1. 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
2. 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
3. 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，
此时需要显性合并两个节点。
对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。