【面试题总结】第二篇

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

---

第一题

题目描述

小明最喜欢吃小熊饼干了。
有一天，她买了一大袋混合口味的小熊饼干，每一块小熊饼干的口味用一个正整数 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)

第二题

题目描述

弹球配对
在某个聚会上，小明得到了一份礼物，里面有 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))

第三题

题目描述

将字符串中指定位置的子字符串反转.
请写出一个方法，将一个字符串中指定位置的字符进行反转，要求时间复杂度 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)

第四题

题目描述

小陈看好某只互联网公司股票，计划进行投资，但小陈作为一名股票投资入门者，不太了解股票的收益情况，让我们来帮助他一起计算一下某段时间内的最大收益。
假设给定一个数组 prices，该数组的第 i 个元素表示该只股票在第 i 天的价格，由于交易所实行 T + 1 机制（即买入当天不能卖出），小陈只能在某一天买入股票，并在将来的某一天才能卖出，并且买入和卖出只能执行一次。
请设计一个算法来计算出在这段时间内小陈能够获取的最大利润是多少，如果不能获取任何利润，那算法结果应该返回 0。

输入描述

一段时间内某只股票每天的价格

输出描述

如果在这段时间内进行交易，所能获取的最大收益。

示例 1

输入

10 12 15 20 9 16 19 23

输出

14

我的解答

if __name__ == "__main__":
    import copy
    prices = input()
    prices = [int(val) for val in prices.split()]
    assert isinstance(prices, list)
    out_prices = []
    for date, buy_in in enumerate(prices):
        prices_copy = copy.copy(prices)
        prices_copy.pop(date)
        sale_out = [val - buy_in for val in prices_copy if (val - buy_in) > 0]
        sale_out.sort(reverse=True)
        if sale_out:
            out_prices.append(sale_out[0])
    out_prices.sort(reverse=True)
    if out_prices:
        print(out_prices[0])
    else:
        print(0)

第五题

题目描述

小熊猫吃竹子。
小花是一只还没有成年的小熊猫，但是聪明的他已经会自己吃竹子了。
小花会把一根长长的竹子分成 a, b, c 三种长度的小段。
现在小花有一根长度为 n 的竹子，聪明的它觉得如果自己把这根竹子分成的小段越多，自己知道的就越多。
但是他却算不出来这根竹子到底最多能被分成几段，你能帮帮小花吗？

输入描述

输入只有一行，有四个被空格分开的整数，分别表示 n, a, b, c ( 1 <= n, a, b, c <= 4000 )；
给出的数据保证至少存在一种正确的分段方法且 1 <= a, b, c <= n

输出描述

你需要输出一个整数，表示小花最多可以将竹子分成几段。

示例 1

输入

6 2 3 4

输出

3

提示

显然，小花可以把这根竹子分成长度均为 2 的三小段，且这是段数最多的方法，所以输出 3。

我的解答

if __name__ == "__main__":
    from itertools import combinations_with_replacement as com_func
    n, a, b, c = map(int, input().split())
    com_str = f"{a}{b}{c}"
    for val in [n, a, b, c]:
        assert (1 <= val <= 4000)
    for val in [a, b, c]:
        assert (1 <= val <= n)

    num, num_one, num_two, num_three = 0, 0, 0, 0
    for val in list(com_func(com_str, 1)):
        if int(val[0]) == n:
            num_one += 1

    for val1, val2 in list(com_func(com_str, 2)):
        if int(val1) + int(val2) == n:
            num_two += 1

    for val1, val2, val3 in list(com_func(com_str, 3)):
        if int(val1) + int(val2) + int(val3) == n:
            num_three += 1

    if num_three != 0:
        num = 3
    elif num_two != 0:
        num = 2
    elif num_one != 0:
        num = 1
    else:
        num = 0

    print(num)

第六题

题目描述

压缩字符串的规则如下：

• 如果字母 x 连续出现 n ( 10000 > n > 1 ) 次，则表示为 (a)n
• 可以嵌套，比如 ((a)2(b)2)2，表示的是 aabbaabb 压缩后的结果
• 只出现一次的字母不进行压缩，a 的压缩后结果仍然为 a。

输入描述

输入为一个字符串的压缩结果

输出描述

请输出压缩前的字符串

示例 1

输入

"(a)2(b)2(c)2"

输出

"aabbcc"

示例 2

输入

"(ab)2c"

输出

"ababc"

示例 3

输入

"((a(b)2)2(c)2)2b"

输出

"abbabbccabbabbccb"

我的解答

import java.util.*;

