Java Day 12

递归练习

优点：代码十分简洁、优雅能解决一些实际问题

缺点：问题规模越大效率指数递增

斐波那契数列

import java.lang.Object;
public class Main {
    public static void main(String[] args){
        System.out.println(fb(7));
    }
 
    public static int fb(int i){
        if (i < 0)
            return 0;

        if (i == 1 || i == 2)
            return 1;
        else
           return fb(i - 1) + fb(i - 2);
    }
}

猴子吃桃

每天吃一半再多吃一个第10天还没吃只剩下 1个问第一天

import java.lang.Object;
public class Main {
    public static void main(String[] args){
        System.out.println( qestion(10, 1));
    }
    public static int qestion(int day, int sum){
        if (day > 1)
            return qestion(day - 1, (sum + 1) * 2);
        else
            return sum;
    }
}

迷宫问题

深搜和宽优

一个矩阵 2为出口 1为障碍找出最路径输出步数

import java.lang.Object;

public class Main {
    static int i = 99999;
    public static void main(String[] args){
        int[][] map = new int[8][7];

        //初始化边界
        for (int i = 0; i < map[0].length; i ++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < map.length; i++){
            map[i][0] = 1;
            map[i][6] = 1;
        }
        
        //调试的
        map[3][1] = 0;
        map[3][2] = 1;
        //出口
        map[4][3] = 2;
        map[3][4] = 1;
        map[3][5] = 1;
        map[3][6] = 1;
        map[2][2] = 1;
        map[1][2] = 1;
        map[3][2] = 1;
        map[4][2] = 1;
        
        //调试用的乱的一比
        
//        for (int i = 0; i < map.length; i++) {
//            for (int j = 0; j < map[i].length; j++)
//                System.out.print(map[i][j] + "  ");
//            System.out.println();
//        }

        //System.out.println(find(map, 1, 1));
//        for (int i = 0; i < map.length; i++) {
//            for (int j = 0; j < map[i].length; j++)
//                System.out.print(map[i][j] + "  ");
//            System.out.println();
//        }

        System.out.println(find_min(map, 1, 1, 0));
        System.out.println(i);
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++)
                System.out.print(map[i][j] + "  ");
            System.out.println();
        }
    }

    public static int find_min(int map[][], int x, int y, int set){

        if (map[x][y] == 2){
            if (i > set)    //找到一个更优路径
                i = set;
            return set;
        }else if (map[x][y] == 1){
            return set;
        }else if (map[x][y] == 0 ){
            map[x][y] = 3;
            find_min(map, x + 1, y, set + 1);
            find_min(map, x, y + 1, set + 1);
            find_min(map, x - 1, y, set + 1);
            find_min(map, x, y - 1, set + 1);
            map[x][y] = 0;
            return set;
        }
        return set;
    }

    public static boolean find(int map[][], int x, int y){
        if (map[x][y] == 2)
            return true;
        else if (map[x][y] == 0 ){
            map[x][y] = 3;
            if(find(map, x + 1, y))
                return true;
            else if (find(map, x, y + 1))
                return true;
            else if(find(map, x - 1, y))
                return true;
            else if(find(map, x, y - 1))
                return true;
        }
        return false;
    }
}

汉罗塔问题

可变参数

对于同一方法，参数类型相同，长度不确定可以选用

function(int... a)

可变参数可以为数组
可变参数长度 0<= n
可变参数本质就是一个数组引用
如果函数入口还有其他参数可变参数必须在最后一个位置
可变参数形参中只能有一个

import java.lang.Object;

public class Main {
    public static void main(String[] args){
        System.out.println(VarP(new int[]{1,2,3}, new int[]{2,3,4,10}));
    }
    
