剑指offer代码Python实现

# 示例 快速排序法
import random
class Solution:
    def Partition(self, data, start, end):
        """随机选择基准数，将较小数移到前方，返回基准数在调整顺序后的索引位置"""
        if not data:
            raise Exception("Invalid Parameters")
        index = random.randrange(start, end)

        temp = data[index]
        data[index] = data[end]
        data[end] = temp

        small = start - 1
        for index in range(start, end):
            if data[index] < data[end]:
                small += 1
                if small != index:
                    temp = data[index]
                    data[index] = data[small]
                    data[small] = temp
        small += 1

        temp = data[small]
        data[small] = data[end]
        data[end] = temp

        return small
    def QuickSort(self, data, start, end):
        """快速排序法，输入需要排序的范围"""
        if start == end:
            return
        index = self.Partition(data, start, end)
        if index > start:
            self.QuickSort(data, start, index - 1)
        if index < end:
            self.QuickSort(data, index + 1, end)
# test code
a = Solution()
data = [1,3,5,76,3,2,6,4]
a.QuickSort(data, 0, len(data)- 1)
data

def duplicate(nums:list):
    """
    
    Arg(Argument参数): nums:list[int]
    Re(return): 若未找到重复数字，或者列表元素不符合要求将返回bool False，否则返回检索到的重复数字
    算法分析：尽管有两重循环，但每个数字最多只要交换两次就能找到属于它的位置，所以总体算法复杂度为O(n)空间复杂度为O(1)
    """
    length = len(nums)
    if length < 2:
        return False
    for i in range(length):
        if nums[i] < 0 or nums[i] > length - 1:
            return False
        while nums[i] != i:
            if nums[i] != nums[nums[i]]:#如果不相等就互换位置
                temp = nums[nums[i]]
                nums[nums[i]] = nums[i]
                nums[i] = temp
#                 nums[i], nums[nums[i]] = nums[nums[i] - 1], nums[i] 逗号赋值并非同时进行，在这种情况下无法得到正确结果
            else:
                return nums[i]
    return False
#测试用例
nums = [2,3,1,0,2,5,3]
print(duplicate(nums))

# 牛客网版代码
class Solution:
    def duplicate(self, nums, duplication):
        """利用列表下标作为哈希表，通过元素互换逐步构建哈希表，若遇到相等的数字则通过下标索引key必然能检测到重复数字
        Arg(Argument参数): nums:list[int]
        Re(return): 若未找到重复数字，或者列表元素不符合要求将返回bool False，否则返回检索到的重复数字
        算法分析：尽管有两重循环，但每个数字最多只要交换两次就能找到属于它的位置，所以总体算法复杂度为O(n)空间复杂度为O(1)
        """
        length = len(nums)
        if length < 2:
            return False
        for i in range(length):
            if nums[i] < 0 or nums[i] > length - 1:
                return False
            while nums[i] != i:
                if nums[i] != nums[nums[i]]:  # 如果不相等就互换位置
                    temp = nums[nums[i]]
                    nums[nums[i]] = nums[i]
                    nums[i] = temp
                else:
                    duplication[0] = nums[i]
                    return True
        return False
# test code
# 代码已在牛客网通过测试

def countRange(nums, start, end):
    """统计nums中所有元素值在区间[start, end]中的数的个数
    """
    if not nums:
        return 0
    count = 0
    for i in range(len(nums)):
        if nums[i] >= start and nums[i] <= end:
            count += 1
    return count

def getDuplication(nums):
    """利用二分查找法来找出数组中任意一重复数字 (注意，此方法不能很好的解决此类问题，偶尔会出现错误)"""
    length = len(nums)
    if length < 2:
        return False
    start = 0
    end = length - 1
    while end >= start:
        middle = (end + start) >> 1  # 利用右移操作除二取整
        count = countRange(nums, start, middle)
        if end == start:
            if count > 1:
                return start
            else:
                break
        # 如果count的数量大于该值区间长度，则此区间中必有重复数值，反之类似
        if count > (middle - start + 1):
            end = middle
        else:
            start = middle + 1
    return False
#测试用例
nums = [2,4,5,4,3,2,6,7]
nums = [2,3,5,4,3,2,6,7]
print(getDuplication(nums))

def Find(nums, target):
    if len(nums) <= 0 or len(nums[0]) <= 0:
        return False
    i = 0
    j = len(nums[0]) - 1
    while i <= len(nums) - 1 and j >= 0:
        if nums[i][j] > target:
            j -= 1
        elif nums[i][j] < target:
            i += 1
        else:
            return True
    return False

def ReplaceBlank(string:list):
    """使用字符型列表来替换str类型，更好的诠释算法思想。若用str类型来做:string.replace(' ', '%20')即可
    输入：string:list[char]
    输出：string：str
    """
    if not string:
        return ''
    numOfBlank = 0
    for i in string:
        if i == ' ':
            numOfBlank += 1
    originalLength = len(string)
    newlength = originalLength + 2*numOfBlank
    string = string + ['']*2*numOfBlank
    while originalLength >= 0 and newlength > originalLength:
        #  从后往前替换空格
        if string[originalLength - 1] == ' ':
            string[newlength - 1] = '0'
            string[newlength - 2] = '2'
            string[newlength - 3] = '%'
            newlength -= 3
        else:
            string[newlength - 1] = string[originalLength - 1]
            newlength -= 1
        originalLength -= 1
    return ''.join(string)

