1 深信服笔试题2

深信服笔试题2

代码如下

def delrepeat(a, bomb):
    stack = []
    i = 0
    while i < len(a):
        if stack == []:
            stack.append(a[i])
        else:
            if stack[-1] == a[i]:
                c = stack[-1]
                stack.pop()
                if c == bomb:
                    if len(stack) > 0:
                        stack.pop()
                    i += 1
            else:
                stack.append(a[i])
        i += 1
    print(''.join(stack))


a = input().strip()
bomb = input().strip()
delrepeat(a, bomb)

2 快速排序找第k大数

快速排序代码

# 快速排序
a = list(map(int, input().strip().split()))


def fastsort(li, l, r):
    # 这个条件容易被遗漏，如果没有这个条件的话，r 会比 l 还小，显然不切实际
    if l < r:
        x = li[l]
        i = l
        j = r
        while i < j:
            while i < j and li[j] >= x:
                j -= 1
            if i < j:
                li[i] = li[j]
                i += 1
            while i < j and li[i] < x:
                i += 1
            if i < j:
                li[j] = li[i]
                j -= 1
        # 一轮遍历后，i 和 j 会重合，所以既可以给li[i]也可以给li[j]赋值
        li[i] = x
        fastsort(li, l, i - 1)
        fastsort(li, i + 1, r)


fastsort(a, 0, len(a) - 1)
print(a)

3 插入排序

a = list(map(int, input().strip().split()))


def insertsort(li):
    for i in range(1, len(li)):
        j = i - 1
        while j >= 0 and li[i] < li[j]:
            j -= 1
        x = li[i]
        for id in range(i - 1, j, -1):
            li[id + 1] = li[id]
        li[j + 1] = x


insertsort(a)
print(a)

求一个整数的逆序

public boolean isPalindrome(int x) {
        if(x < 0)
            return false;
        int cur = 0;
        int num = x;
        while(num != 0) {
            cur = cur * 10 + num % 10;
            num /= 10;
        }
        return cur;
    }

作者：guanpengchn
链接：https://leetcode-cn.com/problems/palindrome-number/solution/hua-jie-suan-fa-9-hui-wen-shu-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一个很清楚的数据库操作例子（顺序是 where, group by, having, order by）

滴滴笔试题1

滴滴笔试题2

参考：
[1] sql篇 select from where group by having order by
[2] 查询语句中select from where group by having order by的执行顺序

滑动窗口中的最大值（在线性时间内解决）

题目：239. 滑动窗口最大值
我觉得最关键的在于clean_deque中的操作，deque中最多能放k个索引，当超过k个索引，就从左端删除；当队尾索引对应的元素小于即将要插入的元素时，那就把队尾中的索引弹出，因为它对应的元素一定不会是最大值；有了这两种机制后，可以保证队列头部的索引对应的元素是滑动窗口中的最大值。

# 双端队列（原答案中使用collections.deque实现的，我直接用的列表）
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if nums==[] or k==0:
            return []
        if k==1:
            return nums
        def clean_deque(i):
            # 判断队列是否满了（队列中元素大于窗口即为满）
            if deq and deq[0]==i-k:
                deq.pop(0)
            # 如果新加入的元素大于队尾元素，则将队尾元素弹出 
            while deq and nums[i]>nums[deq[-1]]:
                deq.pop()
        deq=[]
        output=[]
        for i in range(0,len(nums)):
            clean_deque(i)
            deq.append(i)
            output.append(nums[deq[0]])
        return output[k-1:] if len(output)>k-1 else [output[-1]]

常考题

字符串压缩

迷宫

Q：堆排序

A：
1 堆排序算法（图解详细流程）
2 堆排序

Q：排序算法时间复杂度与稳定性

选择排序为什么不稳定：举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

Q：希尔排序

A： 图解排序算法(二)之希尔排序

Q：基数排序和桶排序

A：
1 基数排序
2 桶排序
3 桶排序复杂度分析

Q：冒泡排序

# 冒泡排序
a = list(map(int, input().strip().split()))
le = len(a)

# 外层循环是遍历次数
for k in range(0, le - 1):
    # 内层循环是遍历a[0:le-k-1]的元素
    i = 0
    while i < le - k - 1:
        j = i + 1
        # 只需要考虑这一种情况就行了
        if a[j] < a[i]:
            a[j], a[i] = a[i], a[j]
        i += 1
