[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

最大流问题之Ford-Fulkerson算法

Ford-Fulkerson算法(亦即标号法?)的输入与步骤如下输入给定一个容量为c的图G=(V, E),源点s与汇点(终点)步骤对图G中每一个边(u, v)的流量f(u, v)进行初始化为查询过程:寻找(DFS、深度优先搜索方式)图G中的一条路径p,其中每一条边(u, v) ∈p,都有fc(u, v) = c(u, v) - f(u, v) > 0(c(u, v) 代表当前边的容量,f(u, v) 代表当前边已有的流量,即c(u, v) - f(u, v)代表当前边可用的最大流量,即剩余流量调整过程:计算当前路径下每条边的最小剩余容量,cf(p) = min{fc(u, v) : (u, v) ∈p},然后对于每条边进行如下操作f(u, v) = f(u, v) + cf(p) (前向狐f(v, u) = f(v, u) - cf(p) (后向狐往复上述2与3步骤,直至无法找到路径p为止... 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] 4 Sum

原题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