#数组篇
##数组的定义
数据类型[数组声明符号] 变量名 = new 数据类型[数组长度]；
数据类型[] 变量名 = {数值，数值，数值，数值，数值}；
数组也是一个对象所以要用到new关键字
整数int型：int[] i = new int[5]; //动态声明
int[] i = {1,2,3,4,5}; //静态声明
int[] i = new int[] {1,2,3,4,5}; //不建议
概念
数组Array是用于储存多个相同类型数据的集合。
想要获取数组中的元素值，可以通过元素的下标来获取，下标是从0开始的。
动态初始化：int[] a = new int[5];
Ø 新建int[],长度是5
Ø 刚创建好的数组都是默认值0，int类型的数据默认值是0
Ø 把数组的地址值给变量a保存
示范
package day004;
import java.util.Arrays;
public class Test6_Arrays {
public static void main(String[] args) {
System.out.println("test...");
f1();
}
private static void f1() {
int[] i = new int[]{1,2,3,4,5};
//Arrays.toString(i);将数组转换成字符串
System.out.println(Arrays.toString(i));
char[] a = new char[5];
a[0]='h';
a[1]='e';
a[2]='l';
a[3]='l';
a[4]='o';
System.out.println(Arrays.toString(a));
}
}
##遍历数组
根据数组的下表输出数组中的数据
public static void main(String[] args) {
int[] i = new int[] {1,2,3,4,5};
for(int a=0;a<i.length;a++) {
System.out.println(i[a]);
}
}
##遍历数组，存入1到10
public static void main(String[] args) {
int[] i = new int[10];
for(int a=0;a<i.length;a++) {
i[a]=a+1;
}
System.out.println(Arrays.toString(i));
}
##遍历数组，给数组动态随机赋值
public static void main(String[] args) {
int[] i = new int[10];
for(int a=0;a<i.length;a++) {
i[a]=new Random().nextInt(100);
}
System.out.println(Arrays.toString(i));
}
##数组工具类
Arrays.toString(数组)
把数组里的数据，用逗号连接成一个字符串。
格式：[10, 14, 20, 46, 51]
Arrays.sort(数组)
对数组排序，对于基本类型的数组使用优化后的快速排序算法，效率高。
对引用类型数组，使用优化后的合并排序算法。
Arrays.copyOf(数组，新的长度)
把数组复制成一个指定长度的新数组。
新数组长度大于原数组，相当于复制，并增加位置。–数组的扩容
新数组长度小于原数组，相当于截取前一部分数据。–数组的缩容
测试
int[] a = Arrays.copyOf(arr, 10);//数组的复制，大于原来长度相当于扩容
System.out.println(Arrays.toString(a));//[12, 30, 20, 90, 34, 0, 0, 0, 0, 0]
System.out.println(a.length);//10
int[] a2 = Arrays.copyOf(arr, 3);//数组的复制，晓宇原来长度相当于截取前几个数据
System.out.println(Arrays.toString(a2));//[12, 30, 20]
System.out.println(a2.length);//10
#拓展
##二维数组
存放数组的数组，也就是说数组里存的还是数组的数据形式。
声明方式 ：
##遍历二维数组
public static void main(String[] args) {
int[][] i = new int[5][5];
for(int a=0;a<i.length;a++) {
for(int b=0;b<i[a].length;b++) {
i[a][b]=new Random().nextInt(10);
}
System.out.println(Arrays.toString(i[a]));
}
}
##冒泡排序
相邻位置比较，从小到大排序，如果小就往前换。i代表从头到尾遍历循环数据。
示列
package day0000;
import java.util.Arrays;
import java.util.Random;
public class TT {
public static void main(String[] args) {
int[] arr = new int[]{43, 36, 45, 18, 24,9,20,32};
int[] arrnew = f1(arr);
System.out.println(Arrays.toString(arrnew));
}
private static int[] f1(int[] a) {
//外循环控制循环次数，如果5个数字，循环4次就行
for (int i = 0; i < a.length-1; i++) {
//内循环控制比大小，循环次数和外循环一样
for (int j = 0; j < a.length-1; j++) {
if(a[j]>a[j+1]){
int t = a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
return a;
}
##斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
递推公式
斐波那契数列：
如果设an为该数列的第n项（ ），那么这句话可以写成如下形式：
显然这是一个线性递推数列。
通项公式
(如上，又称为“比内公式”，是用无理数表示有理数的一个范例。)
注：此时
⑵ an=[(2/√5+1)-1/(√5+1/2)ⁿ]/√5
public static void main(String[] args) {
int a =1;//a , b初始兔子数
for(int b=1;b<20;a=a+b) {//a=b+1,a=b+3
System.out.println(b);//1,2
System.out.println(a);//1,3
b=b+a;//b=2,b=2+3
}
}
##二分算法
判断是否适合分治法实现
###示列
public class Main {
public static void main(String[] args) {
int[] arr = { 11, 22, 33, 44, 55, 66, 77 };
int index1 = Binary(arr, 12, 0, arr.length - 1);
int index2 = Binary(arr, 66, 0, arr.length - 1);
System.out.println(index1);
System.out.println(index2);
}
/**
* 搜索指定要搜索元素在数组中是索引
*
* @param arr：要二分搜索的数组
* @param key：要查找的关键字
* @param low：起始索引
* @param high：结尾索引
* @return：若搜索到这个元素，则返回数组的索引下标；否则返回-1
*/
public static int Binary(int[] arr, int key, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > key) {
high = mid - 1;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
分析
##合并算法
合并排序是分治法当中一个经典的排序算法，它通过将规模为n的原始问题分解为n/2，然后得到各自的解后，在合并两个子问题的解，最终得到原始问题的解。合并排序属于稳定排序，在排序过程中，如果遇到Ai==Aj，假设i < j，在完成排序后不会影响Ai和Aj的相对位置，即Ai仍然在Aj前面。
合并排序的时间复杂度是O(nlogn)，但是在排序当中需要递归拆分元问题，空间复杂度是O(n)，合并排序是用空间换时间的算法。
package com.yellow.mergesort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
//声明一个数组
int original[] = new int[] { 6, 10, 25, 3, 33, 90, 60, 100, 56 };
mergeSort(original);//方法调用
print(original);//方法调用
}
private static void mergeSort(int[] original) {
if (original == null) {//判断数组不为空,如果为空返回一个空指针异常
throw new NullPointerException("The array can not be null !!!");
}
//取出数组长度
int length = original.length;
//if判断数组长度大于1就运行代码块
if (length > 1) {
//数组长度乘以2
int middle = length / 2;
int partitionA[] = Arrays.copyOfRange(original, 0, middle);// 拆分问题规模
int partitionB[] = Arrays.copyOfRange(original, middle, length);
// 递归调用
mergeSort(partitionA);
mergeSort(partitionB);
sort(partitionA, partitionB, original);
}
}
private static void sort(int[] partitionA, int[] partitionB, int[] original) {
int i = 0;
int j = 0;
int k = 0;
while (i < partitionA.length && j < partitionB.length) {
if (partitionA[i] <= partitionB[j]) {
original[k] = partitionA[i];
i++;
} else {
original[k] = partitionB[j];
j++;
}
k++;
}
if (i == partitionA.length) {
while (k < original.length) {
original[k] = partitionB[j];
k++;
j++;
}
} else if (j == partitionB.length) {
while (k < original.length) {
original[k] = partitionA[i];
k++;
i++;
}
}
}
private static void print(int[] array) {
if (array == null) {
throw new NullPointerException("The array can not be null !!!");
}
StringBuilder sb = new StringBuilder("[");
for (int element : array) {
sb.append(element + ", ");
}
sb.replace(sb.length() - 2, sb.length(), "]");
System.out.println(sb.toString());
}
}
##快速算法
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。
接着分别比较左右两边的序列，重复上述的循环。
public class FastSort{
public static void main(String []args){
System.out.println("Hello World");
int[] a = {12,20,5,16,15,1,30,45,23,9};
int start = 0;
int end = a.length-1;
sort(a,start,end);
for(int i = 0; i<a.length; i++){
System.out.println(a[i]);
}
}
public void sort(int[] a,int low,int high){
int start = low;
int end = high;
int key = a[low];
while(end>start){
//从后往前比较
while(end>start&&a[end]>=key) //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
//从前往后比较
while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
}
//递归
if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
}
}
##贪心算法
- 什么是贪心算法？
贪心算法，又称贪婪算法(Greedy Algorithm)，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。
贪婪算法是一种分阶段的工作，在每一个阶段，可以认为所做决定是最好的，而不考虑将来的后果。这种“眼下能够拿到的就拿”的策略是这类算法名称的来源。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路：
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。也就是当算法终止的时候，局部最优等于全局最优。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
如果确定可以使用贪心算法，那一定要选择合适的贪心策略；
public static void main(String[] args) {
int money=1000;
int[] moneyLevel = {1, 5, 10, 20, 50,100};
for (int i = moneyLevel.length - 1; i >= 0; i--) {
int num = money/ moneyLevel[i];
int mod = money % moneyLevel[i];
money = mod;
if (num > 0) {
System.out.println("需要" + num + "张" + moneyLevel[i] + "块的");
}
}
}
策略模式
策略模式的用意是针对一组算法，将每一个算法封装到具有共同接口的独立类中，从而使得它们可以相互替换。策略模式使得算法可以在不影响到客户端的情况下发生变化。
策略模式的结构
策略模式是对算法的包装，是把使用算法的责任和算法本身分开。策略模式通常是把一系列的算法包装到一系列的策略类里面，作为一个抽象策略类的子类。
策略模式涉及到三个角色：
1、环境角色
持有一个策略Strategy的引用
2、抽象策略角色
这是一个抽象角色，通常由一个接口或抽象类实现，此角色给出所有具体策略类所需的接口
3、具体策略角色
包装了相关算法或行为
策略模式实际应用场景-容错恢复机制
容错恢复机制是应用程序开发中非常常见的功能。那么什么是容错恢复呢？简单点说就是：程序运行的时候，正常情况下应该按照某种方式来做，如果按照某种方式来做发生错误的话，系统并不会崩溃，也不会就此不能继续向下运行了，而是有容忍出错的能力，不但能容忍程序运行出现错误，还提供出现错误后的备用方案，也就是恢复机制，来代替正常执行的功能，使程序继续向下运行。
举个实际点的例子吧，比如在一个系统中，所有对系统的操作都要有日志记录，而且这个日志还需要有管理界面，这种情况下通常会把日志记录在数据库里面，方便后续的管理，但是在记录日志到数据库的时候，可能会发生错误，比如暂时连不上数据库了，那就先记录在文件里面，然后在合适的时候把文件中的记录再转录到数据库中。
对于这样的功能的设计，就可以采用策略模式，把日志记录到数据库和日志记录到文件当作两种记录日志的策略，然后在运行期间根据需要进行动态的切换。