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 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...
Leetcode 0826. Most Profit Assigning Work
826. Most Profit Assigning WorkYou have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where: difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]). Every worker can be assigned at most one job, but one job can be completed multiple times. For example, if three workers attempt the same job that pays $1, then th...
Leetcode 0012. Integer to Roman (python)
12. Integer to Roman题目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 0825. Friends Of Appropriate Ages
825. Friends Of Appropriate AgesThere are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the ith person. A Person x will not send a friend request to a person y (x != y) if any of the following conditions is true: age[y] <= 0.5 * age[x] + 7 age[y] > age[x] age[y] > 100 && age[x] < 100 Otherwise, x will send a friend request to y. Note that if x sends a request to y, y will not necessarily send a request to x. Also, a ...
Leetcode 0011. Container With Most Water (python)
11. Container With Most Water题目You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. Example 1: 1234Input: height = [1,8,6,2,5,4,8,3,7]Output: 49Explanation: The above vertical...
Leetcode 0707. Design Linked List
707. Design Linked ListDesign your implementation of the linked list. You can choose to use a singly or doubly linked list.A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed. Implement the MyLinkedList ...
Leetcode 0704. Binary Search
704. Binary Search题目Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Note: You may assume that all elements in nums are un...
Leetcode 0010. Regular Expression Matching (python)
10. Regular Expression Matching题目Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: 123Input: s = "aa", p = "a"Output: falseExplanation: "a" does not match the entire string "aa". Example 2: 123Inp...
Leetcode 0637. Average of Levels in Binary Tree
637. Average of Levels in Binary TreeGiven the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted. Example 1: 1234Input: root = [3,9,20,null,null,15,7]Output: [3.00000,14.50000,11.00000]Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.Hence return [3, 14.5, 11]. Example 2: 12Input: root = [3,9,20,15,7]Output: [3.00000,14.50000,11.00000...
Leetcode 0009. Palindrome Number (python)
9. Palindrome Number题目Given an integer x, return true if x is a palindrome, and false otherwise. Example 1: 123Input: x = 121Output: trueExplanation: 121 reads as 121 from left to right and from right to left. Example 2: 123Input: x = -121Output: falseExplanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3: 123Input: x = 10Output: falseExplanation: Reads 01 from right to left. Therefore it is not a palindrome. Constra...
Leetcode 0626. 换座位
626. 换座位表: Seat 123456789+-------------+---------+| Column Name | Type |+-------------+---------+| id | int || student | varchar |+-------------+---------+id 是该表的主键（唯一值）列。该表的每一行都表示学生的姓名和 ID。ID 序列始终从 1 开始并连续增加。 编写解决方案来交换每两个连续的学生的座位号。如果学生的数量是奇数，则最后一个学生的id不交换。 按 id 升序 返回结果表。 查询结果格式如下所示。 示例 1: 1234567891011121314151617181920212223输入: Seat 表:+----+---------+| id | student |+----+---------+| 1 | Abbot || 2 | Doris || 3 | Emerson || 4 | Green || 5 | Jeames |+----+---...