string = ['W', 'e', ' ', 'a', 'r', 'e', ' ', 'h', 'a', 'p', 'p', 'y', '.']
print(ReplaceBlank(string))

#创建链表类
class ListNode:
    """创建链表类"""
    def __init__(self, x):
        self.val = x
        self.next = None
#反转打印函数
def PrintListReversingly_Iteratively(phead):
    """利用栈来实现反向打印链表"""
    pNode = phead
    stack = []
    if pNode.val == None:
        print("None！")
    while pNode != None:
        stack.append(pNode.val)
        pNode = pNode.next
    while stack != []:
        print(stack.pop(-1))

def PrintListReversingly_Recursively(phead):
    """使用递归函数进行反向打印"""
    if phead is not None:
        if phead.next is not None:
            PrintListReversingly_Recursively(phead.next)
        print(phead.val)
#测试用例代码
##创建链表
head = ListNode('head->')
pnode = head
valueList = list('abcdefg')
for i in valueList:
    pnode.next = ListNode(i)
    pnode = pnode.next
#验证链表用代码
'''
pnode = head
while pnode != None:
    print(pnode.val)
    pnode = pnode.next
print(head.val)
'''
#测试打印函数
PrintListReversingly_Iteratively(head)
PrintListReversingly_Recursively(head)

#牛客网解题对应函数(不要在此cell中运行)
def printListFromTailToHead(self, listNode):
    '''利用栈实现反向输出链表'''
    pNode = listNode
    stack = []
    if pNode is None:
        return stack
    while pNode is not None:
        stack.append(pNode.val)
        pNode = pNode.next
    stack.reverse()
    return stack

def printListFromTailToHead(self, listNode):
    '''利用递归函数反向输出链表'''
    if listNode is None:
        return []
    else:
        return self.printListFromTailToHead(listNode.next) + [listNode.val]

class BinaryTreeNode:
    '''创建二叉树节点'''
    def __init__(self, x=None):
        self.val = x
        self.left = None
        self.right = None
def preTree(treehead):
    """递归的先根序遍历二叉树，返回列表序列"""
    if treehead is None:
        return []
    return [treehead.val] + preTree(treehead.left) + preTree(treehead.right)
def tinTree(treehead):
    """递归的中根序遍历二叉树，返回列表序列"""
    if treehead is None:
        return []
    return tinTree(treehead.left) + [treehead.val] + tinTree(treehead.right)

def _ConstructBinaryTree(pre,tin):
    """递归调用构造子二叉树"""
    root = BinaryTreeNode(pre[0])
    #递归终止条件
    if len(pre) == 1:
        if len(tin) == 1 and pre[0] == tin[0]:
            return root
        else:
            raise Exception("input error")
    rootInorderIndex = tin.index(pre[0])
    if len(tin) == 1 and tin[rootInorderIndex] != root.val:
        raise Exception("input error")
    left = tin[0:rootInorderIndex]
    right = tin[rootInorderIndex+1:]
    if len(left) > 0:
        root.left = _ConstructBinaryTree(pre[1:len(left) + 1], left)
    if len(right) > 0:
        root.right = _ConstructBinaryTree(pre[len(left)+1:], right)
    return root
def reConstructBinaryTree(pre, tin):
    """初始判断输入是否合法，并递归调用构造函数"""
    if not pre or not tin:
        raise Exception("input error")
    return _ConstructBinaryTree(pre, tin)
#测试代码
prelist = [1,2,4,7,3,5,6,8]
tinlist = [4,7,2,1,5,3,8,6]
treehead = reConstructBinaryTree(prelist, tinlist)
#验证prelist和tinlist
print(tinTree(treehead))

#牛客网通过代码   (#####!!不要运行此段代码!!#####)
def _ConstructBinaryTree(self,pre,tin):
    root = TreeNode(pre[0])
    if len(pre) == 1:
        if len(tin) == 1 and pre[0] == tin[0]:
            return root
        else:
            return False
    rootInorderIndex = tin.index(pre[0])
    if len(tin) == 1 and tin[rootInorderIndex] != root.val:
        return False
    left = tin[0:rootInorderIndex]
    right = tin[rootInorderIndex+1:]
    if len(left) > 0:
        root.left = self._ConstructBinaryTree(pre[1:len(left) + 1], left)
    if len(right) > 0:
        root.right = self._ConstructBinaryTree(pre[len(left)+1:],right)
    return root
def reConstructBinaryTree(self, pre, tin):
    if not pre or not tin:
        return None
    return self._ConstructBinaryTree(pre, tin)

class BinaryTreeNode:
    '''创建二叉树节点'''
    def __init__(self, x=None):
        self.val = x
        self.parent = None
        self.left = None
        self.right = None

def GetNext(pNode):
    """获取"""
    if pNode == None:
        return None
    pNext = BinaryTreeNode()
    if pNode.right != None:
        #若存在右子树，则右子树中最左侧的节点是下一节点
        pRight = pNode.right
        while pRight.left != None:
            pRight = pRight.left
        pNext = pRight
    elif pNode.parent != None:
        #若右子树不存在，则父节点中是左子树的父节点是下一节点
        pCurrent = pNode
        pParent = pNode.parent
        while pParent != None and pCurrent == pParent.right:
            pCurrent = pParent
            pParent = pParent.parent
        pNext = pParent
    return pNext
