algorithm thoughts

[ahasusie]

summarize common used algorithm thoughts

[ahasusie]

two pointers

---

-two pointers from start, end towards middle the array is sorted: 344 two pointers in special range: 15, 16

-two pointers with different steps, fast and slow 26

-greedy algorithm

-sliding window problem A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. [i, j)[i,j) (left-closed, right-open). A sliding window is a window "slides" its two boundaries to the certain direction. For example, if we slide [i, j)[i,j) to the right by 11 element, then it becomes [i+1, j+1)[i+1,j+1) (left-closed, right-open). 53, 28

---

# 28. implement strStr() sliding window
def strStr(words, needle):
    l, r = 0, len(needle)
    while r <= len(words):
        if words[l:r] == needle:
            return l
        else:
            l += 1
            r += 1
    return -1

# 3. Longest Substring Without Repeating Characters
# The reason is that if s[j] have a duplicate in the range [i, j) with index j′, we don't need to increase i little by little. We can skip all the elements in the range [i, j′] and let i to be j′+1 directly.
def lengthOfLongestSubstring(s):
    dic, cnt, l = {}, 0, 0     
    for r in range(len(s)):
        if s[r] in dic and l <= dic[s[r]]:
            l = dic[s[r]] + 1
        else:
            cnt = max(cnt, r - l + 1)
        dic[s[r]] = r
    return cnt

15, 16, 3, 763, 80, 28, 844, 88, 26, 141, 283, 167, 125, 345

[ahasusie]

sliding window

---

In any sliding window based problem we have two pointers. One rightright pointer whose job is to expand the current window and then we have the leftleft pointer whose job is to contract a given window. At any point in time only one of these pointers move and the other one remains fixed.

The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now.

The answer is the smallest desirable window.

Algorithm

We start with two pointers, leftleft and rightright initially pointing to the first element of the string SS.

We use the rightright pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of TT.

Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one we keep on updating the minimum window size.

If the window is not desirable any more, we repeat step \; 2step2 onwards.

The above steps are repeated until we have looked at all the windows. The smallest window is returned.

By using HashSet as a sliding window, checking if a character in the current can be done in O(1)O(1).

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. [i, j)[i,j) (left-closed, right-open). A sliding window is a window "slides" its two boundaries to the certain direction. For example, if we slide [i, j)[i,j) to the right by 11 element, then it becomes [i+1, j+1)[i+1,j+1) (left-closed, right-open).

Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character. The reason is that if s[j]s[j] have a duplicate in the range [i, j)[i,j) with index j', we don't need to increase i little by little. We can skip all the elements in the range [i, j'] and let i to be j'+1directly.

[ahasusie]

backtracking subset, permutation, combination sum, palindrome partition leetcode sample

---

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again. Here is a backtrack function which takes the index of the first integer to consider as an argument backtrack(first). 1/ If the first integer to consider has index n that means that the current permutation is done. 2/ Iterate over the integers from index first to index n - 1. -Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]). -Proceed to create all permutations which starts from i-th integer : backtrack(first + 1). -Now backtrack, i.e. swap(nums[first], nums[i]) back.

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # if all integers are used up
            if first == n:  
                output.append(nums[:])
            for i in range(first, n):
                # place i-th integer first 
                # in the current permutation
                nums[first], nums[i] = nums[i], nums[first]
                # use next integers to complete the permutations
                backtrack(first + 1)
                # backtrack
                nums[first], nums[i] = nums[i], nums[first]

        n = len(nums)
        output = []
        backtrack()
        return output

[ahasusie]

recursion

---

commonly used in tree/ permutation problems know how to generate all permutations of a sequence as well as how to handle duplicates.

def subSet(nums):
    res = []
    def dfs(nums, res, index, tmp):
        res.append(tmp[:])
        for i in range(index, len(nums)):
            tmp.append(nums[i])
            dfs(nums, res, i+1, tmp)
            tmp.pop()
    dfs(nums, res, 0, [])
    return res

def permutation(nums):
    res = []
    def dfs(nums, tmp, res):
        if len(tmp) == len(nums):
            res.append(tmp[:])
        else:
            for i in range(len(nums)):
                if nums[i] in tmp:
                    continue
                tmp.append(nums[i])
                dfs(nums, tmp, res)
                tmp.pop()
    dfs(nums, [], res)
    return res

def combineSum(nums, target):
    res = []
    nums = sorted(nums)
    def dfs(res, tmp, nums, remain, index):
        if remain<0: return
        elif remain == 0:
            res.append(tmp[:])
        else:
            for i in range(len(nums)):
                tmp.append(nums[i])
                dfs(res, tmp, nums, remain-nums[i], i)
                tmp.pop()
    dfs(res, [], nums, target, 0)
    return res

def palindrome(s):
    ret = []
    def isPalindrome(s, low, high):
        while low<high:
            if s[low] != s[high]:
                return False
            low += 1
            high -= 1
        return True
    def dfs(ret, tmp, s, index):
        if index == len(s): 
            ret.append(tmp[:])
        else:
            for i in range(index, len(s)):
                if isPalindrome(s, index, i):
                    tmp.append(s[index:i+1])
                    dfs(ret, tmp, s, index+1)
                    tmp.pop()
    dfs(ret, [], s, 0)
    return ret

[ahasusie]

traverse divide and conquer

---

samples

# dfs, recursion, divide and conquer, postorder, buttom-up
def maxDepth(root):
    if not root:
        return 0
    l = maxDepth(root.left) 
    r = maxDepth(root.right)
    ans = max(l, r)+1
    return ans

# dfs, recursion, traversal, preorder top down
class Solution(object):
    def maxDepth(self, root):
        self.ans = 0
        self.dfs(root, 1)
        return self.ans
    def dfs(self, node, depth):
        if not node:
            return
        self.ans = max(self.ans, depth)
        self.dfs(node.left, depth+1)
        self.dfs(node.right, depth+1)

总结一下：

1. 一般来讲分治法的function有return value，遍历（就是那个helper）不需要返回；
2. 一般分治法是从下到上，比如在这道题里，是先找到最底层的最大值，然后逐层向上，最后到root的时候就找到答案了；遍历的顺序就比较随意了，总之就是便利所有数据之后，在容器内找到答案；
3. 有些时候，分治法返回的value会比较复杂，这个时候需要自己define一个自己需要的容器；