Author Archives: elfsong

My Calendar I

Posted on by
Reply

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.Your class will be called like this: MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)

Example 1:
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

  • The number of calls to MyCalendar.book per test case will be at most 1000.
  • In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].
import bisect


class MyCalendar:

    def __init__(self):
        self.ints = []

    def book(self, start: int, end: int) -> bool:
        idx = bisect.bisect_left(self.ints, (start, end))

        is_left_valid = idx == 0 or self.ints[idx - 1][1] <= start
        is_right_valid = idx == len(self.ints) or end <= self.ints[idx][0]

        if is_left_valid and is_right_valid:
            self.ints.insert(idx, (start, end))
            return True
        return False

Find the Shortest Superstring

Posted on by
Reply

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))

Gaia

Posted on by
Reply

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 by
Reply

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

Levithan

Posted on by
Reply

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

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

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

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

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

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

Reverse Pairs

Posted on by
Reply

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:

  1. The length of the given array will not exceed 50,000.
  2. 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