刷算法题

入门级难度的几道题目
简单乘法->斐波那契数列->链表->整数排序->二叉树
一点一点过度, 让思维进入到刷题状态.

矩阵面积

实现一个矩阵类Rectangle，包含如下的一些成员变量与函数：

两个共有的成员变量 width 和 height 分别代表宽度和高度。
一个构造函数，接受2个参数 width 和 height 来设定矩阵的宽度和高度。
一个成员函数 getArea，返回这个矩阵的面积。

python3.5

import os
class ReactAngle():
    width = None
    height = None
    def __init__(self, *args):
        self.width = args[0]
        self.height = args[1]

    def getArea(self):

        if self.width < 0 or self.height < 0 or self.width == None or self.height == None:
            raise AssertionError("参数错误")
        return self.width * self.height

react = ReactAngle(1,1)
print(react.getArea())

斐波那契数列

斐波那契数列, 查找斐波那契数列中的第N个数.
所谓斐波那契数列是指.
前两个数是0,1
第i个数是第i-1个数和第i-2个数的和.
举例前十个数字
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
输出举例
in 1 out 0,
in 3 out 1
in 10 out 34

递归解法

def fibonacci_recursion(n):
    if n < 1:
        return None
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci_recursion(n - 1) + fibonacci_recursion(n - 2)

print(fibonacci_recursion(11))

循环解法

def fibonacci(n):
    if n < 1 or not isinstance(n, int):
        return None

    if n == 1:
        return 0
    elif n == 2:
        return 1
    previousNum0 = 0
    previousNum1 = 1
    result = None
    for i in range(n - 2):
        result = previousNum0 + previousNum1
        previousNum0 = previousNum1
        previousNum1 = result
    return result

print(fibonacci(11))

动态规划+递归(动态规划的思想优化递归过程)

def fibonacci_recursion_guihua(array, n):
    if n < 1:
        return None
    if n == 1:
        array[1] = 0
        return 0
    if n == 2:
        array[2] = 1
        return 1
    try:
        if array[n] != None and array[n] >= 0:
            return array[n]
    except Exception as e:
        pass
    array[n] = fibonacci_recursion_guihua(array, n - 1) + fibonacci_recursion_guihua(array, n - 2)
    return fibonacci_recursion_guihua(array, n - 1) + fibonacci_recursion_guihua(array, n - 2)

array = {}
print(fibonacci_recursion_guihua(array, 11))

删除链表中的元素

删除链表中等于给定值val的所有节点。
给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。

思路: 定义链表结点, 构造链表, 编写删除函数, 链表使用不带头结点的单向链表.

python3.5

# 定义结点
class ListNode:
    val = None
    next = None
    def __init__(self, val, next):
        self.val = val
        self.next = next

# 构造链表函数
def createList(param=[]):
    firstNode = None
    lastNode = None
    if not isinstance(param, list) or param == []:
        return None
    for i in param:
        node = ListNode(i, None)
        if firstNode == None:
            firstNode = node
            lastNode = node
        else:
            lastNode.next = node
            lastNode = node
    return firstNode

# 输出链表以查看删除结果
def printList(list):
    print(id(list))
    while(list != None):
        print(list.val)
        list = list.next

param = [3,3,3,3,1,2,3,4,5,6,5,7,8,9,3]
List = createList(param)
printList(List)

# 删除函数
def removeVal(list, val):
    finalList = list
    previousNode = None
    while(list != None):
        if list.val == val:
            if previousNode == None:
                finalList = list.next
            else:
                previousNode.next = list.next
        else:
            previousNode = list
        list = list.next
    return finalList

import copy
finalList = removeVal(copy.deepcopy(List), 3)
printList(finalList)

整数排序

给一组整数，按照升序排序, 对于数组 [3, 2, 1, 4, 5], 排序后为：[1, 2, 3, 4, 5]

排序算法很多种, 都试一下吧.

首先给出待排序数组

data = [22,2,2,88,8,985,47,12,5544,63,52,48,41,22,33,69,8,52,7,4,1,4,47,47,22,2]

插入排序

插入排序大致思路是依次取各个元素, 遍历 以排序部分, 将新元素插入到以排序部分的合适位置. 整个数组中左侧为以排序部分, 右侧为待排序部分.

最终返回的是原始数组对象, 并没有返回新对象, 仅操作原数组中的元素完成排序.

python3.5

