Linux运维工程师笔试题第二十四套

在一个整形数组中， 1 ≤ a[i] ≤ n (n = 数组长度), 有些数出现两次，有些数出现一次。需要找到所有出现两次的数字。算法复杂度越小越好。比如[4, 3, 2, 7, 8, 2, 3, 1]，能返回[2,3]
【思路】首先这个数组长度是n，那么索引就是0～n-1。要取两个一样的数，因为他们的值是一样的，但是索引又不一样，怎么能够搭配“值跟索引”的关系呢？就借用值一样的前提，那么他们这个“数对应的索引”的值是同一个值，那么这个值可以取负来标记。当第二次取的时候，发现是负数则加入到一个新的列表里，最后这个列表的内容就是结果。

def find_duplicates(nums):
    res = []
    for x in nums:
        idx = abs(x) - 1		# 这里为啥是减1？因为长度是n，索引就是0～n-1
        if nums[idx] < 0:
            res.append(abs(x))
        else:
            nums[idx] = -1 * nums[idx]
    return res

nums = [4, 3, 2, 7, 8, 2, 3, 1]
print(find_duplicates(nums))  # 输出: [2, 3]

如果你想玩暴力，那么就是每一个值都要比较，原列表元素少还好办，如果元素很多的话，需要比较n的平方次，计算量非常大，如果不考虑时间复杂度可以这么搞。

def findDuplicates(nums):
    res = []
    for i in range(len(nums)):
        count = 0
        for j in range(len(nums)):
            if nums[j] == nums[i]:
                count += 1
        if count == 2 and nums[i] not in res:
            res.append(nums[i])
    return res

数组中，所有数字都出现两次，只有一个数字出现一次，找到他。
【思路】要找出数组中唯一出现一次的数字（其余所有数字均出现两次），最高效的方法是使用异或运算（^）。

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

# 示例调用
if __name__ == "__main__":
    sol = Solution()
    print(sol.singleNumber([4, 1, 2, 1, 2]))  # 输出: 4
    print(sol.singleNumber([2, 2, 1]))        # 输出: 1
    print(sol.singleNumber([1]))              # 输出: 1（单个元素）

一维数组查找指定数字。无序数组怎么查？有序数组呢？
无需数组好像只能暴力轮询，有序数组可以用“二分查找”法：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母集合相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

【思路】字符串相同但是排列不同，那么意思就是排列相同的话他们就是一个字符串。如何排列相同呢？那么就用到sort()，所以我们可以利用排列后是同一个字符串作为一个key，而具体的不同排列作为value。所以我们可以上来建立一个dict，格式是{同一个字符串：[]}，然后一点一点把后面的[]填满。那么这个格式的dict可以用defaultdict来创建。

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))。# 这里进行对字符串进行按照字母排序
        groups[key].append(s)
    return list(groups.values())

# 示例测试
input_strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(input_strs))

唠唠mysql的having语句
HAVING 是 SQL 中用于过滤分组后结果的子句，通常与 GROUP BY 一起使用，可以在 HAVING 中使用聚合函数的别名。
与 WHERE 的区别：
a. WHERE 在分组前过滤原始数据。
b. HAVING 在分组后过滤聚合结果。
不要用其他内置工具，纯手动计算阶乘来计算 1! + 2! + 3! + … + 20! 的和
【思路】如果用内置工具，就用math.factorial，直接拿到阶乘。但是题目里要求不要用，就可以先写一个函数，函数的能力就是阶乘。传入的是20，然后设定一个a=1，然后range(1,21)，a轮询自己乘自己得到阶乘。然后再加上一个for循环求和即可。

def jiecheng(n:int):
    a = 1
    for i in range(1,n+1):
        a = a*i   # 直接用上一个结果*最新
    return a
    

total = 0
for x in range(1,21):
    total = total + jiecheng(x)

print(total)

利用递归方法求5!

def jiecheng(n):
    if n == 1:
        return 1
    else:
        return n * jiecheng(n-1)

if __name__ =="__main__":
    print(jiecheng(5))

给定一个字符串，将其进行压缩，例如abbcccdddd，压缩后为a1b2c3d4

total = ''
str1 = 'abbcccdddd'
str2 = sorted(set(str1))
for i in str2:

    print(i,str(str1.count(i)))
    total = total + str(str1.count(i))+i

print(total)

大表join小表，有什么加速手段？
将小表作为驱动表（Build Side）,逐条扫描小表，然后在大表中查找匹配数据。因为小表行数少，减少循环次数。
在大表的 Join 字段上建立索引，这种适合“小表驱动 + 大表的 Join 字段无索引”的场景。
在 Join 前对大表进行过滤，如果大表按 Join 字段分区，利用分区信息跳过无关分区，这样是为了减少参与 Join 的数据量。
给定一个字符串s，找出最长的不含重复元素的“最长子串”。比如s=’abcabcbb’，最长的子串就是‘abc’。
【思路】因为是不重复元素，那么就用set()。这个要用到滑动块的思路，这个滑动块最开始长度为0，然后右移一格，发现里面的元素不在这个set()里，就继续右移一格，发现元素在set()里，就左移，直到左右指针相遇代表已经遍历了整个字符串s。然后取这个set()里最多的元素个数就行了。


def longest_unique_substring(s: str) -> int:
    sw = set()  # 这个是一个滑动窗口
    l = res = 0 # 左指针 和 result = 0
    for r in range(len(s)):
        while s[r] in sw:  # 这里用while是因为有可能是abb这样连续2个b的情况，持续移除左边界字符
            sw.remove(s[l])
            l = l+1 #去除最左边的元素，然后左移一格

        sw.add(s[r])
        res = max(res,r-l+1) # 这里加1的原因是l r都是索引，是从0开始的，而数量是从1开始，所以要+1
    return res

if __name__ == "__main__":
    s = 'abcabcbb'
    print(longest_unique_substring(s))

什么是回表？
假设有一个表users，结构如下：
CREATE TABLE users (
id INT PRIMARY KEY, – 聚簇索引（主键）
name VARCHAR(100), – 普通字段
age INT,
INDEX idx_name (name) – 非聚簇索引
);

SELECT * FROM users WHERE name = 'Alice';这个语句使用 idx_name 索引：查找 name = ‘Alice’ 的记录，得到对应的主键 id。而回表就是：“再根据主键 id，到聚簇索引中查找完整的数据行（如 age 字段）”这个过程。回表每次回表都需要额外的 I/O 操作。

为什么”产生大量生命周期长/无法回收的对象，会导致GC频繁”?
那为什么GC会让CPU飙升？
dig命令和nslookup命令有用过么？