print(a)

Q：堆排序

'''
堆排序思想：想要对堆排序，先得构造一个最大堆/最小堆
如何构造最大/最小堆呢？
让每个有子节点的节点都和它的子节点中的最大值比较大小，如果父节点的值大于子节点中的最大值，那就继续找前一个父节点，
否则的话，就把父节点和子节点中的最大节点交换位置，然后以这个子节点为父节点，循环更新堆
'''


def max_heapify(ary, start, end):
    root = start
    while True:
        # 左子节点的索引
        child = 2 * root + 1
        if child > end:
            break
        # child+1是右子节点
        if child + 1 <= end and ary[child] < ary[child + 1]:
            child = child + 1
        if ary[root] < ary[child]:
            ary[root], ary[child] = ary[child], ary[root]
            root = child
        else:
            break


def heap_sort(ary):
    n = len(ary)
    # 找到最后一个父节点，这是根据公式来的
    first = int(n / 2 - 1)
    for i in range(first, -1, -1):
        # 先构造一个最大堆
        max_heapify(ary, i, n - 1)
    for i in range(n - 1, 0, -1):
        # 每次将堆顶元素与堆尾元素交换位置
        ary[i], ary[0] = ary[0], ary[i]
        # 对剩下的未排序的元素排序
        max_heapify(ary, 0, i - 1)
    return ary

if __name__ == '__main__':
    a = [6, 5, 3, 1, 8, 7, 2, 4]
    print(heap_sort(a))

Q：一个列表A=[A1，A2，…,An]，要求把列表中所有的组合情况打印出来（全排列问题）

s = [1, 2, 3]
temp = [[]]
output = [[]]
for ele in s:
    for ele1 in temp:
        output.append(ele1 + [ele])
    # 要用深拷贝，不然的话temp和output会指向同一块内存，这样的话
    # 修改其中任一列表都会影响另一个
    temp = output[:]
output.remove([])
print(output)

Q：单向链表长度未知，如何判断其中是否有环

方法一

# 链表结点类
class Node():
    def __init__(self, item=None):
        self.item = item  # 数据域
        self.next = None  # 指针域


# 判断是否为环结构并且查找环结构的入口节点
def findbeginofloop(head):
    # 默认环不存在，为False
    loopExist = False
    # 如果头节点就是空的，那肯定就不存在环结构
    if head == None:
        return "不是环结构"

    s = set()
    while head.next:
        # 判断遍历的节点是否在set中
        if id(head) in s:
            # 返回环入口
            print("存在环结构")
            return head.item
        s.add(id(head))
        head = head.next
    print(s)
    return "不是环结构"


if __name__ == "__main__":
    # 构建环
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(10)
    node4 = Node(4)
    node5 = Node(5)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node3
    print(findbeginofloop(node1))

方法二

# 链表结点类
class Node():
    def __init__(self, item=None):
        self.item = item  # 数据域
        self.next = None  # 指针域


# 判断是否为环结构并且查找环结构的入口节点
def findbeginofloop(head):
    # 默认环不存在，为False
    loopExist = False
    # 如果头节点就是空的，那肯定就不存在环结构
    if head == None:
        return "不是环结构"
    # i是慢指针，j是快指针
    i, j = head, head
    # 注意这个判断条件，如果快指针的next和next.next不为空的话，才继续进行
    # 为什么不用慢指针的next来判断，因为快指针的next不为空，那么慢指针的next一定不为空
    while j.next and j.next.next:
        i = i.next
        j = j.next.next
        if i == j:
            loopExist = True
            print('存在环结构')
            break

    # 为什么要写下面这个if，因为光靠上面的程序是无法判断出环的入口点在哪儿的
    # 因为快慢指针交汇的地方是环入口点的下一个位置，所以需要重新写语句来找出入口点
    if loopExist == True:
        i = head
        while i != j:
            i = i.next
            j = j.next
        return '入口点是%s' % i.item
    return '不是环结构'


if __name__ == "__main__":
    # 构建环
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(10)
    node4 = Node(4)
    node5 = Node(5)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    # node5.next = node3
    print(findbeginofloop(node1))

Q：找前序遍历序列中两个节点的最近公共父节点

Q：

image.png

Q：

image.png

Q：

image.png

Q：

image.png

Q：

image.png

Q：

image.png

Q：

image.png