Algorithms.1

數組

代码

• 寻找字符串中最长不重复字符串

使用一个dict，key存出现的字符，value存key最后出现的index，遍历字符串时更新dict

def longest_non_repeat(string):
    start = 0
    used_char, temp = {}, ""

    for index, char in enumerate(string):
        if char in used_char and start <= used_char[char]:
            if len(temp) < index - start + 1:
                temp = string[start:index]
            start = used_char[char] + 1

        used_char[char] = index
    return temp

s = "abcabcdddabcdftghooooabcdftghoo"
subs = longest_non_repeat(s)
assert subs == "abcdftgho"

• 找出截断区间

遍历截断数组成员，如果截断成员等于开始区间，开始index加一，如果成员大于开始值就将前面区间，最后带上尾部

def missing_ranges(arr, lo, hi):
    res, start = [], lo

    for n in arr:
        if n == start:
            start += 1
        elif n > start:
            res.append((start, n - 1))
            start = n + 1

    if start <= hi:
        res.append((start, hi))

    return res

arr = [4, 9]
lo = 1
hi = 15

res = missing_ranges(arr, lo, hi)

assert len(res) == 3
assert res[0] == (1, 3)
assert res[1] == (5, 8)
assert res[2] == (10, 15)

• 移动zeros

跳过成员为0的，并计算为0的次数

def move_zeros(array):
    res, num = [], 0

    for i in range(len(array)):
        if array[i] is 0:
            num += 1
        else:
            res.append(array[i])

    return res + [0] * num

assert move_zeros([False, 1, 0, 1, 2, 0, 1, 3, "a"]) == [
    False, 1, 1, 2, 1, 3, "a", 0, 0]

• 旋转

def rotate(arr, k):
    len_arr = len(arr)
    k %= len_arr
    return arr[len_arr - k:] + arr[:-k]


assert rotate([1, 2, 3, 4, 5, 6, 7, 8], 4) == [5, 6, 7, 8, 1, 2, 3, 4]

• 找出连续区间

数组成员前一个和后一个相减，过滤掉绝对值为1的，最后通过index找出连续区间

def summarize_ranges(arr):
    rec = [arr[i] - arr[i - 1] for i in range(1, len(arr))]
    idx = [index for index, x in enumerate(rec) if x != 1]

    res, start = [], 0
    for x in idx:
        res.append((arr[start], arr[x]))
        start = x + 1
    res.append((arr[start], arr[-1]))

    return res


arr = [0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 20, 21]
res = summarize_ranges(arr)
assert res[0] == (0, 2)
assert res[1] == (4, 5)
assert res[2] == (7, 11)
assert res[3] == (20, 21)