2018/9/9 字节跳动笔试 ac三道(附思路)
好多都是 Leetcode 原题， 或者改编的。
1. 最大不重复子串
思路：
用一个 map used_char 保存所有字符出现的最后一次位置。
max_length 记录最大不重复子串的长度
begin 记录每一个不重复子串的起始位置
对字符串的字符进行一次遍历
-
如果这个字符之前出现过，并且当前不重复子串的起始位置小于等于其位置:
更新 begin
-
否则
更新 max_length
def get_max_substring(s):
begin = 0
max_length = 0
used_char = {}
for i in range(len(s)):
s_i = s[i]
if s_i in used_char and begin <= used_char[s_i]:
begin = used_char[s_i] + 1
else:
max_length = max(max_length, i - begin + 1)
used_char[s_i] = i
return max_length
2. 所有看做一个整体的部门（寻找孤岛）
只过了 80， 应该是用例的问题
思路:
result = 0 保存结果
dfs 函数深度遍历，把所有相邻的 1 设为 0
遍历一遍二维数组，如果值为1, 用 dfs 函数把所有相邻的 1 设为 0
def get_single_department(array, M):
def dfs(array, i, j):
# 把 array[i][j]旁边的所有1设为0
if i < 0 or j < 0 or i >= M or j >= M or array[i][j] != 1:
return
array[i][j] = 0
dfs(array, i + 1, j)
dfs(array, i - 1, j)
dfs(array, i, j + 1)
dfs(array, i, j - 1)
if not array:
return 0
result = 0
for i in range(M):
for j in range(M):
if array[i][j] == 1:
dfs(array, i, j)
result += 1
return result
有效ip
没 ac 就不放代码了
讲下思路：
ip 分为四段，无非就是把每一段找出来。不符合要求，回溯。
合法 UTF-8
前面用例错了导致我想很久。。后来时间不够按照自己的思路写了写 a了40 md
抖音红人
按照自己的暴力思路写了下，本来以为会超时，结果ac了。
用两个 map: fensi_map 和 follower_map （不知道粉丝英语怎么拼，索性就用汉语拼音了，蛤蛤）
follower_map 存储一个人的所有关注者
fensi_map 存储 一个人的所有粉丝
数据结构是 int -> set ，因为 set 查找元素是否存在的复杂度为1
初始化
- 初始化 follower_map ，遍历一下输入
- 把自己添加到关注的人的粉丝列表中
设置一个 flag 表示搜索是否停止，然后进入下面的循环:
flag = False
对每一个人:
对他关注的每一个人:
对他的所有粉丝：
如果他的粉丝不在他关注的人的粉丝列表中（好绕）:
加进去
flag 设为 True 表示有新的更新
停止条件就是 flag 为 False
大概思路就是这样，不过我觉得用图论的知识可能会简单一点，不过不太会=-=
def get_all_people_number(array, N, M):
fensi_map = defaultdict(set) # 一个人的所有粉丝
follower_map = defaultdict(set) # 一个人关注的所有人
for i in range(0, 2 * M, 2):
follower_map[array[i] - 1].add(array[i + 1] - 1)
for i in range(N):
for j in follower_map[i]:
if i not in fensi_map[j]:
fensi_map[j].add(i)
flag = True
while flag:
flag = False
for i in range(N):
for j in follower_map[i]:
for fensi in fensi_map[i]:
if fensi not in fensi_map[j]:
fensi_map[j].add(fensi)
flag = True
for i in range(N):
fensi_map[i].add(i)
result = 0
for key in fensi_map.keys():
if len(fensi_map[key]) == N:
result += 1
return result
