..

那些年 用python刷过的面试算法题

准备面试的过程中用Python写了一些的算法题, 用这篇日志记录一下.

##fibonacci数组:
/blog/20160915/dynamic-programming/

##Generating all possible permutations of a list 生成一个列表的所有组合.
1.The feeling of completing an algorithm with only one error, awesome.

def permutation(ABC, len_fix):
    if len_fix == len(ABC)-1:
        print(ABC)
    else:
        for i in range(len(ABC)-len_fix):
            part1, part2 = ABC[:len_fix], ABC[len_fix:]
            part2[i], part2[0] = part2[0], part2[i]
            permutation(part1+part2, len_fix+1)

ABC = [0, 1, 2, 3]
permutation(ABC, 0)

2.Python buildin method:

>>> horses = [1, 2, 3, 4]
>>> races = itertools.permutations(horses)
>>> print(races)
<itertools.permutations object at 0xb754f1dc>
>>> print(list(itertools.permutations(horses)))
[(1, 2, 3, 4),
 (1, 2, 4, 3),
...
 (4, 3, 1, 2),
 (4, 3, 2, 1)]

本来是想刷一遍leecode, 但算法题有四百多题..刷了三四题就放弃了
接下来的一些算法题是剑指offer里的: https://www.nowcoder.com/ta/coding-interviews?query=&asc=false&order=submissionCount&page=1

输入一个链表，从尾到头打印链表每个节点的值.

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here

        if listNode is None:
            return []
        else:
            result = [listNode.val]

        while listNode.next:
            result.append(listNode.next.val)
            listNode = listNode.next

    	return result[::-1]

反转链表

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def ReverseList(self, pHead):
        if pHead is None or pHead.next is None:
            return pHead

        h = self.ReverseList(pHead.next)

        # reverse the linked list, except last one(because of return).
        pHead.next.next = pHead
        # head set null
        pHead.next = None

        return h

合并两个有序的链表

class Solution:
    def Merge(self, pHead1, pHead2):
        if pHead1 is None: return pHead2
        if pHead2 is None: return pHead1

        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next, pHead2)
            head = pHead1
        else:
            pHead2.next = self.Merge(pHead1, pHead2.next)
            head = pHead2

        return head

生成二叉树的镜像

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):

        if root:
            root.left, root.right = self.Mirror(root.right), self.Mirror(root.left)

        return root

输入两棵二叉树A，B，判断B是不是A的子结构。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        if pRoot1 is None or pRoot2 is None:
            return False
        elif self.is_subtree(pRoot1, pRoot2):
            return True
        else:
            return self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)

    def is_subtree(self, pRoot1, pRoot2):
        if pRoot2 is None:
            return True

        elif pRoot1 and pRoot2 and pRoot1.val == pRoot2.val:
            return self.is_subtree(pRoot1.left, pRoot2.left) and self.is_subtree(pRoot1.right, pRoot2.right)
        else:
            return False


# t1 = TreeNode(1)
# t1.left = TreeNode(1)
# t1.left.right = TreeNode(3)
# t1.left.left = TreeNode(2)
#
#
# t2 = TreeNode(1)
# t2.left = TreeNode(2)
# t2.right = TreeNode(3)
# # t2.left.left = TreeNode(4)
#
#
# print(Solution().is_sametree(t1, t2))
# print(Solution().HasSubtree(t1, t2))

一层一层打印二叉树

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        result = []

        nodes_in_level = [root] if root else []
        while nodes_in_level:
            nodes_in_next_level = []
            for node in nodes_in_level:
                result.append(node.val)
                nodes_in_next_level.append(node.left)
                nodes_in_next_level.append(node.right)

            nodes_in_level = [node for node in nodes_in_next_level if node]

        return result



# t1 = TreeNode(1)
# t1.left = TreeNode(1)
# t1.left.right = TreeNode(3)
# t1.left.left = TreeNode(2)
#
# print(Solution().PrintFromTopToBottom(t1))

栈的压入弹出序列

# -*- coding:utf-8 -*-

# 输入两个整数序列，第一个序列表示栈的压入顺序, 请判断第二个序列是否为该栈的弹出顺序。
# 假设压入栈的所有数字均不相等。
# 例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

class Solution:
    def IsPopOrder(self, pushV, popV):
        if pushV and popV and set(pushV) == set(popV):
            l = [pushV.pop(0)]

            while popV:
                # False
                if popV[0] in l[:-1]:
                    return False

                # 1. push
                elif pushV and l[-1] != popV[0]:
                    l.append(pushV.pop(0))

                # 2. pull
                else:
                    l.pop()
                    popV.pop(0)

            return True
        else:
            return False
EOF