#test code
#tin=list('dbheiafcg')
#pre=list('abdehicfg')
headNode = BinaryTreeNode('a')
headNode.left = BinaryTreeNode('b')
headNode.left.parent = headNode
pNode = headNode.left
pNode.left = BinaryTreeNode('d')
pNode.right = BinaryTreeNode('e')
pNode.left.parent = pNode
pNode.right.parent = pNode
pNode = pNode.right
pNode.left = BinaryTreeNode('h')
pNode.right = BinaryTreeNode('i')
pNode.left.parent = pNode
pNode.right.parent = pNode
headNode.right = BinaryTreeNode('c')
headNode.right.parent = headNode
pNode = headNode.right
pNode.left = BinaryTreeNode('f')
pNode.right = BinaryTreeNode('g')
pNode.left.parent = pNode
pNode.right.parent = pNode


result = GetNext(pNode)
print(result.val)

# 牛客网版代码
class Solution:
    def GetNext(self, pNode):
        if pNode == None:
            return None
        pNext = None
        if pNode.right != None:
            # 若存在右子树，则右子树中最左侧的节点是下一节点
            pRight = pNode.right
            while pRight.left != None:
                pRight = pRight.left
            pNext = pRight
        elif pNode.next != None:
            # 若右子树不存在，则父节点中是左子树的父节点是下一节点
            pCurrent = pNode
            pParent = pNode.next
            while pParent != None and pCurrent == pParent.right:
                pCurrent = pParent
                pParent = pParent.next
            pNext = pParent
        return pNext
# test code
# 代码已在牛客网通过测试

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if len(self.stack2) <= 0:
            #若栈2为空则转移已入栈元素
            while len(self.stack1) > 0:
                self.stack2.append(self.stack1.pop())
        if len(self.stack2) == 0:
            #若已转移元素之后栈2还是空，则说明队列为空
            raise Exception('queue is empty')
        return self.stack2.pop()
#测试代码
inqueue = [1,2,3,4,5,6,7,8,9]
testqueue = Solution()
for i in inqueue:
    testqueue.push(i)
while testqueue.stack1 or testqueue.stack2:
    print(testqueue.pop())

def Fibonacci(n):
    """从小到大计算，类推出第n项，时间复杂度O(n)比递归小"""
    result = [0,1]
    if n < 2:
        return result[n]
    fibOne = 1
    fibTwo = 0
    temp = None
    for i in range(2,n+1):
        temp = fibOne + fibTwo
        fibTwo = fibOne
        fibOne = temp
    return temp
Fibonacci(10)

def FibonacciM():
    """利用数学公式[[f(n), f(n-1)], [f(n-1), f(n-2)]] = [[1, 1], [1,0]]^(n-1)。此方法时间复杂度为O(log(n))"""
    print("此函数待实现，留作练习")
    pass

"""函数Fibonacci在牛客网上测试通过"""

class Solution:
    """青蛙台阶问题、矩形覆盖问题"""
    def jumpFloor(self, number):
        result = [0,1,2]
        if number < 3:
            return result[number]
        fibOne = 2
        fibTwo = 1
        fibN = None
        for i in range(3,number+1):
            fibN = fibOne + fibTwo
            fibTwo = fibOne
            fibOne = fibN
        return fibN
    
class Solution:
    """青蛙跳台阶变态版：青蛙每次可以跳任意级"""
    def jumpFloorII(self, number):
        if number == 0:
            return 0
        return 2**(number - 1)

def MinInorder(nums):
    """顺序查找最小数字子函数"""
    result = nums[0]
    for i in nums:
        if i < result:
            result = i
    return result

def Min(nums):
    if not nums:
        raise Exception("无效的输入")
    length = len(nums)
    if length < 2:
        return nums[0]
    start = 0
    end = length - 1
    mid = start
    while nums[start] >= nums[end]:
        if end - start == 1:
            mid = end
            break
        mid = (end + start) / 2
        if nums[start] == nums[end] and nums[mid] == nums[start]:
            return MinInorder(nums[start:end])
        if nums[mid] >= nums[start]:
            start = mid
        elif nums[mid] <= nums[end]:
            end = mid
    return nums[mid]


# test code
"""在牛客网上通过测试"""

def hasPathCore(matrix, i, j, strs, visited, pathLength):
    """递归调用自己，探索每一个节点"""
    if pathLength >= len(strs):
        return True
    result = False
    if i >= 0 and i < len(matrix) and j >= 0 and j < len(matrix[0]) and matrix[i][j] == strs[pathLength] and not visited[i][j]:
        # 索引范围正确且此时矩阵的值和字符串的值相匹配，并且此点未被占据过，则递归探索下一符合要求的点
        pathLength += 1
        visited[i][j] = True
        result = hasPathCore(matrix,i,j-1,strs,visited,pathLength) or hasPathCore(matrix,i-1,j,strs,visited,pathLength) \
        or hasPathCore(matrix,i,j+1,strs,visited,pathLength) or hasPathCore(matrix,i+1,j,strs,visited,pathLength)
        # 递归探索四个方向的下一节点是否符合要求，若不符合要求则退回上一节点
        if not result:
            pathLength -= 1
            visited[i][j] = False
    return result

