这次比赛做完四道题了 😊

第一题Non-decreasing Array

给定一个数组，问是否可以最多修改一个元素，使得整个数组非递降。

我是首先找出第一个i，满足nums[i] < nums[i-1]。这样我们必须要修改i或者i-1的位置，只要分别检查修改这两个位置是否可以得到一个非递降数组就行。因为两个元素相等也是非递降，所以修改一个位置可以等价于将那个位置的数字去除。

class Solution(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def check(i):
            if i >= len(nums):
                return True
            temp = [nums[j] for j in xrange(len(nums)) if j != i]
            return all(temp[j]>=temp[j-1] for j in xrange(1, len(temp)))
        i = 1
        while i < len(nums) and nums[i] >= nums[i-1]:
            i += 1
        return check(i) or check(i-1)

第二题Path Sum IV

一个三位数DPV可以表示一颗高度小于5的二叉树的一个节点。其中，D（1 <= D <= 4）表示节点所在的高度，P（1 <= P <= 8）表示节点在该层所在的位置，V（0 <= V <= 9）表示节点的值。现在给定一个包含三位数的递增数组表示一颗高度小于5的二叉树，问所有路径之和是多少？

我们知道树的高度小于5，所以我们可以用一个小的二维数组tree表示这棵树。其中tree[d]表示高度为d那层的节点，而tree[d][p]则表示树的第d层第p个位置的节点。我用-1表示空节点。根据这个对应关系，tree[d][p]的左儿子是tree[d+1][2*p-1]，右儿子是tree[d+1][2*p]。读入树后，只要扫描出所有叶节点找出对应的路径就行。

class Solution(object):
    def pathSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def decomp(n):
            return n/100, (n/10)%10, n%10

        tree = [[-1]*17 for _ in xrange(6)]
        for n in nums:
            d, p, v = decomp(n)
            tree[d][p] = v
        ans = 0
        for d in xrange(1, 5):
            for p in xrange(1, 17):
                if tree[d][p] != -1 and tree[d+1][2*p-1] == tree[d+1][2*p] == -1:
                    t = d
                    s = p
                    while t > 0:
                        ans += tree[t][s]
                        t -= 1
                        s = (s+1) / 2
        return ans

第三题Beautiful Arrangement II

给定n和k，构造一个由1到n构成的数组[a1, a2, ..., an]， 使得
|a1-a2|, |a2-a3|, ..., |an-1-an|
恰好有k个不同的值。

我构造的数组是这样的: n, 1, n-1, 2, n-2, 3, ...
这样可以保证前面的k-1个值不一样且都不为1，然后用剩下的数字要么递增要么递降排起来，得到最后一个值1。

class Solution(object):
    def constructArray(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[int]
        """
        ans = []
        t = [1, n]
        for i in xrange(k):
            if i & 1:
                ans.append(t[0])
                t[0] += 1
            else:
                ans.append(t[1])
                t[1] -= 1
        temp = range(t[0], t[1]+1)
        if k & 1:
            temp = temp[::-1]
        return ans + temp

第四题Kth largest Number in Multiplication Table

给定一个m x n的乘法表，问第k大的数是什么？

二分查找。给定一个数x，我们可以在O(n)时间内找出乘法表中比x小和不比x大的数的个数，所以对区间[1，m*n]二叉查找的话，我们可以得到一个O(n log(mn))的算法。

class Solution(object):
    def findKthNumber(self, m, n, k):
        """
        :type m: int
        :type n: int
        :type k: int
        :rtype: int
        """
        def divide(t, n, m):
            lo = hi = 0
            for i in xrange(1, n+1):
                cur = min((t-1) / i, m)
                lo += cur
                if t % i == 0 and t/i <= m:
                    cur += 1
                hi += cur
            return lo, hi

        n, m = min(n, m), max(n, m)
        a = 1
        b = n * m
        while True:
            c = (a+b)/2
            lo, hi = divide(c, n, m)
            if lo < k <= hi:
                return c
            if k <= lo:
                b = c-1
            else:
                a = c+1
leetcode contest