data = [22,2,2,88,8,985,47,12,5544,63,52,48,41,22,33,69,8,52,7,4,1,4,47,47,22,2]
def insertSort(data):

    location = 0
    if not isinstance(data, list):
        return None
    for i in range(1, len(data)):
        for x in range(location + 1):
            if data[x] == data[i]:
                val = data[i]
                del data[i]
                data.insert(x+1, val)
                continue
            elif data[x] > data[i]:
                val = data[i]
                del data[i]
                data.insert(x, val)
                continue
            if x == location:
                val = data[i]
                del data[i]
                data.insert(x+1, val)
        location = location + 1


print(data)
insertSort(data)
print(data)

选择排序

选择排序大致思路, 是每次选出最小值和以排序部分的最右侧进行交换

data = [22,2,2,88,8,985,47,12,5544,63,52,48,41,22,33,69,8,52,7,4,1,4,47,47,22,2]
def chooseSort(data):
    if not isinstance(data, list):
        return None
    for i in range(len(data)):

        minNum = None
        maxNumLocation = None
        for x in range(i, len(data)):
            if minNum == None:
                minNum = data[x]
                maxNumLocation = x
            if data[x] < minNum:
                minNum = data[x]
                maxNumLocation = x
        if minNum == None:
            raise AssertionError("没有选出最小值")
        del data[maxNumLocation]
        data.insert(i, minNum)

print(data)
chooseSort(data)
print(data)

冒泡排序

冒泡排序思路, 进行n次交换, 每一轮交换意味着待排序数组中的最大值已经被交换到最顶端.

def bubblingSort(data=[]):
    if data == [] or not isinstance(data, list):
        return None
    for x in range(len(data)):

        for y in range(len(data)-x-1):
            if data[y] > data[y+1]:
                data[y], data[y+1] = data[y+1], data[y]

print(data)
bubblingSort(data)
print(data)

希尔排序

希尔排序是基于一个事实, 类似分代收集法, 是基于越先创建的对象越不容易被销毁, 希尔排序是基于, 数组整体越接近有序, 则插入排序的效率就越高.

increment = [8,3,1] #增量序列
def shellSort(data=[]):
    for x in increment:
        location = 0
        while(location*x < len(data)):
            # val = data[location+1 * x]
            array = list(range(0, len(data), x))
            for y in range(0, len(data), x)[:-1]:
                # 插排过程
                if data[y+x] < data[y]:
                    # 此时需要将有序数组右移空出位置
                    val = data[y+x]
                    i = 1
                    sentry = y
                    while(sentry < y+x):
                        data[y+x] = data[y+x-(i*x)]
                        sentry = sentry+i*x
                        i = i+1
                    data[y] = val
            location = location +1


print(data)
shellSort(data)
print(data)

快速排序

快速排序首先选出基准元素, 然后把数组按基准元素分为左右两侧, 左右两侧再分别选出基准元素, 再次分隔, 递归进行此过程 直到待分隔数组中只有一个元素为止.

def quickSort(data=[], start=0, end=0):
    standard = data[start]

    height = start + 1
    standardLocation = start
    if height >= end:
        return
    while(height < end):
        if data[height] < standard:
            val = data[height]
            del data[height]
            data.insert(standardLocation, val)
            standardLocation = standardLocation + 1
        height = height + 1

    quickSort(data, start, standardLocation)
    quickSort(data, standardLocation+1, end)

print(data)
quickSort(data, 0, len(data))
print(data)

归并排序

归并排序的核心思想是归并操作, 归并操作是指将两个有序数组合并为一个有序数组的过程, 先进行分隔, 分隔到最底层, 每个有序数组只有1个元素,两个元素之间归并自然有序, 这样依次进行归并操作.