def hasPath(matrix,strs):
    if not matrix or not strs:
        return False
    rows = len(matrix)
    clos = len(matrix[0])
    # visited = [[False]*clos]*rows 
    # 这样构造矩阵，其行将会是第一行的浅拷贝，修改任一元素，将引起整列元素同时被改，因此采用下面的循环进行构造
    visited = [[False]*clos for _ in range(rows)]
    pathLength = 0
    for i in range(rows):
        for j in range(clos):
            #双循环遍历每一个点作为起点
            if hasPathCore(matrix,i,j,strs,visited,pathLength):
                return True
    return False

#test code
a = [[None]]*3
a[0] = list('abtg')
a[1] = list('cfcs')
a[2] = list('jdeh')
strs = 'tegsc'
print(hasPath(a, strs))

# 牛客网版代码
class Solution:
    def hasPathCore(self, matrix, i, j, strs, visited, pathLength):
        """递归调用自己，探索每一个节点"""
        if pathLength >= len(strs):
            return True
        result = False
        if i >= 0 and i < len(matrix) and j >= 0 and j < len(matrix[0]) and matrix[i][j] == strs[pathLength] and not visited[i][j]:
            # 索引范围正确且此时矩阵的值和字符串的值相匹配，并且此点未被占据过，则递归探索下一符合要求的点
            pathLength += 1
            visited[i][j] = True
            result = self.hasPathCore(matrix,i,j-1,strs,visited,pathLength) or self.hasPathCore(matrix,i-1,j,strs,visited,pathLength) or self.hasPathCore(matrix,i,j+1,strs,visited,pathLength) or self.hasPathCore(matrix,i+1,j,strs,visited,pathLength)
            # 递归探索四个方向的下一节点是否符合要求，若不符合要求则退回上一节点
            if not result:
                pathLength -= 1
                visited[i][j] = False
        return result
    
    def hasPath(self, matrix, rows, cols, strs):
        if not matrix or not strs:
            return False
        temp = [list(matrix[i:i+cols]) for i in range(0, len(matrix), cols)]
        # visited = [[False]*clos]*rows
        # 这样构造矩阵，其行将会是第一行的浅拷贝，修改任一元素，将引起整列元素同时被改，因此采用下面的循环进行构造
        visited = [[False]*cols for _ in range(rows)]
        pathLength = 0
        for i in range(rows):
            for j in range(cols):
                #双循环遍历每一个点作为起点
                if self.hasPathCore(temp,i,j,strs,visited,pathLength):
                    return True
        return False
# test code
# 代码已在牛客网通过测试

def getDigitSum(number):
    """计算数字和函数"""
    sumResult = 0
    while number > 0:
        sumResult += number % 10
        number /= 10
    return sumResult


def check(threshold, rows, cols, row, col, visited):
    """条件判断函数"""
    if row >= 0 and row < rows and col >= 0 and col < cols and getDigitSum(row) + getDigitSum(col)\
    <= threshold and not visited[row][col]:
        return True
    return False


def movingCountCroe(threshold, rows, cols, row, col, visited):
    """递归探索每一个可能的格子"""
    count = 0
    if check(threshold, rows, cols, row, col, visited):
        visited[row][col] = True
        count = 1 + movingCountCroe(threshold, rows, cols, row - 1, col, visited) \
            + movingCountCroe(threshold, rows, cols, row, col - 1, visited)\
            + movingCountCroe(threshold, rows, cols, row + 1, col, visited)\
            + movingCountCroe(threshold, rows, cols, row, col + 1, visited)
    return count


def movingCount(threshold, rows, cols):
    """主函数，初始化visited方便核心函数递归调用"""
    if threshold <= 0 or rows <= 0 or cols <= 0:
        return 0
    visited = [[False]*cols for _ in range(rows)]
    count = movingCountCroe(threshold, rows, cols, 0, 0, visited)
    return count


# test code
print(movingCount(18, 35, 35))

# 牛客网版代码
class Solution:
    def getDigitSum(self, number):
        """计算数字和函数"""
        sumResult = 0
        while number > 0:
            sumResult += number % 10
            number /= 10
        return sumResult

    def check(self, threshold, rows, cols, row, col, visited):
        """条件判断函数"""
        if row >= 0 and row < rows and col >= 0 and col < cols and self.getDigitSum(row) + self.getDigitSum(col) \
                <= threshold and not visited[row][col]:
            return True
        return False

    def movingCountCroe(self, threshold, rows, cols, row, col, visited):
        """递归探索每一个可能的格子"""
        count = 0
        if self.check(threshold, rows, cols, row, col, visited):
            visited[row][col] = True
            count = 1 + self.movingCountCroe(threshold, rows, cols, row - 1, col, visited) \
                    + self.movingCountCroe(threshold, rows, cols, row, col - 1, visited) \
                    + self.movingCountCroe(threshold, rows, cols, row + 1, col, visited) \
                    + self.movingCountCroe(threshold, rows, cols, row, col + 1, visited)
        return count

    def movingCount(self, threshold, rows, cols):
        """主函数，初始化visited方便核心函数递归调用"""
        if threshold <= 0 or rows <= 0 or cols <= 0:
            return 0
        visited = [[False] * cols for _ in range(rows)]
        count = self.movingCountCroe(threshold, rows, cols, 0, 0, visited)
        return count
# test code
# 代码已在牛客网通过测试

