Wiggle Sort II

Posted on September 15, 2019 by elfsong

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4] 
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1] 
Output: One possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        half = len(nums[::2])
        nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]

Increasing Triplet Subsequence

Posted on September 15, 2019 by elfsong

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

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

Example 2:

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

Since this problem is literally similar another one (longest-increasing-subsequence), I have tried the traditional dynamic programming at very first. However, this question is not as easy as it looks be, I got a Time Limit Exceeded.

After that, I noticed that we actually can iterate the entire array by one pass with maintaining two pointers.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
#         # TLE
#         if not nums:
#             return False
        
#         dp = [1] * len(nums)
        
#         for i in range(1, len(nums)):
#             for j in range(i):
#                 if nums[i] > nums[j]:
#                     dp[i] = max(dp[i], dp[j] + 1)
#                 if dp[i] == 3:
#                     return True
        
#         return False
    
        first = second = float('inf')
        
        for n in nums:
            if n <= first:
                first = n
                
            elif n <= second:
                second = n
            else:
                return True
            
        return False

抛硬币

Posted on September 12, 2019 by elfsong

平均需要抛掷多少次硬币，才会首次出现连续的 n 个正面？

在Matrix67上看到了顾森大佬的解释，真的是超级通俗易懂。这可能真的是把一件简单的事讲复杂很容易，但是那一件复杂的事情讲容易就很难了吧。

有一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续的 n 个正面？它的答案是 2^(n+1) – 2 。取 n=2 的话，我们就有这样的结论：平均要抛掷 6 次硬币，才能得到两个连续的正面。或许这个期望次数比你想象中的要多吧。我们不妨试着来验证一下这一结果。由简单的递推可得，所有 1 都不相邻的 k 位 01 串有 F_k+2 个，其中 F_i 表示 Fibonacci 数列中的第 i 项。而“抛掷第 k 次才出现连续两个正面”的意思就是， k 位 01 串的末三位是 011 ，并且前面 k – 3 位中的数字 1 都不相邻。因此，在所有 2^k 个 k 位 01 串中，只有 F_k-1 个是满足要求的。因此，我们要求的期望值就等于 ∑ (k=2..∞) k * F_k-1 / 2^k 。这个无穷级数就等于 6 。我怎么算的呢？我用 Mathematica 算的。

设想有这么一家赌场，赌场里只有一个游戏：猜正反。游戏规则很简单，玩家下注 x 元钱，赌正面或者反面；然后庄家抛出硬币，如果玩家猜错了他就会输掉这 x 元，如果玩家猜对了他将得到 2x 元的回报（也就是净赚 x 元）。
让我们假设每一回合开始之前，都会有一个新的玩家加入游戏，与仍然在场的玩家们一同赌博。每个玩家最初都只有 1 元钱，并且他们的策略也都是相同的：每回都把当前身上的所有钱都押在正面上。运气好的话，从加入游戏开始，庄家抛掷出来的硬币一直是正面，这个玩家就会一直赢钱；如果连续 n 次硬币都是正面朝上，他将会赢得 2^n 元钱。这个 2^n 就是赌场老板的心理承受极限——一旦有人赢到了 2^n 元钱，赌场老板便会下令停止游戏，关闭赌场。让我们来看看，在这场游戏中存在哪些有趣的结论。

首先，连续 n 次正面朝上的概率虽然很小，但确实是有可能发生的，因此总有一个时候赌场将被关闭。赌场关闭之时，唯一赚到钱的人就是赌场关闭前最后进来的那 n 个人。每个人都只花费了 1 元钱，但他们却赢得了不同数量的钱。其中，最后进来的人赢回了 2 元，倒数第二进来的人赢回了 4 元，倒数第 n 进来的人则赢得了 2^n 元（他就是赌场关闭的原因），他们一共赚取了 2 + 4 + 8 + … + 2^n = 2^(n+1) – 2 元。其余所有人初始时的 1 元钱都打了水漂，因为没有人挺过了倒数第 n + 1 轮游戏。
另外，由于这个游戏是一个完全公平的游戏，因此赌场的盈亏应该是平衡的。换句话说，有多少钱流出了赌场，就该有多少的钱流进赌场。既然赌场的钱最终被赢走了 2^(n+1) – 2 元，因此赌场的期望收入也就是 2^(n+1) – 2 元。而赌场收入的唯一来源是每人 1 元的初始赌金，这就表明游戏者的期望数量是 2^(n+1) – 2 个。换句话说，游戏平均进行了 2^(n+1) – 2 次。再换句话说，平均抛掷 2^(n+1) – 2 次硬币才会出现 n 连正的情况。