def mergeSort(data=[], left=0, right=0):
    if not isinstance(data, list):
        return None
    if left >= right:
        return
    mid = int((left+right)/2)
    mergeSort(data, left, mid)
    mergeSort(data, mid+1, right)

    # 归并操作
    temp = []
    pointer0 = left
    pointer1 = mid+1
    i = 0

    while(pointer0 <= mid and pointer1 <= right):
        if data[pointer0] == data[pointer1]:
            temp.append(data[pointer0])
            temp.append(data[pointer1])
            pointer0 = pointer0 + 1
            pointer1 = pointer1 + 1
        elif data[pointer0] < data[pointer1]:
            temp.append(data[pointer0])
            pointer0 = pointer0 + 1
        # else:
        elif data[pointer1] < data[pointer0]:
            temp.append(data[pointer1])
            pointer1 = pointer1 + 1

    # 此时还有一种可能就是  二路归并的时候, 一路已经走完了.  上面的
    # 循环 一路走完就break 此时如果一路长度大于另一路, 大一路中的剩余元素没有被添加到辅助temp空间中.
    while(pointer0 <= mid):
        temp.append(data[pointer0])
        pointer0 = pointer0 + 1
    while(pointer1 <= right):
        temp.append(data[pointer1])
        pointer1 = pointer1 + 1

    x = 0
    while(x < len(temp)):
        data[left+x] = temp[x]
        x = x + 1

print(data)
mergeSort(data, 0, len(data)-1)
print(data)

堆排序

堆排序就是利用二叉树进行排序, 构造二叉树, 根据升序, 降序, 选择大根堆, 小根堆, 将根节点和末尾界定啊交换, 输出, 再调整二叉树到大根堆(小根堆), 重复此过程.
小根堆的构造, 类似于冒泡排序的思想, 从第一个非叶子结点开始遍历二叉树判断它的两个叶子结点, 如果存在右孩子, 判断它与右孩子的大小, 做交换, 再判断它与做孩子的大小做交换, 如果不存在右孩子, 直接与做孩子比较做交换, 依次向上直到根节点, 交换完毕, 根节点就是当前树中的最小节点, 输出根, 将它与末尾结点做交换, 下一次遍历过程不遍历末尾已经输出的结点.

data = [22,2,2,88,8,985,47,12,5544,63,52,48,41,22,33,69,8,52,7,4,1,4,47,47,22,2]
def heapSort(data=[]):

    if not isinstance(data, list):
        raise AssertionError("传入参数类型必须为list")
    result = []
    x = 0
    while (x < len(data)):
        # 构造小根堆. 首先将数组看做是一个完全二叉树的存储结构. 对其进行改造
        # 从第一个非叶子节点开始向根节点遍历. 此节点一定有左孩子不一定有右孩子.
        for i in range(0, int((len(data)-x)/2))[::-1]:
            temp = data[i] #当前节点
            leftChild = data[i*2+1]  #因为数组从0开始所以要+1
            # 判断是否有右孩子.
            if i*2+2 < len(data) - x:
                # 有右孩子
                if data[i*2+1] < data[i*2+2]:
                    if data[i*2+1] < temp:
                        data[i], data[i*2+1] = data[2*i+1], data[i]
                else:
                    if data[i*2+2] < temp:
                        data[i], data[i*2+2] = data[2*i+2], data[i]
            else:
                if leftChild < temp:
                    data[i], data[i*2+1] = data[2*i+1], data[i]

        # 堆构造完毕
        result.append(data[0])
        data[0], data[len(data)-x-1] = data[len(data)-x-1], data[0]
        x = x+1
    return result

# md最后还是没忍住 操作了data, 由于每次和最后一个元素交换, 所以data 是逆序的.
print(data)
print(heapSort(data))
print(data)

基数排序

也叫木桶排序, 首先计算各个数字的各位, 按照个位大小值分别放入不同的"桶"中, 再将桶中的数据按照桶的大小顺序, 顺序排列, 再计算10位的值, 再计算100位的值, 一次类推, 直到计算完最大数字的最大位, 最后得到的数组是有序的.

data = [22,2,2,88,8,985,47,12,5544,63,52,48,41,22,33,69,8,52,7,4,1,4,47,47,22,2]
def radixSort(data=[]):
    if not isinstance(data, list):
        raise AssertionError("出入参数必须为list类型")
    # 待排序数组中最大数字的 数值量级(是10的多少次方的量级) 求出指数
    # 我不愿意使用 数字转字符串的形式计算量级, 都使用数字的运算来搞定它吧.
    exponent = 0
    for i in data:
        iexponent = 0
        for e in range(0,100): #恐怕10**100 在python中int已经溢出了. 先不管它.
            if i / (10**e) > 1:
                iexponent = e
        if iexponent > exponent:
            exponent = iexponent
    #量级计算完毕  创建"桶"  基数排序? 木桶排序?
    bucket = []
    for i in range(10):
        ibucket = []
        bucket.append(ibucket)
    for i in range(0, exponent+2):
        dividend = 10**i
        for x in data:
            val = x % dividend
            val = int(val / (dividend / 10))
            bucket[val].append(x)
        # 分配完毕将 木桶中的数字重新放入数组中
        data.clear()
        for x in bucket:
            for y in x:
                data.append(y)
        # 按照某个次方数 排序完毕 清理木桶空间
        for x in bucket:
            x.clear()

