网易笔试——算法卷

拆分句子

给定一个字符串，统计其中不重复的英文单词的数量。

补充说明：

1. 字符串只会出现：数字、英文单词、间隔符
2. 单词之间的间隔符包括空格、!、,
3. 统计单词数量时要求不包括数字
4. 重复单词记为1

示例：

输入：

“Hey, how its going?Not bad”

输出：

6

说明：

单词分别为hey、how、its、going、not、bad

这里我不记得句子是啥了，就自己随便编了一个

思路

1. 价格字符串按照间隔符分割为单词列表
2. 过滤掉数字
3. 全部转化为小写
4. 用集合去重
5. 计算数量

代码

class Solution:
    def countWords(self , s: str) -> int:
        words = s.replace(',', ' ').replace('!', ' ').split()
        unique_words = set(word.lower() for word in words if not word.isdigit())
        return len(unique_words)

这题为核心代码模式

时间复杂度

时间复杂度O(n)，空间复杂度O(n)

最小数

据说是leetcode179最大数的变体，我还没去看

给定一组非0整数nums，重新排列每个数的顺序，使之组成一个最小的数

注意：

1. 有且只有一个负数
2. 输出结果很大需要返回的是字符串
3. 不可拆分数字

示例1

输入

10 2

输出

102

示例2（得亏编译器还有记录，不然我根本想不起来）

输入

-9 30 3 34 5

输出

-9534330

思路

1. 解决负数，如果存在直接放最前面
2. 自定义比较函数，这里是需要字符加和而不是数值加和，30 + 3 = 303而不是33，303 < 330
3. 使用比较函数进行比较
4. 如果结果为空返回0

代码

这个为ACM模式，只过了70%，有知道问题的记得评论下啊🤣

def smallest_number(nums):
    if not nums:
        return ''
    negative = next((num for num in nums if num < 0), None)
    positive = [str(num) for num in nums if num >= 0]
    
    def compare(a, b):
        if a + b > b + a:
            return 1
        elif a + b < b + a:
            return -1
        else:
            return 0
    positive.sort(key = cmp_to_key(compare))
    
    result = ''.join(positive)
    if negative:
        result = str(negative) + result
    return result if result else '0'
nums = list(map(int, input().split()))
print(smallest_number(nums))

时间复杂度

时间复杂度O(n + m log m)，空间复杂度O(n)

验证树是否成立

给定编号从0到n - 1的n个结点，给定一个整数n和一个edges列表。其中$edges[i] = [a_i, b_i]$表示图中两个结点之间存在一个无向边

如果这些便能够组成一个有效的树，则返回true，否则返回false

示例

输入

5, [[0, 1], [0, 2], [0, 3], [0, 4]]

输出

true

思路

1. 检查边的数量（按照树的特性，需要符合n - 1）
2. 用并查集合并节点，这里有两个思路，一个用并查集一个用DFS。我选的并查集
3. 检查最后是否只有一个连通分量

代码

这题也是核心代码

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges)!= n - 1:
            return False
        parent = list(range(n))
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(x, y):
            parent[find(x)] = find(y)
        for a, b in edges:
            if find(a) == find(b):
                return False
            union(a, b)
        return len(set(find(x) for x in range(n))) == 1

时间复杂度

时间复杂度O(n)，空间复杂度O(n)

最近点对问题

给定一个二维平面上的n个点，找到距离最近的两个点，并输出它们的坐标。其中点集是由一组点坐标对组成，每个坐标对都表示点在平面上的位置

输入描述

一个包含所有坐标对的列表，数量需要大于等于2，（小于边界忘了）

输出描述

最近两个点坐标

要求

需要时间复杂度O(nlogn)

这个题目我没做出来，就不写思路和代码了，大家可以去搜一下。然后题目的话是ACM模式