online coding case, since 2020-0

2020-05-23
Case 1(easy): 上山下山问题
，上山一步用U表示，下山一步用D表示，起始点和结束点都是sea level。一个从sea level开始的[U,D]序列，求其中经过了几次valley。

思路：vallery中可能有山，但只要山的高度没有超过vallery的深度就可以仍然算作一个vallery。也就是只要sl没有从负值变成0，则可算作一个vallery。sl正时不考虑。设定一个sea level指标sl，每经过一个U则sl+1，经过D则sl-1。当sl+1后等于0，则vallery counter+1.

def countingValleys(n, s):
    if not 0<=n<=10**6:
        return 'again'
    cv = 0
    sl = 0
    for st in s:
        if st == 'U':
            sl += 1
            if sl == 0:
                cv +=1
        elif st == 'D':
            sl -= 1
    return cv

Case 2 (medium): 排队相邻交换问题，排队的每个人有从1到n的序号，按顺序发放。但是有人会bribe前面紧邻的一个人交换位置。每个人最多只能bribe两次。先提供一个序列，求出这个队伍中发生了几次bribe使得位置交换成这样。如21534，2 bribed 1(1次)，5依次bribed 3/4(2次)，累计有3次bribe。但25134这个序列则不满足条件，输出too chaotic，因为5需要bribe超过两次才能到这个位置。
思路1：复杂度为。经过bribe调整后队列上的元素用表示，是在队列上的索引。比较与的大小，并计算比小的元素个数。遍历这个队列，对每个做这样的操作，所有对应的之和。得到的就是bribe调整的次数。注意在测试中一旦则认为too chaotic。
这个问题的假设是每个人只能bribe前面的人，不会bribe后面的人，不然就not make sense了。该思路的缺点是复杂度高。

def minimumBribes(q):
    if not 1<= len(q) <= 10**5:
        return 'again'
    res = 0
    for i, e in enumerate(q):
        t = max(e-i-1,0)
        if t > 2:
            res = 'Too chaotic'
            break
        if i < len(q) - 1:
            tl = [True for term in q[i+1:] if term-e<0]
            if sum(tl)>0:
                res += sum(tl)
    print(res)

思路2：一种复杂度为的算法
用到分治法。

(2020.06.06 Sat)
Case 3 (medium): Power Sum问题幂之和问题。给定一个数字X，和幂次数N，找出X可以用多少种N次幂之和的表达形式。1<=X<=1000，2<=N<=10。例: X=100，N=2，输出3，因为共三种表达。提示用recursion。
思路：讨论者给出的思路，智慧得到了成长。

def cal_num(X, N, num):
    if pow(num, N) < X:
        return cal_num(X, N, num+1) + cal_num(X-pow(num,N), N, num+1)
    elif pow(num, N) == X:
        return 1
    else:
        return 0
ans = cal_num(X, N, 1)

(2020.09.21 Mon)
Case 4 Minimal absolute difference in a list 序列中的最小绝对值
原题在这里
一个list中的元素两两计算差的绝对值，找出其中的最小值。
如果从头遍历，则需要计算每个元素与其后的元素的abs diff，复杂度为。降低复杂度，首先可以对元素排序，用复杂度为的排序算法，之后只需遍历一次排序好的序列，计算相邻元素的值，这种算法的复杂度是即。

def min_abs_diff(arr):
    arr = sorted(arr)
    ma = min(abs(x-y) for x,y in zip(arr, arr[1:]))
    return ma