   public static int VarP(int[]... num){//可变参数
        int max = -1;
        for (int i = 0; i < num.length; i++)
            for (int j = 0; j < num[i].length; j++) {
                if (num[i][j] > max)
                    max = num[i][j];
            }

        return  max;
   }

== 和 equals

比较方法

==比较的是值变量的值是否相等，这里就要区分基础类型和引用类型，引用变量的值实际上是存储的是一个地址，而基本数据类型的值就是其本身存储值；
equals（）判断的是地址是否相等，只能判断引用类型

特殊:

String str = new String("helloworld");
String str2 = new String("helloworld");
== //faluse
equals //true

大多数语言会对字符串进行优化，相同的字符串在堆栈只有一个。

`Object` 超类

`hashcode()`

提高哈希结构的容器效率
每个引用对象，都有一个不同的哈希值
哈希值主要根据地址来计算的
可以重写

`toString()`

返回全类名（包名+类名）@ hashcode 16进制

可重写打印一些类信息

常用类

包装类分类 WrapperType.java

父类：Number

装箱和拆箱

JDK5以前没有自动装拆箱，JDK5以后有了自动的特性

import com.sun.jdi.ClassType;

public class Main {
    public static void main(String[] args) {
        // 手动装箱
        int n = 100;
        Integer _1n = new Integer(n);
        Integer _2n = Integer.valueOf(n);
        System.out.println(_1n.getClass());
        System.out.println(_2n);
        //自动装箱 jdk 5 以后
        Integer i = n;
        System.out.println(i.getClass());
        System.out.println(i);
    }
}

自动装箱底层呢逻辑依旧是使用包装类valueof()方法操作的！

补充：三元运算符是一个整体

1	System.out.println(true ? 1 : 1.1);

输出的是1.0而不是1 。因为三元运算符是一个整体当前最大的类型是double 因为机制会向上转换为double 1—> 1,0

String <- 转换-> Integer

Interger转String包装类三种方法

Integer i = 233;	//自动装箱 233 为int  
 //自动装箱
 String str = i + "";
 String str2 = i.toString();
 String str3 = String.valueOf(i);
 System.out.println(str + str2 + str3);

String ->Interger 2种

String str = "123";

        Integer i1 = new Integer(str);
        Integer i2 = Integer.parseInt(str);
        System.out.println(i1 + i2);

面试题：使用== 判断值相等的时候

凡是new的判断的是对象地址是否相等
==一边有基础类型那就是判断值是否相等
使用自动装箱的封装类判断的是底层valueOf() 返回的值是否相等
- Integer 底层valueOf low-128 heigh 是 127 这个区间内不会new 值具体情况看底层源码

String类

结构

底层使用的是一个数组private final char value[]; 存放的值不可以修改

final 修饰的是 value 的值值是地址而不是具体数据因此这个指向是不可变的

不可修改指定是value 这个数组指针不可修改 value 存放的数组地址不可改类似C 语言const 修饰的指针

value地址下的这个数组的值是可以更改的

在时间操作中String 底层的数组是可变的与上述结论矛盾？实际上每次更改是新建了一个全新对象（包含在常量池中创建字符串）而并非更改了value引用和底层数据

String两种基本创建方法

直接赋值（装箱）

“123” 是字符串常量存在于方法区中的常量池 JVM 先会从常量池中找到123 字符串并且直接指向该地址所以==True
1
2
3
String str = "123";
String str1 = "123";
System.out.println(str == str1);

通过各种构造器

流程 str 在常量池中找123 如果不存在则新建 str2 先是在堆中创建了其String对象 str2指向该对象然后由对象中的value[] 数组在常量池中找字符串123 并指向

String str = "123";
        String str2 = new String("123");
        System.out.println(str == str2);
        System.out.println(str.hashCode());
        System.out.println(str2.hashCode());

intern() 方法

返回Stirng 对象中 value 在常量池的地址

1
2
3

String str = "123";
String str2 = new String("123");
System.out.println(str == str2.intern());//等价于 str == str

out true

字符串特性

简单的栗子

1	String a = "hello" + "adc" //等价于 "helloabc" 编译器做了优化

因此看起来像是创建了三个字符串常量”hello” “abc” “helloabc”

实际上编译器为我们做了优化只创建一个”helloabc” 常量

栗子2：

public class Demo1 {
    String str = "常量池";
    final char[] ary = {'a','b', 'c'};
    char[] ary2 =  {'a','b', 'c'};
    public void change(String str, char[] ary, char[] ary2){
        str = "hellow";	//这里实际上进行了一个装箱操作 str 指向的地址已经改变了
        ary[0] = 'c';	//数组存储在堆中 这个操作也改变了Demo对象中的ary的值
        ary2[0] = 'c';
    }

