Leetcode 0037.sudoku-solver
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
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
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
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(C++)
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 "...
Leetcode 0035.search-insert-position
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
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
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(C++)
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...
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 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 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 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 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 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 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 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 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 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 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 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 |+----+---...
