JAVA笔记
注释需要注意的地方：
/** */这是文档注释，会生成一个html文件来对这个文档进行说明
多行注释中，注释不能嵌套
编译需要注意的
一个java文件中可以生命多个class但是最多只能有一个class被public修饰而且要求声明为public的类的类名必须与源文件相同
程序入口是main（）方法，格式是固定的
输出语句
System.out.println(): 输出完之后有换行
System.out.print()： 输出完之后不换行
编译之后会生成一个或多个字节码文件，字节码文件的文件名与java文件中类名相同
JDK = JRE + Java的开发工具（javac.exe.java.exe. javadoc.exe）
JRD = JVM + JAVA 核心类库
配置path环境变量目的是为了在cmd运行框中，任何盘之下都可以进行java语法的调用
命名规范
包名：多单词组成时所有字母都小写：xxxyyyzzz
类名，接口名：多单词组成时所有单词的首字母大写：XxxYyyZzz
变量名，方法名：多单词组成时，第一个单词首字母 ...
最短路径（Dijkstra方法）
求两点之间的最短路径
最短路径（Dijkstra）和最小生成树（prim， kruskal）的区别：
最短路径：是两个点之间的最短路径
最小生成树：是这几个节点之间的链接距离最短，但是不能够保证两点之间的距离一定是最短的
步骤（有向图）
我们的目标图为（使用邻接矩阵的方法）：
0
1
2
3
4
5
0
∞
∞
10
∞
30
100
1
∞
∞
5
∞
∞
∞
2
∞
∞
∞
50
∞
∞
3
∞
∞
∞
∞
∞
10
4
∞
∞
∞
20
∞
60
5
∞
∞
∞
∞
∞
∞
我们先创建一个数组
这个数组的每一个元素都是一个节点，每一个元素都要包括：
这个节点是否被选取过了（如果被选取过了就是证明这个节点的最短路径已经找到了）
起始位置到这个节点的距离
这个节点的上一个节点是谁
节点名称
节点状态
节点权重
前一个节点
0
0
∞
null
1
0
∞
null
2
0
∞
null
3
0
∞
null
4
0
∞
null
5
0
∞
null
...
0-1背包问题
蛮力枚举法
依次列出所有可能情况！！！
n表示有n个商品， C表示容量
其中颜色相同的是需要重复计算的
带备忘的递归
为了解决这个问题->需要大量计算重复的过程，这个时候我们可以引进一个“备忘录”，如果遇到需要重复计算的式子的话，我们可以直接重备忘录中获取。
伪代码的实现：
KnapsackMR(i, c)
1输入：商品集合{1，...，i}，背包容量c
1输出：最大总价格P[i, c]
1if(c < 0) then 容量为零 返回负无穷
1return 负无穷
1end
1if i ≤ 0 then 如果商品的个数小于零的话，返回零
1return 0
1end
1if P[i, c] ≠ NULL then 如果备忘录中有这个的话就不用计算 直接返回即可
1return P[i, c]
1end
1P1 = KnapsackMR(i-1, c-vi)
1P2 = KnapasckMR(i-1, c)
1p[i, c] <= max{P1 + pi, P2}
1return P[i, c]
计算 ...
最小编辑距离
目的：找出串S经过多少次变化之后成为串T，要让这个次数变的最小
方法：插入，删除，替换
.注意 ：这里我们只对串S进行操作
操作方法
删除方法：
S删除最后一位来进行对串T的转换
D[i, j] = D[i-1, j] + 1 ==>这里的含义是：S， T串中分别以i和j结尾的的最小编辑距离，依靠于D[i-1, j] 的最小编辑距离 + 1（删除操作）
插入方法：
在串S的后面插入串T的最后一位（因为是要将串S变为T所以 需要在串S的后面加入T的最后一个元素）
S最后插入一个元素来进行对串T的转换
D[i, j] = D[i, j-1] + 1 ==>这里的含义就是 S， T串中分别以i和j结尾的的最小编辑距离，依靠于串S的i位和串T的j-1为的最小编辑距离 + 1 （串S进行插入操作 插入串T的最后一位）
替换操作
在进行字符串变化操作的时候我们可以通过替换S的最后一个元素为T的最后一个元素，来进行字符串的变换操作
D[i , j] = D[i-1, j-1] + (a = 0 if S[i] == T[j] else ...
钢条切割问题
问题背景
现在有一个长度为10的钢条，可以零成本 将其切割成多段长度更小的钢条，我们先要求出最大收益
钢条长度
0
1
2
3
4
5
6
7
8
9
10
价格p
0
1
5
8
9
10
17
17
20
24
24
如果我们不切割的话可以获得的最大收益为 24
如果我们按照 2 2 6 切割方法，收益为 27
所以不同的切割方法收益不同，我们寻求的就是收益最大的切割方法
问题定义
输入：
钢条的长度n
价格表pl(1≤ l ≤n)：表示长度为l的钢条价格
输出：
求得一组切割方法，令收益最大化
问题观察
假设钢条能够至多切割一次：有以下这几种情况
我们就需要从这几种切割情况中寻找出收益最大的，max{p[i] + p[10-i], p[10]}
如果钢条能够切割两次：
我们可以现将钢条切割出一段
然后再剩余的钢条中继续切割
这时候 长度为8的就可以看做切割次数为一 的那一种情况
这里可能存在最优子结构 和重叠子问题
问题结构分析
问题表示：
C[j]:切割长度为j的钢条可得到的最大总收益
递推关系的建立
...
最长公共子序列问题（动态规划）
给定两个序列X和Y：
其公共序列为：
这里我们要找出它的最长子序列，由上面的情况得出最长的公共自序列长度为4 为BCAB
如果我们采用枚举法的话，有如下这种情况：
我们再次观察一下这个公共自序列：
我们发现长一点的数组依靠于短一点的数组：这时候可能会出现最优子结构 和重叠子问题
当一个结构里面包含最优子结构问题和重叠子问题的时候我们就应该想到使用动态规划来解决这个问题
动态分析问题
我们采用C[i, j] 来表示[1…i]和Y[1…j]的最长公共子序列长度
我们从最后一个字母来开始推导，有两种情况，
情况一：
这两个序列的最后一个字母不相同
如果最后两个字母不同的话，可分为两种情况
情况一
C[i, j] = C[i, j -1 ] + 0
情况二
C[i, j] = C[i-1, j] + 0
情况二：
这两个序列的最后一个字母相同。
这里面需要分为三种情况：
第一种：最后这个相同的字符在最长子序列中
第二种：最后这个相同的字符不一定出现在最长子序列中，我们删除第一个序列的最后一个，在和第二个序列相比较
第三种：最后这 ...
最大公共子数组问题（分治法）
原理：
采用二分法，分别找出左边数组的最大值，右边数组的最大值，再找出带有中间元素的最大值
S1:数组X[1,n/2]中的最大值
S2:数组X[n/2+1, n]的最大值
S3:包含中间元素的最大值
算法实例：
分解：
归并：
代码：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071'''最大子数组问题（分治法） 这里主要分为三个部分 1.求二分之后左边和右边的最大值 2.求合并之后的最大值 3.上面三者比较取最大值'''def max_sub(X, start, end): # 如果只有一个数字的话那么最大子数组就是它本身 if start == end: return X[start] # 记录一下中间位置 ...
硬币收集问题（动态规划）
问题：
（硬币收集问题）在n*m格木板中放置一些硬币，每一个格子上最多放置一个硬币。在木板的左上方，一个机器人需要收集尽可能多的硬币，并把他们带到右下角的单元格。每一步，机器人可以从当前位置向右或向下移动一格，当遇到一个有硬币的单元格时，就会将该硬币收集起来。设计一个算法，找出机器人能够收集到最大硬币数，并给出路径。
因为这里机器人只能向下和右边 走所以matrix[n,j]的位置确定依赖于 上面和左边
代码为：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960''' 收集硬币问题： （硬币收集问题）在n*m格木板中放置一些硬币，每一个格子上最多放置一个硬币。 在木板的左上方，一个机器人需要收集尽可能多的硬币，并把他们带到右下角的单元格。 每一步，机器人可以从当前位置向右或向下移动一格， 当遇到一个有硬币的单元格时，就会将该硬 ...
理解：
线性回归，首相非为两类， 一类是线性模型， 一类是回归问题， 综合起来就是使用线性模型解决回归问题
线性模型和回归问题并不是一开始就被绑在一起的，模型与问题之间是多对多的关系，例如有逻辑模型，分类问题， 只是因为在使用线性模型解决回归问题的时候，发现比较好用，所以才有了“线性回归”这个名词
回归问题
用于预测未来的回归问题：
在回归的世界里，万物的发展轨迹都不是一条单调向上走或向下走的直线，而是循着均值来回波动，一时会坠入低谷，但也会迎来春暖花开，而一时春风得意，也早晚会遇到坎坷挫折，峰回路转，否极泰来，从这个角度看，回归与其说是一个统计学问题，不如说更像是一个哲学问题。
简单来说就是各个数据点都沿着一条主轴来回波动的问题都算是回归问题
记录历史值和预测未来值是回归问题的两个代表特征
回归问题和分类问题的区别
回归问题和分类问题最大的区别是在于预测结果：
根据预测值类型的不同，预测结果可以分为两种，一种是连续的一种是离散的，连续的就是预测问题
下面是连续型数据
下面是离散型数据，离散型数据最大的特征就是缺乏中间过渡值，出现阶级跳跃，譬如“是”和“否”，通常使用boo ...
