azl397985856/leetcode

【秋招】牛客2019 字节跳动秋招编程题汇总

azl397985856 opened this issue · 5 comments

azl397985856 commented

题目地址

https://www.nowcoder.com/test/16516564/summary

1. 大锤的自动校对程序

题目描述

我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：

  1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
  2. 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
  3. 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！
……
万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……

请听题：请实现大锤的自动校对程序

输入描述:
第一行包括一个数字N，表示本次用例包括多少个待校验的字符串。

后面跟随N行，每行为一个待校验的字符串。

输出描述:
N行，每行包括一个被修复后的字符串。

输入例子1:
2
helloo
wooooooow

输出例子1:
hello
woow

思路

第一想法是用正则实现，简单直接。

代码

const n = Number(readline());
let cur = ""
while(cur = readline()) {
    console.log(cur.replace(/([a-z])\1{1,}/g, "$1$1").replace(/([a-z])\1([a-z])\2/g, "$1$1$2"))
}

复杂度分析

  • 时间复杂度：取决于正则引擎的实现
  • 空间复杂度：取决于正则引擎的实现

2. 大锤特工

题目描述

我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议

  1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。
  2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过D。

我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！
……
万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！

请听题：给定N（可选作为埋伏点的建筑物数）、D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
注意：

  1. 两个特工不能埋伏在同一地点
  2. 三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用

输入描述:
第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)

第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）

输出描述:
一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模

输入例子1:
4 3
1 2 3 4

输出例子1:
4

例子说明1:
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

输入例子2:
5 19
1 10 20 30 50

输出例子2:
1

例子说明2:
可选方案 (1, 10, 20)

思路

思路是：

  • 固定两个端点，两个端点的距离是 X (X<=D)。
  • 然后将第二个和三个特工塞到两个端点内的 X 个 空位即可。
  • 在 X 个位置上塞两个人的组合数是 $C_X^(2)$， 即 $N*(N - 1) / 2$。

代码

实际上可以利用 dict，单调栈等技巧加速寻找右边界的过程。

n, dist = map(int, input().split())
nums = list(map(int, input().split()))

ans = l = 0
r = 2 # ∵ D >= 1

while l < n - 2:
    while r < n and nums[r] - nums[l] <= dist:
        r += 1
    if r - 1 - l >= 2:
        cnt = r - l - 1
        ans += cnt * (cnt - 1) // 2
    l += 1

print(ans % 99997867)

复杂度分析

  • 时间复杂度：$O(N ^ 2)$，加速之后可以到 $O(N)$
  • 空间复杂度：$O(1)$

3. 雀魂

略

4.猫的运动

题目描述

小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。

因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。
现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。

输入描述:
第一行包含一个正整数N，代表测试用例的个数。

每个测试用例的第一行包含一个正整数M，代表视频的帧数。

接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2>
所有用例的输入特征总数和<100000

N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。
特征取值均为非负整数。

输出描述:
对每一个测试用例，输出特征运动的长度作为一行

输入例子1:
1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1

输出例子1:
3

例子说明1:
特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3

思路

用一个 dict 记录上一帧的最长特征运动，枚举这一帧的运动信息并更新 dict即可，在这个过程记录最大值，类似滚动数组。

代码

n = int(input())

while n > 0:
    n -= 1
    ans = 1
    pre = {}
    for _ in range(int(input())):
        l = list(map(int , input().split()))
        k = l[0]
        cur = {}
        for j in range(k):
            k = (l[2 * j + 1], l[2 * j + 2])
            if k in pre:
                cur[k] = pre[k] + 1
                ans = max(ans, cur[k])
            else:
                cur[k] = 1
        pre = cur
    print(ans)·

复杂度分析

  • 时间复杂度：$O(N * K)$，，其中 K 为所有帧的特征平均值
  • 空间复杂度：$O(M)$，其中 M 为所有帧的特征最大值。

5. 小明的毕业旅行

题目描述

小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

输入描述:
城市个数n（1<n≤20，包括北京）

城市间的车票价钱 n行n列的矩阵 m[n][n]

输出描述:
最小车费花销 s

输入例子1:
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出例子1:
13

例子说明1:
共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。

思路

典型的旅行商问题（TSP）， DP即可解决。

copy 一个模板过来改改就行了。

代码

改成非递归的 bottom-up 性能更好

import functools
n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
visited = 1 << (n - 1)
@functools.lru_cache(None)
def dp(fr, to):
    if to == 0: return graph[fr][0]
    ans = float('inf')
    for i in range(1, n):
        if ((to >> (i - 1)) & 1) == 1:
            to ^= 1 << (i - 1) # mark visited
            ans = min(ans, graph[fr][i] + dp(i, to))
            to ^= 1 << (i - 1) # unmark
    return ans
    
print(dp(0, visited - 1))

复杂度分析

  • 时间复杂度：$O(2^N*N^2)$
  • 空间复杂度：$O(2^N*N)$

6. 硬币找零

题目描述

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品，请问最少他会收到多少硬币？

输入描述:
一行，包含一个数N。

输出描述:
一行，包含一个数，表示最少收到的硬币数。

输入例子1:
200

输出例子1:
17

例子说明1:
花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。

思路

完全背包问题，力扣硬币找零的简化版。

代码

n = 1024 - int(input())
dp = [1024] * (n + 1)
dp[0] = 0

for i in range(n + 1):
    for coin in [1, 4, 16, 64]:
        if i >= coin:
            dp[i]= min(dp[i], dp[i - coin] + 1)
print(dp[-1])

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

代码

7.机器人跳跃

see: #423

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

stale commented

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

cherie-wuyajun commented
fyyzkd commented
peak-up-fsl commented
stale commented

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.