淘先锋技术网

首页 1 2 3 4 5 6 7

#数组篇
##数组的定义
数据类型[数组声明符号] 变量名 = 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到最后一个
     }
     
}

在这里插入图片描述
##贪心算法

  1. 什么是贪心算法?
      贪心算法,又称贪婪算法(Greedy Algorithm),是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优解出发来考虑,它所做出的仅是在某种意义上的局部最优解。
      贪婪算法是一种分阶段的工作,在每一个阶段,可以认为所做决定是最好的,而不考虑将来的后果。这种“眼下能够拿到的就拿”的策略是这类算法名称的来源。
      贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路:

  1. 建立数学模型来描述问题。
  2. 把求解的问题分成若干个子问题。
  3. 对每一子问题求解,得到子问题的局部最优解。
  4. 把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题
  贪心策略适用的前提是:局部最优策略能导致产生全局最优解。也就是当算法终止的时候,局部最优等于全局最优。

四、贪心算法的实现框架
从问题的某一初始解出发;
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、具体策略角色

包装了相关算法或行为

策略模式实际应用场景-容错恢复机制
容错恢复机制是应用程序开发中非常常见的功能。那么什么是容错恢复呢?简单点说就是:程序运行的时候,正常情况下应该按照某种方式来做,如果按照某种方式来做发生错误的话,系统并不会崩溃,也不会就此不能继续向下运行了,而是有容忍出错的能力,不但能容忍程序运行出现错误,还提供出现错误后的备用方案,也就是恢复机制,来代替正常执行的功能,使程序继续向下运行。
举个实际点的例子吧,比如在一个系统中,所有对系统的操作都要有日志记录,而且这个日志还需要有管理界面,这种情况下通常会把日志记录在数据库里面,方便后续的管理,但是在记录日志到数据库的时候,可能会发生错误,比如暂时连不上数据库了,那就先记录在文件里面,然后在合适的时候把文件中的记录再转录到数据库中。
对于这样的功能的设计,就可以采用策略模式,把日志记录到数据库和日志记录到文件当作两种记录日志的策略,然后在运行期间根据需要进行动态的切换。