Leetcode 2356. 每位教师所教授的科目种类的数量
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 |+------------+---...
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 1934. 确认率
1934. 确认率表: Signups 12345678+----------------+----------+| Column Name | Type |+----------------+----------+| user_id | int || time_stamp | datetime |+----------------+----------+User_id是该表的主键。每一行都包含ID为user_id的用户的注册时间信息。 表: Confirmations 1234567891011+----------------+----------+| Column Name | Type |+----------------+----------+| user_id | int || time_stamp | datetime || action | ENUM |+----------------+----------+(user_id, time_sta...
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 1757. 可回收且低脂的产品
1757. 可回收且低脂的产品表：Products 12345678910+-------------+---------+| Column Name | Type |+-------------+---------+| product_id | int || low_fats | enum || recyclable | enum |+-------------+---------+product_id 是该表的主键（具有唯一值的列）。low_fats 是枚举类型，取值为以下两种 ('Y', 'N')，其中 'Y' 表示该产品是低脂产品，'N' 表示不是低脂产品。recyclable 是枚举类型，取值为以下两种 ('Y', 'N')，其中 'Y' 表示该产品可回收，而 'N' 表示不可回收。 编写解决方案找出既是低脂又是可回收的产品编号。 返回结果 无顺序要求 。 返回结果格式如下例...
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 1201. Ugly Number III
1201. Ugly Number III题目Write a program to find the n-th ugly number. Ugly numbers are positive integers which are divisible by a or b or c. Example 1: Input: n = 3, a = 2, b = 3, c = 5 Output: 4 Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4. Example 2: Input: n = 4, a = 2, b = 3, c = 4 Output: 6 Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6. Example 3: Input: n = 5, a = 2, b = 11, c = 13 Output: 10 Explanation: The ugly numbers are 2,...
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 1193. 每月交易 I
1193. 每月交易 I表：Transactions 123456789101112+---------------+---------+| Column Name | Type |+---------------+---------+| id | int || country | varchar || state | enum || amount | int || trans_date | date |+---------------+---------+id 是这个表的主键。该表包含有关传入事务的信息。state 列类型为 ["approved", "declined"] 之一。 编写一个 sql 查询来查找每个月和每个国家/地区的事务数及其总金额、已批准的事务数及其总金额。 以 任意顺序 返回结果表。 查询结果格式如下所示。 示例 1: 123456789101112131415161718输入：Transactio...
Leetcode 1089. Duplicate Zeros
1089. Duplicate Zeros题目Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right. Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place, do not return anything from your function. Example 1: 123Input: [1,0,2,3,0,4,5,0]Output: nullExplanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4] Example 2: 123Input: [1,2,3]Out...
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 1048. Longest String Chain
1048. Longest String ChainYou are given an array of words where each word consists of lowercase English letters. wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB. For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".A word chain is a sequence of words [word1, word2, ..., wordk] with k >...
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 1047. Remove All Adjacent Duplicates In String
1047. Remove All Adjacent Duplicates In StringYou are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique. Example 1: 1234Input: s = "abbaca"Output: "ca"Explanation: For example, in "abbaca&...
Leetcode 1023. Camelcase Matching
1023. Camelcase MatchingGiven an array of strings queries and a string pattern, return a boolean array answer where answer[i] is true if queries[i] matches pattern, and false otherwise. A query word queries[i] matches pattern if you can insert lowercase English letters into the pattern so that it equals the query. You may insert a character at any position in pattern or you may choose not to insert any characters at all. Example 1: 12345Input: queries = ["FooBar","FooBarTest&qu...
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 0977. Squares of a Sorted Array
977. Squares of a Sorted ArrayGiven an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1: 12Input: [-4,-1,0,3,10]Output: [0,1,9,16,100] Example 2: 12Input: [-7,-3,2,3,11]Output: [4,9,9,49,121] Note: 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order. 解题思路这一题由于原数组是有序的，所以要尽量利用这一特点来减少时间复杂度。 最终返回的数组，最后一位，是最大值，这个值应该是由原数组最大值，或者最小值得来的，所以可...
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 0922. Sort Array By Parity II
922. Sort Array By Parity IIGiven an array of integers nums, half of the integers in nums are odd, and the other half are even. Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even. Return any answer array that satisfies this condition. Example 1: 123Input: nums = [4,2,5,7]Output: [4,5,2,7]Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted. Example 2: 12Input: nums = [2,3]Output: [2,3] 双指针解法： 初始化： 偶数索引指针 i 从 0 开始，每次移动 2 步...
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 0905. Sort Array By Parity
905. Sort Array By ParityGiven an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers. Return any array that satisfies this condition. Example 1: 123Input: nums = [3,1,2,4]Output: [2,4,3,1]Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. Example 2: 12Input: nums = [0]Output: [0] 解法1：双指针12345678910111213141516class Solution{public: vector<int> sortArrayByParity(vector<int> &...
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 0904. Fruit Into Baskets
904. Fruit Into Baskets题目In a row of trees, the i-th tree produces fruit with type tree[i]. You start at any tree of your choice, then repeatedly perform the following steps: Add one piece of fruit from this tree to your baskets. If you cannot, stop. Move to the next tree to the right of the current tree. If there is no tree to the right, stop. Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then st...
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...
Leetcode 0844. Backspace String Compare
844. Backspace String Compare题目Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character. Example 1: 123Input: S = "ab#c", T = "ad#c"Output: trueExplanation: Both S and T become "ac". Example 2: 123Input: S = "ab##", T = "c#d#"Output: trueExplanation: Both S and T become "". Example 3: 123Input: S = "a##c", T = "#a#c"Output: trueExplanation: Bo...
