小旭讲解 LeetCode 399. Evaluate Division 并查集

原题英文 —— Evaluate DivisioEquations are given in the formatA / B = k, whereAandBare variables represented as strings, andkis a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return-1.0.Example:Givena / b = 2.0, b / c = 3.0.queries are:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .return[6.0, 0.5, -1.0, 1.0, -1.0 ].The input is:vec... Read More

小旭讲解 LeetCode 39. Combination Sum 回溯法

原题Given asetof candidate numbers (candidates)(without duplicates)and a target number (target), find all unique combinations incandidateswhere the candidate numbers sums totarget.Thesamerepeated number may be chosen fromcandidatesunlimited number of times.NoteAll numbers (includingtarget) will be positive integers.The solution set must not contain duplicate combinations.Example 1Input: candidates... Read More

小旭讲解 LeetCode 53. 最大子序和 动态规划 分治策略

原题Given an integer arraynums, find the contiguous subarray(containing at least one number) which has the largest sum and return its sum.ExampleInput: [-2,1,-3,4,-1,2,1,-5,4]Output: Explanation:[4,-1,2,1] has the largest sum = 6.Follow upIf you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.题解动态规划哔哩哔哩 动态规划YouTube 动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。... Read More

[LeetCode]743. Network Delay Time

原题There are N network nodes, labelled 1 to N.Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.NoteN will be in the ... Read More

[LeetCode]893. Groups of Special-Equivalent Strings

原题You are given an array A of strings.Two strings S and T are special-equivalent if after any number of moves, S == T.A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.Return the number of groups o... Read More

[LeetCode]Valid Palindrome II

原题Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.Example 1Input: "aba"Output: TruExample 2Input: "abca"Output: TruExplanation: You could delete the character 'c'.NoteThe string will only contain lowercase characters a-z. The maximum length of the string is 50000.思路水题。判断是否是回文字符串最简单的方式就是从左右两端逐步向中心逼近(双指针),如下代码[code lang="cpp"for (in... Read More

[LeetCode 889]Construct Binary Tree from Preorder and Postorder Traversal

原题Return any binary tree that matches the given preorder and postorder traversals.Values in the traversalspreandpostare distinctpositive integers.Example 1Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1Output: [1,2,3,4,5,6,7Note1 <= pre.length == post.length <= 30pre[]andpost[]are both permutations of1, 2, ..., pre.length.It is guaranteed an answer exists. If there exists multiple an... Read More

[LeetCode]Sum of Subarray Minimums

原题Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.Since the answer may be large, return the answer modulo 10^9 + 7.Example 1Input: [3,1,2,4Output: 1Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.Note1 <= A.length <1 <= A[i] <... Read More

[LeetCode]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 stepsAdd 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... Read More

[LeetCode]Remove Nth Node From End of List

原题Given a linked list, remove the n-th node from the end of list and return its head.ExampleGiven linked list: 1->2->3->4->5, and n = 2.After removing the second node from the end, the linked list becomes 1->2->3->5.NoteGiven n will always be valid.Follow upCould you do this in one pass思路首先,明确题意。题目给出了一个只有后继(successor),没有前驱(predecessor)的一个单向链表。要求删除倒数第n个节点。那么,思路自然会想到的就是在一次遍历就搞定题目要求。所以,我们自然要在遍历的过程中保存一... Read More

[LeetCode]4Sum

原题Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.NoteThe solution set must not contain duplicate quadruplets.ExampleGiven array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is[-1, 0, 0, 1][-2, -1, 1, 2][-2, 0, 0, 2题解本题的... Read More

[LeetCode]3Sum Closest

原题Given an array nums of n integers 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.ExampleGiven array nums = [-1, 2, 1, -4], and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).思路本题目的解题思路和3Sum很像,区别在于3Sum求解的是三个数字和为target(即为0),然而3Su... Read More

[LeetCode]3Sum

原题Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not contain duplicate triplets.For example, given array S = [-1, 0, 1, 2, -1, -4]A solution set is[-1, 0, 1][-1, -1, 2题解暴力解法因为需要计算三个数字的总和,所以需要进行3层的遍历,故时间复杂度需要O(n^3),看来不可取,果断放弃。毕竟是medium难度的题,不至于这么个解法。two-pointes solutio... Read More

[LeetCode]Two Sum

原题Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.ExampleGiven nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].题解暴力解法暴力解法使用两层for循环,遍历每一种存在的情况。[code lang="cpp"class Solution publicvector<int... Read More

[LeetCode]Palinkdrom Number

ProbleDetermine whether an integer is a palindrome. Do this without extra space.Some hints[code lang="shell" collapse="true"Could negative integers be palindromes? (ie, -1If you are thinking of converting the integer to string, note the restriction of using extra space.You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that th... Read More