Apart from vanilla BFS introduced in Intro to Graph Algorithms – BFS & DFS, there’s another variant of BFS called bi-directional BFS. Instead of searching from source to target, bi-directional BFS starts with the source and the target at the same time, and search the graph simultaneously. The improvement of time complexities is shown as below, as referring to @Huahua.
Continue reading “BFS and Bi-directional BFS”[Leetcode]1537. Get the Maximum Score
You are given two sorted arrays of distinct integersContinue reading “[Leetcode]1537. Get the Maximum Score”nums1
andnums2.
A valid path is defined as follows: Choose array nums1 or nums2 to traverse (from index-0). Traverse the current array from left to right. If you are reading any value that is present innums1
andnums2
you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path). Score is defined as the sum of uniques values in a valid path. Return the maximum score you can obtain of all possible valid paths. Since the answer may be too large, return it modulo 10^9 + 7.
[Leetcode]1286. Iterator for Combination
Design an Iterator class, which has: A constructor that takes a stringContinue reading “[Leetcode]1286. Iterator for Combination”characters
of sorted distinct lowercase English letters and a numbercombinationLength
as arguments. A function next() that returns the next combination of lengthcombinationLength
in lexicographical order. A function hasNext() that returnsTrue
if and only if there exists a next combination. Constraints:1 <= combinationLength <= characters.length <= 15
There will be at most10^4
function calls per test. It's guaranteed that all calls of the functionnext
are valid.
[Leetcode]31. Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.Continue reading “[Leetcode]31. Next Permutation”1,2,3
→1,3,2
3,2,1
→1,2,3
1,1,5
→1,5,1
[Leetcode]238. Product of Array Except Self
Given an arrayContinue reading “[Leetcode]238. Product of Array Except Self”nums
of n integers where n > 1, return an arrayoutput
such thatoutput[i]
is equal to the product of all the elements ofnums
exceptnums[i]
. Note: Please solve it without division and in O(n). Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.) Example: Input:[1,2,3,4]
Output:[24,12,8,6]
[Leetcode]560. Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2 Output: 2Continue reading “[Leetcode]560. Subarray Sum Equals K”
[Leetcode]442. Find All Duplicates in an Array
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime?Continue reading “[Leetcode]442. Find All Duplicates in an Array”
[Leetcode]3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc"
, with the length of 3.
Continue reading “[Leetcode]3. Longest Substring Without Repeating Characters”