    public static void main(String[] args) {
        Demo1 text = new Demo1();
        text.change(text.str, text.ary, text.ary2);
        System.out.println(text.str);
        System.out.println(text.ary);
        System.out.println(text.ary2);
    }
}

StirngBuffer

特性

可变的字符序列，可以对字符串内容进行更改
String类的扩展，可变长字符串
StringBuffer 实现了Serializeble 接口，可以进行串型化（可在网络中传输）
在String 父类中的实现了AbstractStringBuilder 有属性char[] value 而String 是本身final 修饰的 char[]，因此StringBuffer 的底层数组是可变的而不是final常量可变长并且存储在堆中而不是方法区的常量池
StringBuffer 是final类不可以被继承

对比String类优点

主要体现在更改字符串的 效率

String 底层是字符串常量，底层字符串 private final char value[] 意味着每次改变String 字符串实际上是新建或从常量池中找到一个字符串常量，并且更新 String 对象的指向简单来说就是效率低
StringBuffer 的底层数组是char[] value 并不是常量保存的是字符串变量是在堆中的是可以更改原本的数组，并没有创建新的内容，效率相对较高

构造

String 转为 StringBuffer

//默认16长度
StringBuffer str = new StringBuffer();
//给定一个长度
StringBuffer str2 = new StringBuffer(100);
//给定一个字符串  给定的字符串长度+16  这里为 26
StringBuffer str3 = new StringBuffer("helloworld");
//append 方法
StringBuffer str4 = new StringBuffer();
str4.append("helloworld");

StringBuffer 转 String

toString()

public class Demo02 {
    public static void main(String[] args) {
        String str = "helloworld";
        StringBuffer strb  = new StringBuffer(str);

        String str1 = strb.toString();
        System.out.println(str1);
        String str2 = new String(new StringBuffer("helloworld2"));
        System.out.println(str2);
    }
}

常用方法

增删改查

补充：

StringBuffer() 构造不能用null 而append 可以为空实际上String 指向空的时候是指向了一个表示null字符串

append 可以添加这个字符串而构造器直接抛出异常

public class Demo02 {
    public static void main(String[] args) {
        String str1 = null;
        StringBuffer str = new StringBuffer();
        str.append(str1);
        System.out.println(str.length());
        System.out.println(str1);
        System.out.println(str.length());
        //StringBuffer str = new StringBuffer(null);  NullPointerException
    }
}

StringBuilder

特性

可变的字符序列提供一个与StringBuffer兼容的api，但不保证同步 (不是线程安全),
单线程使用最优
StringBuffer的替代品基础关系和它一模一样
实现了Serializibale 可以串行化
多线程不建议使用

上代码看效率，下面代码对字符串反复修改

StringBuilder>StringBuffer> String(效率)

这可不是倍数，这是指数级的差距

import java.sql.Time;
import java.util.Scanner;

public class Demo02 {
    public static void main(String[] args) {
        String text = "";

        String str_text = new String();
        StringBuffer str_buff = new StringBuffer();
        StringBuilder str_buider = new StringBuilder();

        long start = System.currentTimeMillis();
        for (int i = 0; i < 8000; i++) {

        }

        start = System.currentTimeMillis();
        for (int i = 0; i < 80000; i++) {
            str_buider.append(String.valueOf(i));
        }
        long end = System.currentTimeMillis();
        System.out.println("Stringbuilder"+(end - start));

        for (int i = 0; i < 80000; i++) {
            str_buff.append(String.valueOf(i));
        }
        end = System.currentTimeMillis();
        System.out.println("StringBuffer"+(end - start));


        start = System.currentTimeMillis();
        for (int i = 0; i < 80000; i++) {
            str_text += i;
        }
        end = System.currentTimeMillis();
        System.out.println("String"+(end - start));


    }
}

String总结

对于字符串 java提供了3个类，String 、StringBuffer, StringBuilder优势互补，String 要相对劣势一些

String
- 底层char[] 数组为private final char[] value ，字符串常量，字符串被创建于常量池中
- 重用率高，大部分编译器都有这个特性对相同的字符串常量只存储一份，节约内存开销
- 如果字符串要进行大量的增删操作，效率非常低，对非常低（原因字符串常量不可修改， String是一个不可变的字符序列）
StringBuffer
- 底层char[] value 可变的字符串序列栈中存储的
- 继承关系可查看源码，实现了Serializeble接口，可串行化用于网络输出
- 增删改查效率非常高
- 它是一个线程安全的
StringBuilder
- 它的继承关系和StringBuffer 一样所以StringBuffer 有的特性大多它也有
- 它不是一个线程安全的
- 效率比Buffer 还要高

结论：特点环境用特定类型

只要涉及大量的修改操作Buffer YYDS ， Builder 如果是单线程且伴随大量修改 Builder更优

如果只是简单使用并没有大量的修改，并且被大量对象指向（常量池中的字符串），显然String

最优，

别杀鸡用牛刀..

Arrays类

简化了数组操作

多是静态方法

toStirng() 字符串序列化输出可以替换掉for

sort(arr, Comparator<>) 排序看了下源码应该是快排参数而接受一个Comparator 接口使用这个方法

我们需要，创建一个匿名内部类类重载Comparator 中的 compare（）方法

自定义排序

import javax.annotation.processing.Completion;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;

public class Demo04 {
    public static void main(String[] args) {
        Book[] books = new Book[4];
        books[0] = new Book("红楼梦", 100);
        books[1] = new Book("金瓶梅新", 90);
        books[2] = new Book("青年文摘20年", 5);
        books[3] = new Book("Java从入门到放弃", 300);

        Arrays.sort(books, new Comparator(){
            @Override
            public int compare(Object o1, Object o2) {
                Book b1 = (Book) o1;
                Book b2 = (Book) o2;

                double re = b2.price - b1.price;
                if (re > 0)
                    return -1;
                else if (re < 0)
                    return 1;
                else
                    return 0;

            }
        });

        System.out.println(Arrays.toString(books));
        Arrays.sort(books, new Comparator<Book>() {
            @Override
            public int compare(Book o1, Book o2) {
                return o1.name.length() - o2.name.length();
            }
        });
        System.out.println(Arrays.toString(books));
    }


}

class Book{
    String name;
    int price;

