变态跳台阶 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 分析 设 级台阶有 种跳法，根据最后一次跳台阶的数目可以分解为最后一次一级，则前面需要跳 级，有 种跳法；最后一次跳两级，则前面需要跳 级，有 种跳法。以此类推 易知，$$两式相减得， # -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, n): if n<0: return 0 ans = 1 for i in r...

斐波那契数列与跳台阶 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 差别只在于初始值的不同 # -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): if n<0: return if n ==0: return 0 pre,ppre=1,0 ...

旋转数组的最小数字 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 旋转数组的最小数字 分析 旋转数组有两个单调区间在每个单调区间内，都是递增的。右边的单调区间整体偏小。因此，若中间的数大于最右边的那个数。说明中间的那个数在左单调区间内。因此就可以确定最小值一定在中间的那个数的右边。其余同理。 # -*- coding:utf-8 -*- class Solution: ...

用两个栈实现队列 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 分析 第一个栈用来当蓄水池和入队，第二个栈用来出队，此栈没有元素时，从蓄水池中取出一部分元素。 第一个栈先进的后出（从而在第二个栈中后进）。第二个栈后进的先出。因此连接起来就是第一个栈先进的第二个栈先出。 # -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack1 = []#enqueue self.stack2 = [] def push(self, node)...

重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回构造的...

编程实现单链表的逆转函数 实现单链表的逆转函数，输入一个链表，反转链表后，返回翻转之后的链表。 同从尾到头打印链表 # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, head): if not head : return [] cur = head.next ...

每K个一组反转链表 答案来自答主 输入描述: 第一行输入是链表的值第二行输入是K的值，K是大于或等于1的整数输入形式为：1 2 3 4 52输出描述: 当 k = 2 时，应当输出:2 1 4 3 5当 k = 3 时，应当输出:3 2 1 4 5当k=6时，应当输出：1 2 3 4 5输入 1 2 3 4 5 2输出 2 1 4 3 5确定k有几组，然后用reverse循环翻转每组， reverse翻转cishu = k//2次，举例3，4时，翻转1，2次，很合理。链接：https://www.nowcoder.com/questionTerminal/a632ec91a4524773b8a...