1 深信服筆試題2
這道題不難渊啰，但是考試的時候思路很亂探橱，寫的也很亂，也沒通過測試用例绘证，還好拍下來（突然想起來還開了監(jiān)控隧膏，我拿平板拍照應該被視作作弊吧？Ｈ履恰）胞枕，又做了一次，理清了思路（只是我以為的我理清了思路魏宽，但還是不對腐泻，我想的是雙指針法，但是實際操作起來有我無法解決的問題队询，花了三小時也沒做對派桩，問了王哥后，改用棧來操作（碰到這種往前進又往后退的問題要第一時間想到棧））蚌斩。
深信服筆試題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大數(shù)
快速排序代碼
# 快速排序
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)
求一個整數(shù)的逆序
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）
著作權歸作者所有。商業(yè)轉載請聯(lián)系作者獲得授權逆趋，非商業(yè)轉載請注明出處盏阶。
一個很清楚的數(shù)據(jù)庫操作例子（順序是 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的執(zhí)行順序
滑動窗口中的最大值（在線性時間內(nèi)解決）
題目：239. 滑動窗口最大值
我覺得最關鍵的在于clean_deque中的操作晒奕，deque中最多能放k個索引闻书，當超過k個索引，就從左端刪除脑慧；當隊尾索引對應的元素小于即將要插入的元素時魄眉，那就把隊尾中的索引彈出，因為它對應的元素一定不會是最大值闷袒；有了這兩種機制后坑律，可以保證隊列頭部的索引對應的元素是滑動窗口中的最大值。
# 雙端隊列（原答案中使用collections.deque實現(xiàn)的囊骤，我直接用的列表）
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：排序算法時間復雜度與穩(wěn)定性
選擇排序為什么不穩(wěn)定：舉個例子也物，序列5 8 5 2 9宫屠，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了滑蚯，所以選擇排序不是一個穩(wěn)定的排序算法浪蹂。
Q：希爾排序
Q：基數(shù)排序和桶排序
A：
1 基數(shù)排序
2 桶排序
3 桶排序復雜度分析
Q：冒泡排序
# 冒泡排序
a = list(map(int, input().strip().split()))
le = len(a)
# 外層循環(huán)是遍歷次數(shù)
for k in range(0, le - 1):
# 內(nèi)層循環(huán)是遍歷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：堆排序
'''
堆排序思想：想要對堆排序，先得構造一個最大堆/最小堆
如何構造最大/最小堆呢告材？
讓每個有子節(jié)點的節(jié)點都和它的子節(jié)點中的最大值比較大小坤次，如果父節(jié)點的值大于子節(jié)點中的最大值，那就繼續(xù)找前一個父節(jié)點斥赋，
否則的話缰猴，就把父節(jié)點和子節(jié)點中的最大節(jié)點交換位置，然后以這個子節(jié)點為父節(jié)點疤剑，循環(huán)更新堆
'''
def max_heapify(ary, start, end):
root = start
while True:
# 左子節(jié)點的索引
child = 2 * root + 1
if child > end:
break
# child+1是右子節(jié)點
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)
# 找到最后一個父節(jié)點滑绒，這是根據(jù)公式來的
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會指向同一塊內(nèi)存棘幸，這樣的話
# 修改其中任一列表都會影響另一個
temp = output[:]
output.remove([])
print(output)
Q：單向鏈表長度未知焰扳，如何判斷其中是否有環(huán)
方法一
# 鏈表結點類
class Node():
def __init__(self, item=None):
self.item = item # 數(shù)據(jù)域
self.next = None # 指針域
# 判斷是否為環(huán)結構并且查找環(huán)結構的入口節(jié)點
def findbeginofloop(head):
# 默認環(huán)不存在，為False
loopExist = False
# 如果頭節(jié)點就是空的，那肯定就不存在環(huán)結構
if head == None:
return "不是環(huán)結構"
s = set()
while head.next:
# 判斷遍歷的節(jié)點是否在set中
if id(head) in s:
# 返回環(huán)入口
print("存在環(huán)結構")
return head.item
s.add(id(head))
head = head.next
print(s)
return "不是環(huán)結構"
if __name__ == "__main__":
# 構建環(huán)
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 # 數(shù)據(jù)域
self.next = None # 指針域
# 判斷是否為環(huán)結構并且查找環(huán)結構的入口節(jié)點
def findbeginofloop(head):
# 默認環(huán)不存在吨悍，為False
loopExist = False
# 如果頭節(jié)點就是空的扫茅，那肯定就不存在環(huán)結構
if head == None:
return "不是環(huán)結構"
# i是慢指針，j是快指針
i, j = head, head
# 注意這個判斷條件育瓜，如果快指針的next和next.next不為空的話葫隙，才繼續(xù)進行
# 為什么不用慢指針的next來判斷，因為快指針的next不為空躏仇，那么慢指針的next一定不為空
while j.next and j.next.next:
i = i.next
j = j.next.next
if i == j:
loopExist = True
print('存在環(huán)結構')
break
# 為什么要寫下面這個if恋脚，因為光靠上面的程序是無法判斷出環(huán)的入口點在哪兒的
# 因為快慢指針交匯的地方是環(huán)入口點的下一個位置，所以需要重新寫語句來找出入口點
if loopExist == True:
i = head
while i != j:
i = i.next
j = j.next
return '入口點是%s' % i.item
return '不是環(huán)結構'
if __name__ == "__main__":
# 構建環(huán)
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：找前序遍歷序列中兩個節(jié)點的最近公共父節(jié)點
Q：
![]()
image.png
image.png
Q：
![]()
image.png
image.png
Q：
![]()
image.png
image.png
Q：
![]()
image.png
image.png
Q：
![]()
image.png
image.png
Q：
![]()
image.png
image.png
Q：
![]()
image.png
image.png