    public Book(){}

    @Override
    public String toString() {
        return this.name + "," +  this.price;
    }

    public Book(String name, int price) {
        this.name = name;
        this.price = price;
    }
}

binarySerch(arr, value) 二叉查找，前提arr 数组是有序的返回index 不存在返回-1

copyOf(arr, arr.length) 相当于一个对数组切片操作返回一个新数组 length 可以超过本身数组长度超出部分null

fill(arr， replace) 替换原来数组值

equals(arr1, arr2) 字符串也重载了这个方法对比各元素值是否相等

asList()

System类

比较常用的方法

arraycopy()

接受5个参数 src, scrPos(源数组位置),dest,destPos(目标数组开始位置),length(拷贝长度)

import java.util.Arrays;

import static java.lang.System.*;

public class Demo05 {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1,2,3};
        int[] arr2 = new int[3];

        arraycopy(arr1, 0, arr2, 0, 3);
        out.println(Arrays.toString(arr2));
    }
}

currentTimeMillis() 返回从1970-1-1 到现在毫秒数

BigInteger BigDecimal

一个数非常大超过了long 可以使用BigInteger 类型

import java.math.BigInteger;

public class Demo06 {
    public static void main(String[] args) {
        BigInteger bigInteger = new BigInteger("233333333333333333333333333333333333");//需要用字符串的形式传入
        BigInteger bigInteger1 = new BigInteger("12321");

        //运算操作需要用BigInteger中的方法
        //并不会改变原本数据 是生成新的数
        System.out.println(bigInteger1.add(bigInteger));
        System.out.println(bigInteger.add(new BigInteger("2333")));
        System.out.println(bigInteger.subtract(bigInteger));//－
        System.out.println(bigInteger.multiply(bigInteger));//*
        System.out.println(bigInteger.divide(bigInteger));//÷
    }
}

BigDecimal

注意：divide方法除可能会得到一个无理数会抛出异常ArithmeticException

import java.math.BigDecimal;
import java.math.BigInteger;

public class Demo06 {
    public static void main(String[] args) {
        BigDecimal bigInteger = new BigDecimal("2333333333333333.33333333333333333333");//需要用字符串的形式传入
        BigDecimal bigInteger1 = new BigDecimal("1232.1");

        //并不会改变原本数据 是生成新的数
        System.out.println(bigInteger1.add(bigInteger));
        System.out.println(bigInteger.add(new BigDecimal("2333")));
        System.out.println(bigInteger.subtract(bigInteger));//－
        System.out.println(bigInteger.multiply(bigInteger));//*
        System.out.println(bigInteger.divide(bigInteger));//÷  
    }
}

1	System.out.println(bigInteger.divide(new BigDecimal("3")));//÷

此时抛出异常

可以使用BigDecimal中的属性ROUND_CEILING 保留几位小数这个被弃用了

1	System.out.println(bigInteger.divide(new BigDecimal("3"), BigDecimal.ROUND_CEILING));//÷

Calender

第二代时间类

抽象类构造器是私有的通过类中静态方法getlnstance() 创建对象