Leetcode 0037.sudoku-solver(python)
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",".","."...
Leetcode 0036.valid-sudoku(python)
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...
Leetcode 0032.longest-valid-parentheses(python)
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 题目大意给定一个只包含 '(...
Leetcode 0031.next-permutation(python)
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 ...
Leetcode 0030.Substring with Concatenation of All Words(python)
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] 二...
Leetcode 0035.search-insert-position(python)
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 <=...
Leetcode 0034.find-first-and-last-position-of-element-in-sorted-array(python)
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...
Leetcode 0033.search-in-rotated-sorted-array(python)
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...
Leetcode 0029.Divide Two Integers(python)
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符号：正转化为负...
Leetcode 0028.Implement strStr()(python)
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 这些方法具体怎么运用？方法一...
Leetcode 0027.Remove Element(python)
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 ...
Leetcode 0026.Remove Duplicates from Sorted Array(python)
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...
Leetcode 0025.Reverse Nodes in k-Group(python)
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...
Leetcode 0024.Swap Nodes in Pairs(python)
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) 推荐 ...
Leetcode 0023.Merge k Sorted Lists(python)
23. Merge k Sorted Lists题目You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example 1: 12345678910Input: lists = [[1,4,5],[1,3,4],[2,6]]Output: [1,1,2,3,4,4,5,6]Explanation: The linked-lists are:[ 1->4->5, 1->3->4, 2->6]merging them into one sorted list:1->1->2->3->4->4->5->6 Example 2: 12Input: lists = []Output: [] Example 3: 12Input: lis...
Leetcode 0022.Generate Parentheses(python)
22. Generate Parentheses题目Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example 1: 12Input: n = 3Output: ["((()))","(()())","(())()","()(())","()()()"] Example 2: 12Input: n = 1Output: ["()"] 题目大意数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 你选用何种方法解题？本题的核心是生成所有有效的括号组合，属于经典的回溯算法（Backtracking）问题。 方法 时间复杂度 空间复杂度 是否推荐 DFS（字符串拼接） $O(\frac{4^n}{\sqrt{n}})$ $O(n)$ 推荐 DF...
Leetcode 0021.Merge Two Sorted Lists(python)
21. Merge Two Sorted Lists题目You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. Example 1: 12Input: list1 = [1,2,4], list2 = [1,3,4]Output: [1,1,2,3,4,4] Example 2: 12Input: list1 = [], list2 = []Output: [] Example 3: 12Input: list1 = [], list2 = [0]Output: [0] 题目大意将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ...
Leetcode 0020.Valid Parentheses(python)
20. Valid Parentheses题目Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. Example 1: 12Input: s = "()"Output: true Example 2: 12Input: s = "(...
Leetcode 0019.Remove Nth Node From End of List(python)
19. Remove Nth Node From End of List题目Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: 12Input: head = [1,2,3,4,5], n = 2Output: [1,2,3,5] Example 2: 12Input: head = [1], n = 1Output: [] Example 3: 12Input: head = [1,2], n = 1Output: [1] 题目大意给定一个链表的头节点 head，删除链表的倒数第 n 个节点，并返回链表的头节点。 你选用何种方法解题？本题的核心是找到链表的倒数第 n 个节点并删除。 方法 时间复杂度 空间复杂度 是否推荐 双指针（快慢指针，哑节点） O(n) O(1) 推荐 双指针（快慢指针，无哑节点） O(n) O(1) 推荐 两次遍历 O(n) O(1) 可选 栈 O(n) O...
Leetcode 0018.4Sum(python)
18. 4Sum题目Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order. Example 1: 12Input: nums = [1,0,-1,0,-2,2], target = 0Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] Example 2: 12Input: nums = [2,2,2,2,2], target = 8Output: [[2,2,2,2]] 题目大意在整数数组中找出所有不重复的四元组，使得四个数的和等于目标值 target。要...
Leetcode 0017.Letter Combinations of a Phone Number(python)
17. Letter Combinations of a Phone Number题目Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. 123456782 -> "abc"3 -> "def"4 -> "ghi"5 -> "jkl"6 -> "mno"7 -> "pqrs"8 -> "tuv"9...
Leetcode 0016.3Sum Closest(python)
16. 3Sum Closest题目Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example 1: 123Input: nums = [-1,2,1,-4], target = 1Output: 2Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). Example 2: 12Input: nums = [0,0,0], target = 1Output: 0 题目大意在整数数组中找出三个数，使其和最接近给定的目标值 target。题目保证有且仅有一个解。 你选用...
Leetcode 0015.3Sum(python)
15. 3Sum题目Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Example 1: 12345678Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.Different triplets are [-1,0,1...
Leetcode 0014. Longest Common Prefix (python)
14. Longest Common Prefix 你选用何种方法解题？ 方法 核心思路 时间复杂度 空间复杂度 说明 方法一：横向扫描 依次比较相邻两个字符串的公共前缀 O(S) O(1) 最直观：逐个比较 方法二：纵向扫描 按字符位置逐列比较所有字符串 O(S) O(1) 提前终止：遇到不匹配立即返回 方法三：二分查找 在最短字符串长度范围内二分查找 O(S×log(minLen)) O(1) 适合长字符串 方法二是推荐解：纵向扫描可以提前终止，实际性能更好。 解题过程核心洞察最长公共前缀的长度不可能超过最短字符串的长度。 纵向扫描步骤12345输入: ["flower","flow","flight"]第1列: f, f, f → 全部相同，继续第2列: l, l, l → 全部相同，继续第3列: o, o, i → 不相同，返回前2个字符 "fl" 边界情况 场景 输入 结果 空数组 [] "" 单元素 ["a"]...
Leetcode 0013. Roman to Integer (python)
13. Roman to Integer题目Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. 12345678Symbol ValueI 1V 5X 10L 50C 100D 500M 1000 For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from le...
