Leetcode

37. Sudoku Solver题目Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. Example 1: 12Input: board = [["5","3",".","."...

37. Sudoku Solver题目Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. Example 1: 12Input: board = [["5","3",".","."...

36. Valid Sudoku题目Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to t...

36. Valid Sudoku题目Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to t...

32. Longest Valid Parentheses题目Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: 123Input: s = "(()"Output: 2Explanation: The longest valid parentheses substring is "()". Example 2: 123Input: s = ")()())"Output: 4Explanation: The longest valid parentheses substring is "()()". Example 3: 12Input: s = ""Output: 0 题目大意给定一个只包含 '(...

32. Longest Valid Parentheses题目Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: 123Input: s = "(()"Output: 2Explanation: The longest valid parentheses substring is "()". Example 2: 123Input: s = ")()())"Output: 4Explanation: The longest valid parentheses substring is "()()". Example 3: 12Input: s = ""Output: 0 题目大意给定一个只包含 '(...

31. Next Permutation题目A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then ...

31. Next Permutation题目A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then ...

30. Substring with Concatenation of All Words题目You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters. You can return the answer in any order. Example 1: 1234Input: s = "barfoothefoobarman", words = ["foo","bar"]Output: [0,9]Explanation: Substrings starting at index 0 and 9 are "...

30. Substring with Concatenation of All Words一、问题描述给定一个字符串 s 和一个字符串数组 words，找出 s 中所有恰好由 words 中所有单词串联形成的子串的起始索引。 注意：words 中的单词可以以任意顺序串联。 示例 1： 12输入：s = "barfoothefoobarman", words = ["foo","bar"]输出：[0,9] 示例 2： 12输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[] 示例 3： 12输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]输出：[6,9,12] 二...

35. Search Insert Position题目Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Example 1: 12Input: nums = [1,3,5,6], target = 5Output: 2 Example 2: 12Input: nums = [1,3,5,6], target = 2Output: 1 Example 3: 12Input: nums = [1,3,5,6], target = 7Output: 4 Constraints: 1 <= nums.length <= 104 -104 <=...

35. Search Insert Position题目Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Example 1: 12Input: nums = [1,3,5,6], target = 5Output: 2 Example 2: 12Input: nums = [1,3,5,6], target = 2Output: 1 Example 3: 12Input: nums = [1,3,5,6], target = 7Output: 4 Constraints: 1 <= nums.length <= 104 -104 <=...

34. Find First and Last Position of Element in Sorted Array题目Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. Example 1: 12Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4] Example 2: 12Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1] Example 3: 12Input: nums = [], target = 0Output: [-1,-1...

34. Find First and Last Position of Element in Sorted Array题目Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. Example 1: 12Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4] Example 2: 12Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1] Example 3: 12Input: nums = [], target = 0Output: [-1,-1...

33. Search in Rotated Sorted Array题目There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation a...

33. Search in Rotated Sorted Array题目There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation a...

29. Divide Two Integers题目Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator. The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2. Return the quotient after dividing dividend by divisor. Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31...

29. Divide Two Integers你选用何种方法解题？本题的核心是不使用乘法、除法和取模运算实现整数除法。 方法 时间复杂度 空间复杂度 是否推荐 位运算（位移法） O(log n) O(1) 推荐 负数倍增法 O(log n) O(1) 推荐 方法选择理由： 位运算（位移法）：通过左移实现快速乘法，时间效率高 负数倍增法：使用负数处理避免溢出问题，更安全 解题过程问题分析输入：被除数 dividend，除数 divisor输出：两数相除的商（截断小数部分） 关键约束： 不能使用乘法、除法、取模运算 需要处理溢出情况 核心洞察 位运算替代乘法：x << k 等价于 x * 2^k 二分查找思想：找到最大的 k 使得 divisor * 2^k <= dividend 符号处理：先记录符号，将问题转化为正数或负数除法 负数处理：使用负数避免 abs(INT_MIN) 溢出 算法流程（负数倍增法）以 dividend = 15, divisor = 3 为例： 12345678910111213141516符号：正转化为负...

28. Implement strStr()你选用何种方法解题？本题的核心是实现字符串匹配算法。 方法 时间复杂度 空间复杂度 是否推荐 暴力匹配 O(n×m) O(1) 简单场景 KMP 算法 O(n + m) O(m) 推荐 方法选择理由： 暴力匹配：代码简单，适合短字符串 KMP 算法：时间效率更高，适合长字符串 解题过程问题分析输入：主串 haystack，模式串 needle输出：needle 在 haystack 中第一次出现的索引，不存在返回 -1 核心洞察 暴力匹配：逐个比较，不匹配时回溯 KMP 算法：利用部分匹配信息，避免不必要的回溯 暴力匹配算法流程以 haystack = "hello", needle = "ll" 为例： 1234i=0: h vs l -> 不匹配i=1: e vs l -> 不匹配i=2: l vs l -> 匹配，继续 i+j=3: l vs l -> 匹配，j=1 == lenn-1=1，返回 2 这些方法具体怎么运用？方法一...

27. Remove Element你选用何种方法解题？本题的核心是原地移除数组中等于给定值的元素。 方法 时间复杂度 空间复杂度 是否推荐 快慢指针 O(n) O(1) 推荐 方法选择理由： 快慢指针：只需一次遍历，空间复杂度 O(1) 解题过程问题分析输入：数组 nums，目标值 val输出：移除目标值后的数组长度 关键约束： 原地修改数组，不能使用额外空间 不需要保持元素顺序 核心洞察 双指针技巧：使用两个指针，一个指向待填位置，另一个遍历数组 原地修改：直接在原数组上进行修改 算法流程以 nums = [3,2,2,3], val = 3 为例： 1234567891011121314初始化: num = 0（指向待填位置）遍历过程: i=0: nums[0]=3 == val=3，跳过 i=1: nums[1]=2 != val=3 nums[0] = 2, num = 1 nums = [2,2,2,3] i=2: nums[2]=2 != val=3 nums[1] = 2, num = 2 ...

26. Remove Duplicates from Sorted Array你选用何种方法解题？本题的核心是原地删除有序数组中的重复元素。 方法 时间复杂度 空间复杂度 是否推荐 快慢指针 O(n) O(1) 推荐 方法选择理由： 快慢指针：只需一次遍历，空间复杂度 O(1) 解题过程问题分析输入：有序数组 nums输出：删除重复元素后的数组长度 关键约束： 原地修改数组，不能使用额外空间 相同元素只保留一个 核心洞察 双指针技巧：使用两个指针，一个指向不重复元素的最后一个位置，另一个遍历数组 原地修改：直接在原数组上进行修改 算法流程以 nums = [1,1,2,2,3,4,4,5] 为例： 12345678910111213141516171819202122初始化: num = 0（指向第一个元素）遍历过程: i=1: nums[0]=1, nums[1]=1, 1 < 1 不成立，跳过 i=2: nums[0]=1, nums[2]=2, 1 < 2 成立 num = 1, nums[1] = 2 n...

25. Reverse Nodes in k-Group题目Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed. Example 1: 12Input: head = [1,2,3,4,5], k = 2Output: [2,1,4,3,5] Example 2: 12Inp...

3002. Maximum Size of a Set After RemovalsYou are given two 0-indexed integer arrays nums1 and nums2 of even length n. You must remove n / 2 elements from nums1 and n / 2 elements from nums2. After the removals, you insert the remaining elements of nums1 and nums2 into a set s. Return the maximum possible size of the set s. Example 1: 1234Input: nums1 = [1,2,1,2], nums2 = [1,1,1,1]Output: 2Explanation: We remove two occurences of 1 from nums1 and nums2. After the removals, the arrays become e...

24. Swap Nodes in Pairs题目Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.) Example 1: 12Input: head = [1,2,3,4]Output: [2,1,4,3] Example 2: 12Input: head = []Output: [] Example 3: 12Input: head = [1]Output: [1] 题目大意给定一个链表，两两交换其中相邻的节点，并返回交换后的链表头节点。要求不能修改节点的值，只能通过改变节点指针来实现交换。 你选用何种方法解题？本题的核心是两两交换链表节点。 方法 时间复杂度 空间复杂度 是否推荐 递归 O(n) O(n) 推荐 ...

2356. 每位教师所教授的科目种类的数量表: Teacher 123456789+-------------+------+| Column Name | Type |+-------------+------+| teacher_id | int || subject_id | int || dept_id | int |+-------------+------+在 SQL 中，(subject_id, dept_id) 是该表的主键。该表中的每一行都表示带有 teacher_id 的教师在系 dept_id 中教授科目 subject_id。 查询每位老师在大学里教授的科目种类的数量。 以 任意顺序 返回结果表。 查询结果格式示例如下。 示例 1: 1234567891011121314151617181920212223242526272829输入: Teacher 表:+------------+------------+---------+| teacher_id | subject_id | dept_id |+------------+---...