print(data)
radixSort(data)
print(data)

二叉树的最大结点

在二叉树中寻找值最大的节点并返回。

遍历二叉树即可, 此处仅考虑二叉树的链式存储结构, 不考虑顺序存储结构.

import queue

class TreeNode():
    val = None
    leftNode = None
    rightNode = None
    def __init__(self, val, left, right):
        self.val = val
        self.leftNode = left
        self.rightNode = right

data = [3,4,6,234,5,66,4,98,1002,8990,456,65]
# 使用队列做辅助, 层序构建二叉树.
def createTree(data=[]):

    que = queue.Queue()
    root = TreeNode(data[0],None, None)
    que.put(root)
    i = 1
    while(i < len(data)):
        if not que.empty():
            node = que.get()
            if node.leftNode == None:
                nNode = TreeNode(data[i], None, None)
                node.leftNode = nNode
                que.put(nNode)
                i = i+1
            if (i) < len(data) and node.rightNode == None:
                nNode = TreeNode(data[i], None, None)
                node.rightNode = nNode
                que.put(nNode)
                i = i+1
        else:
            return root
    return root

root = createTree(data)



class traverse():
    maxNode = None

    def beforeTraverse(self, root):
        if not isinstance(root, TreeNode):
            raise AssertionError("传入参数必须是二叉树的根节点")

        if self.maxNode == None:
            self.maxNode = root
        if root.val != None and self.maxNode.val != None and self.maxNode.val < root.val:
            self.maxNode = root

        if root.leftNode != None:
            self.beforeTraverse(root.leftNode)
        if root.rightNode != None:
            self.beforeTraverse(root.rightNode)

        return self.maxNode

    def middleTraverse(self, root):
        if not isinstance(root, TreeNode):
            raise AssertionError("传入参数必须是二叉树的根节点")
        if self.maxNode == None:
            self.maxNode = root

        if root.leftNode != None:
            self.middleTraverse(root.leftNode)
        print(root.val)
        if root.val != None and self.maxNode.val != None and self.maxNode.val < root.val:
            self.maxNode = root
        if root.rightNode != None:
            self.middleTraverse(root.rightNode)

        return self.maxNode

    def backTraverse(self, root):
        if not isinstance(root, TreeNode):
            raise AssertionError("传入参数必须为二叉树的根节点")
        if self.maxNode == None:
            self.maxNode = root

        if root.leftNode != None:
            self.backTraverse(root.leftNode)
        if root.rightNode != None:
            self.backTraverse(root.rightNode)
        print(root.val)
        if root.val != None and self.maxNode.val != None and self.maxNode.val < root.val:
            self.maxNode = root
        return self.maxNode

obj = traverse()
print(obj.backTraverse(root).val)

翻转二叉树

递归法

def invertBinaryTree(root):
    if root == None:
        return
    root.leftNode, root.rightNode = root.rightNode, root.leftNode
    invertBinaryTree(root.leftNode)
    invertBinaryTree(root.rightNode)

invertBinaryTree(root)

栈辅助

def invertTree(root):

    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        if node != None:
            continue
        # 维持先序的二叉树遍历过程
        root.leftNode, root.rightNode = root.rightNode, root.leftNode
        if root.rightNode:
            stack.append(root.rightNode)
        if root.leftNode:
            stack.append(root.leftNode)

invertTree(root)

队列辅助

def queueInvertTree(root):
    que=queue.Queue()
    que.put(root)

    while(not que.empty()):
        # 交换, 然后子结点入队列, 其实和栈是一样的.
        root = que.get()
        root.leftNode, root.rightNode = root.rightNode, root.leftNode
        if root.leftNode:
            que.put(root.leftNode)
        if root.rightNode:
            que.put(root.rightNode)

queueInvertTree(root)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,222评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,455评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,720评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,568评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,696评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,879评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,028评论 3赞 409
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,773评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,220评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,550评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,697评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,360评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,002评论 3赞 315
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,782评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,010评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,433评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,587评论 2赞 350