public class Solution {
    public String decompress(String compressed_str) {
        StringBuilder sb = new StringBuilder("");
        StringBuilder tmp = new StringBuilder("");
        char flag = '(';
        Stack stack = new Stack();
        char[] chars = compressed_str.toCharArray();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            while(i < chars.length && (chars[i] + "").matches("[0-9]")){
                count = count * 10 + Integer.parseInt(chars[i] + "");
                i++;
            }
            count = putUnCompressedValueToStack(count, tmp, stack);
            if(i == chars.length)
            {
                break;
            }
            if (chars[i] =='(') {
                stack.push(chars[i]);
            }else if (chars[i] ==')') {
                tmp = getStackValue(stack, flag);
                stack.pop();
            }else if((chars[i] + "").matches("[a-z]")) {
                if(i < (chars.length-1) && (chars[i+1] + "").matches("[0-9]")){
                    tmp = new StringBuilder("").append(chars[i]);
                }else{
                    stack.push(chars[i]);
                }
            }
        }
        sb = getStackValue(stack, flag);
        return sb.reverse().toString();
    }
    
    public static StringBuilder getStackValue(Stack stack, Character character){
        StringBuilder tmp = new StringBuilder("");
        while(!stack.isEmpty() && stack.peek()!= character){
            tmp.append(stack.peek());
            stack.pop();
        }
        return tmp;
    }
    
    public static int putUnCompressedValueToStack(int count,StringBuilder tmp, Stack stack){
        if(count>0 && tmp.length()!=0){
            for (int j = 0; j < count; j++) {
                for (int k = tmp.length()-1; k>=0; k--) {
                    stack.push(tmp.charAt(k));
                }
            }
        }
        return 0;
    }
}

第七题

题目描述

多抓鱼的仓库在为用户准备订单发货时，需要将订单中的商品从仓库内对应的货架位置上取出，这个过程被称为“拣货”。
为了使拣货人员操作起来更加方便。多抓鱼的仓库管理系统会将不同订单中的商品合并在一起，并按照操作人员的动线来排序。
现在有两个订单 a 和 b，各自一个有序链表来表示订单中的所有物品，链表中的数字表示物品在拣货路径中的顺序。
目前两个链表均为升序，请将这两个订单中的物品合并为一个整体升序的链表，并返回。
题目中使用的是单向链表。

示例 1

输入

{1, 3, 5}, {2, 4}

输出

{1, 2, 3, 4, 5}

我的解答

不会

第八题

题目描述

游戏中的摆摊地图是一个矩阵，里面有很多格子。
每个格子有两种状态，可以摆摊和不可以摆摊。
可以摆摊用 1 表示，否则用 0 表示。
在这块地图中摆摊，要求两个相邻的格子不能同时摆摊（不包括斜着的），即两个摊位不能相邻。
问有多少种摆摊的方案（一个摊位也没有也是一种方案）。

输入描述

第 1 行为两个整数 n，m。( 1 <= n <= 12, 1 <= m <= 12 )
第 2 行到第 n + 1 行为 m 个整数，表示地图中的每个格子是否可以摆摊

输出描述

方案数对 987654321 的取余结果

示例 1

输入

2 3
1 1 1
0 1 0

输出

9

我的解答

不会

第九题

题目描述

给定一个长度为 n ( 2 <= n <= 10^5 ) 的数组 a1, a2, a3, ... , an。
现在你需你需要从中选出一个区间 [i, j] ( 1 <= i <= j <= n )，使得这个区间里的所有数都相同，求出所有选择中最长区间的长度。
但这过于简单，于是给你一个交换两个相邻的数的机会，即你可以选择一个下标 i ( 1 <= i < n ) 并交换 ai 与 ai+1 的值。
你可以选择使用这个机会，也可以不用，求能选出的满足条件的区间的最大长度。

输入描述

第一行一个正整数 n ( 2 <= n <= 10^5 )。
第二行 n 个整数 a1, a2, a3, ... , an (0 <= ai <= 10^5)。

输出描述

一个数，代表满足条件的区间的最大长度。

示例 1

输入

4
1 2 1 2

输出

2

说明

选择交换 a2，a3 可得到新数组 [1, 1, 2, 2]。
此时区间 [1, 2] 里的树都为 1，区间 [3, 4] 里的数都为 2，都满足题目条件，且长度都为 2，都是最长的区间。

示例 2

输入

9
1 1 1 2 3 3 3 4 3

输出

4

说明

选择交换 a8，a9 可得到新数组 [1, 1, 1, 2, 3, 3, 3, 3, 4]。
此时区间 [5, 8] 里的树都为 3，区间长度为 4，是最长的区间。

我的解答

不会

第十题

题目描述

求二叉树叶子结点的个数。
求最深叶子节点的个数，该节点没有左右子节点。

输入描述

会输入一个 string 的对象，通过使用 input() 来获取传入的字符串，记得使用 json.loads() 转成传入的参数。

输出描述

使用 print() 返回结果值。

示例 1

输入

{
    "value":3,
    "left":{
        "value":9,
        "left":{
            "value":15,
            "left":None,
            "right":None
        },
        "right":{
            "value":7,
            "left":None,
            "right":None
        }
    },
    "right":{
        "value":9,
        "left":{
            "value":15,
            "left":None,
            "right":None
        },
        "right":{
            "value":7,
            "left":None,
            "right":None
        }
    }
}

输出

4

我的解答

不会

（本文完）