Leetcode Contest 135

Minimum Score Triangulation of Polygon

Given N, consider a convex N-sided polygon with vertices labelled A[0], A[i], …, A[N-1] in clockwise order.

Suppose you triangulate the polygon into N-2 triangles. For each triangle, the value of that triangle is the product of the labels of the vertices, and the total score of the triangulation is the sum of these values over all N-2 triangles in the triangulation.

Return the smallest possible total score that you can achieve with some triangulation of the polygon.

Keyword: DP. record[i][j] means the min score from A[i] to A[j] when the points i-j are connected.

Suppose j = i + step, where step could be in range(2, length). Then in the range of points i-j, the value record[i][j] is minimal sums of A[i]*A[j]*A[k] for k in range(i, j).

class Solution(object):
    def minScoreTriangulation(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        length = len(A)
        record = [[0 for i in range(length)] for j in range(length)]
        # record[i][j] means the min score from A[i] to A[j] when i-j connected

        for step in range(2, length):
            for i in range(0, length - step):
                j = i + step
                record[i][j] = 100 * 100 * 100
                for k in range(i + 1, i + step):
                    record[i][j] = min(record[i][j], record[i][k] + record[k][j] + A[i] * A[j] * A[k])

        return record[0][-1]

Moving Stones Until Consecutive II

On an infinite number line, the position of the i-th stone is given by stones[i]. Call a stone an endpoint stone if it has the smallest or largest position. Each turn, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone. When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

Keyword: Math, sliding window

1. Sort the array, n = len(A)
2. Maximum move would be (A[n-1] - A[1]) - (n - 2) or (A[n-2] - A[0]) - (n - 2)
3. Minimum move could be 0 or >= 2, we can use a sliding window with length n to scan and detect when could the window contain most number of stones.

class Solution(object):
    def numMovesStonesII(self, stones):
        """
        :type stones: List[int]
        :rtype: List[int]
        """
        length = len(stones)
        stones.sort()

        high = max(stones[-1] - stones[1] - (length - 2), stones[-2] - stones[0] - (length - 2))
        low = length

        for i in range(length):
            j = 0
            while stones[i] - stones[j] >= length:
                j += 1

            if j < length and i - j == length - 2 and stones[i] - stones[j] == length - 2:
                low = min(low, 2)
            else:
                low = min(low, length - (i - j + 1))

        print [low, high]
        return [low, high]

Valid Boomerang

Given a list of three points in the plane, return whether these points are a boomerang.

Calculate slope of AB and AC (but avoid same x value). Notice that we need float type for slope value.

Better solution: Use multiplication instead of division when calculation slope.

Binary Search Tree to Greater Sum Tree

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

Inorder traversal, then update the value from right to left.