【JAVA基础】算法与集合

1 查找

1.1 二分查找

public class Main {
    public static void main(String[] args) throws IOException, CloneNotSupportedException, ParseException {
//数组必须有序
        int[] arr={1,2,4,5,6,24,123};
        System.out.println(binarySearch(arr,123));//6
    }
    public static int  binarySearch(int[] arr,int num){
        int min=0;
        int max=arr.length-1;
        while (true)
        {
            if(min>max){return -1;}
            int middle=(max+min)/2;
            if(arr[middle]>num)
            {
                max=middle-1;
            }
            else if(arr[middle]<num){
                min=middle+1;
            }
            else{
                return middle;
            }
        }
    };
}

1.2 插值查找

数据要有顺序

1.3 分块查找

索引表

package DEMO1;

import java.io.IOException;
import java.text.ParseException;

public class Main {
    public static void main(String[] args) throws IOException, CloneNotSupportedException, ParseException {
        int[] arr={
                5,4,3,2,
                7,9,8,6,
                11,14,13,15
        };
        Block b1=new Block(5,0,3);
        Block b2=new Block(9,4,7);
        Block b3=new Block(15,8,11);
//        创建索引表
        Block[] blockarr={b1,b2,b3};
//        要查找的元素
        int num=9;
        System.out.println(getIndex(blockarr,arr,num));//5
    }

    private static int getIndex(Block[] blockarr, int[] arr, int num) {
        int n=NumBlock(blockarr,num);
        if (n == -1) {
            return -1;
        }
        int start=blockarr[n].getStartIndex();
        int end=blockarr[n].getEndIndex();
        for (int i = start; i < end; i++) {
            if (arr[i] == num) {
                return i;
            }
        }
        return -1;

    };
    //num在哪一块
    private static int NumBlock(Block[] blockarr, int num) {
        for (int i = 0; i < blockarr.length; i++) {
            if(num<=blockarr[i].getMax())
            {
                return i;
            }
        }
        return -1;
    };
}
class Block{
    private int max;
    private int startIndex;
    private int endIndex;

//ptg生成

    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

1.4 hash查找

2 排序

2.1 冒泡排序

int[] arr={4,5,2,1,3};
        for(int j=0;j<arr.length;j++)
        {
            for (int i = arr.length-1; i >0; i--) {
                if(arr[i]<arr[i-1])
                {
                    int temp=arr[i-1];
                    arr[i-1]=arr[i];
                    arr[i]=temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);//1 2 3 4 5
        }

2.2选择排序

2.3 插入排序

        int[] arr={4,5,2,1,3};
//        1.记录无序数组第一个索引
        int start = -1;
        for (int i = 1; i < arr.length; i++) {
            if(arr[i-1]>arr[i])
            {
                start=i;
                break;
            }
        }
//          2.遍历无序数组

        for (int i = start; i < arr.length; i++) {
            int j=i;
            while(j>0&&arr[j-1]>arr[j]){

                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                    j--;
            }
        }
        for (int j : arr) {
            System.out.println(j);
        }

2.4 快速排序

     int[] arr={4,5,2,1,3};
        long start=System.currentTimeMillis();
        quick(arr,0,arr.length-1);

        for(int i:arr)
        {
            System.out.println(i);//1 2 3 4 5
        }
        long end= System.currentTimeMillis();
        System.out.println(end-start);//执行快速排序所花的时间

    }
    public static void quick(int arr[],int start,int end)
    {
        //第一轮
        int i=start;
        int j=end;
        if(start>end)
        {//递归出口
            return;
        }
        int basicN=arr[start];
        while (start!=end){
            while (true){
                if(end<=start||arr[end]<basicN)
                    break;
                end--;
            }

            while (true)
            {
                if(end<=start||arr[start]>basicN)
                    break;
                start++;
            }
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
        }
        int temp=arr[start];
        arr[start]=arr[i];
        arr[i]=temp;

        quick(arr,i,start-1);
        quick(arr,start+1,j);

3 集合

3.1 集合体系结构

单链集合Collection

双列集合Map

list 允许重复，set不允许重复

有序:存和取的元素顺序一致（队列）

3.2 Collection集合

3.2.1 方法

public class Frog   {
    public static void main(String[] args) {
//        Collection是一个接口，不能直接创建其对象
        Collection<String> co=new ArrayList<>();
        co.add("11");
        co.add("22");
        System.out.println(co);//[11, 22]
//        全部清空
//        co.clear();
        System.out.println(co.remove("11"));//true
        System.out.println(co);//[22]
//        是否包含
        //底层依赖equals判断，如果存储自定义对象用contains，要重写
        System.out.println(co.contains("22"));//true
        Collection<Dog> coDog=new ArrayList<>();
        Dog d1=new Dog("do1",18);
        Dog d3=new Dog("do1",18);
        coDog.add(d1);
        coDog.add(d3);
        System.out.println(d1.equals(d3));//true
        System.out.println(coDog.isEmpty());//false
        //集合长度
        System.out.println(coDog.size());//2
    }
}

Dog.java

public class Dog {
    private String name;
    private int age;


   public Dog() {
    }

    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }

    /**
     * 获取
     * @return name
     */
    public String getName() {
        return name;
    }

    /**
     * 设置
     * @param name
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * 获取
     * @return age
     */
    public int getAge() {
        return age;
    }

    /**
     * 设置
     * @param age
     */
    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Dog dog = (Dog) o;
        return age == dog.age && Objects.equals(name, dog.name);
    }
    
