Find the Shortest Superstring

Posted on October 19, 2019 by elfsong

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:
Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:
Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:
1 <= A.length <= 12
1 <= A[i].length <= 20

Solution 1 (Naive and TLE):
At the very first, I did this solution that naively using DFS to search each possible solution, and finally we can pick up the shortest one. It works on small test set but got TLE on large sets.

from functools import lru_cache

class Solution:
    @lru_cache(None)
    def combinateStrings(self, str1, str2):
        for i in range(len(str2), -1, -1):
            if str1.endswith(str2[:i]):
                return str1 + str2[i:]

    def shortestSuperstring(self, A):

        def func(current_list, result, results):
            if not current_list:
                results.append(result)

            for s in current_list:
                current_list.remove(s)
                func(current_list, self.combinateStrings(result, s), results)
                func(current_list, self.combinateStrings(s, result), results)
                current_list.append(s)

        results = []

        func(A, "", results)

        return min(results, key= lambda x: len(x))

Animals in the zoo

Posted on October 18, 2019 by elfsong

Gaia

Posted on October 18, 2019 by elfsong

In Greek mythology, Gaia is the personification of the Earth and one of the Greek primordial deities.
Gaia is the ancestral mother of all life: the primal Mother Earth goddess. She is the immediate parent of Uranus (the sky), from whose sexual union she bore the Titans (themselves parents of many of the Olympian gods) and the Giants, and of Pontus (the sea), from whose union she bore the primordial sea gods.
Her equivalent in the Roman pantheon was Terra.

Best Time to Buy and Sell Stock with Transaction Fee

Posted on October 18, 2019 by elfsong

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        sell = 0
        buy = -0x7777777
        
        for price in prices:
            # Not buy or pay current price and fee
            buy = max(buy, sell - price - fee)
            
            # Not sell or get current price
            sell = max(sell, buy + price)
            
        return sell

Bifurcation and Feigenbaum Constant

Posted on October 14, 2019 by elfsong

Continue reading →

Levithan

Posted on October 13, 2019 by elfsong

Leviathan, or The Matter, Forme and Power of a Common Wealth Ecclesiastical and Civil

在人类的自然状态下，有一些人可能会比另外一些人更加强壮或者更加聪明，但是没有一个人会强壮到或聪明到不怕在暴力下死亡。当死亡成为威胁时，在自然状态下的人必然会尽一切所能来保护自己。Hobbes 认为保护自己免于暴力死亡就是人类的最高必要，而权利就是来自于必要。

在自然状态下，每个人都需要世界上的每一样东西，也有获取每一样东西的权利。但世界上的东西都是不足的，因此就有持续的，基于权利的“所有人对所有人的战争”。人生在自然状态下是“孤独、贫穷、龌蹉、粗暴又短命”。

自然状态下的战争并非对人最有利的状态。Hobbes 认为人因为自利和对物质的欲求，会想要结束战争——“使人倾向于和平的热忱其实是怕死，以及对于舒适生活之必要东西的欲求和殷勤获取这些东西的盼望”。

霍布斯认为社会要和平就必需要有社会契约。社会是一群人在一个威权之下，而每个人都将所有的自然权力交付给这威权，让它来维持内部和平和进行外部防御，只保留自己免于一死的权力。这个主权，无论是君主制、贵族制或民主制（Hobbes 较中意君主制），都必须是一个“利维坦”，一个绝对的威权。

对霍布斯而言，法律就是要确保契约的执行。利维坦国家在防止人对人的攻击以及保持国家的统合方面是有无限威权的。至于其他方面，国家是完全不管的。只要一个人不去伤害别人，国家主权是不会去干涉他的。（不过，在国家主权之上并没有任何更高的权力可以防止国家破坏这规则。）国家主权也要保持内部的平等。

Reverse Pairs

Posted on October 13, 2019 by elfsong

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.

# Solution 1: Using Binary Index Tree, which has O(nlogn) time complexity.

class BIT():
    def __init__(self, n):
        self.n = n + 1
        self.sums = [0] * self.n

    def update(self, i, delta):
        while i < self.n:
            self.sums[i] += delta
            i += i & (-i)

    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res
    
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        sorted_nums = sorted(list(set(nums + [x * 2 for x in nums])))
        tree = BIT(len(sorted_nums))

        res = 0
        ranks = {}

        for i, n in enumerate(sorted_nums):
            ranks[n] = i + 1

        for n in nums[::-1]:
            res += tree.query(ranks[n] - 1)
            tree.update(ranks[n * 2], 1)

        return res

# Solution 2: At this time, we are going to use bisect. Got inspiration from Merge Sort (Divide and Conquer).

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        ranks = list()
        ans = 0

        for n in reverse(nums):
            ans += bisect.bisect_left(ranks, n)
            bisect.insort_left(ranks, n * 2)

        return ans

Binary Index Tree

Posted on October 13, 2019 by elfsong

class BIT:
    def __init__(self, n):
        self.n = n + 1
        self.sums = [0] * self.n

    def update(self, i, delta):
        while i < self.n:
            self.sums[i] += delta
            i += i & (-i)

    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

TCP States Transformer

Posted on October 11, 2019 by elfsong

Largest Rectangle in Histogram

Posted on October 10, 2019 by elfsong

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Actually, I have met this problem on the online assessment of Amazon a few days ago.

IT IS A REALLY TOUGH QUESTION FOR MY DUMB BRAIN!

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        stack = [-1]
        ans = 0
        
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, h * w)
            stack.append(i)

        return ans

凛冬之怒

无为善道止战非攻

Monthly Archives: October 2019

Find the Shortest Superstring

Animals in the zoo

Gaia

Best Time to Buy and Sell Stock with Transaction Fee

Bifurcation and Feigenbaum Constant

Levithan

Reverse Pairs

Binary Index Tree

TCP States Transformer

Largest Rectangle in Histogram