def maxProductAfterCutting_solution(length):
    """动态规划法，从上而下的分析分解问题，自下而上的顺序计算问题"""
    result = [0, 1, 2, 3]
    if length < 2:
        return 0
    elif length < 4:
        return result[length - 1]
    products = [None]*(length + 1)
    for i in result:
        products[i] = i
    maxValue = 0
    for i in range(4, length + 1):
        maxValue = 0
        j = 1
        while j <= i/2:
            product = products[j]*products[i-j]
            if maxValue < product:
                maxValue = product
            products[i] = maxValue
            j += 1
    maxValue = products[length]
    return maxValue


def maxProductAfterCutting_solution2(length):
    """贪婪算法，尽可能多的剪长度为3的绳子，当剩下的绳子长度为4时，把绳子剪成两段为2的绳子。
    解释：当n>=5时,3*(n-3)>=2*(n-2)>n,故选用上述策略"""
    result = [0, 1, 2, 3]
    if length < 2:
        return 0
    elif length < 4:
        return result[length - 1]
    timesOf3 = length / 3
    if length - timesOf3 * 3 == 1:
        timesOf3 -= 1
    timesOf2 = (length - timesOf3 * 3) / 2
    return int(pow(3, timesOf3))*int(pow(2, timesOf2))


# test code
print(maxProductAfterCutting_solution(8))
print(maxProductAfterCutting_solution2(8))

# 方法一
def NumberOf1Croe(n):
    """将1逐位与n按位与，检测该二进制位是否有1，若有则计数。该算法需要循环sizeof(int)次"""
    count =0
    flag = 1
    while flag <= abs(n):
        if n&flag:
            count += 1
        flag = flag << 1
    return count
def NumberOf1(n):
    """计算整数的二进制数中1的个数，由于在python中负数没有用补码表示，故在主函数中另行处理"""
    if n < 0:
        return 32 - NumberOf1Croe(abs(n) -1)
    else:
        return NumberOf1Croe(n)
# 方法二
def numberOf1Croe(n):
    """将一个整数减1，都是把二进制中最右边的1变成0，并且把它右边的所有0变成1，将此数再与原数按位与，相当于将原数二进制数中最右
    边的1变成0，整数中有多少个1就可以做多少次这种操作。基于这种思想写出类的算法需要循环count次，即有多少个1循环多少次"""
    count =0
    while n:
        count += 1
        n = (n-1)&n
    return count
def numberOf1(n):
    """计算整数的二进制数中1的个数，由于在python中负数没有用补码表示，故在主函数中另行处理"""
    if n <0:
        return 32 - numberOf1Croe(abs(n) -1)
    else:
        return numberOf1Croe(n)

#test code
print(NumberOf1(-3))
print(numberOf1(-3))

"""
#将int类型转为补码表示的函数
def int2Bin32(i):
    return (bin(((1<<32) - 1) & i)[2:]).zfill(32)
"""

def PowerWithUnsignedExponent(base, exponent):
    """使用循环连乘来计算无符号指数"""
    result = 1.0
    for i in range(exponent):
        result *= base
    return result
def PowerWithUnsignedExponent2(base, exponent):
    """递归的将指数拆分成平方，减少乘法的次数，并用右移运算符代替除2，利用按位与运算符来判断函数奇偶"""
    if exponent ==0:
        return 1
    if exponent == 1:
        return base
    result = PowerWithUnsignedExponent2(base, exponent >> 1)
    result *= result #平方
    if exponent & 0x1 == 1:
        result *=base
    return result

g_InvalidInput = False
#错误输入指示，在牛客网python编程中，请删除此功能，否则不能通过测试
def Power(base, exponent):
    """主函数。浮点型数据类型不可直接用‘==’判断是否为0，可借助比较较小数1.0e-9来判断"""
    g_InvalidInput = False
    if abs(base) < 1.0e-9 and exponent < 0:
        g_InvalidInput = True
        return 0.0
    absExponent = abs(exponent)
    result = PowerWithUnsignedExponent2(base, absExponent)
    if exponent < 0:
        result = 1.0/result
    return result

#test code 
base = 2
exponent = 10
print(Power(base, exponent))

def PrintNumber(nums):
    """打印函数，从第一个非零数字开始打印，循环查找第一个非零数字打印并跳出循环
    nums必须是list类型"""
    isBeginning = True
    for i in range(len(nums)):
        if isBeginning and nums[i] != '0':
            isBeginning = False
        if not isBeginning:
            print(''.join(nums[i:]))
            break
def Increment(nums):
    """数字自增函数，并判断是否溢出，返回溢出标志，nums必须是list[str]类型，list是可变类型，在传参的时候类似于c++
    中传指针，所以无需返回即可修改传入nums中的元素"""
    isOverflow = False
    nTakeOver = 0 # 进位
    nLength = len(nums)
    for i in range(nLength - 1,-1,-1):
        #反向循环[nLength,0]，设置步长为-1即反向
        nSum = ord(nums[i]) - ord('0') + nTakeOver
        if i == nLength - 1:
            nSum += 1
        if nSum >= 10:
            if i == 0:
                isOverflow = True
            else:
                nSum -= 10
                nTakeOver = 1
                nums[i] = chr(ord('0') + nSum)
        else:
            nums[i] = chr(ord('0') + nSum)
            break
    return isOverflow
def PrintToMaxOfNDigits(n):
    """打印主函数，生成长度为n的list[str]来表示n位数字，可表示任意大的数字"""
    if n <= 0:
        return
    nums = ['0']*n
    while not Increment(nums):
        PrintNumber(nums)

        
