【面试题总结】第一篇

我的博客中有一个系列，叫做【面试题总结】，这是这个系列的第一篇博文。
这个系列会记录我曾经做过的面试题，每篇十道。随着以后我做的面试题越来越多，这个系列也会相应的持续更新下去。

---

第一题

题目描述

小吉和小特是一对好朋友，他们常常一起玩儿不同的策略游戏。
这天小吉提出了一种新的玩法。
这里一共有 n 个石子，编号从 1 到 n 排成一排。
有一个常数 k，每人可以从 [1, k] 中选择一个数，获取编号连续的 k 个石子。
拿到最后的石子的人赢，也就是最后不能继续取的人输，每个回合都是小吉先手。
假定两人都足够聪明，在给定 n (1 <= n <= 1e6) 的情况下，
如果小吉获胜输出 G win，小特获胜输出 T win。

输入描述

每一行的输入都是 n k 两个数。

输出描述

如果小吉获胜输出 G win，小特获胜输出 T win。

示例 1

输入

3 1

输出

G win

示例 2

输入

4 1

输出

T win

我的解答

if __name__ == "__main__":
    g_win = "G win"
    t_win = "T win"
    n, k = [int(var) for var in input().split()]
    is_zhengchu = n % k == 0 # 是否能整除
    shang = n // k # 商
    yushu = n - shang * k # 余数
    if is_zhengchu:
        # 整除，正好能取完，T win
        if shang % 2 == 0:
            print(t_win)
        else:
            print(g_win)
    else:
        # 不整除
        if yushu < k:
            # 余数小于除数，G 能取完，G win；否则 T win
            print(g_win)
        else:
            print(t_win)

第二题

题目描述

小明最喜欢吃小熊饼干了。
有一天，她买了一大袋混合口味的小熊饼干，每一块小熊饼干的口味用一个正整数 a 表示。
这一大袋饼干一共有 n 块，他把这 n 块饼干依次排成一长列。
从左到右依次编号为第 1 块饼干、第 2 块饼干、 ... 、第 n 块饼干。
于是饼干的口味就组成了一个序列 a1, a2, ... , an。
这时小明的妈妈想考考小明，就给出了 m 个数字 b1, b2, ... , bm ( 1 <= bi <= n )。
对于每一个数字 bi ( 1 <= i <= m )，妈妈想让小明数出从 bi 块饼干到第 n 块饼干中，一共有几种不同的口味。
小明只想吃饼干，回答不上妈妈的问题，你能帮帮小明吗？

输入描述

第一行有两个整数 n, m，分别表示饼干的个数，妈妈给出的数字的个数。
第二行有 n 个整数 ( a1, a2, ... , an )，表示 n 块饼干的口味。
接下来有 m 行，第 i 行有一个整数 bi ( 1 <= bi <= n )，表示妈妈给出的某一个数 ( 1 <= n, m <= 100000, 1 <= ai <= 100000 )。

输出描述

你的输出一共有 m 行，每行一个整数，第 i 行的整数表示从 bi 块饼干到第 n 块饼干中，一共有几种不同的口味。

示例 1

输入

5 3
8 4 5 2 4
1
2
3

输出

4
3
3

提示

第 1 到第 5 块饼干中有 4 种不同的口味，输出 4；
第 2 到第 5 块饼干中有 4 种不同的口味，输出 3；
第 3 到第 5 块饼干中有 4 种不同的口味，输出 3。

我的解答

if __name__ == "__main__":
    n, m = input().strip().split()
    a_list = input().strip().split()
    n, m = int(n), int(m)
    b_list = []
    for m_value in range(m):
        b = int(input()) - 1
        bb = a_list[b:]
        bb_len = len(set(bb))
        b_list.append(str(bb_len))
    result = "\n".join(b_list)
    print(result)

第三题

题目描述

大二学生牛牛参加了本学期的专业必修课操作系统（OS）课程的考试。
不久，教授将所有学生的期中、期末和作业成绩转换成 300 分然后上传到教务系统。
正在看成绩的牛牛突然想起来，自己一定要拿到奖学金。
如果没有拿到 A0 以上的等级就很难拿到奖学金。
教授给出了成绩等级的分配：

等级	名次
A+	第 1 ~ 第 5 名
A0	第 6 ~ 第 15 名
B+	第 16 ~ 第 30 名
B0	第 31 ~ 第 35 名
C+	第 36 ~ 第 45 名
C0	第 46 ~ 第 48 名
F	第 49 ~ 第 50 名

