数据分析笔试编程题复盘

import math
import re

'''
1 算术平方根

思想：
    牛顿迭代法 x1=x0-f(x0)/f'(x0)
        推导 f(x) -> f(x0)+f'(x0)(x-x0) = 0

    转换为f(x)=0的形式，即求解 x^2=n <=> f(x)=x^2-n=0
        x1=x0/2+n/(2x0)

注意保留小数：
    round(x,4) : NO, x为整数时不保留小数
    "%.4f"%x : YES
'''
print('\nQ1 --------------------')
def test1(n):
    x0 = n/2
    x1 = x0/2 + n/x0/2
    while abs(x1-x0)>1e-6:
        x0 = x1
        x1 = x0/2 + n/x0/2
    return '%.4f'%x1

print(
test1(1)
, math.sqrt(1)
)


'''
2 词典与句子：句子能用词典中的词语完全分解返回'YES'

思想：0-1书包问题
    转换为二叉树，左树为加入当前物品，右树为不加入
'''
print('\nQ2 --------------------')
def test2(w, s):
    # 叶节点：YES
    if s=="":
        return 1
    # 叶节点：NO
    elif w==[]:
        return 0
    # 其他节点
    else:
        # 如果当前词过长，直接进入右树
        if len(w[0])>len(s):
            return test2(w[1:], s)
        # 对比左右树
        else:
            res_left = test2(w[1:], re.sub(w[0],'',s))
            res_right = test2(w[1:], s)
            if res_left>res_right:
                return res_left
            else:
                return res_right

w = "这里很美,这,这里,非常,很,美,美丽"
s = "这里很美丽"

w = w.split(',')
res2 = 'YES' if test2(w, s) else 'NO'
print(res2)

'''
动态规划版本

注意：
    dict的key不能为list或包含list
        "TypeError: unhashable type: 'list'"

    解决方法
        tuple(['a','b'])
'''
print('\nDynamic Programming ------------------')
def test3(w, s, memo={}):
    key = (tuple(w), s)
    # 有memory
    if key in memo:
        return memo[key]
    # 无memory
    else:
        # 叶节点：YES
        if s=="":
            res = 1
        # 叶节点：NO
        elif w==[]:
            res = 0
        # 其他节点
        else:
            # 如果当前词过长，直接进入右树
            if len(w[0])>len(s):
                res = test3(w[1:], s, memo)
            # 对比左右树
            else:
                res_left = test3(w[1:], re.sub(w[0],'',s), memo)
                res_right = test3(w[1:], s, memo)
                if res_left>res_right:
                    res = res_left
                else:
                    res = res_right
        # 记录
        memo[key]=res
        return res

res3 = 'YES' if test3(w, s) else 'NO'
print(res3)