Hypercube's LeetCode Weekly Contest 47

  • Rank: 83 / 2554
  • Score: 27 / 27
  • Finish Time: 01:51:48

Non-decreasing Array

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4, 2, 3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4, 2, 1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10000].

Accepted in 00:16:30 
class Solution:
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        chance = True
        i = 1
        while i < len(nums):
            if nums[i] < nums[i-1]:
                if i == 1 or nums[i] >= nums[i-2]:
                    if chance:
                        chance = False
                    else:
                        return False
                else:
                    if i == len(nums)-1:
                        return chance
                    if chance:
                        chance = False
                    else:
                        return False
                    nums[i] = nums[i+1]
                    continue
            i += 1
        return True

Path Sum IV

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

  1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
  3. The units digit represents the value V of this node, 0 <= V <= 9. Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: [113, 215, 221]
Output: 12
Explanation:
The tree that the list represents is:
  3
 / \
5   1
The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: [113, 221]
Output: 4
Explanation:
The tree that the list represents is:
3
 \
  1
The path sum is (3 + 1) = 4.
Accepted in 00:28:39 
def maketree(level, l, d):
    if not level:
        return None
    r = TreeNode(None)
    r.left = maketree(level-1, l*2, d)
    r.right = maketree(level-1, l*2+1, d)
    d[str(5-level)+str(l+1)] = r
    return r

def calc(r):
    if r is None:
        return 0, 0
    if r.val is None:
        return 0, 0
    a, b = calc(r.left)
    c, d = calc(r.right)
    if b == d == 0:
        b = 1
    return a+c+r.val*(b+d), b+d

class Solution:
    def pathSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        d = {}
        r = maketree(4, 0, d)
        for i in nums:
            a, b, c = str(i)
            d[a+b].val = int(c)
        return calc(r)[0]

Beautiful Arrangement II

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:

Suppose this list is [a1, a2, a3, …, an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, …, |an-1 - an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

Example 1:

Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

Note:

  1. The n and k are in the range 1 <= k < n <= 10^4.
Accepted in 00:37:24 
class Solution:
    def constructArray(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[int]
        """
        r = [i for i in range(1, n-k+1)]
        s = r[-1]
        d = 1
        while len(r) < n:
            s += d*k
            r.append(s)
            d = -d
            k -= 1
        return r

Kth largest Number in Multiplication Table

Nearly every one have used the Multiplication Table. But could you find out the k-th largest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th largest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation:
The Multiplication Table:
1   2   3
2   4   6
3   6   9
The 5-th largest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 6
Explanation:
The Multiplication Table:
1   2   3
2   4   6
The 6-th largest number is 6 (1, 2, 2, 3, 4, 6).

Note:

  1. The m and n will be in the range [1, 30000].
  2. The k will be in the range [1, m * n]
Accepted in 01:21:48 with 6 wrong submissions 
def oub(m, n, v):
    """order's upper boundary"""
    r = 0
    i = 1
    mn = min(m, n)
    while i*i <= v and i <= mn:
        t = v // i
        r += min(t, m) - i + min(t, n) - i + 1
        i += 1
    return r

def bsearch(m, n, k, l, r):
    mid = (l + r) >> 1
    o = oub(m, n, mid)
    if o < k:
        return bsearch(m, n, k, mid+1, r)
    if o-mid >= k or oub(m, n, mid-1) >= k:
        return bsearch(m, n, k, l, mid)
    else:
        return mid

class Solution:
    def findKthNumber(self, m, n, k):
        """
        :type m: int
        :type n: int
        :type k: int
        :rtype: int
        """
        return bsearch(m, n, k, 1, m*n+1)