数据结构和算法
2022-07-13 16:30:42 4 举报AI智能生成
登录查看完整内容
数据结构和算法是计算机科学的核心概念，它们为解决实际问题提供了基础。数据结构是组织和存储数据的方式，如数组、链表、栈、队列等，而算法则是一系列步骤来操作和处理这些数据。通过选择合适的数据结构和算法，我们可以更高效地解决问题，提高程序的性能。例如，哈希表可以快速查找元素，排序算法可以对数据进行有序排列。学习数据结构和算法有助于我们编写出更优秀的代码，提升编程能力。
作者其他创作
大纲/内容
Java学习笔记Java_Practice
Go学习笔记GO_Practice
高效开发工具EfficientDevTools
软件基础知识SoftwareBasic
机器学习
数据结构和算法AlgorithmPractice
数据库(原理和指令)
中间件(指令和原理)
踩坑记录(复盘和总结)
工作项目UML图汇总
高可用/高并发/高性能解决方案(3H)
思考
路径跳转
CMGTest
graphApplyTest
KruskalTest
mstTest
UnionFindTest
UnionFindTimeTest
UnionFindOptTest
unionFindTest
DFSTest
BFSTest
graphConnectionTest
BellmanFordTest
DijkstraTest
SingleSourceShortestPathTest
FloydTest
MultiSourceShortestPathTest
shortestPathTest
graphTest
FindDiffinMonotonousArrayTest
FindMostValueofMonotonousArrayTest
applyTest
oneDimensionalArrayTest
Matrix_MultiplyTest
ClockwiseSpiralMatrixTest
twoDimensionalArrayApplyTest
twoDimensionalArrayRealizeTest
twoDimensionalArrayTest
arrayTest
linkListRealizeTest
SkipListTest
listApplyTest
listTest
lineTest
DecompressTest
HalfPastNumTest
ReturnKMinTest
ReturnKthMinTest
StatisticFirstThreeCharTest
innerSortApplyTest
功能测试
将所有的类装载到一个集合中
通过反射获取该类
所有的类实现统一接口，有统一方法
执行测试
功能实现
InnerSortRealizeTest
性能测试（时间）
InnerSortRealizeTimeTest
链表快排
LinkQuicksortTest
innerSortRealizeTestInnerSortRealizeTest测试3大类排序中的所有功能，InnerSortRealizeTimeTest测试3大类排序中的性能，LinkQuicksortTest测试双向链表的快速排序
innerSortTest
sortTest
heapTest
ArrayQueueTest
LinkedQueueTest
queueRealizeTest
queueApplyTest
queueTest
MinValueStackOptTest
MinValueStackTest
CalculateTest
TestEffectBracketsbyStack
TestEffectBracketsbyTotalNum
EffectBracketsTest
TestLongestEffectBrackets_violence
TestLongestEffectBrackets_stack
TestLongestEffectBrackets_TotalNum
LongestEffectBracketsTest
stackApplyTest
LinkedStackTest
ArrayStackTest
stackRealizeTest
stackTest
stackHeapQueueTest
LNRSubstringTest
stringApplyTest
BMTest
KMPTest
RabinKarpTest
SundayTest
VoilenceTest
stringCompareTest
PokeStringTest
SequenceExistTest
sequenceApplyTest
stringTest
avlTreeTest
redBlackTreeTest
balanceBinaryTreeTest
BinaryTreeMirrorTest
TestcountLargestSum
TestcountLargestSubPath
TestFindPath
TestFindPathStack
BTFindCertainValuePathTest
apply
equal
printTreebyLine
BinaryTreeImplTest
BinaryTreeCreateImplTest
Binary2ArrayImplTest
realize
binaryTreeTest
bTree_bplusTreeTest
HuffmanTest
huffmanTest
intervalTreeTest
two_three_treeTest
treeTest
数据结构单元测试(datastructureTest)
CreatePalindromebyAddTest
CreatePalindromebyDeleteTest
FindPalindromeOpsTest
FindPalindromeTest
字符串为空
字符串为空串
字符串为一个字符
字符串为奇数回文
字符串为偶数回文
含回文串
不含回文串
测试用例的设计
PalindromeTest
ChangeMoneyTest
ClimbStairsTest
DungeonGameTest
LCSTest
TestLis
TestLis_divide
LISTest
Testmethodlss
TestmethodlsSopt
Testmethodlss_divide
LSSTest
MiniValuePathofMatrixTest
MiniValuePathofTriangleTest
ThiefStealTest
NumReduceMaxMultiTest
dynamicPrimaryTest
EditDistanceTest
LargestSquareTest
ShortestDeliveryPathTest
dynamicOrdinaryTest
dynamicTest
recallTest
backpackTest
choirTest
ShortPath_GreedyTest
ShortPath_RecallTest
shortestDeliveryPathTest
combineTest
OptimalScheduleTest
BranchandBoundTest
EraseOverlapIntervalsTest
greedyTest
算法单元测试(algorithmTest)
设计模式单元测试DesignPatternTest
productRandomStringTest
getEqualNumTest
RamdomUtilTest
UnifiedSpecialCharTest
utilsTest
PoolpigTest
mathTest
SaleStocksTest
logictest
DigitalTransTest
TransIPtoIntTest
regulartest
逻辑题及面试题单元(logicTest)
测试用例UnitTest
judgeisNull
judgeisSquare
judgeisRectangle
judgeisTriangle
矩阵检查包matrixCheck
检查包check
老虎机
老虎机无限版
game游戏
数组中左小右大的数
贪吃蛇
记录最小值，和遍历值做差，保存最大差值
情况一只允许买卖一次股票
找出波峰和波谷
先找波谷，找到波谷，记得用当前值刷新波峰，
再找波谷，两者做差
情况二允许买卖多次股票
买卖股票的最佳时机SaleStocks
求数组中两两之差绝对值最小的值
业务逻辑题logic
Alpha_transto_num
1、获取二进制中1位的数量：右移法
2、末尾1取反法
实际应用中存在表过大的问题
3、查表法
两两合并法
推荐：简洁
4、JDK自带补码字节统计工具
获取二进制中1位的数量
1、左移法，尽量不要使用右移，因为有符号位
4、两两合并法
获取二进制补码中1位的数量
获取二进制(补码)中1位的数量
光线投射算法
夹角法
判断点是否在区域内
Math—水仙花数和吸血鬼数字的实现
有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？
假设有n只水桶，猪饮水中毒后会在m分钟内死亡，你需要多少猪（x）就能在p分钟内找出 “有毒” 水桶？这n只水桶里有且仅有一只有毒的桶。
进阶
题目描述
先去想一只猪能够测试出几桶水，答案是5桶，15分钟死，30分钟死，45分钟死，60分钟死，活下来不死，这五种情况
第一只猪喝列的水的混合物，第二只猪喝行的水的混合物，最后一行和一列不喝
按照这样的方案喝完水之后，第一只猪在45分钟死去，第二只猪在15分钟死去，则2号水有毒，若两只猪都平安无事，那么标号为24的水有毒
两只猪呢？如果你再说是10桶就真的无可救药了，两只猪分别对应5种状态而且相互独立，5*5=25，三只呢，5的三次方等于125，四只呢，625，五只呢，等于几不知道，但肯定比1000大，第一个问题秒杀之，5只！
设计思路
用对数函数解决问题
注意事项
可怜的小猪Poolpig
将1-99，共99个数，放入长度为100的数组中，空出来的位置，随即放入范围内的一个数，找出该随机数
将0-99，共100个数，放入长度为99的数组中，找出少放的这个数
easy
将0-99，共100个数，放入长度为100的数组中，其中一个数覆盖类另外一个数找出覆盖或者被覆盖的这个数
hard
找出不同的数FindDiffNum
数学问题Math
^ 为匹配输入字符串的 开始位置
abc$匹配字母 abc 并以 abc 结尾，$ 为匹配输入字符串的 结束位置
[0-9]+匹配多个数字， [0-9] 匹配单个数字，+ 匹配一个或者多个
基础
只允许用户名包含字符、数字、下划线和连接字符(-)，并设置用户名的长度
应用
Pattern p=Pattern.compile(\"\\\\w+\"); p.pattern();//返回 \\w+
使用方法
java Pattern和Matcher详解
正则表达式介绍
统计最后一个单词长度
DigitalTrans
大小写互换
查找单词个数
正则表达式应用
将string类型的IP地址转化成int
将int类型数转化成string类型的IP地址
问题描述
IP和整数互相转化TransIPtoInt
大整数相乘
边界检测
正则表达式/边界检测regular
文件对比神器(FileCompare)
读文本(ReadTxt)
productrandomdomString
productRandomNumandString
随机生成不同长度的字符串
productRandomString(int num)
productRandomNumandString(int num)
随机生成给定长度的字符串
字符串仅含有a-z/A-Z/0-9
随机返回一个int型整数范围：Integer.MIN_VALUE ~ Integer.MAX_VALUE
public static void main(String[] args) { Random random = new Random(); int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i = 0; i < 100000; i++) { int j = random.nextInt(); if(j < min){ min = j; } if(j > max){ max = j; } } System.out.println(\"max:\"+max+\"====\"+\"min\"+min); }
证明代码
int nextInt()
int nextInt(int num)
注意
随机生成字符串（含大小写字母和数字）
随即生成一个等概率的数区间
随即工具包(RamdomUtil)
对list内的元素排序SelectionSortforFileCompare
工具包Utils
逻辑题Logic
思路一：回溯
思路二：动态规划
背包问题(backpack)
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
题目
输入描述:
输出一行表示最大的乘积。
输出描述:
输入例子: 3 7 4 7 2 50 输出例子: 49
例子
二维矩阵记录最优解
dpMax[i][j] 有3种情况：设 1 <= h <= d。就是它自己，即 1、dpMax[i][j]。2、dpMax[i - h][j - 1] * a[i]，这是在 a[i] >= 0 的情况。3、dpMin[i - h][j - 1] * a[i]，这是在 a[i] < 0 的情况。三个取最大即可。
保持两个二维矩阵，因为存在负数两两相乘积最大
这个二维矩阵不能全部填满，是个 右上 三角矩阵
思路一：动态规划
递归深度表示选取的 n 个人
注意选择区间
for循环表示 剩余人的选择区间
思路二：回溯法
合唱团(Choir)
维护一个最短路径的数组，每次选择最短的，然后根据当前点，更新最短路径数组，最后一步回起点
思路一：贪心算法：Dijkstra模式、prim模式
按照所有的点进行递归，所以当递归深度为 节点数时，递归截止，进行最优解判断
每次递归，再对节点进行循环，找出合适的点，此处需要进行节点访问判断
代码的 39-44 相对应
代码的 52-56 相对应
代码的 64-72 相对应
代码的 68-70 相对应
代码的 41-43 相对应
所有回退的地方都要进行先加后减
思路二：回溯法：回溯就是全排列组合加剪枝
思路三：动态规划：
送货最短路径ShortestDeliveryPath
综合性题目(comprehensive )
动态规划思想介绍
求两串字符串中最长相似部分（不连续）
优化
最长公共子序列算法（LCS）
新建数组，longest[i]表示以i结尾的最长子序列，intarray[]表示原始数值序列
for (int i = 0; i < length; i++) { for (int j = 0; j < i; j++) { if((intarray[j] < intarray[i])&&((longest[j] + 1) > longest[i])){ longest[i] = longest[j] + 1; } } if(longest[i] > best){ best = longest[i]; point = i; } }
对于第N个元素，通过循环前N-1个元素，找出元素值比其小，但是子序列数值最大的哪个值，赋值给第N个元素的子序列值。
for (int i = point - 1; i >= 0; i--) { if(longest[i] == longest[point] - 1){ sb.append(intarray[i]); point = i; } }
从最大值处依次往后找，找出值
寻找值
状态方程
动态规划
二分法
最长递增子序列LIS
给定一个数组，求这个数组的连续子数组中，最大的那一段的和
子问题
站在自身角度考虑，如果前面的值加起来还没有自身大，那么就刷新数组，前面舍去不要
状态转移方程
LSS
优化空间复杂度至 O(1)
可以记录起始和结束地址
LSSopt
左边的最大值
右边的最大值
从中间往左求最大值
从中间往右求最大值
两者相加
中间的最大值
分成左中右三部分
分治的思想
LSS_dvide
最大子段和LSS
字符串反转，字符串匹配，equal就是，否则不是
判断一个字符串是否 是回文
给定一个字符串s，你可以从中 添加 一个 字符，使得剩下的串是一个回文串
如果通过添加一个字符得到回文，则返回删除元素的位置(起始地址：0)，否则返回 -1.
设置两个指针，头指针指向字符串首部，尾指针指向字符串尾部。若头尾指针相等，头指针加加，尾指针减减，向中间靠拢，若不相等，则进一步判断（头指针++，尾指针）和（头指针，尾指针--）中是否存在回文，运用递归完成
方法一：首位对比
既然可以通过添加构造回文，那么也可以通过删除一个构造回文
方法二：删除构造
判断原字符串和翻转字符串的最长公共子序列长度是否比原字符串长度小1或相等
方法三：LCS思想
解决思路
构造回文（添加一个字符构造）(CreatePalindromebyAddTest)
给定一个字符串s，你可以从中 删除 一些 字符，使得剩下的串是一个回文串
字符串反转，做自身LCS，得到相似字符串（回文），统计相似字符串长度 sameLength
字符串总长度减去相似字符串长度，即得到该删减的数字符数量
构造回文（删除一些字符构造）(CreatePalindromebyDelete)
含有不连续回文字符串（查找回文子序列）
给定一个字符串s，从中找出回文子串，要求子串连续
两层循环，找出所有可能的字符串，进行回文匹配
返回最长匹配的回文串
暴力法
预处理函数，用特殊符号把字符串间隔开
回文边界函数：获取字符串以每个点为中心的最大对称边界
获取最大边界，算出最大回文
匹配长度为1时，即未匹配上，返回为空
字符串的比较尽量使用equals
中心扩散法
Manacher 算法查找回文（优化）(FindPalindromeOps)
查找回文(FindPalindrome)
含有连续回文字符串
判断一个字符串是否 含有回文
回文应用(Palindrome)
已知不同面值的钞票，求如 何用最少数量的钞票组成某个金额，求可 以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额， 则返回-1
找零钱ChangeMoney
在爬楼梯时，每次可向上走1阶台阶或2阶台阶，问有n阶楼 梯有多少种上楼的方式
确认状态第 i 个状态 即为第 i 阶台阶的所有走法数量
确认边界状态（初始条件）： 边界状态为1阶台阶与2阶台阶的走法，1 阶台阶有1种走法，2阶台阶有2种走法， 即dp[1] = 1，dp[2] = 2。
状态转移方程 ： dp[i] = dp[i-1] + dp[i-2]; (i>=3)
爬楼梯ClimbStairs/青蛙跳台阶FrogJumps
已知一个二维数组，左上角代表骑士的位置，右下角代表公主的位置， 二维数组中存储整数，正数可以给骑士增加生命值，负数会减少骑士的生命值，问骑士初始时至少是多少生命值，才可保证骑士在行走的过程中至少保持生命值为1。(骑士只能向下或向右行走)
地牢游戏DungeonGame
给定一个二维数组，其保存了一个数字三角形 triangleMatrix[] []，求从数字三角形顶端到底端各数字和最小的路径之和，每次可以向下走相邻的两个位置
三角形数组和最小路径MiniValuePathofTriangle
已知一个二维数组，其中存储了非负整数，找到从左上角到右下角的一 条路径，使得路径上的和最小。(移动过程中只能向下或向右)
二维矩阵中左上角到右下角的最短路径和MiniValuePathofMatrix
在一条直线上，有n个房屋，每个房屋中有数量不等的财宝，有一个盗 贼希望从房屋中盗取财宝，由于房屋中有报警器，如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问在不触发报警器的前提下，最多可获取多少财宝？例如 [5，2，6，3，1，7]，则选择5，6，7
只考虑前两个房间时，谁大选谁考虑第三个房间如果偷第三个房间，则意味着第二个房间不投，也就是第三个房间值 + 第一个房间的宝藏数量如果不偷第三个房间，则宝藏数量等于前两个房间宝藏数量
values == null || values.length == 0
先判空再判定length
打家劫舍ThiefSteal
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积
思路一：数学的均值定理
状态转换方程
美团面试题（整数拆分）
LeetCode 整数拆分（动态规划）
参考博客
整数化积NumReduceMaxMulti
动态规划应用_初级dynamicPrimary
编辑距离EditDistance
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
求出某个点为 1，以此为起点，向下/右求解最大变长
暴力循环扫描法（含冗余扫描）
图解
逐层扫描法
最大长度限制法
getMaxSideLength()
暴力求解法
当前最大值 = Min{左上角最大值，上方最大值，左边最大值} + 1
状态转换公式
循环体内，确定最大值
状态矩阵是 [n+1][n+1]
动态规划法
将动态规划的二维矩阵降为一维矩阵，空间复杂度降低
左上角最大值
pre
上方最大值
now
左边最大值
statusMatrix[j-1]
状态值
在判断语句的一前一后，写上状态变更
动态规划优化
解法
最大正方形LargestSquare
F(i) = G(i - 1) * G(n - i)
G(n) = F(1) + F(2) + …… + F(n)
定义一个 F(i) 表示以 i 为根，生成的树的种数。定义一个 G(n) 表示输入 n 的时候，输出的结果。此处一定要注意 F 与 G 的区别
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
例题1：括号序列：给 n 对括号，可以合成的合法序列有多少种？
例题2 ：一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
例题3 ：给出一个n，要求一个长度为2n的01序列，使得序列的任意前缀中1的个数不少于0的个数， 有多少个不同的01序列?
例题4 ：2n个人要买票价为五元的电影票，每人只买一张，但是售票员没有钱找零。其中，n个人持有五元，另外n个人持有十元，问在不发生找零困难的情况下，有多少种排队方法？
通解
卡特兰数
动态规划应用_普通dynamicOrdinary
动态规划(dynamic)
回溯算法就是 穷举 加 分支限界
回溯法思想介绍
字符串按照排列组合打印
合唱团_回溯
假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早
第一行有2个正整数n和k(1≤n≤20，1≤k≤6）；第二行的n个正整数是完成n个任务需要的时间ti(1≤ti≤100）。
输入
1行1个数：完成全部任务的最早时间
输出
将每个任务进行递归，递归的同时，对于当前任务，有N个机器可以选择 (for循环) ，这里进行分支，分支的同时进行限界
类中的所有属性只能定义，不能赋初始值，不然复用的时候会乱
递归的for循环处，就是分支限界的地方
最佳调度问题（分支限界） OptimalSchedule
回溯算法都是套路
回溯法应用
回溯(recall)
见 Dijkstra
无重叠区间EraseOverlapIntervals
贪心算法Greedy
算法及其应用Algorithm
直接插入
折半插入排序
2路插入排序
表插入排序
其他插入
希尔排序
插入
多关键字排序
链式基数排序
基数
归并
树形选择
选择
概念
将相等的数字的字母进行选择排序
根据排序结果，输出
解压字符串并且排序输出Decompress
如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多
上述循环只为过滤出选定值，推出循环后，进入下一个循环，判断该值是否为超过半数的值
多于数组一半则输出，否则输出 -1
鸽笼原理
对数组进行排序，如果存在多余一半的数，则不然出现在数组中间
记录下数组一半的那个特殊值，通过循环查找该值出现的次数
快排原理
通过循环，将数组数据放入map中
循环的过程中，查找出现次数最多的那个值
map方法
桶排序，需要单独为数组长度为1的做判断
找出超过半数的那个数字HalfPastNum
防止到一个map中，返回首先出现的大于三次的字母
方法一：红黑树统计法
方法二：桶计数
统计字符串中首先出现三次的英文字符StatisticFirstThreeChar
内部排序的应用innerSortApply
通过遍历数组，得到最大值和最小值，然后定义桶数量（即将数据分为几堆）
循环数组，将每个数据分到桶内，桶内按照链表的插入排序 插入
排序结束，循环桶，取出数据
数组判空
桶结构是 数组加链表，散列表用内部类实现
每个首届点都用最大值表示，则不存在首节点插入的问题需要在遍历哈希表的时候注意，首节点值不能统计
方法1
HashtableNode[head] == pro && point.value < pro.value
首节点存数据，则使用两个指针pro和p，pro是p的前节点，插入的前提是pro还是首届点，且其值比插入点大
方法2
首节点对比插入问题
链表插入排序的方法
注意事项
桶排序
通过遍历数组a，得到最大值和最小值，求出数组区间长度定义新数组b，b长度为a的区间
遍历a数组，根据遍历数组值，将b数组对应下标的位置值加一，b数组的下标表示a数组中该值出现过，对应的数组值表示出现几次
嵌套循环：外层循环长度为b数组长度内层循环长度为当前b数组值
再定义一个新的数组c，顺序统计非0的b数组
考虑到最后统计c数组的双层循环，寻找优化至一层的方法
for (int i = 1; i < array_b.length; i++) { array_b[i] += array_b[i-1];\t\t}
注意 i 是从1开始的
累加的过程其实就是排序的过程累加后的array_b[i]其实就是 i 这个元素在整个数组中的 并列名次
修改b数组为自身数据的累加
for (int i = array_a.length - 1; i >= 0; i--) { array_c[ --array_b[ array_a[i]-min ] ] = array_a[i];\t\t}
i必须到0，否则array_a[0]无法遍历到
b数组，必须先--，考虑到array_b中最小的统计位是1，表示有一个这样的数，\t\t 这个数对应整个数组的最小值(即 0 位)，所以必须先--
根据并列名次 反向输出到新数组c
方法调用时，如果没有接受值，那么必须采用原址排序，需要修改传入参数，否则相当于无用功
计数排序
数组分成两段，每段去排序
排序时判断这两段是否越界，越界停止返回
实行归并
归并排序
确定进制，根据最大值的位数来控制总循环的次数
基数排序
基数合并
普通排序的实现normalSort桶排、计数、归并、基数
首先定义好带排序数组的 区间，即定位左右指针位置
定义 mid 指针为中间定位指针，统计小于标杆的元素数量，并跟该元素发生交换
因为最左边元素作为标杆用，循环从最左边元素+1开始，循环至右边元素
循环结束，交换 mid指针 和 标杆指针
递归 左指针 和 mid 指针，mid指针 和 右指针
递归的判断条件：左指针 小于 右指针
单向快排
首先定义好带排序数组的 区间，即定位 左右双向指针 位置
定义最左边的元素为标杆，后续元素均跟它进行对比，小的在它左边，大的在它右边，后续由它定中点，
进入循环，判断条件：左指针小于右指针
满足 1）左指针小于右指针 2）左指针小于标杆
左指针增大
左指针
满足 1）左指针小于右指针 2）右指针大于等于标杆
右指针
也可以
双方均带等于
左右指针存在不相遇的可能性
双方均不带等于
在上述的判断条件中，必须有一方是带等于的，方便处理另一方不能处理的数据
左指针小于右指针，元素交换
用左指针更新 mid指针
循环结束，标杆指针 和 mid指针 元素交换
时刻注意左指针 小于 右指针
双向快排
当数组值长度小于给定值 K 时，使用插入排序，当数组值长度大于给定值 K 时，使用快速排序，
快速排序优化
双向快排（链表）
快速排序quickSort(单向、双向、快排优化)
外部循环 i 循环 n-1次，最后一次无需排序
外部循环
内部循环根据外部循环的起始位置，朝着另外一个方向进行排序比较
内部循环
有序区：从 n 向 0 扩展
与选择排序的区别是：选择排序记录多次，只交换一次，冒泡排序不记录，直接交换，一趟内部排序会出现多次交换
内部排序是相邻元素对比，因此，需要注意排序边界
外部排序每次从头比到尾，能至少确定一个元素的最终位置
时间复杂度：O(n^2)空间复杂度：O(1)
如果第一次内部排序，无数据交换，则默认数据有序
冒泡排序优化
冒泡排序
从某点开始，分别比较其与左右孩子的大小
先取左孩子，判断是否越界
再取右孩子，判断是否越界
都存在的情况下，对比找出最大/小值
需要注意取左右孩子时是否发生越界
整堆结束
父节点就是最大/小值
交换节点值
递归 该节点值
父节点就不是最大/小值
对比父节点和左右孩子中的最大/小值
整堆函数
从数组的 n/2 处开始，通过整堆函数，不断调整堆结构，循环至 0 结束
初始化建堆
经过建堆，堆顶元素是最大/小值
取出来跟最后一个元素 i (堆尾)交换，此时有序区是最后一个元素
继续整堆，不过此时整堆区间是[0，i-1]
循环结束条件是 i > 0，最后一个元素一定自身有序
排序
建堆排序
时间复杂度：初始化建堆：n/2 * logn;排序：n * logn;最终：O(n*lgn)空间复杂度：O(1)
堆排排序
外部循环 i 从1循环到n，0(第一个元素)默认是有序的
内部循环的开始位是 i (后续会被覆盖)，结束位是 0
有序区：从 0 向 n 扩展
插入排序
内部循环 j 从外部位置右边(即 i+1 )遍历到 n (最后一个元素)
内部循环中，找到合适的元素(运用 if 判断)，记录下角标
内部循环结束，元素通过下角标交换
外部循环的结束为：n-1，因为最后一个元素不再需要选择
选择排序
简单排序的实现simpleSort冒泡、插入、选择、堆排
数组实现
上述排序的链表实现
内部排序的实现innerSortRealize
内部排序innerSort
外部排序的应用
最佳归并树
置换选择排序
多路平衡归并排序
败者树、胜者树
外部排序
排序(sort)
pulbic void push (E x);public E poll ();public E peek ();public boolean isEmpty ();public void resize ();
主要方法
优先队列
一方面：考虑内存大小，建议维护[k]的最小堆，
不建议使用，维护堆的成本较高，
将 [length-k] 维护成一个最小堆，设length-k = h : O(hlogh)
对比和交换：O(klogh)
把数据分成 [k] 和 [length-k] 两块，将 [length-k] 维护成一个最小堆，每次对比 [k]和[length-k]中堆顶的数据，进行交换。最后输出[k]，既是最小堆
对比和交换 ： O(hlogk)
适合内部排序
把数据分成 [k] 和 [length-k] 两块，将 [k] 维护成一个最大堆，每次对比 [k]和[length-k]中堆顶的数据，进行交换。最后输出[k]，既是最小堆
最小堆
if(k == low || k == low - 1){\t\t\t\treturn ; \t\t\t}
在排序后，判断界点是否等于k
快排 K 分区
输出[k]数据均是无序的最小的k个数
返回数组中最小的k个数ReturnKMin
思路类似ReturnKMin
返回数组中最小的第k个数ReturnKthMin
堆(heap)
队首指针 front
队尾指针 tail
链队需要，数组队不需要，数组队可以通过队尾剪队头实现
队列的实际容量 QueueRealsize
队列的最大容量 QueueMaxsize
公共属性
offer()
入队
poll()
出队
peek()
返回队首元素
size()
获取队列长队
empty()
队列判空
队列的方法
主要实现是 数组队列
循环队列
队列的种类
含数组queue
数组队列
含内部类LinkedNode
链表队列
队列的实现形式
front == tail
判空
tail + 1 == front
判满
数组栈判空/判满
QueueRealsize==0
QueueRealsize == QueueMaxsize
链栈判空/判满
出队判空，入队判满
不可以QueueRealsize <= QueueMaxsize，必须用QueueRealsize < QueueMaxsize
判断条件
linkedQueueNode.next = tail; tail = linkedQueueNode;
不可以使用
tail.next = linkedQueueNode;tail = linkedQueueNode;
必须使用
赋值条件
插入数据的时候，需要考虑将第一个数据复制给front指针和tail指针，即关联队列的收尾指针。
链队列在第一次入队时
链队入队时
链队
tail + 1 < front
不可以用
tail + 1 != front
必须用
数组队入队判断
因为数组实现的循环队列的性质（判满性质），导致数组循环队列的实际容量是最大容量-1
数组队
负载因子，超过某负载因子，进行扩容，数组整体复制
队满后如何扩容
加锁
如何保证线程安全
advance
基本概念及实现
数组队列ArrayQueue
链表队列LinkedQueue
通过两个堆栈实现一个队列
队列(queue)
栈顶 stackTop
栈容量最大值 stackMaxSize
链栈需要，数组栈不需要，数组栈可以通过栈顶元素实现
栈的实际大小 stackRealSize
pop()
出栈
push(Object o)
入栈
返回位于栈顶的元素
emty()
search(Object o)
查找元素
栈大小
栈的方法
数据结点node
链式栈
数组array
数组栈
栈的实现形式
出栈需要先判空，入栈需要先判满
栈满后如何扩容
stackTop == 0
stackTop == stackMaxSize
数组队判空/判满
stackTop为null && QueueRealsize == 0
链队判空/判满
数组栈(ArrayStack)
链表栈(LinkedStack)
计算器(Calculate)
定义一个栈，除了常规操作，还可以随时查找栈中最小值
getMinValue()
push()
继承自Stack，方法由JDK保证特性
super.push(item);if (ministack.size() == 0 || item < ministack.peek()) { return ministack.push(item);\t\t}else { return ministack.push(ministack.peek());\t\t}
push方法中的判断条件，在第一次的时候需要加上size判断，否则会出现空指针错误
缺点是需要两个栈，空间复杂度为O(n)
随时查找栈中最小值最小栈(MinValueStack)
空间复杂度降为O(1)
优点
如果差值小于0，说明压栈值目前最小，miniStackValue就是入栈值
如果差值大于0，说明miniStackValue目前最小，miniStackValue保持不变
每次push的时候，将压栈值跟最小值做差，并将差值入栈
如果peek值大于0，说明miniStackValue目前还是最小，miniStackValue保持不变
负数求和用减法
如果peek值小于0，说明压栈值目前最小，miniStackValue需要跟peek值求和
更新miniStackValue
父方法pop
每次pop的时候，先判空，然后取出peek值
主要思路
缺点是对数值有要求，做差可能存在数值越界问题
栈的注意事项需要牢记
随时查找栈中最小值最小栈（优化方案）MinValueStackOpt
用栈统计
用符号总量统计
判断有效括号
栈统计法
符号总量统计法
统计最长有效括号
括号匹配
栈(stack)
堆栈队列(stackHeapQueue)
二叉树的数组存储
数组 单调递增然后单调递减 ，输出元素中不同的个数，要求：数组原址，不能改变数组元素和顺序， 空间复杂度：O(1)，时间复杂度O(n)
左右两个指针，不断做比较，往最大值靠拢，相当于排序每次比较的最大值保存起来，跟下次的最大值比较，相同，说明存在相同值，不想同，计数值++
单调数组中找出不同的元素个数FindDiffinMonotonousArray
单调数组，返回数组的最值（最大/最小值）存在情况：1、单调递增， 2、单调递减， 3、先增后减， 4、先减后增。 5、均值单调要求：数组原址，不能改变数组元素和顺序， 空间复杂度：O(1)，时间复杂度O(logn)
首先找出是否为均值单调
不断取中值，做判断
单调递增的函数
递增
单调递减的函数
递减
判断开始趋势
单调数组中找出最值FindMostValueofMonotonousArray
大整数相乘BigIntegersMulti
一维数组应用
一维数组(oneDimensionalArray)
稀疏矩阵
三层循环
materix_b.length=materix_a[0].length != materix_c的任何值
错误用法： target.equals(Assert01Materix_c)
数组的相似
矩阵相乘Matrix_Multiply
输入，红黑树初始化
数独初始化
横向充填
竖向充填
九宫格充填
充填函数
空值
横向检测
竖向检测
九宫格检测
检测函数
非空值
输入值判断
对于两个以上的值，进行其小值尝试
尝试函数
循环判断
数独函数
数独实现(Sudoku)
非正方形的需要考虑 单独行、单独列的情况
每圈打印 和 特殊情况是 并列关系，需要做好 if判断
list转数组 需要考虑一下情况
点位计算法
每次把矩阵转置，然后输出
转置法
顺时针螺旋矩阵ClockwiseSpiralMatrix
二维数组应用twoDimensionalArrayApply
邻接表(Adjacency)
邻接矩阵(adjacencyMatrix)
二维数组实现twoDimensionalArrayRealize
二维数组(twoDimensionalArray)
数组/顺序表array
HashTableNode
散列表的实现hashTableRealize
散列表的应用hashTableApply
散列表hashTable
int size;\tSinglyLinkedNode next = null;
表头节点SinglyLinkedNode
int value; SinglyLinkedNode next = null;
表节点SinglyLinkedList
单链表数据结构
头插法insertHead
尾插法insertTail
数组转链表
单个元素插入
单链表的插入
元素存在并删除成功，返回true
元素不存在或删除失败，返回false
删除某元素
删除第几个元素
单链表删除
查找成功，返回位置 index
查找失败，返回 -1
查找某元素
查找成功，返回该位置的值
查找失败，返回 Integer.MIN_VALUE
查找某位置
单链表查找
遍历转数组
单链表转数组
单链表的构造
考虑数组扩容得不偿失
1、数组存放，倒序输出
2、利用栈倒叙输出，不改变链表本身（利用递归输出）
非递归输出
递归输出
3、反置链表
单链表逆置
构造较交叉链表
判断两个链表是否相交
找出两个链表的交点
链表相交
尾插法构造有环单链表
判断单聊表是否有环
找出带环单链表的入口
带环单链表
环链表(RangList)
单链表应用
单链表(SinglyLinkedList)
DoubleLinkedNode head = null; DoubleLinkedNode tail = null; int size;
表头节点DoubleLinkedList
DoubleLinkedNode front = null; DoubleLinkedNode next = null; int value;
表节点DoubleLinkedNode
双链表数据结构
双向链表的插入
删除某位置
双向链表删除
双向链表查找
双向链表转数组
双向链表的构造（双向循环链表）
双链表的应用
双向链表(DoubleLinkedList)
add()
delete()
find()
initial()
print()
方法
跳表及其实现
链表list
LCS最长公共子序列
将一个字符串转换成一个128位链表数组；数组中的位数表示是否存在某个字符；数组中某位对应的哪个链表表示字符串中该数组出现的位置
目标串预处理stringPreDeal
根据当前目标串的值去源串的list中查找；返回源串中该值出现的 list中的 最左边 的位置
获取左边边界getLeftBound
PokeString扑克法序列匹配
两个指针，源串指针，目标串指针；若相似，则指针均加一；若不相似，源串++;最后对比目标串指针数 是否等于 目标串长度
SequenceExist序列匹配
序列匹配
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
无重复字符的最长子串LNRSubstring
字符串排列 * 一个S和一个T，请问你S中是否存在一个子串，包含T中所有字符且不包含其他字符 * 注意：这道题要注意区别是字符串，不是序列，因此最好是用滑动窗口，而不是仅仅map之间的对比
字符串排列PermutationinString
最小覆盖子串 * 在S(source) 中找到包含T(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的 * 允许T(target)子串中包含多个相同的字符 * 比如在 sx65ytguhuihuba9d08cuygf4e5f3wsedc89faojinbfre43wedcfgv * 中查找 abcdeff 的 最小覆盖子串 是 edc89faojinbf
最小覆盖子串MinimumWindowSubstring
找所有字母异位词 * 输入一个串S，一个串T，找到S中所有T的排列，返回它们的起始索引
找所有字母异位词FindallAnagrams
序列和字符串 sequenceANDstring（排列连续的是串，不连续的是序列）
定义default方法，做源串和目标串的非空校验和长度校验
StringCompare接口设计
坏字符规则
预处理模式串，填充suffix，prefix
好后缀规则
BM
字符串匹配（KMP）算法及Java实现
KMP字符串模式匹配算法Java实现
从头到尾彻底理解KMP
前缀：字符串除了最后一个字符的全部头部组合；
后缀：字符串处理第一个字符的全部头部组合；
例如
前缀与后缀
\"部分匹配\"的实质是，有时候，字符串头部和尾部会有重复。比如，\"ABCDAB\"之中有两个\"AB\"，那么它的\"部分匹配值\"就是2（\"AB\"的长度）。搜索词移动的时候，第一个\"AB\"向后移动4位（字符串长度-部分匹配值），就可以来到第二个\"AB\"的位置。所以我们需要找到一个字符串中每一个子串的匹配值，即找到字符串的部分匹配值表，这样的话我们在下面匹配字符串的过程中就可以根据匹配表来进行跳跃了，而不必一个一个字符往后移，这就是关键所在
字符串部分匹配表
代表在模式串P中，当前下标对应的字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表在模式串P中，下标为j的字符之前的字符串中有最大长度为k 的相同前缀后缀
含义
next[0] = -1
不断在前缀中找匹配
若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1
求解方法
next数组
优化方案
KMP
字符可以用数子表示，数字对比比字符串对比简单
1*10^2 + 2*10^1 + 3*10^0 = 123
4*10^2 + 0*10^1 + 4*10^0 = 404
(a-'a')*26^2 + (b-'a')*26^1 + (c-'a')*26^0 = 28
abc可以看成是26进制的
如何表示
p = P[m] + 10(P[m-1] + 10(P[m-2]+ …. + ( 10(P[2]) + P[1])…)
t 类似
初始值
例子
通过 t0 求解 t1
通项
计算
ts+1 = (d*(ts - T[s+1] * h ) + T[s+m+1]) mod q
for (int i = 0; i < target.length() - 1; i++) { h = h * HEX % prime; }
d 是进制
简化计算，化简值溢出的问题
比较
跟进制和素数的选择有关系
RabinKarp
Sunday 算法 与 KMP 算法 一样是从前往后匹配
结果发现在第 2 个字符处发现不匹配，不匹配时关注文本串中参加匹配的最末位字符的下一位字符，即绿色的字符 i，因为模式串 search 中并不存在 i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符 n）开始下一步的匹配，如下图
图示
如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1
结果第一个字符就不匹配，再看文本串中参加匹配的最末位字符的下一位字符，是 'r' ，它出现在模式串中的倒数第 3 位，于是把模式串向右移动 3 位（ r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个 'r' 对齐，如下
否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1
在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符
浅谈什么是 Sunday 算法
两次循环，一次对比源串，一次对比目标串
temp指针用于查找目标串
Sunday
将源串切割成目标串长度，然后循环做匹配
Voilence
字符串匹配StringCompare
字符串和数组stringANDline
判断两个二叉树相等
BinaryTreeImpl重写equals方法
根据按层/先/中/后序遍历的数组 创建 二叉树
主题
要么借助先序、后序、中序的顺序，要么借助堆栈来捋清楚 关系
按层构建二叉树
先序创建二叉树
中序创建二叉树
后序创建二叉树
单序创建
根据先序和中序，创建二叉树
根据后序和中序，创建二叉树
多序创建
Array2BinaryTree数组转二叉树
二叉树根据按层/先/中/后序遍历的 输出 数组
assert array.equals(treeDemo03);
判断数组值相等的错误写法：
二叉树按层遍历输出按行遍历打印二叉树
S形遍历打印二叉树
先序遍历二叉树输出数组
中序遍历二叉树输出数组
后序遍历二叉树输出数组
按序打印
Binary2ArrayImpl二叉树转数组
二叉树BinaryTree
二叉搜索树
时间复杂度较高
缺点
正常准确的（含子树关系）
不正常，概率极地的（不含子树关系）
存在某种关系树，验证不准确
双遍验证：第一遍：先序+中序第二遍：后序+中序
子树序列化，KMP判断
子树判断（子节点递归判断）SubTreeJudge判断一个树是否为另一个树的子树
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
递归/显式栈
非递归/系统栈
1）首先是采用先序遍历二叉树的思想2）先对根节点进行非空判断（非空结点先加进来，如果不合适，后续删除）3）当遍历到叶子结点，并且累加值为target的时候，结束4）左右孩子递归，删除不合适结点。
在返回值的list中，数组长度大的数组靠前
这道题目前只支持解全部是结果集为正数的题目，如果是负数，需要遍历到根节点，无法剪枝
当数据为int或者字符的时候，禁止使用 ： route_list.remove((Integer) root.value);因为移除数据的时候会发生错误对象移除
二叉树中和为某一值的路径BTFindCertainValuePath
回溯法
输出具体路径countLargestSubPath
sumTemp += binaryTree.value; if(sumTemp > sum){ sum = sumTemp; }if判断要在加和之后，不要再加和之前，不然无法记录值
输出路径和countLargestSum
二叉树中最大子路径和BinaryTreeLargestSubPath
镜像二叉树（二叉树反转）BinaryTreeMirror
查找二叉树中x和y的最小公共父节点FindNearestParent
二叉树是否为平衡二叉树JudgeBalanceTree
二叉树的最大深度FindTreeDepth
二叉树的应用binaryTree.apply
二叉树 binaryTree
B树及B+树bTree_bplusTree
赫夫曼树本质上是数组，具有二叉树结构，有左孩子、右孩子、父节点、值
构建Huffman数组并初始化
寻找最小值和次小值
构建关系
构建步骤
借助队列，实现按层访问
计算WPL
赫夫曼树及编码问题(Huffman)
赫夫曼树huffman
不重复随机数
写段代码，定义一个字符串常量，字符串中只有大小写字母和整数，输出字符串中的出现最多的数字的和？例如 ” 9fil3dj11P0jAsf11j ” 中出现最多的是11两次，输出22
解题思路
统计字符串中出现最多数之和StatictisSumofNum
红黑树的应用apply
add()增加函数
insertFixup()颜色调整
rotateRight()左旋
rotateLeft()右旋
add函数共包含四部分
步骤一：常规插入：树的二分查找，然后对插入点进行颜色调整。
步骤二：调整方式见下图。
步骤三：部分结点需要进行左旋和右旋。
1）步步为营，必须弄清楚所以指针去向。
2）因为Java语言的原因，栈内的指针不保存，因此需要每次返回root。
3）左旋右旋发生后，当前结点发生变化，需要更改当前结点。
4）严格按照上图思考，先判断叔叔是祖父节点的左孩子还是右孩子？再对当前结点是左孩子还是右孩子进行判断。
构建说明
不用进行调整
当要插入的节点的父节点是黑色的时候
直接涂黑即可
初始化：当插入的节点是根节点时
父节点是黑色普通情况
步骤一：父节点和祖父结点换颜色互换
步骤二：祖父节点右旋
情况1：插入的节点是父节点的左支
步骤一：父节点左旋，父子节点身份互换
转换成情况一的步骤
情况2：插入的节点是父节点的右支
叔叔节点为黑
步骤一：父节点和叔叔结点颜色变黑
步骤二：祖父节点颜色变红
步骤三：向上对祖父节点进行判断
情况3：叔叔节点为红
父节点是祖父节点的左支
步骤一：父节点右旋，父子节点身份互换
转换成情况五的步骤
情况4：插入的节点是父节点的左支
步骤二：祖父节点左旋
情况5：插入的节点是父节点的右支
同情况3
情况6：叔叔节点为红
父节点是祖父节点的右支
父节点是红色
红叔问题：叔叔节点为红
黑叔问题
红黑树增加节点图解
红黑树插入算法
1、先看待删除的节点的颜色，2、再看兄弟节点的颜色， 3、再看侄子节点的颜色（侄子节点3.1、先看远侄子3.2、再看近侄子）， 4、最后看父亲节点的颜色
判定思路
红黑树之删除节点
直接删除
情况一：删除叶子节点为红色
调整做法是将父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，然后将P树进行AVL树种的RR型操作然后参考情况2.2
情况2.1：待删除节点D的兄弟节点S为红色
颜色互换，旋转、颜色调整，删除
情况2.2.1：且远侄子节点为红色
旋转，颜色互换，转化为情况2.2.1
情况2.2.2：近侄子结点为红色且远侄子节点为黑色
有一个侄子结点为红色
颜色互换
情况2.2.3：父节点为红色
改兄弟结点的颜色，向上进行递归颜色调整
情况2.2.4：父节点为黑色
判断父亲结点
情况2.2：待删除节点D的兄弟节点S为黑色。
情况二：删除叶子节点为黑色
1、单个的叶子节点
直接用子节点进行值替换，并更改颜色，删除
情况三：删除节点为黑色，子节点为红色
2、只有右子树（或只有左子树）的节点
共两种
我们知道，对于一棵普通的二叉排序树来说，删除的节点情况可以分为3种：1、 叶子节点2、 只有左子树或只有右子树的节点3、 既有左子树又有右子树的节点。我们知道对于一棵普通二叉树的情况3来说，要删除既有左子树又有右子树的节点，我们首先要找到该节点的直接后继节点，然后用后继节点替换该节点，最后按1或2中的方法删除后继节点即可。所以情况3可以转换成情况1或2。同样，对于红黑树来讲，我们实际上删除的节点情况只有两种。
说明：其他情况要么不存在要么可以转化
删除的节点类型
红黑树删除节点图解
红黑树删除算法
红黑书的实现realize
红黑树RedBlackTree
区间树上的重叠区间查找算法
区间树intervalTree
2-3树two_three_Tree
树(tree)
数组表示法/邻接矩阵
邻接表
十字链表
邻接多重表
图的存储
深度优先遍历DFS
广度优先遍历BFS
图的遍历
图的基本概念
完全多部图CMG
图的应用(graphApply)
Union-Find 并查集算法详解
关联 x 和 y 为一个联通分量
查找 x 的父节点
find（x）
判断 p 和 q 是否连通
返回图中有多少个连通分量
count()
method
路径压缩
根据树的大小进行合并
优化find和union
UnionFindOpt
while (parent[x] != x) { // 进行路径压缩 parent[x] = parent[parent[x]]; x = parent[x]; }
注意i事项
并查集UnionFind
在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
介绍
排序，可以使用各种排序算法
这种结构的数据部分是三部分组成：边长、起点、终点
边数据结构
用于记录每条边的 绝对终点
终点数组
基于特殊的数据结构：边数据结构和终点数组
取出一条边的起点和终点，分别找到他们对应的绝对终点，如果相同，则构成边，不同则可以加入。
判断方式
遍历边，且判断回路
输入：一个邻接矩阵或邻接表，将其转化为边的数据结构，按照Kruskal算法计算（获取边、边排序、根据绝对终点判断回路），输出：1、最小生成树的总长度， 2、最小生成树的边集合（终点数组），可以打印出边长及连接的两个点
Kruskal这个类含有 最小生成树的 总长度、最小边集合、最小生成树矩阵
改进输出
实践
Kruskal算法核心是对边排序，然后遍历边，只要不形成回路，就加入最小生成树的数组
克鲁斯卡尔算法Kruskal
普瑞姆算法Prim
最小生成树mst
图的连通性graphConnection
输入：一个 邻接矩阵 或者 邻接表 所代表的图， 这个图的路径权值必须全部为正， 指定某个起点。
输出：一个散列表， 数组代表这个起点到其他所有点的最短距离， 列表部分表示，起点到当前点的路径。
某源点到途中任意点的最短路径
新建一个 list[] (路径散列表)，数组头表示起点到所有其他点的最短距离，链表来存储起点到各点的最短路径，
初始化：将所有点分成两堆，一堆是起点组，一堆是未加入起点组的，采用松弛方式，先给 路径散列表 中 数组部分 全部赋值正无穷，起点到自己是0
for( 遍历所有点 ){ for(整个数组){ 找出当前数组中的最小值k， } for(整个数组){ 用最小值更新当前数组值， 记录路径和值 }}
hashTableNode4Dijkstras数组的节点，需要每次new出来
选择Integer.MAX_VALUE作为不可达，在更新时，matrix[findpoint][j] != Integer.MAX_VALUE也要作为条件，否则matrix[findpoint][j] + minvalue为负数，扰乱判断条件
最外层的判断条件：遍历所有点的次数应该是 点数-1，因为一个点到其他点的边数为 n-1 条
迪杰斯特拉算法Dijkstra
某源点到途中任意点的最短路径，解决了负权路径的最短距离问题
贝尔曼-福特算法BellmanFord
单源最短路径SingleSourceShortestPath
任意两点的最短路径
弗洛伊德算法Floyd
多源最短路径MultiSourceShortestPath
最短路径shortestPath
图(graph)
动态存储
实现
判断子序列(二分查找)
二分查找
静态查找
B树
动态查找
哈希
查找
顺序文件
索引文件
散列文件
多重表文件
倒排文件
多关键字文件
文件
数据结构Datastructure
对于扩展是开放的（Open for extension）。这意味着模块的行为是可以扩展的。当应用的需求改变时，我们可以对模块进行扩展，使其具有满足那些改变的新行为。也就是说，我们可以改变模块的功能。
对于修改是关闭的（Closed for modification）。对模块行为进行扩展时，不必改动模块的源代码或者二进制代码。
开闭原则
设计原则
lazy ideas in programming(编程中的惰性思想)
设计模式思想
构造方法：私有、确保单例不会在系统中的其他代码内被实例化
自身(private)实例成员变量：静态的(static)、不可修改的(final)
静态返回方法：返回一个实例
饿汉单例模式在类加载时就创建实例对象，并通过getinstance方法返回实例对象
弊端：慢，必须加载完对象的所有属性
饿汉模式
饱汉模式在类加载的时候不创建对象，通过getinstance方法的时候判断是否存在实例对象，没有则创建
弊端：在判断的时候，容易出现线程不安全
无锁
通过使用synchronized锁，保证线程安全，每次只能让一个对象访问
弊端：非同步，每次只能一个对象访问，效率很低
单锁
懒汉模式
先判断，再加锁，再判断
特点：效率较高(实验证明加双锁的比较快)
双重锁模式
静态内部类中将对象实例化，通过getinstance方式返回
特点：一般企业用这种模式实现单例模式
内部类单例模式
为 uniqueInstance 分配内存空间初始化 uniqueInstance将 uniqueInstance 指向分配的内存地址
执行步骤
指令重排在单线程环境下不会出现问题，但是在多线程环境下会导致一个线程获得还没有初始化的实例。例如，线程 T1 执行了 1 和 3，此时 T2 调用 getUniqueInstance() 后发现 uniqueInstance 不为空，因此返回 uniqueInstance，但此时 uniqueInstance 还未被初始化
由于 JVM 具有指令重排的特性，执行顺序有可能变成 1>3>2
存在问题
使用 volatile 可以禁止 JVM 的指令重排，保证在多线程环境下也能正常运行。
解决方案
singlePattern = new SinglePattern();
volatile
种类
考虑方面：类对象的延时加载、线程安全、加载性能
饿汉单例模式在类加载时就创建实例对象，但是存在不能延迟加载的问题，因此引入懒汉单例模式，虽然懒汉设计模式解决了延迟加载的问题，但是存在线程不安全，加入synchronized关键字，却带来了性能问题，表现为耗时，最后采用内部类的方式来完美展现（最完美的是懒汉模式的双锁，速度最快）。
浅谈单例设计模式的几种实现方式
https://blog.csdn.net/zhangliangzi/article/details/52438401
单例模式三种模式，饿汉、饱汉、双重锁模式，实例及优劣详解
单例模式的七种写法
如何实现一个线程安全的单例，前提是不能加锁
序列化会通过反射的方式调用无参构造函数新建一个对象
readresolve
解决办法
深度解析单例与序列化之间的爱恨情仇
单例模式被反射和序列化破坏
Singleton 单例模式学习笔记
有接口或者继承关系存在
真实角色的若干功能封装在代理类中工作，方便替换
UML图
1个接口proxyinterface
一个被代理类real也实现这个接口
一个proxy实现接口
实体测试类，检查proxy是否完全实现了real
包含对象
proxy中含有real的引用，并在接口的方法中融入real的方法
客户类调用proxy，实际上是proxy+real在工作，核心是real在工作
实现过程
必须维护一个跟被代理类一样的代理类
接口发生变化，代理类和被代理类都需要改，太麻烦
静态代理
反射对象的某些方法
invoke
InvocationHandler
获取类加载器、获取类实现的接口、对象本身
参数
通过类获取实现的所有接口，组装代理
newProxyInstance
Proxy
希望有一个通用的接口，可以代理不同的类，无需再写一个代理类来过渡
动态代理不用我们去手编写代理类，在运行时，动态的在内存中生产代理类。（字节码对象级别的代理对象）
静态代理模式的目的是：保护和隐藏目标对象
动态代理模式的目的是：在不修改目标类的前提下，增强目标对象
动态代理和静态代理的区别
动态代理
设计模式之---代理模式(AOP的原理)
前言1.6 ---动态代理模式(概念) / JDK 的 Proxy 动态代理
Java反射
Proxy 代理模式学习笔记
将每个策略封装起来，使之相互可以替代，策略本身相互独立，策略和使用策略的方法相互独立
包括：一个策略接口、若干策略实现、一个策略容器
策略定义接口
不同策略的接口实现
策略上下文（环境）
过程
设计模式学习之策略模式
Strategy 策略模式学习笔记
被观察者发生改变时，通知观察者
思路
super.setChanged();
flag/change：表示被观察者发生变化
super.notifyObservers(\"AnimalObservable eat\");
传入变化信息：参数
Object[] arrLocal;
创建本地观察者的快照
synchronized (this)
返回，并清除状态
if (!changed) return; arrLocal = obs.toArray(); clearChanged(); }
代码
非更改
获取当前本地观察者，调用观察者的update方法，逐个更新（后续更新也是用反射获取所以当前观察者对象）
更改
状态判断，并执行操作
通知方法
通知其他观察者已经发生变化
被观察者
update方法执行被通知后操作
观察者
通过反射获取所有观察者
改进
依赖注入
Message Queue
相关延伸
Observer 观察者模式学习笔记
子类继承父类实现接口
数据结构父类PositionCom
接口用于接受访问者
数据结构接口Accept
数据结构
子类实现接口的具体操作
接口用于实现一组行为规范
操作接口Visitor
一组包括不同种类的数据结构
通过数据结构内部的接口接受访问者，再调用访问者执行操作
测试
分离数据结构和操作
测试用的数据结构的集合，必须是满足接口的集合，不能是满足父类的集合
Visitor 访问者模式学习笔记
Adapter 适配器模式学习笔记
简单工厂（简单）
工厂方法（中等）
抽象工厂（困难）
Factory 工厂模式学习笔记
Delegate 委派模式学习笔记
Prototype 原型模式学习笔记
模板设计模式的本质就是固定算法框架
父类固定模板，但是开放模板的具体实现步骤，允许子类重写
父类的模板方法可以是final，也可以不是，父类是抽象类，可以有抽象方法也可以没有
继承GenericServlet，实现service()方法，需要重写里面的doPost和doGet方法。
实例讲解
模板方法设计模式（Template Method）
Template 模板模式学习笔记
Builder 构造器设计模式
设计模式DesignPattern
AlgorithmPractice
0 条评论
回复 删除
下一页