教授将学生的最终成绩先按照降序排序，然后上传至教务系统。
但只是显示了每个人的分数，并未显示成绩等级。
现在请你编写一个程序，帮助牛牛判断自己的成绩属于哪个等级。

输入描述

在第一行，给出了 50 个学生的分数，包括牛牛的分数，用空格分隔（假设每个人的分数均不同）。
第二行给出牛牛的分数。
所有分数都是 0 到 300 之间的整数。

输出描述

输出牛牛的等级成绩。

示例 1

输入

285 271 270 268 264 251 237 236 228 227 226 225 224 217 216 205 198 193 192 190 182 168 165 161 157 146 141 135 127 126 122 114 105 81 80 76 70 67 63 59 55 44 34 24 19 14 9 5 2 1
251

输出

A0

说明

牛牛的分数为 251 分，排名第 6，因此等级为 A0。

示例 2

输入

299 293 291 288 287 286 278 276 275 269 262 260 244 239 236 232 213 209 204 199 197 184 179 178 175 170 167 166 162 158 141 130 128 124 115 111 108 105 63 60 57 54 49 44 40 34 17 11 4 3
4

输出

F

说明

牛牛的分数为 4 分，排名第 49，因此等级为 F。

我的解答

if __name__ == "__main__":
    records = [ int(record) for record in input().split() ]
    x_record = int( input() )
    assert len(records) == 50
    assert x_record in records
    levels = {
        "A+": (1, 5),
        "A0": (6, 15),
        "B+": (16, 30),
        "B0": (31, 35),
        "C+": (36, 45),
        "C0": (46, 48),
        "F": (49, 50)
    }
    records.sort(reverse=True)
    position = records.index(x_record) + 1
    for level, record_range in levels.items():
        min, max = record_range
        if min <= position <= max:
            print(level)
            break

第四题

题目描述

弹球配对
在某个聚会上，小明得到了一份礼物，里面有 n 个弹珠，弹珠的颜色需要匹配起来才好看。
每个弹珠都有自己的编号和颜色号。
小明用一个数组来表示这些弹珠，a[i] 表示编号为 i 弹珠的颜色号。
小明希望将弹珠两两匹配，且得到好看的颜色组合。
好看的标准是两个弹珠的颜色号的和大于等于 L，小于等于 R。
小明想知道，这个数组里面一共有多少个这样的好看组合。

输入描述

第一行三个整数 n, L, R，空格隔开，1 <= n <= 200000, 1 <= L <= R < 1000000000
第二行 n 个整数，空格隔开，其中任意数字的大小范围 [1, 1000000000]。

输出描述

是一个整数，表示满足要求的组合的数量。

示例 1

输入

3 4 7
5 1 2

输出

2

示例 2

输入

5 5 8
5 1 2 4 3

输出

7

我的解答

if __name__ == "__main__":
    n, l, r = [int(value) for value in input().strip().split()]
    a = [int(value) for value in input().strip().split()]
    assert len(a) == n
    result = set()
    for i, value in enumerate(a):
        for j, value2 in enumerate(a):
            if i == j:
                continue
            else:
                if l <= (value + value2) <= r:
                    if i < j:
                        b = f"{i}{j}"
                    else:
                        b = f"{j}{i}"
                    if b not in result:
                        result.add(b)
    print(result)
    print(len(result))

第五题

题目描述

有一个醉汉，初始在坐标为 x ( 0 <= x <= 60 ) 的位置。
每次他会等概率的向左走一步 (x -> x - 1)，或者向右走一步 (x -> x + 1)。
当他走到位置 p ( p < 0 || p > 60 ) 的时候，它会掉下悬崖。
现在给你初始位置 x 和他会走的步数 st ( 1 <= st <= 60 )，问这个醉汉不掉下悬崖的概率是多少？
（整个图可视为一维坐标系）

输入描述