    public String toString() {
        return "Dog{name = " + name + ", age = " + age + "}";
    }
}

Dog.java需要重写equals方法：点到底就可以

3.2.2 遍历

1 迭代器遍历

不依赖索引

public class Frog   {
    public static void main(String[] args) {
//        Collection是一个接口，不能直接创建其对象
        Collection<String> co=new ArrayList<>();
        co.add("11");
        co.add("22");
        co.add("33");
//        迭代器
        Iterator<String> it=co.iterator();
//        hasNext()判断当前元素是否有值
        while (it.hasNext())
        {
            //next();获取当前元素，并将迭代器对象移到下一个位置
            //循环中只能用一次next方法，如用多次该值给变量
            String s=it.next();
            //System.out.println(it.next());NoSuchElementException,循环只能用一次next方法
            System.out.println(s);
//            当上面循环结束，迭代器指针指向没有元素的位置



//            迭代器遍历，不能用集合的方法删除或者添加
                if("33".equals(s)){
                  //  co.add("45");//ConcurrentModificationException
                    //添加没办法，删除可以用迭代器对象删除
                    it.remove();
                }

        }
        //System.out.println(it.next());//NoSuchElementException没有索引异常，只是没有元素
//        迭代器遍历完毕，指针不会复位
        System.out.println(it.hasNext());//false
        
    }
}

2 增强for遍历

内部是Iterator迭代器

单列集合、数组用增强for遍历

        Collection<String> co=new ArrayList<>();
        co.add("11");
        co.add("22");
        co.add("33");
//        快捷：co.for
        //遍历时只是把数据交给s记录，改变s的值不会改变co的值
        for(String s:co)
        {
            System.out.println(s);
        }

3 Lambda表达式遍历

Lambda表达式（匿名函数）前提：必须是函数接口匿名内部类，接口中只能有一个抽象方法

省略规则：

//        Collection是一个接口，不能直接创建其对象
        Collection<String> co=new ArrayList<>();
        co.add("11");
        co.add("22");
        co.add("33");
        //自己遍历集合，获得每一个元素，传递给accept方法
        co.forEach(new Consumer<String>() {
            @Override
            public void accept(String s) {
                System.out.println(s);
            }
        });