def PrintToMaxOfNDigitsRecursively(nums, length, index):
    """利用排列组合的思想，递归的循环调用函数，打印不同的数字组合"""
    if index == length - 1:
        PrintNumber(nums)
        return
    for i in range(10):
        nums[index+1] = chr(ord('0') + i)
        PrintToMaxOfNDigitsRecursively(nums, length, index + 1)
def PrintToMaxOfNDigits2(n):
    """打印数字，递归调用版"""
    if n <=0:
        return
    nums = ['0']*n
    for i in range(10):
        nums[0] = chr(i+ord('0'))
        PrintToMaxOfNDigitsRecursively(nums, len(nums), 0)
#test code
PrintToMaxOfNDigits(1)
PrintToMaxOfNDigits2(-1)

class ListNode:
    """创建链表类"""
    def __init__(self, x=None):
        self.val = x
        self.next = None
def DeleteNode(pListHead, pToBeDelete):
    """通过复制的方式删除指定节点，若要删除尾节点，则只能遍历再删除。平均时间复杂度[(n-1)*O(1)+O(n)]/n=O(1)"""
#     print("pListHead's id is: "+str(id(pListHead)))
#     print("pToBeDelete's id is: "+str(id(pToBeDelete)))
    if not pListHead or not pToBeDelete:
        return
    if pToBeDelete.next != None:
        pNext = pToBeDelete.next
        pToBeDelete.val = pNext.val
#         print("pToBeDelete.val's id is: "+str(id(pToBeDelete.val)))
        pToBeDelete.next = pNext.next
    elif pListHead == pToBeDelete:
        pListHead.val = None
        pListHead.next = None
#         pListHead = ListNode()
#         print("pListHead's id is: "+str(id(pListHead)))
    else:
        pNode = pListHead
        while pNode.next != pToBeDelete:
            pNode = pNode.next
        pNode.next = None
#     return pListHead
##创建链表
head = ListNode('head->')
# print("head's id is: "+str(id(head)))
#可变对象直接赋值就是浅拷贝，相当于c++中传递地址
pnode = head
# print("pnode's id is: "+str(id(pnode)))
valueList = list('')
for i in valueList:
    pnode.next = ListNode(i)
    pnode = pnode.next
#     print("pnode's id is: "+str(id(pnode)))
# gnode = ListNode('1')
DeleteNode(head, pnode)    
#验证链表用代码
# print(gnode.val)
rnode = head
while rnode != None:
    print(rnode.val)
    rnode = rnode.next

"""
！！！注：python传参与c++中常引用传参相似，对于可变对象，不可直接改变对象本身，但可改变对象内置的值,如直接
改链表头不可行，但可以改链表头的值及其他未传入的节点，若一定要改链表头则只能通过返回值的方式进行，例如list对象
"""

#该算法仅能删除相邻重复节点，比如[1,2,3,4,1]首位节点重复就不会被删除，故不作深入测试
class Solution:
    def deleteDuplication(self, phead):
        if phead == None:
            return phead
        pPreNode = None
        pNode = phead
        while pNode != None:
            pNext = pNode.next
            needDelete = False
            if pNext != None and pNext.val == pNode.val:
                needDelete = True
            if not needDelete:
                pPreNode = pNode
                pNode = pNode.next
            else:
                value = pNode.val
                pToBeDel = pNode
                while pToBeDel != None and pToBeDel.val == value:
                    pNext = pToBeDel.next
                    del pToBeDel
                    pToBeDel = pNext
                if pPreNode == None:
                    phead = pNext
                else:
                    pPreNode.next = pNext
                pNode = pNext
        return phead
# test code
# 代码已在牛客网通过测试

class Solution:
    def matchCore(self, strs, pattern):
        """递归探索每一种情况"""
        if not strs and not pattern:
            return True
        if strs and not pattern:
            return False
        if len(pattern) > 1 and pattern[1] == '*':
            if strs and (pattern[0] == strs[0] or pattern[0] == '.'):
                return self.matchCore(strs[1:],pattern[2:]) or self.matchCore(strs[1:],pattern) or self.matchCore(strs, pattern[2:])
            else:
                return self.matchCore(strs, pattern[2:])
        if strs and (strs[0] == pattern[0] or pattern[0] == '.'):
            return self.matchCore(strs[1:], pattern[1:])
        return False
    def match(self, s, pattern):
        if s == None or pattern == None:
            return False
        return self.matchCore(s, pattern)
a = Solution()
print(a.match('aaa', 'a.a'))

class Solution:
    def scanUnsignedInterger(self, strs):
        """对传入字符串从头计算是无符号数字的长度，返回长度"""
        if not strs:
            return 0
        i = 0
        while i >= 0 and i < len(strs) and strs[i] >= '0' and strs[i] <= '9':
            i += 1
        return i
    def scanInteger(self, strs):
        """对传入字符串从头计算有符号数字的长度，返回长度"""
        if not strs:
            return 0
        if strs[0] in '-+':
            return 1 + self.scanUnsignedInterger(strs[1:])
        return self.scanUnsignedInterger(strs)
    def isNumeric(self, s):
        """使用index表示首个未进行遍历的字符的索引，使用temp变量表示上一个匹配的长度，为应对index有可能超出字符串长度，
        每次进行判断之前先进行判断是否溢出"""
        if not s:
            return False
        index = 0
        temp = self.scanInteger(s)
        numeric = temp > 0
        index += temp
        if index < len(s) and s[index] == '.':
            index += 1
            temp = self.scanUnsignedInterger(s[index:])
            numeric = temp or numeric
            index += temp
        if index < len(s) and (s[index] == 'e' or s[index] == 'E'):
            index += 1
            temp = self.scanInteger(s[index:])
            numeric = numeric and temp
            index += temp
        return bool(numeric) and index == len(s)
