秋招有意思的机器学习算法笔试题

给定一个只由abc组成的字符串，求里面abc字串的个数。
计数法

def count_abc(s):
    a, ab = 0, 0
    c = 0
    for i in s:
        if i == 'a': a += 1
        elif i == 'b': ab += a
        else:
            c += ab
    return c

s = 'abbcabc'
print(count_abc(s))

最长重复字符串

# -*- coding: utf-8 -*-
# @Date : 2018/8/27
# @Author  : wqs

# n ** 3的复杂度是先枚举长度 1 - len(n)//2
# 然后判断当前字符串是否出现在剩下的字符串里面

def find_longest_repeating_strings1(s):
    n = len(s)
    for l in range(n // 2, 0, -1):
        for i in range(0, n - l):
            if s[i:i + l] in s[i + l:]:
                return s[i:i + l]
    return ''

# 这是采用后缀，复杂度是n * n log n

def find_common_string(s1, s2):
    i, j = 0, 0
    while i < len(s1) and j < len(s2) and s1[i] == s2[j]:
        i += 1
        j += 1
    return i, s1[:i]

def find_longest_repeating_strings(s):
    n = len(s)
    suffix = [s[i:] for i in range(n)]
    suffix.sort()
    _max = 0
    res = ''
    for i in range(n - 1):
        for j in range(i + 1, n):
            a, b = find_common_string(suffix[i], suffix[j])
            if a > _max:
                _max = a
                res = b

    return res

s = 'abacdbacf'
print(find_longest_repeating_strings(s))

最长不重复子串

# 用字典记录上一次出现的位置，如果发现在字典中并且位置大于left，说明left需要更新了
class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        res = 0
        left = 0
        d = {}

        for i, ch in enumerate(s):
            if ch in d and d[ch] >= left:
                left = d[ch] + 1
            d[ch] = i
            res = max(res, i - left + 1)
        return res

k阶斐波那契数列
已知K阶斐波那契数列定义为： f0 = 0, f1 = 0, … , fk-2 = 0, fk-1 = 1; fn = fn-1 + fn-2 + … + fn-k , n = k ,...
①：f(m)=f(m-1)+f(m-2)+…+f(m-k)
②：f(m-1)=f(m-2)+f(m-3)+…+f(m-k-1)
①-②: f(m)-f(m-1)=f(m-1)-f(m-k-1)
f(m)=2f(m-1)-f(m-k-1)

def KFibonacci(n, k):
    dp = [0] * (n)
    dp[k - 1] = 1
    dp[k] = 1

    for i in range(k + 1, n):
        dp[i] = 2 * dp[i - 1] - dp[i - k - 1]

    return dp

print(KFibonacci(15, 10))

字符串转int

int my_atoi(const char *str) {
    int sign = 1, base = 0, i = 0;
    while (str[i] == ' ') { i++; }
    if (str[i] == '-' || str[i] == '+') {
        sign = 1 - 2 * (str[i++] == '-');
    }
    while (str[i] >= '0' && str[i] <= '9') {
        // 7 设计的很巧妙，int_max, int_min的值最后一位就是7和8
        // 用来判断是否要越界了
        if (base >  INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) {
            if (sign == 1) return INT_MAX;
            else return INT_MIN;
        }
        base  = 10 * base + (str[i++] - '0');
    }
    return base * sign;
}

def is_complete_tree(root):
    if not root: return True
    queue = [root]
    flag = False
    while queue:
        cur = queue.pop(0)
        if cur:
            if flag: return False   #第一次出现None,如果是完全二叉树那么后面的都应该是None
            queue.append(cur.left)  #否则就不是。
            queue.append(cur.right)
        else:
            flag = True
    return Tru