算法 - 技术教程文章
冒泡排序、选择排序、快速排序、插入排序【代码】
冒泡排序 排序只对一维数据有意义. 两层循环, 第一层是遍历每一个元素. 第二层循环,让两两之间进行比较交换. 时间复杂度: O(n^2) 空间复杂度: O(1) 稳定性: 稳定的 def buble_sort(arr):for i in range(len(arr)-1):for j in range(len(arr)-i-1):if arr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]return arr选择排序 选择后面的最小的和当前的元素进行对比 时间复杂度: O(n^2) 空间复杂度: O(1) 稳定性: 不稳定 def select_sor...
归并排序【代码】
下面是归并排序的一些特征：时间复杂度，最好最坏平均都为：O(nlog2n) 空间复杂度，最好最坏平均都为：O(n) 是否稳定：稳定二路归并的时间复杂度为O(nlog2n)，多路归并排序在引入败者树后也为O(nlog2n) 只有在最后一次排序后才每个元素才确定是在最终位置 归并的含义是将两个或两个以上的有序表组合成一个新的有序表 2路归并排序的基本思想：将初始待排序的每个元素都看成是一个排好序的子表，然后两两归并，得到n/2个长度为2或1的...
245-二叉树的学习(1)【代码】【图】
树的定义树形结构：一对多的结构 注意：第一层下标为0。 二叉树的概念 （递归定义） 左右孩子也是二叉树 左子树和右子树的数据互不相交！ 二叉树的定义 满二叉树 证明：n0=n2+1 解：因为 n=n0+n1+n2 ，分枝数：一个结点针对一个分枝，2 * n2+ 1n1=L。根节点由root指向，分枝和root没关系。即n=2n2+1*n1+1。所以将两式结合。得出：n0=n2+1 完全二叉树 注意：是从右向左依次缺少若干个结点。 证明： 二叉树的存储结构(3种) 1、...
线索二叉树（C语言）【代码】【图】
实现下面这棵树：先序遍历: A B C D E F中序遍历: C B D A E F 代码 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <unistd.h>typedef enum {links, thread} TAG;typedef struct treeNode {char name;struct treeNode *lchild, *rchild;TAG ltag;TAG rtag; }TREENODE, *TREE;void createTree(TREE *); void traverse(TREE); void traverse_middle(TREE); void traverse_middle_detail(TREE); // 线索化二...
插入排序和归并排序【代码】【图】
插入排序思想:在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使这n个数也是排好顺序的。如此反复循环，直到全部排好顺序.(当待排序数据全部有序时,时间复杂度为O(N),最坏情况下时间复杂度为O(N*N),与待排序数据的状态有关).public class InsertSort {public static void insertSort(int[] arr) {if(arr == null || arr.length < 2)return ;for(int i = 1; i < arr.length; i++) {for(int j = ...
【Leetcode热题100——宽度优先搜索-二叉树】Leetcode 102. 二叉树的层序遍历【代码】【图】
Leetcode 102. 二叉树的层序遍历 题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 一道非常标准的宽度优先搜索题目，直接套算法模板就成。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(null...
LeetCode114二叉树展开为链表(递归)【代码】【图】
题目 递归保存当前结点的左右结点，遇到的左结点直接拼到右节点，左节点遍历完之后回溯，找到当前最底层的右结点，再将右节点拼接过去。两个版本 一 有返回值public TreeNode build(TreeNode root){if (root == null) return null;TreeNode left = root.left;TreeNode right = root.right;root.left = null;root.right = build(left);TreeNode tmp = root;while (tmp.right != null) tmp = tmp.right;tmp.right = build(right);re...
101. 对称二叉树【图】
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetric(self, root: TreeNode) -> bool: def cmp(le,ri): if le is None and ri is None: return True if le is None or ri is None or le.v...
剑指Offer55-II题解-平衡二叉树【代码】
问题描述 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 示例 1: 给定二叉树 [3,9,20,null,null,15,7]3/ 9 20/ 15 7 返回 true 。示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4]1/ 2 2/ 3 3/ 4 4 返回 false 。限制： 0 <= 树的结点个数 <= 10000解题思路：后序遍历 + 剪枝 （从底至顶） 思路是对二叉树做后序遍历，...
邻接表【代码】【图】
邻接矩阵缺点： 邻接矩阵是不错的存储结构，但是我们发现，对于边数相对于顶点较少的图，这种结构是存在对存储空间的极大浪费的 因此在处理稀疏图时，可以采用下面将要介绍的邻接表无向图的邻接表有向图的邻接表网图的邻接表邻接表存储有向图的类有向图邻接表的构造函数初始化操作邻接表的构造函数和输出函数代码实现#include<iostream> using namespace std; //邻接链表 typedef char DataType; //顶点的数据类型 //边表结构体 st...
Day52 二叉树的层序遍历【代码】【图】
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点） https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 示例1：二叉树：[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 [ [3], [9,20], [15,7] ]Java解法思路： 层序边历，通过栈缓存当前数据，因为先进后出，所以先存储右节点，优化使用队列来存储，但效率没有太多提升package sj.shimmer.algorithm.m3_2021;import ja...
LeetCode #111 二叉树的最小深度【图】
题目描述 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。 示例 1： 输入：root = [3,9,20,null,null,15,7]输出：2 示例 2： 输入：root = [2,null,3,null,4,null,5,null,6]输出：5 dfs遍历 bfs遍历 参考： https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
Leetcode——(剑指offer)从上到下打印二叉树 II与|||，双队列实现【代码】【图】
本文是记录做该类题的一些思想，效率不算特别高，只是提供一些新的想法； 在LeetCode的剑指offer篇章中，有三个特别近似的打印二叉树的题目，分别是： (1)剑指Offer 32 - I 从上到下打印二叉树 (2)剑指 Offer 32 - II 从上到下打印二叉树 II (3)剑指 Offer 32 - III 从上到下打印二叉树 III 三道其实都是BFS； 第一道可以通过创建一个队列实现，利用队列的FIFO实现，将结点从队列取出后，如果子节点非空，就将其子节点放入队列尾...
冒泡排序【代码】【图】
冒泡排序 原理比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个，即需要进行length-1次。动画演示代码 package day0515; public class demo_sort {public static void main(String[] args) {//冒泡排序算法int[] numbers=new int[]{1,5,8,2,3,9,4};//需进行length-1次冒...
4树 二叉树 二叉搜索树 堆【代码】【图】
#python class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, Nonepublic class TreeNode {public int val;public TreeNode left, right;public TreeNode(int val) {this.val = val;this.left = null;this.right = null; } }示例代码 前序 中序 后序 示例代码 def preorder(self, root): if root: self.traverse_path.append(root.val) self.preorder(root.left) self.preorder(root.right...