#test code 
a_test = Solution()
print(a_test.isNumeric('+100'))

class Solution:
    def reOrderArray(self, array):
        """对撞指针法，发现不符合要求的元素则与另一不符合要求的元素调换顺序"""
        if not array:
            return
        pBegin = 0
        pEnd = len(array) - 1
        while pBegin < pEnd:
            while pBegin < pEnd and array[pBegin] & 0x1 != 0:
                pBegin += 1
            while pBegin < pEnd and array[pEnd] & 0x1 == 0:
                pEnd -= 1
            if pBegin < pEnd:
                temp = array[pBegin]
                array[pBegin] = array[pEnd]
                array[pEnd] = temp
#test code
a_test = Solution()
b_list = [1,2,3,4,5,6,7,8,9]
a_test.reOrderArray(b_list)
print(b_list)

class Solution:
    """将判断函数解耦分离出来，可以让程序具有更好的通用性"""
    def _isEven(self, n):
        """判断函数"""
        return (n&1) == 0
    def reOrderArray(self, array):
        """主函数，指针对撞，交换不符合条件的值"""
        if not array:
            return
        pBegin = 0
        pEnd = len(array) - 1
        while pBegin < pEnd:
            while pBegin < pEnd and not self._isEven(array[pBegin]):
                pBegin += 1
            while pBegin < pEnd and self._isEven(array[pEnd]):
                pEnd -= 1
            if pBegin < pEnd:
                temp = array[pBegin]
                array[pBegin] = array[pEnd]
                array[pEnd] = temp
#test code
a_test = Solution()
b_list = [1,2,3,4,5,6,7,8,9]
a_test.reOrderArray(b_list)
print(b_list)

#注意牛客网上增加了附加条件，奇数与奇数之间，偶数与偶数之间的相对位置不能改变，目前暂无较好的解法
class Solution:
    def reOrderArray(self, array):
        # write code here
        count = 0
        for i in range(0,len(array)):
            for j in range(len(array)-1,i,-1):
                if array[j-1]%2 ==0 and array[j]%2==1:
                    array[j], array[j-1]= array[j-1], array[j]
        return array

class ListNode:
    """创建链表类"""
    def __init__(self, x=None):
        self.val = x
        self.next = None
class Solution:
    def FindKthToTail(self, head, k):
        if head is None or k <= 0:
            return None
        pAHead = head
        for i in range(k-1):
            if pAHead.next != None:
                pAHead = pAHead.next
            else:
                return None
        pBHead = head
        while pAHead.next != None:
            pAHead = pAHead.next
            pBHead = pBHead.next
        return pBHead
#test code
#牛客网已通过测试

class Solution:
    def MeetingNode(self, pHead):
        """利用速度不同的双指针，检查链表中是否包含环，若包含则返回环中的节点"""
        if pHead == None:
            return None
        pSlow = pHead.next
        if pSlow == None:
            return None
        pFast = pSlow.next
        while pFast != None and pSlow != None:
            if pFast == pSlow:
                return pFast
            pSlow = pSlow.next
            pFast = pFast.next
            if pFast != None:
                pFast = pFast.next
        return None
    def EntryNodeOfLoop(self, pHead):
        """获取环中的节点，并循环统计环中包含节点的个数nodesInLoop，再利用间隔nodesInLoop个节点的指针对撞，判断入口"""
        meetingNode = self.MeetingNode(pHead)
        if meetingNode == None:
            return None
        nodesInLoop = 1
        pNode1 = meetingNode
        while pNode1.next != meetingNode:
            pNode1 = pNode1.next
            nodesInLoop += 1
        pNode1 = pHead
        for i in range(nodesInLoop):
            pNode1 = pNode1.next
        pNode2 = pHead
        while pNode1 != pNode2:
            pNode1 = pNode1.next
            pNode2 = pNode2.next
        return pNode1
    
#test code 
#牛客网上已通过测试

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        """利用三个指针分别指向当前指针的前和后节点，以防止链表反转时断裂，并初始化反转后链表的头节点和前节点，
        以防返回出错"""
        pReversedHead = None
        pNode = pHead
        pPrev = None
        while pNode != None:
            pNext = pNode.next
            if pNext == None:
                pReversedHead = pNode
            pNode.next = pPrev
            pPrev = pNode
            pNode = pNext
        return pReversedHead
#test code
#代码通过牛客网测试

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        """递归比较每一个节点的值，并将较小的节点加入新的链表中"""
        if pHead1 == None:
            return pHead2
        elif pHead2 == None:
            return pHead1
        pMergedHead = None
        if pHead1.val < pHead2.val:
            pMergedHead = pHead1
            pMergedHead.next = self.Merge(pHead1.next, pHead2)
        else:
            pMergedHead = pHead2
            pMergedHead.next = self.Merge(pHead1, pHead2.next)
        return pMergedHead
#test code
#牛客网已通过测试

