某厂算法笔试记录

算法

第一次远程笔试,本来是以为leetcode类似,结果和预想的有点差别,然后测试用例和leetcode也不太一样,样例输入也不太相似, 做的很不理想. 大致记录下, 题目记得不是很清楚只能大概写下.

使环上三点中任意两点距离大于k

输入格式: n, k, a1, a2, a3 n为环上点的个数 k为间距大小 a1, a2, a3为指定点的位置,节点一次只能动一次,输出最少需要的移动次数

比如6, 2, 1, 2, 3. 我们需要将节点1往左移动一次,节点3往右一次即可满足,总共移动2次,所以应该返回2

笔试的时候想法是取三点任两点中距离中最小的两组, 从而确定最低需要的次数, 代码如下. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def least_move(n, k, a1, a2, a3):
    # 排除不满足的
    if n // 3 < k:
        return -1

    # 考虑环首尾相连
    def distance(a, b):
        abs_v = abs(a - b)
        return min(abs_v, abs(n - abs_v))


    d = [distance(a1, a2), distance(a1, a3), distance(a2, a3)]
    d.sort()
    d.pop()

    # 最近的两组都满足, 返回0
    if d[0] >= k and d[1] >= k:
        return 0

    # 最近的两组都需移动到k距离
    elif d[0] < k and d[1] < k:
        return 2 * k - d[0] - d[1]

    # 一组大于k, 一组小于k, 先移动中间再考虑移动小于k侧
    else:
        larger = max(d)
        less = min(d)
        # k - less 为中间点移向large,直到距离large为k还不满足只能移动less
        # 后者为中间点移向large过程中就满足了
        return max(k - less, k - less - (larger - k))

# print(least_move(12, 4, 1, 2, 7))
# 应该是3, 2往右1次, 1往左2次

同花顺

给一堆输入, 检测其中的同花顺(仅5张), 感觉是针对c语言的,用python感觉简单不少,不过给出的样例过了但是提交之后结果错误,不是很理解哪里写错了.

这里简化一下问题, 给出一个字典, key为牌的大小, value为此牌的数量, 每找到一个同花顺, 字典中对应key的value-1(即不放回).

目标为找出手牌中最大同花顺数量

不确定写错没,这里直接写的检测所有同花顺的函数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def flush(dict1):
    found = 1
    flush_list = []
    keys = []
    for k, v in dict1.items():
        if v > 0:
            keys.append(k)

    while found == 1:
        found = 0
        left = 0
        right = 0
        while right < len(keys):
            if keys[right] - keys[left] == right - left:
                right += 1
            else:
                left = right

            if right - left == 5:
                found = 1
                flush_key = keys[left:right]
                flush_list.append(flush_key)
                for key in flush_key:
                    dict1[key] -= 1

                keys = []
                for k, v in dict1.items():
                    if v > 0:
                        keys.append(k)
                break
    return flush_list
# test = {1:2, 2:2, 3:2, 4:3, 5:3, 6:3, 7:1, 8:1, 9:1, 10:1}
# print(flush(test))
# [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [4, 5, 6, 7, 8]]

好数组

给出一个长度为n的数组, 目标是让其变成n-1且仅n-1个元素相同的数组,具体记得不太清了,样例倒是记得一些 输入: [1, 2, 2, 2, 5] 输出: 1 解释: 只需要将1变为2即可

输入:[1, 1, 1] 输出1: 解释: 将随便一个1变成0或者2即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 好数组
from collections import Counter
def good_list(lst):
    counter = Counter(lst)
    keys = counter.keys()
    if len(keys) == 1:
        return 1
    elif len(keys) == 2 and (1 in counter.values()):
        return 0

    mean = lambda x: sum(x)/len(x)
    sorted_list = sorted(lst)
    mean_all = mean(sorted_list)
    # 去除一个极端值然后依据平均数来移动
    mean_without_last = mean(sorted_list[:-1])
    mean_without_first = mean(sorted_list[1:])
    # 对平均数影响越大说明越极端
    # 去除最大值更好
    if mean_all - mean_without_last > mean_without_first - mean_all:
        # 向上取整还是向下取整取决于两边元素的数量,最终取min就行
        target_floor = int(mean_without_last)
        target_ceil = target_floor + 1
        res_floor = 0
        res_ceil = 0
        for i in sorted_list[:-1]:
            res_floor += abs(target_floor - i)
            res_ceil += abs(target_ceil - i)
    # 去除最小值更好
    else:
        target_floor = int(mean_without_first)
        target_ceil = target_floor + 1
        res_floor = 0
        res_ceil = 0
        for i in sorted_list[1:]:
            res_floor += abs(target_floor - i)
            res_ceil += abs(target_ceil - i)
    return min(res_ceil, res_floor)
# print(good_list([2,2,2,2,2,4,4,4,4,8,8,8,8,8,888]))
# output : 30
# to 2: 4 * 2 + 5 * 6 = 38
# to 4: 5 * 2 + 5 * 4 = 30
# to 8: 5 * 6 + 4 * 4 = 46

最大连续子串权重

具体记不太清了,描述有点长. 首先定义连续子串权重: 比如11000111 11, 000, 111分别是三个最大连续子串,则记权重为3

然后要求输出一个字符串的所有子串的最大连续子串权重. 比如1101 1元素:1, 1, 0, 1. 共计4

2元素:11, 10, 01. 11记1, 10记2, 01记2

3元素:110, 101. 110记2, 101记3

4元素:1101. 记3

所以总权重为4+1+2+2+2+3+3 = 17,输出17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 最大连续子串权重
def weight(s):
    left = 0
    right = 0
    length = len(s)
    ret = 0
    while right < length:
        if s[left] == s[right]:
            right += 1
        else:
            left = right
            ret += 1
    return ret + 1

def get_substring(s):
    s_weight = 0
    lens = len(s)
    for i in range(1, lens + 1):
        left = 0
        right = i
        while right <= lens:
            # ret_lst = []
            # ret_lst.append(s[left:right])
            s_weight += weight(s[left:right])
            left += 1
            right += 1

    return s_weight

# print(weight('11000111'))
# should be 3
# 11, 000, 111


# print(get_substring('1101'))
# should be 17

不过最后TLE了,应该还能优化,比如get_substring带一个字典,每算出一个weight先查询,没有的话再计算然后更新,空间换时间. 不过当时没反应过来.