最近在准备各种实习面试，感觉基础很薄弱，所以找来一些基础恶补一下。在此博客看到15道据说出现频率很高的算法题，原博用C++实现，我决定用python重新完成一下。

目录

1、合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元
2、合并两个已经排序的单链表
3、倒序打印一个单链表
4、给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点
5、找到链表倒数第K个节点
6、反转单链表
7、通过两个栈实现一个队列
8、二分查找
9、快速排序
10、获得一个int型的数中二进制中的个数
11、输入一个数组，实现一个函数，让所有奇数都在偶数前面
12、判断一个字符串是否是另一个字符串的子串
13、把一个int型数组中的数字拼成一个串，这个串代表的数字最小
14、输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置)
15、输入两个链表，找到它们第一个公共节点

本文中链表节点和树节点定义如下

1
2
3
4
5
6
7
8
9
10
class NodeL:#链表节点
	def __init__(self,value):
        self.value = value
        self.next = None

class NodeT:#树节点
    def  __init__(self,value,left,right):
        self.value = value
        self.left = None
        self.right = None

合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素

常规思路是新建一个数组C，然后将A、B两数组的值按顺序放进C，最后把剩下的全部放进去。这里提供的是之间把A扩大到B的大小，然后从后往前放元素，这样便不用再创建数组了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
#合并已排序的数组
    def MergeArray(self,a,alen,b,blen):
        len = alen + blen - 1
        a.extend([0 for _ in range(blen)])
        alen -= 1
        blen -= 1
        while alen>=0 and blen >= 0:
            if a[alen] > b[blen]:
                a[len] = a[alen]
                alen -= 1
            else:
                a[len] = b[blen]
                blen -= 1
            len -= 1
        if blen >=0:
            a[0:blen+1] = b[0:blen+1]

合并两个已经排序的单链表

这与合并数组类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    # 合并连个已经排序的单链表
    def Merge(self, pHead1, pHead2):
        # write code here

        res = head = NodeL(0)
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                head.next = pHead1
                pHead1 = pHead1.next

            elif pHead1.val >= pHead2.val:
                head.next = pHead2
                pHead2 = pHead2.next
            head = head.next
        head.next = pHead1 or pHead2

        return res.next

倒序打印一个单链表

递归实现，先递归后打印

1
2
3
4
5
class Solution:
    def ReservePrintNode(self,head):
        if head:
            self.ReservePrintNode(head.next)
            print(head.value)

给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点

因为需要时间复杂度O(1)，所以不能对链表进行搜索找到节点的上一节点，从而删除。不过原文算法在删除尾节点时似乎还是用到了循环，没想到良好的解决方法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def DeleteNode(self,head,delNode):
        if delNode == head:
            head = delNode.next
            return head
        elif not delNode.next: #这里是不对嗒
            delNode = None
            return head
        else:
            next = delNode.next
            delNode.next = next.next
            delNode.value = next.value
            return head

找到链表倒数第K个节点

python里可以按序把节点放进list中，然后输出list[-k]

更加省空间的做法是使用两个指针，第一个先往前走k个节点，然后另一个指向head，之后两个一起往前走，第一个到最后，第二个便指向倒数第k个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def FindkthToTail(self,head,k):
        if not head or k == 0:
            return None
       	tmpNode = head
        for i in range(0,k):
            if tmpNode:
                tmpNode = tmpNode.next
            else:
                return None
        kNode = head
        while tmpNode:
            kNode = kNode.next
            tmpNode = tmpNode.next
        return kNode

反转单链表

使用三个指针，依次翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def ReverseList(self,pHead):
        if not pHead or not pHead.next:
            return pHead
       	pPre = None
        pCur = pHead
        pReverse = None
        while pCur:
            pNext = pCur.next
            if not pNext:
                pReverse = pCur.next
            pCur.next = pPre
            pPre = pCur
            pCur = pNext
        return pReverse

通过两个栈实现一个队列

主要思路就是把stack1当作存储空间，stack2作为缓冲区

入队时，将元素压入stack1

出队时，若stack2不为空，之间把stack2栈顶元素弹出即可，若为空，则需要把stack1内元素倒入stack2中，把最后一个元素弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
class Queue:
    def __init__(self):
        self.stack1 = []
        self.stack2 =[]
    def push(self,x):
        self.stack1.append(x)
    def pop(self):
        if len(self.stack2) ==0:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()
    def size(self):
        return len(self.stack1) + len(self.stack2)

二分查找

很常见很基础的题目了

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def binartSearch(self,lists,x):
        start = 0
        end = len(lists) - 1
        while start <= end:
            middle = (end + start)//2
            if a[middle] == x:
                return middle
            elif a[middle] > x:
            	end = middle -1
            else:
                start = middle + 1
        return -1

快速排序