第一行给出样例数 T ( 1 <= T <= 1000 )。 接下来 T行，每行两个整数x, st`，分别表示醉汉的初始位置和他回走的步数

输出描述

输出一个浮点数，表示醉汉不掉下悬崖的概率。
当误差不超过 1e-6，视答案正确。

示例 1

输入

1
1 2

输出

0.7500000000

说明

只有连续像左走两步才会掉下悬崖，这个概率是 1/4。
所以不会掉下悬崖的概率是 3/4，即 0.75。

示例 2

输入

1
0 1

输出

0.5000000000

我的解答

if __name__ == "__main__":
    def is_alive(position):
        print(f"position is {position}")
        if 0 <= position <= 60:
            return True
        else:
            return False
    def go_left(x):
        return x - 1
    def go_right(x):
        return x + 1
    alive, dead, total = 0, 0, 0
    t = int( input() )
    for i in range(t):
        x, st = input().strip().split()
        x, st = int(x), int(st)
        left, right = x, x
        for j in range(st):
            total += 2
            left = go_left(left)
            right = go_right(right)
            if is_alive(left):
                alive += 1
            else:
                dead += 1
            if is_alive(right):
                alive += 1
            else:
                dead += 1
    print(
        "%.10f" % (alive / total)
    )

第六题

题目描述

给定一个 nums 数组，由一些非负整数组成，现需要将它们进行排列并拼接。
每个数不可拆分，使得最后的结果最大。返回值需要是 string 类型，否则可能会溢出。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 10000

示例 1

输入

[30, 1]

输出

"301"

示例 2

输入

[2, 20, 23, 4, 8]

输出

"8423220"

示例 3

输入

[2]

输出

"2"

我的解答

class Solution:
    def solve(self, nums):
        from itertools import permutations
        assert isinstance(nums, list)
        nums = map(lambda x: str(x), nums)
        num_p = permutations(nums)
        max_num = -1
        for result in num_p:
            int_result = int("".join(result))
            if max_num == -1:
                max_num = int_result
            else:
                assert max_num != -1
                if max_num < int_result:
                    max_num = int_result
        return str(max_num)

第七题

题目描述

写一个中划线字符串转驼峰的算法

示例 1

输入

"border-bottom-color"

输出

"borderBottomColor"

我的解答

class Solution:
    def test(self, str):
        str_s = str.split("-")
        if len(str_s) == 1:
            return str
        a = str_s[0]
        b = str_s[1:]
        b_upper = list(map(lambda x: f"{x[0].upper()}{x[1:]}", b))
        return f"{a}{''.join(b_upper)}"

第八题

题目描述

编写一个方法 count，计算出字符串中，两个相同的字符中间最少隔着多少个字符（字符串最大长度为 10000）。

示例 1

输入

"你是中国人，你就是中国人"

输出

5

示例 2

输入

"是你，你是中国人，你中国人"

输出

1

示例 3

输入

"你是中国人"

输出

-1

示例 4

输入

"你你是中国人"

输出

0

我的解答

class Solution:
    def count(self, str):
        diff = {}
        for index, value in enumerate(str):
            if value not in diff:
                diff[value] = []
            diff[value].append(index)
            diff[value].sort()
        result = []
        for index_list in diff.values():
            if len(index_list) <= 1:
                continue
            num = index_list[1] - index_list[0] - 1
            result.append(num)
        result.sort()
        if len(result) == 0:
            return -1
        return result[0]

第九题

题目描述

将字符串中指定位置的子字符串反转.
请写出一个方法，将一个字符串中指定位置的字符进行反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

输入描述

一个字符串 str, m, n
其中 m, n 为整数且 0 <= m < n < 字符串的长度。

输出描述

子字符串反转的新字符串

示例 1

输入

abcdefghijk, 2, 4

输出

abedcfghijk

我的解答

if __name__ == "__main__":
    foo = input()
    foo_str, m, n = [val.rstrip(",") for val in foo.split()]
    m, n = int(m), int(n)
    assert 0 <= m < n < len(foo_str)
    start_m = foo_str[0:m]
    m_n = foo_str[m+1:n]
    n_end = foo_str[n+1:]
    result = "{}{}{}{}{}".format(
        start_m,
        foo_str[n],
        m_n,
        foo_str[m],
        n_end
    )
    print(result)

第十题

题目描述

金额展示优化。
商家在看当月交易额时，需要将所展示的金额整数部分每隔三位就用 , 分开。
例如：9777.5 -> 9,777.5 元。

输入描述

使用 input() 来获取传入的字符串，使用 print() 来返回结果值。

输出描述
示例 1

输入

9777.5

输出

9,777.5

我的解答

if __name__ == "__main__":
    num = input()
    num_len = len(num)
    zheng = ""
    xiao = ""
    if "." in num:
        zheng, xiao = num.split(".")
    else:
        zheng = num
    comma = num_len // 3 + 1
    zheng_list = []
    for i in range(comma):
        pre = -3*i-1
        tal = -3*i-4
        value = zheng[pre:tal:-1]
        zheng_list.insert(0, value[::-1])
    one = ",".join(zheng_list).strip(",")
    if "." in num:
        result = ".".join([one, xiao])
    else:
        result = one
    print(result)