第16章面试题

[1.最小k个数【腾讯】](https://leetcode.cn/problems/smallest-k-lcci/description/)
```py
class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        heap = []
        for num in arr:
            heapq.heappush(heap, -num)
            if len(heap) > k:
                heapq.heappop(heap)
        return [-num for num in heap]
```
[2.对角线遍历【腾讯】](https://leetcode.cn/problems/diagonal-traverse/description/)

![](/media/202503/2025-03-18_233331_7604810.7347645695898414.png)
```py
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if len(mat) == 0:
            return []
        m, n = len(mat), len(mat[0])
        res = []
        for cur_line in range(m + n - 1):
            row_begin = 0 if (cur_line + 1) <= n else cur_line + 1 - n
            row_end = m - 1 if cur_line + 1 >= m else cur_line
            if cur_line % 2 == 1:
                for i in range(row_begin, row_end + 1):
                    res.append(mat[i][cur_line - i])
            else:
                for i in range(row_end, row_begin - 1, -1):
                    res.append(mat[i][cur_line - i])
        return res
```
[3.子集【美团】](https://leetcode.cn/problems/subsets/?envType=study-plan-v2&envId=top-100-liked)

[4.对换域名位置]()
```
input = "www.abc.com.cn"
output = "cn.com.abc.www"
```
要求不使用额外空间

[5. 字节1面]()
计算 x 的 n 次幂的函数
```python
def pow1(x,n):
    if n == 0:
        return 1
    res = 1
    abs_n = abs(n)
    for _ in range(abs_n):
        res *= x
    if n < 0:
        return 1/res
    else:
        return res
```

```python
def pow2(x,n):
    if n == 0:
        return 1
    if n == 1:
        return x
    if n < 0:
        return 1/pow2(x,-n)
    half = pow2(x, n//2)
    if n % 2 == 0:
        return half * half
    else:
        return half * half * x
```

第16章 面试题

第16章面试题