简单数据结构

1. 动态数组

1.1 动态数组是什么

固定数组:数组的长度是固定的

动态数组:比如ArrayList

1.2 动态数组的使用与扩容

其底层是基于复制的实现的动态扩容，当数组长度不够的时候，会先生成一个两倍长度的数组，如果发现两倍还是不够，就会直接计算所需要的长度，然后将原数组的内容全部复制过去

1.3 时间复杂度分析

扩容代价:在扩容过程中由于存在着数组元素复制的问题，而复制是一个常数操作，一般来说，扩容的序列是1 2 4 8 16 .. N(接近)，这个等比数列进行求和，就是动态数组扩容的代价，但是是在时间复杂度的分析上看，假设我们每一次操作都进行扩容，最坏情况下有N次扩容(其实远远不到)，那么这N次的扩容代价均摊到N次上，其实还是O(1)的时间复杂度操作，也就是说，这种行为存在虽然会拖慢程序的速度，但是不会影响时间复杂度

2. 哈希表和有序表的用法

2.1 哈希表

虽然哈希表的查询时间是常数时间，但是这种常数时间比数组寻址之类的操作要远远大得多

• (对于原生类型):哈希表的内部查询是依照值传递的原则进行的，也就是说不管key的内存地址是否一致，只要其内容是一致的，那么就认为这是同一个key，一个例子是(Integer 、String等)
• (对于非原生类型,例如自己定义的对象类类型):非原生类型是按照引用传递的原则进行的，也就是比较的是内存地址
• 关于内存占用数:如果是原生类型的话(也就是按值传递的那些类型)，那么在哈希表中的占用就是所有原生类型对象的所占字节数，如果是按引用传递的话，就只是记录引用地址

2.2 有序表

TreeMap<Integer,String>...

• 用法与哈希表类似，但是功能比较强大，其内部的元素是有序的，其默认的排序是按照key的值大小进行排序
• 如果是非原生类型的话，那么就需要定义一个新的排序规则来确定树的结构，否则的话树无法进行比较

floorKey(5):把离5最近的key返回(<=5)

ceilingkey(5):把离5最近的key给返回(>=5)

3. 链表

3.1 单链表结构实现队列

package leetcode_2;

public class MyQueue <V>{

    class ListNode <V>{
        V val;
        ListNode next;
        ListNode() {}
        ListNode(V val) { this.val = val; }
        ListNode(V val, ListNode next) { this.val = val; this.next = next; }
    }

    private ListNode<V> head;
    private ListNode<V> tail;
    private int size;

    public MyQueue() {
        head = tail = null;
        size = 0;
    }

    public void offer(V val){
        //如果是队列是空的
        if(head == null && tail == null){
            head = tail = new ListNode<V>(val);
        }else{
            //如果队列非空,那么就在队列尾部添加元素
            tail.next = new ListNode<>(val);
            tail = tail.next;
        }
        this.size++;
    }

    public V poll(){
        V val = null;
        if(head == null && tail == null){
            return null;
        }else{
            //从头部删除元素
            ListNode next = head.next;
            val= head.val;
            head = next;
        }
        this.size--;
        return val;
    }

    public V peek(){
        V ans = null;
        if(head != null){
            ans = head.val;
        }
        return ans;
    }


}

3.2 单链表结构实现栈

package leetcode_2;

public class MyStack <V>{
    class ListNode <V>{
        V val;
        ListNode next;
        ListNode() {}
        ListNode(V val) { this.val = val; }
        ListNode(V val, ListNode next) { this.val = val; this.next = next; }
    }

    private ListNode<V> head;
    private int size;

    public MyStack() {
        head = null;
        size = 0;
    }

    public void offer(V val){
        if(head == null){
            head = new ListNode<>(val);
            this.size++;
            return;
        }else{
            ListNode<V> cur = new ListNode<>(val);
            cur.next = head;
            head = cur;
            this.size++;
        }

    }

    public V poll(){
        V val = null;
        if(head == null){
            return null;
        }else{
            this.size--;
            ListNode<V> pre = head.next;
            val = pre.val;
            head = pre;
        }
        return val;
    }

    public V peek(){
        V ans = null;
        if(head != null){
            ans = head.val;
        }
        return ans;
    }
}

3.3 双链表结构实现双端队列

package leetcode_2;

public class MyDequeue<V> {

    class ListNode <V>{
        V val;
        ListNode next;
        ListNode pre;
        ListNode() {}
        ListNode(V val) { this.val = val; }
        ListNode(V val, ListNode next) { this.val = val; this.next = next; }
    }

    public MyDequeue() {
        head = null;
        tail = null;
        size = 0;
    }
    private ListNode<V> head;
    private ListNode<V> tail;
    private int size;

    public void offerFirst(V val){
        ListNode<V> cur = new ListNode<>(val);
        if(head == null){
            head = cur;
            tail = cur;
        }else{
            cur.next = head;
            head.pre = cur;
            //cur.pre = null
            head = cur;
        }
        this.size++;
    }

    public void offerLast(V val){
        ListNode<V> cur = new ListNode<>(val);
        if(head == null){
            return;
        }else{
            cur.pre = tail;
            tail.next = cur;
            tail = cur;
        }
        this.size--;
    }

    public V getFirst(){
        return head.val;
    }

    public V getLast(){
        return tail.val;
    }

}

3.4 K个节点的组内逆序调整

给定一个单链表的头结点head，和一个正数k，请你实现k个节点的小组内部逆序，如果最后一组不够k个就不调整

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode start  = head;
    ListNode end = getKEnd(start, k);
    if(end == null){//不够k个一组
        return start;//返回老头部
    }
    //第一组凑齐了,如果我们现在的链表是a->b->c,我们最终返回的链表头部一定是反转之后的头部
    head = end;
    reverse(start,end);
    //我们知道a(start)->b->c(end)是初始状态,进入reverse之后end会移动到下一个位置
    //然后反转之后,变成:c->b->a(start),然后咱们的下一段链表的上一个节点就是a,start已经默认连到下一个节点了
    ListNode lastEnd = start;
    while (lastEnd.next!=null){
        start = lastEnd.next;
        end = getKEnd(start,k);
        if(end == null){
            return head;
        }
        reverse(start,end);
        lastEnd.next = end;
        lastEnd = end;
    }
    return head;
}

public void reverse(ListNode start,ListNode end){
    //翻转的方法,从start开始,一直走到end,将路径上的所有节点进行翻转
    //翻转的步骤
    end = end.next;//结束节点
    ListNode pre = null;
    ListNode next = null;
    ListNode cur = start;
    while (cur != end){
        next = cur.next;    //第一步,先记录当前节点的下一个节点
        cur.next = pre;     //修改指针,让指针指向上一个节点
        pre = cur;          //第二步,让上一个节点等于当前节点
        cur = next;         //第三步,搜索指针步进
    }
    //完成了组内的逆序之后,得到一个新的节点,这个节点是逆序之后的最后一个节点
    //比如说原来是1 2 3
    //那么逆序之后就会返回3(head) 2 1
    //这里确保pre不会是空
    start.next = end;
}

public ListNode getKEnd(ListNode start,int k){
    while (--k !=0 && start!= null){start = start.next;}
    return start;
}