//        简化版本
        co.forEach((String s)-> {
                System.out.println(s);
            }
        );
//        更简化版本
        co.forEach(s->System.out.println(s));
}}

3.3 List集合

       List<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println(list);//[1, 2, 3]
        //原来索引元素依次往后移
        list.add(1,4);
        System.out.println(list);//[1, 4, 2, 3]
//        当方法重载调用，删除元素优先删除实参与形参一致的方法
        //调用value==1的还是index==1？
        list.remove(1);
        System.out.println(list);//[1, 2, 3]
        list.add(1,4);
//        手动装箱
        Integer i=Integer.valueOf(1);
        list.remove(i);
        System.out.println(list);//[4, 2, 3]
//        修改
        Integer in=list.set(0,5);
        System.out.println(in);//4
        System.out.println(list);//[5, 2, 3]
//        获取值
        System.out.println(list.get(2));//3

remove两种方法，当方法重载调用，删除元素优先删除实参与形参一致的方法

遍历

public class Frog   {
    public static void main(String[] args) {
        List<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        Iterator<Integer> it=list.iterator();
        while (it.hasNext()){
            Integer it1=it.next();
            System.out.println(it1);//1 2
        }
        for(Integer i:list){
            System.out.println(i);//1 2
        }
        list.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);//1 2
            }
        });
        list.forEach(integer-> System.out.println(integer));//1 2
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

}}

3.4 ArrayList集合

查看源码：

ctrl+n：搜索ArrayList

alt+7或者ctrl+f12：

3.4.1 空参构造

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

选中elementData：ctrl+b

transient Object[] elementData;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

当用空参构造创建对象，底层创建一个长度为0的数组

3.4.2 add

ArrayList<Integer> arr=new ArrayList<>();
        arr.add(1);

public boolean add(E e) {
        modCount++;
//e：当前要添加的元素
//elementData：底层数组名
//size：集合的长度/当前元素应存入的位置
        add(e, elementData, size);
        return true;
    }

跟进中间add方法

private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
//新方法满了用无参grow方法扩容
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

private Object[] grow() {
//有参grow
        return grow(size + 1);
    }

