Simplify Path

Description LeetCode 71 Given an absolute path for a file (Unix-style), simplify it. For example, path = “/home/”, => “/home” path = “/a/./b/../../c/”, => “/c” Corner Cases: Did you consider the case where path = “/../”? In this case, you should return “/”. Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”. In this case, you should ignore redundant slashes and return “/home/foo”.

Search in Rotated Sorted Array

Description LeetCode 33 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in

Find First and Last Position of Element in Sorted Array

Description LeetCode 34 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input:

Substring with Concatenation of All Words

Description LeetCode 30 You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. Example 1: Input: s = “barfoothefoobarman”, words = [“foo”,”bar”] Output: [0,9] Explanation: Substrings starting at

Merge k Sorted Lists

Description LeetCode 23 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [   1->4->5,   1->3->4,   2->6 ] Output: 1->1->2->3->4->4->5->6 Analysis Based on the idea of MergeSort, it is easy to come up with the method of selecting the minimum element each time. And extend

The reason of using “(high-low)/2+low” instead of “(low+high)/2”

When we want to calculate the middle element of a segment of array, we should use $$(high-low)/2+low$$ instead of $$(low+high)/2$$. Why? The reason is we may not know the scope of input size of the array. If it is near from the upper bound of the data type used, $$low+high$$ may overflow. But $$high-low$$ can’t.

Two Pointer Technique

When we need to find a pair of elements that satisfies some conditions, two pointer technique could effectively decrease the time. Generally, there are two types of two pointer. The first one is the two pointers start from the first element and the last element respectively and move to the center. The other one is

Regular Expression Matching

Description LeetCode 10 Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’. ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains

Median of Two Sorted Arrays

Description LeetCode 4 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.   Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1,

Bit Manipulation

Bit Manipulation is a topic that is not easy to come up with without specific memory. So I conclude the useful conclusions and some typical problems here. Conclusions $$a\oplus 0=a$$ $$a\oplus a=0$$ $$a\oplus b\oplus a=(a\oplus a)\oplus b=0\oplus b=b$$ Problems 1. LeetCode 371 Description Calculate the sum of two integers a and b, but you are not allowed to use the