class Solution:
    def Equal(self, num1, num2):
        """定义通用的比较函数，可以兼容更多不同类型的存储值"""
        if abs(num1 - num2) < 1E-7:
            return True
        else:
            return False
    def DoesTree1HaveTree2(self, pRoot1, pRoot2):
        """递归比较，两颗子树的值"""
        if pRoot2 == None:
            return True
        if pRoot1 == None:
            return False
        if not self.Equal(pRoot1.val, pRoot2.val):
            return False
        return self.DoesTree1HaveTree2(pRoot1.left, pRoot2.left) and \
    self.DoesTree1HaveTree2(pRoot1.right, pRoot2.right)
    
    def HasSubtree(self, pRoot1, pRoot2):
        """递归的进行先根序遍历，从根节点开始对值进行比较"""
        result = False
        if pRoot1 != None and pRoot2 != None:
            if self.Equal(pRoot1.val, pRoot2.val):
                result = self.DoesTree1HaveTree2(pRoot1, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
# test code
# 已在牛客网通过测试

class Solution:
    def Mirror(self, root):
        """递归的交换二叉树的左右子树，遇叶子节点停止递归"""
        if root == None:
            return
        if root.left == None and root.right == None:
            return
        pTemp = root.left
        root.left = root.right
        root.right = pTemp
        if root.left:
            self.Mirror(root.left)
        if root.right:
            self.Mirror(root.right)
# test code
# 已在牛客网通过测试

class Solution:
    def isSymmetricalCore(self, pRoot1, pRoot2):
        """递归比较前序遍历和对称前序遍历序列的值，若相同，则为对称二叉树"""
        if pRoot1 == None and pRoot2 == None:
            return True
        if pRoot1 == None or pRoot2 == None:
            return False
        if pRoot1.val != pRoot2.val:
            return False
        return self.isSymmetricalCore(pRoot1.left,pRoot2.right) and self.isSymmetricalCore(pRoot1.right, pRoot2.left)
    def isSymmetrical(self, pRoot):
        """调用核心函数，利用传参避免指向同一个对象"""
        return self.isSymmetricalCore(pRoot, pRoot)
    
# test code
# 已在牛客网上通过测试

class Solution:
    def PrintMatrixInCircle(self, matrix, start, result):
        """根据给定的start打印二维矩阵的一圈，并将其存入result中，因为result是列表、可变类型，函数不返回
        任何参数也可对传入的result中的元素进行修改"""
        endX = len(matrix[0]) - 1 - start
        endY = len(matrix) - 1 - start
        #从左到右打印一行
        for i in range(start, endX + 1):
            number = matrix[start][i]
            result.append(number)
        #从上到下打印一列
        if start < endY:
            for i in range(start + 1, endY + 1):
                number = matrix[i][endX]
                result.append(number)
        #从右到左打印一行
        if start < endX and start < endY:
            for i in range(endX - 1, start - 1, -1):
                number = matrix[endY][i]
                result.append(number)
        #从下到上打印一列
        if start < endX and start < endY - 1:
            for i in range(endY - 1, start, -1):
                number = matrix[i][start]
                result.append(number)

    def printMatrix(self, matrix):
        """循环打印每一圈矩阵"""
        result = []
        if not matrix or len(matrix) < 0 or len(matrix[0]) < 0:
            return result
        start = 0
        while len(matrix[0]) > start*2 and len(matrix) > start*2:
            self.PrintMatrixInCircle(matrix, start, result)
            start += 1
        return result
# test code
# 已在牛客网通过测试

class Solution:
    """维护一个和data相同大小的辅助栈，用来存储最小值"""
    def __init__(self):
        self.m_data = []
        self.m_min = []
    def push(self, node):
        """压入数据的同时维护辅助栈，使的辅助栈中存储的最小值始终和数据栈中具有相同的位置"""
        self.m_data.append(node)
        if len(self.m_min) == 0 or node < self.m_min[-1]:
            self.m_min.append(node)
        else:
            self.m_min.append(self.m_min[-1])
    def pop(self):
        if len(self.m_min) > 0 and len(self.m_data) > 0:
            self.m_data.pop(-1)
            self.m_min.pop(-1)
        else:
            assert Exception("data is empty")
    def top(self):
        return self.m_data[-1]
    def min(self):
        return self.m_min[-1]
    
# test code
# 已在牛客网通过测试

class Solution:
    def IsPopOrder(self, pushV, popV):
        """利用辅助栈模拟栈的压入和弹出，与弹出序列比较若不符合则返回False"""
        bPossible = False
        if pushV != None and popV != None:
            pNextPush = 0
            pNextPop = 0
            stackData = []
            nLength = len(pushV)
            while pNextPop < nLength:
                while not stackData or stackData[-1] != popV[pNextPop]:
                    if pNextPush == nLength:
                        break
                    stackData.append(pushV[pNextPush])
                    pNextPush += 1
                if stackData[-1] != popV[pNextPop]:
                    break
                stackData.pop(-1)
                pNextPop += 1
            if not stackData and pNextPop == nLength:
                bPossible = True
        return bPossible
# test code
# 已在牛客网通过测试

class Solution:
    def PrintFromTopToBottom(self, root):
        """利用队列的先进先出原则，顺序存储要打印的数值"""
        result = []
        if not root:
            return result
        dequeTreeNode = []
        dequeTreeNode.append(root)
        while len(dequeTreeNode):
            pNode = dequeTreeNode.pop(0)
            result.append(pNode.val)
            if pNode.left:
                dequeTreeNode.append(pNode.left)
            if pNode.right:
                dequeTreeNode.append(pNode.right)
        return result
# test code
# 已在牛客网通过测试