private Object[] grow(int minCapacity) {
//第一次添加， minCapacity=1，oldCapacity=0
        int oldCapacity = elementData.length;
//如果老容量不等于0或者数组不等于空数组
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //计算数组新长度
            int newCapacity = ArraysSupport.newLength(oldCapacity,
//如果10个存满要扩容，此时minCapacity - oldCapacity=11-10=1
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
//copyOf进行老数组复制到新数组，elementData是老的数组，newCapacity是新的数组长度
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
//Math.max比较谁大，DEFAULT_CAPACITY=10.minCapacity=1
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

 //如果10个存满要扩容，oldLength=10，minGrowth=1，prefGrowth=5
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0
//比较的原因是新增的数可能比老容量多得多，集合可以一次添加多个元素
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }

3.5 LinkedList集合

底层是双链表

  //内部类，表示链表结点
  private static class Node<E> {
//表示现在我要存储的数据
        E item;
//下一个节点的地址值
        Node<E> next;
//前一个节点的地址值
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;


    transient Node<E> first;


    transient Node<E> last;


//使用空参构造，其成员变量存在，但都是默认值
    public LinkedList() {
    }

 public boolean add(E e) {
        linkLast(e);
        return true;
    }

  void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

4 泛型

没有给集合指定类型，那么默认都是Object类型，如多态一样不能访问子类的特有功能

泛型不能写基本数据类型，因为不是object类

4.1 泛型类

MyArrayList.java

public class MyArrayList<E> {
    Object[] obj=new Object[10];
    int size;
//    E表示不确定的类型
    public boolean add(E e){
        obj[size]=e;
        size++;
        return true;
    }
    public E get(int index){
        return (E)obj[index];    }
//作用：打印的不是地址值，而是属性值
    @Override
    public String toString() {
//        把数组所有元素都拼接为字符串再返回
        return Arrays.toString(obj);
    }
}

Frog.java

public class Frog   {
    public static void main(String[] args) {
        //String传给E
        MyArrayList<String> list=new MyArrayList<>();
        list.add("111");
        list.add("112");
        String s=list.get(1);
        System.out.println(s);//112
}}

4.2 泛型方法

MyArrayList.java

public class MyArrayList {
//    第一个<E>表示我已经定义的不确定类型E
    //E...e 表示可变参数，传一个或者多个都可以，底层是数组
   public static <E> void addL(ArrayList<E> list, E...e){
       //e.for回车：快捷,增强for
        for (E e1:e){
            list.add(e1);
        }
   }
}

Frog.java

public class Frog   {
    public static void main(String[] args) {
        ArrayList<String> arr= new ArrayList<>();
        MyArrayList.addL(arr,"1","2","3");
        System.out.println(arr);//[1, 2, 3]
}}

4.3 泛型接口

//java定义的泛型接口

public interface List<E> extends Collection<E> {...}

//使用方式1
public class Frog implements List<String> {}

//使用方式2
public class Frog<E>  implements List<E> {}

4.4 泛型通配符

5 set集合

方法基本与Collection的API一致

5.1 HashSet

无序、不重复、无索引。无序指的是存和取有可能不一样

底层：哈希表。哈希表组成：JDK8之前：数组+链表；JDK8之后：数组+链表+红黑树

哈希值：根据hashCode()计算的int整数，确定数据添加到数组哪个位置，然后用equals方法看属性值是否相等。所以存储自定义对象，一定要重写这两个方法

public class Frog {
    public static void main(String[] args) {
        Dog do1=new Dog("do1",19);
        Dog do2=new Dog("do1",19);
//        没有重写hashCode方法，不同对象计算的哈希值不同
//        重写hashCode方法，不同对象属性值相同，计算的哈希值相同
        System.out.println(do1.hashCode());//没有重写1078694789 重写3088270
        System.out.println(do2.hashCode());//没有重写1831932724 重写3088270
        Dog do3=new Dog("do3",19);
        Dog do4=new Dog("do4",112);
        HashSet<Dog> hash=new HashSet<>();
        System.out.println(hash.add(do1));//true
        System.out.println(hash.add(do2));//false
        System.out.println(hash.add(do3));//true
        System.out.println(hash.add(do4));//true
        //不重写hash方法相同的属性也会打印
        System.out.println(hash);//[Dog{name = do1, age = 19}, Dog{name = do3, age = 19}, Dog{name = do4, age = 112}]
    }
}

重写hashCode()不需要自己写

5.2 LinkedHashSet

有序、不重复、无索引

相比HashSet每个元素多了双链表记录存储顺序

5.3 TreeSet

可排序、不重复、无索引

基于红黑树

Dog.java

  @Override
    public int compareTo(Dog o) {
        //指定排序规则,年龄升序排列
        return this.age-o.age;
    }

Frog.java

public class Frog {
    public static void main(String[] args) {
        Dog do1=new Dog("do1",16);
        Dog do2=new Dog("do1",12);
        Dog do3=new Dog("do3",19);
        TreeSet<Dog> ts=new TreeSet<>();
        ts.add(do3);
        ts.add(do1);
        ts.add(do2);
        System.out.println(ts);//[Dog{name = do1, age = 12}, Dog{name = do1, age = 16}, Dog{name = do3, age = 19}]
    }
}

public class Frog {
    public static void main(String[] args) {
        Dog do1=new Dog("do1",16);
        Dog do2=new Dog("do1",12);
        Dog do3=new Dog("do3",19);
        TreeSet<Dog> ts=new TreeSet<>();
        ts.add(do3);
        ts.add(do1);
        ts.add(do2);
        System.out.println(ts);//[Dog{name = do1, age = 12}, Dog{name = do1, age = 16}, Dog{name = do3, age = 19}]


        //Comparator比较器排序

        //存入四个字符串长度排序，长度一样字母排序
        TreeSet<String> tss=new TreeSet<>(new Comparator<String>() {
            //lambda前提：compare接口必须是函数接口
            @Override
            public int compare(String o1, String o2) {
                int i=o1.length()-o2.length();
                //w为0就用默认的匹配规则
                i=i==0?o1.compareTo(o2):i;
                return i;
            }
        });
        TreeSet<String> tss1=new TreeSet<>((String o1, String o2)-> {
                int i=o1.length()-o2.length();
                //w为0就用默认的匹配规则
                i=i==0?o1.compareTo(o2):i;
                return i;

        });
        TreeSet<String> tss2=new TreeSet<>((o1, o2)-> {
            int i=o1.length()-o2.length();
            //w为0就用默认的匹配规则
            i=i==0?o1.compareTo(o2):i;
            return i;

        });
        tss.add("aa");
        tss.add("aab");
        tss.add("bb");
        tss.add("a");
        System.out.println(tss);//[a, aa, bb, aab]
    }
}

Dog.java

//默认排序，JavaBean类实现Comparable接口
public class Dog implements Comparable<Dog>{
    private String name;
    private int age;


   public Dog() {
    }

    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }

    
    @Override
    public int compareTo(Dog o) {
        //指定排序规则,年龄升序排列
        return this.age-o.age;
    }
}

6 Arrays

        int[] arr={1,2,3,4,5,6};
//        将数组变为字符串,底层:StringBuilder,append方法
        System.out.println(Arrays.toString(arr));
//        二分查找元素
        System.out.println(Arrays.binarySearch(arr,4));//索引为3
        //查找元素不存在,-索引点-1,索引点是应该插入的位置,-1是因为找0返回的是-0,容易误解
        System.out.println(Arrays.binarySearch(arr,8));//-7
        int[] new1=Arrays.copyOf(arr,10);
        //底层System.arraycopy();
        System.out.println(Arrays.toString(new1));//[1, 2, 3, 4, 5, 6, 0, 0, 0, 0]
        System.out.println(new1);//[I@41629346
        //包头不包尾
        int[] new2=Arrays.copyOfRange(arr,0,4);
        System.out.println(Arrays.toString(new2));//[1, 2, 3, 4]
        //底层:循环赋值
        Arrays.fill(new2,100);
        System.out.println(Arrays.toString(new2));//[100, 100, 100, 100]
        Integer[] arri={1,2,3,4,5};
        //o1-o2 升序 o2-o1 降序
        //o2 有序序列的元素,o1 无序序列的元素
        //只能给引用类型数据排序
        Arrays.sort(arri, new Comparator<>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return 0;
            }
});

7 算法题

        Dog do1=new Dog("do1",18,180);
        Dog do2=new Dog("do2",18,181);
        Dog do3=new Dog("do3",9,176);
        Dog do4=new Dog("do4",1,121);
        Dog[] arr={do1,do2,do3,do4};
        Arrays.sort(arr, new Comparator<Dog>() {
//            o1,无序序列的元素,o2有序序列的元素
            //返回值为负,插入前面,>=0 插入后面
            @Override
            public int compare(Dog o1, Dog o2) {
                double d1=o1.getAge()-o2.getAge();
                d1=d1==0?o1.getHeight()- o2.getHeight():d1;
                d1=d1==0?o1.getName().compareTo(o2.getName()):d1;
                if(d1>0){return 1;}
                else if(d1<0){return -1;}
                else{   return 0;}

            }
        });
        System.out.println(Arrays.toString(arr));
//[Dog{name = do4, age = 1, height = 121}, Dog{name = do3, age = 9, height = 176}, Dog{name = do1, age = 18, height = 180}, Dog{name = do2, age = 18, height = 181}]