主要思路就是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。借用百度百科的图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def quicksort(self,lists,left,right):
        x = lists[right]
        i = left - 1
        for j in range(len(lists)-1):
            if lists[j] < x:
                i += 1
                lists[i],list[j] = lists[j],lists[i]
            lists[i+1],lists[right] = lists[right],lists[i+1]
        return i+1
   	def quicksortself(self,lists,left,right):
        if left < right:
            num = self.quicksort(lists,left,right)
            quicksort(lists,left,num-1)
            quicksort(lists,num+1,right)

获得一个int型的数中二进制中1的个数

python内置bin函数，可以将数字转为对应二进制字符串，然后使用count函数便可得到1的个数。只是注意bin函数并不是把数字转为补码，

1
2
3
4
5
6
class Solution:
    def bindigits(self,n, bits):
        s = bin(n & int("1"*bits, 2))[2:]
        return s
    def NumberOf1(self, n):
        return self.bindigits(n,32).count('1')

更普遍的实现方式是通过这个数和比他小1的数的二进制进行&运算，将二进制中1慢慢地从后往前去掉，直到没有。

1
2
3
4
5
6
7
8
9
10
class Solution:
	    def find1count(self,num):
        if num == 0:
            return 0
        count = 1
        num = num & (num - 1)
        while num:
            count += 1
            num = num & (num - 1)
        return count

后来发现上面的代码遇到负数时会进入死循环可以将最高位的符号位1变成0，也就是n & 0x7FFFFFFF，这样就把负数转化成正数了，唯一差别就是最高位由1变成0，因为少了一个1，所以count加1。不过这里还会遇到-1和-2147483648两个特例，想想决定单独处理掉，于是就变成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def find1count(self,num):
        if num == 0:
            return 0
        count = 1
        if num == -1:
            return 32
        if num == -2147483648:
            return 1
        if num < 0:
            num = num & 0x7FFFFFFF
            count +=1
        num = num & (num - 1)
        while num!=0:
            count += 1
            num = num & (num - 1)
        return count

看到的最简洁的代码是这个

1
2
3
class Solution:
    def one(self,num):
        return sum([(num >> i & 1) for i in range(0, 32)])

输入一个数组，实现一个函数，让所有奇数都在偶数前

python可以用sorted方法，参数key使用判断奇偶数的lambda表达式即可。

正经方法的话，借用快速排序的思路，完成一次快排即可

1
2
3
4
5
6
7
8
9
10
class Solution:
    def RecordOddEven(self,lists):
        i = -1
        j = 0
        while j <= len(lists):
            if lists[j] % 2 != 0:
            	i += 1
                lists[i],list[j] = lists[j],lists[i]
          	j +=1
        return lists

判断一个字符串是否是另一个字符串的子串

python可以用in操作符，string模块的find方法，index方法，这些就不赘述了。

1
2
3
4
5
6
7
8
9
class Solution:
    def checkchild(self,s1,s2):
        j = 0
        for i in range(len(s2)):
            while j < len(s1) and s1[i] != s2[j]:
                j+=1
           	if j == len(s1):
                return False
       	return True

暴力按序统计

把一个int型数组中的数字拼成一个串，这个串代表的数字最小

把数组里所有数转为字符串，再把字符串拼在一起，排序，如果首位是0，就和之后第一个不是0的数交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def getmin(self,lists):
        l=''
        for i in lists:
            l+=str(i)
        l = list(l)
        l.sort()
        if l[0] == '0':
            for i in range(1,len(l)):
                if l[i] != '0':
                    l[0],l[i]=l[i],l[0]
                    break
        s=''.join(l)
        return int(s)

输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置

递归实现，只要某个节点的两个子节点都不为空，就左右交换，让左子树交换，让右子树交换。

1
2
3
4
5
6
7
8
9
10
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if not root or (not root.left and not root.right):
            return
        root.left,root.right = root.right,root.left
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root

输入两个链表，找到它们第一个公共节点

如果两个链表有公共的节点，那么第一个公共的节点及往后的节点都是公共的。从后往前数N个节点（N=短链表的长度节点个数）,长链表先往前走K个节 点（K=长链表的节点个数-N），这时两个链表都距离末尾N个节点，现在可以一一比较了，最多比较N次，如果有两个节点相同就是第一个公共节点，否则就没 有公共节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def getLength(self,pHead):
        l = 0
        while pHead:
            pHead = pHead.next
            l+=1
        return l
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        l1 = self.getLength(pHead1)
        l2 = self.getLength(pHead2)
        if l1<l2:
            shortL = pHead1
            longL = pHead2
        else:
            shortL = pHead2
            longL = pHead1
        for i in range(self.getLength(longL) - self.getLength(shortL)):
            longL = longL.next
        for i in range(self.getLength(shortL)):
            if longL != shortL:
                longL = longL.next
                shortL = shortL.next
            else:
                return longL
        return None

原文链接 http://blog.wuqingzhe.cn/2018/04/17/15questions/