2 interview coding problems

leetcode402_alike_keep_largest.py

# 这题与LeetCode 402 极为相似；就是把『最小』改成了『最大』
#
# 链接：https://www.nowcoder.com/questionTerminal/7f26bfeccfa44a17b6b269621304dd4a
# 来源：牛客网
#
# [编程题]保留最大的数
# 时间限制：1秒
# 空间限制：32768K
#
# 给定一个十进制的正整数number，选择从里面去掉一部分数字，希望保留下来的数字组成的正整数最大。
# 输入描述:
# 输入为两行内容，第一行是正整数number，1 ≤ length(number) ≤ 50000。第二行是希望去掉的数字数量cnt 1 ≤ cnt < length(number)。
#
# 输出描述:
# 输出保留下来的结果。
# 示例1
# 输入
# 325 1
# 输出
# 35


import sys

num, k = sys.stdin.readlines()
num = num.rstrip()  # trim '\n'
k = int(k)


# sol1: simple simulate, remove leftmost "right-peak"
# O(Nk) pass 90% test-cases
def sol1(num, k):
    num = list(num)  # str -> list, for supporting del
    for _ in range(k):  # outer O(k)
        for a, b in zip(num, num[1:]):
            if a < b:
                num.remove(a)  # trick: mono-inc invariant
                break
        else:  # trick: python for-else
            del num[-1]
    return ''.join(num).lstrip('0') if num else '0'  # CAUTION, ('10', 1)


# sol2: cached i, O(k+N)
def sol2(num, k):
    i = 0  # cached starting point; invariant: num[:i] is mono-dec
    num = list(num)
    for _ in range(k):
        while i < len(num) - 1:  # search from last_i
            if num[i] < num[i + 1]:
                break
            i += 1

        del num[i]
        i = max(0, i - 1)  # CAUTION: -1 index
    return ''.join(num).lstrip('0') or '0'


# sol3: mono-dec stack, O(k+N)
def sol3(num, k):
    stk = []
    for n in num:
        while k and stk and stk[-1] < n:
            k -= 1
            stk.pop()
        stk.append(n)
    return ''.join(stk[:-k or None]).lstrip('0') or '0'


# sol4: speed up by early stop at k==0, O(min(k, N))
def sol4(num, k):
    stk = []
    for i, n in enumerate(num):
        if k == 0:  # early stop
            stk += num[i:]  # speed up
            break
        while k and stk and stk[-1] < n:  # caution: avoid k == -1
            k -= 1
            stk.pop()
        stk.append(n)
    return ''.join(stk[:-k or None]).lstrip('0') or '0'


print(sol4(num, k))

leetcode72_edit_distance.py

class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        import numpy as np  # numpy不是必须，只是为了方便书写

        M, N = len(word1), len(word2)
        dp = np.zeros((M + 1, N + 1), dtype=np.int)  # 注意首行/首列是空串
        dp[0, :] = range(N + 1)
        dp[:, 0] = range(M + 1)

        for i in range(1, M + 1):
            for j in range(1, N + 1):
                # 注意："第i行"的意思是"长度为i的子串"，对应原串word1中的字符下标是i-1
                if word1[i - 1] == word2[j - 1]:
                    dp[i, j] = dp[i - 1, j - 1]
                else:
                    dp[i, j] = min(dp[i - 1, j], dp[i, j - 1], dp[i - 1, j - 1]) + 1

        return int(dp[-1, -1])  # OJ要求返回int类型而非np.int


if __name__ == '__main__':
    print(Solution().minDistance('bbc', 'abcd'))