转载自：http://www.matrix67.com/blog/archives/3638

Flip Equivalent Binary Trees

Posted on September 12, 2019 by elfsong

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.

Example 1:

Input: 
root1 = [1,2,3,4,5,6,null,null,null,7,8], 
root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7] 
Output: true 
Explanation: We flipped at nodes with values 1, 3, and 5.

Note:

Each tree will have at most 100 nodes.
Each value in each tree will be a unique integer in the range [0, 99].

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
        if root1 == root2 == None:
            return True
        
        elif root1 and root2 and root1.val == root2.val:
            return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.right, root2.left) and self.flipEquiv(root1.left, root2.right))
        
        else:
            return False

Remove Zero Sum Consecutive Nodes from Linked List

Posted on September 10, 2019 by elfsong

Firstly, I can’t help myself to say: “Lee, you are a fucking genius!”

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        
        prefix = 0
        seen = collections.OrderedDict()
        
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur = cur.next
            
        return dummy.next

Path In Zigzag Labelled Binary Tree

Posted on September 9, 2019 by elfsong

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

from math import log

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        ans = [label]
        
        def findParent(label):
            level =  math.floor(math.log(label,2))            
            diff = math.ceil((label - 2**level + 1) / 2)       
            parent = 2**(level) - diff
            return parent
            
        while label != 1:
            label = findParent(label)
            ans.append(label)
            
        return ans[::-1]

Remove Duplicates from Sorted Array

Posted on September 8, 2019 by elfsong

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

class Solution:
    def removeDuplicates(self, nums: List[int]):
        if not nums:
            return 0

        newTail = 0

        for i in range(1, len(nums)):
            if nums[i] != nums[newTail]:
                newTail += 1
                nums[newTail] = nums[i]

        return newTail + 1

Permutations II

Posted on September 8, 2019 by elfsong

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.result = []

        def perm(data, begin, end):
            if begin == end:
                self.result += [[item for item in data]]
            else:
                i = begin
                for j in range(begin, end):
                    data[i], data[j] = data[j], data[i]
                    perm(data, begin + 1, end)
                    data[i], data[j] = data[j], data[i]
                    
        perm(nums, 0, len(nums))

        return self.result

Permutation Sequence

Posted on September 8, 2019 by elfsong

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        res, nums = "", list(range(1, n + 1))

        k -= 1

        for n in range(n, 0, -1):
            index, k = divmod(k, math.factorial(n-1))
            res += str(nums.pop(index))

        return res

Lowest Common Ancestor with N nodes

Posted on September 7, 2019 by elfsong

Similar with finding lowest common ancestor of two nodes, we can extend this function to N nodes.

The method buildTree in the solution is in order to building a tree instantly by given strings.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, inorder, postorder):
        if not inorder or not postorder:
            return None

        while postorder:
            if postorder[-1] not in inorder:
                postorder.pop()
            else:
                break

        if len(postorder) == 1:
            return TreeNode(postorder[0])

        else:
            node = TreeNode(postorder[-1])
            in_index = inorder.index(postorder[-1])
            node.left = self.buildTree(inorder[:in_index], postorder[:-1])
            node.right = self.buildTree(inorder[in_index + 1:], postorder[:-1])
            return node

    def find(self, root, nodes):
        if not root:
            return None
        else:
            if root.val in nodes:
                return root

            left = self.find(root.left, nodes)
            right = self.find(root.right, nodes)

            if left and right:
                return root

            return right if not left else left


if __name__ == "__main__":
    obj = Solution()
    root = obj.buildTree([6, 5, 7, 2, 4, 3, 0, 1, 8], [6, 7, 4, 2, 5, 0, 8, 1, 3])
    nodes = [0, 1, 8]
    result = obj.find(root, nodes)
    print(result.val)

凛冬之怒

无为善道止战非攻

Category Archives: Aha moments

Wiggle Sort II

Increasing Triplet Subsequence

抛硬币

Flip Equivalent Binary Trees

Remove Zero Sum Consecutive Nodes from Linked List

Path In Zigzag Labelled Binary Tree

Remove Duplicates from Sorted Array

Permutations II

Permutation Sequence

Lowest Common Ancestor with N nodes