前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识;

前序文章:

什么是优先队列?

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优先队列ADT来完成操作,优先队列ADT是一种数据结构,它支持插入和删除最小值操作(返回并删除最小元素)或删除最大值操作(返回并删除最大元素);

这些操作等价于队列的enQueuedeQueue操作,区别在于,对于优先队列,元素进入队列的顺序可能与其被操作的顺序不同,作业调度是优先队列的一个应用实例,它根据优先级的高低而不是先到先服务的方式来进行调度;

如果最小键值元素拥有最高的优先级,那么这种优先队列叫作升序优先队列(即总是先删除最小的元素),类似的,如果最大键值元素拥有最高的优先级,那么这种优先队列叫作降序优先队列(即总是先删除最大的元素);由于这两种类型时对称的,所以只需要关注其中一种,如升序优先队列;

优先队列ADT

下面操作组成了优先队列的一个ADT;

1.优先队列的主要操作
优先队列是元素的容器,每个元素有一个相关的键值;

  • insert(key, data):插入键值为key的数据到优先队列中,元素以其key进行排序;
  • deleteMin/deleteMax:删除并返回最小/最大键值的元素;
  • getMinimum/getMaximum:返回最小/最大剑指的元素,但不删除它;

2.优先队列的辅助操作

  • 第k最小/第k最大:返回优先队列中键值为第k个最小/最大的元素;
  • 大小(size):返回优先队列中的元素个数;
  • 堆排序(Heap Sort):基于键值的优先级将优先队列中的元素进行排序;

优先队列的应用

  • 数据压缩:赫夫曼编码算法;
  • 最短路径算法:Dijkstra算法;
  • 最小生成树算法:Prim算法;
  • 事件驱动仿真:顾客排队算法;
  • 选择问题:查找第k个最小元素;
  • 等等等等….

优先队列的实现比较

实现 插入 删除 寻找最小值
无序数组 1 n n
无序链表 1 n n
有序数组 n 1 1
有序链表 n 1 1
二叉搜索树 logn(平均) logn(平均) logn(平均)
平衡二叉搜索树 logn logn logn
二叉堆 logn logn 1

堆和二叉堆

什么是堆

堆是一颗具有特定性质的二叉树,堆的基本要求就是堆中所有结点的值必须大于或等于(或小于或等于)其孩子结点的值,这也称为堆的性质;堆还有另一个性质,就是当 h > 0 时,所有叶子结点都处于第 h 或 h - 1 层(其中 h 为树的高度,完全二叉树),也就是说,堆应该是一颗完全二叉树;

在下面的例子中,左边的树为堆(每个元素都大于其孩子结点的值),而右边的树不是堆(因为5大于其孩子结点2)

二叉堆

在二叉堆中,每个结点最多有两个孩子结点,在实际应用中,二叉堆已经足够满足需求,因此接下来主要讨论二叉最小堆和二叉最大堆;

堆的表示:在描述堆的操作前,首先来看堆是怎样表示的,一种可能的方法就是使用数组,因为堆在形式上是一颗完全二叉树,用数组来存储它不会浪费任何空间,例如下图:

用数组来表示堆不仅不会浪费空间还具有一定的优势:

  • 每个结点的左孩子为下标i的2倍:left child(i) = i * 2;每个结点的右孩子为下标i的2倍加1:right child(i) = i * 2 + 1
  • 每个结点的父亲结点为下标的二分之一:parent(i) = i / 2,注意这里是整数除,2和3除以2都为1,大家可以验证一下;
  • 注意:这里是把下标为0的地方空出来了的,主要是为了方便理解,如果0不空出来只需要在计算的时候把i值往右偏移一个位置就行了(也就是加1,大家可以试试,下面的演示也采取这样的方式);

二叉堆的相关操作

堆的基本结构

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity){ data = new Array<>(capacity); }
    public MaxHeap(){ data = new Array<>(); }
    // 返回堆中的元素个数
    public int size(){ return data.getSize(); }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){ return data.isEmpty(); }
    // 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }
    // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){ return index * 2 + 1; }
    // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){ return index * 2 + 2; }
}

向堆中添加元素和Sift Up

当插入一个元素到堆中时,它可能不满足堆的性质,在这种情况下,需要调整堆中元素的位置使之重新变成堆,这个过程称为堆化(heapifying);在最大堆中,要堆化一个元素,需要找到它的父亲结点,如果不满足堆的基本性质则交换两个元素的位置,重复该过程直到每个结点都满足堆的性质为止,下面我们来模拟一下这个过程:

下面我们在该堆中插入一个新的元素26:

我们通过索引(上面的公式)可以很容易地找到新插入元素的父亲结点,然后比较它们的大小,如果新元素更大则交换两个元素的位置,这个操作就相当于把该元素上浮了一下:

重复该操作直到26到了一个满足堆条件的位置,此时就完成了插入的操作:

对应的代码如下:

// 向堆中添加元素
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k){

    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
        data.swap(k, parent(k));
        k = parent(k);
    }
}

取出堆中的最大元素和Sift Down

如果理解了上述的过程,那么取出堆中的最大元素(堆顶元素)将变得容易,不过这里运用到一个小技巧,就是用最后一个元素替换掉栈顶元素,然后把最后一个元素删除掉,这样一来元素的总个数也满足条件,然后只需要把栈顶元素依次往下调整就好了,这个操作就叫做Sift Down(下沉):

用最后元素替换掉栈顶元素,然后删除最后一个元素:

然后比较其孩子结点的大小:

如果不满足堆的条件,那么就跟孩子结点中较大的一个交换位置:

重复该步骤,直到16到达合适的位置:

完成取出最大元素的操作:

对应的代码如下:

// 看堆中的最大元素
public E findMax(){
    if(data.getSize() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty.");
    return data.get(0);
}

// 取出堆中最大元素
public E extractMax(){

    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

private void siftDown(int k){

    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
        if( j + 1 < data.getSize() &&
                data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;
        // data[j] 是 leftChild 和 rightChild 中的最大值

        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break;

        data.swap(k, j);
        k = j;
    }
}

Replace 和 Heapify

Replace这个操作其实就是取出堆中最大的元素之后再新插入一个元素,常规的做法是取出最大元素之后,再利用上面的插入新元素的操作对堆进行Sift Up操作,但是这里有一个小技巧就是直接使用新元素替换掉堆顶元素,之后再进行Sift Down操作,这样就把两次O(logn)的操作变成了一次O(logn):

// 取出堆中的最大元素,并且替换成元素e
public E replace(E e){

    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

Heapify翻译过来就是堆化的意思,就是将任意数组整理成堆的形状,通常的做法是遍历数组从0开始添加创建一个新的堆,但是这里存在一个小技巧就是把当前数组就看做是一个完全二叉树,然后从最后一个非叶子结点开始进行Sift Down操作就可以了,最后一个非叶子结点也很好找,就是最后一个结点的父亲结点,大家可以验证一下:

从22这个节点开始,依次开始Sift Down操作:

重复该过程直到堆顶元素:

完成堆化操作:

将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn),而heapify的过程,算法复杂度为O(n),这是有一个质的飞跃的,下面是代码:

public MaxHeap(E[] arr){
    data = new Array<>(arr);
    for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
        siftDown(i);
}

基于堆的优先队列

首先我们的队列仍然需要继承我们之前将队列时候声明的哪个接口Queue,然后实现这个接口中的方法就可以了,之类简单写一下:

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(){ maxHeap = new MaxHeap<>(); }
    @Override
    public int getSize(){ return maxHeap.size(); }
    @Override
    public boolean isEmpty(){ return maxHeap.isEmpty(); }
    @Override
    public E getFront(){ return maxHeap.findMax(); }
    @Override
    public void enqueue(E e){ maxHeap.add(e); }
    @Override
    public E dequeue(){ return maxHeap.extractMax(); }
}

Java中的PriorityQueue

在Java中也实现了自己的优先队列java.util.PriorityQueue,与我们自己写的不同之处在于,Java中内置的为最小堆,然后就是一些函数名不一样,底层还是维护了一个Object类型的数组,大家可以戳戳看有什么不同,另外如果想要把最小堆变成最大堆可以给PriorityQueue传入自己的比较器,例如:

// 默认为最小堆
PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(5);
pq.add(2);
pq.add(1);
pq.add(10);
pq.add(3);

while (!pq.isEmpty()) {
    System.out.println(pq.poll() + ", ");
}
System.out.println();
System.out.println("————————————————————————");

// 使用Lambda表达式传入自己的比较器转换成最大堆
PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> b - a);
pq2.add(5);
pq2.add(2);
pq2.add(1);
pq2.add(10);
pq2.add(3);

while (!pq2.isEmpty()) {
    System.out.println(pq2.poll() + ", ");
}

LeetCode相关题目整理

23. 合并K个排序链表

参考答案:(85ms)

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null) {
            q.add(lists[i]);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (!q.isEmpty()) {
        tail.next = q.poll();
        tail = tail.next;
        if (tail.next != null) {
            q.add(tail.next);
        }
    }

    return dummy.next;
}

215. 数组中的第K个最大元素

我的答案:(75ms)

public int findKthLargest(int[] nums, int k) {

    // 正确性判断
    if (0 == nums.length || null == nums || k <= 0 || k > nums.length) {
        return -1;
    }

    // 构造优先队列,默认为最小堆,传入自定义的比较器转换成最大堆
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    for (Integer num : nums) {
        pq.add(num);
    }
    for (int i = 0; i < k - 1; i++) {
        pq.remove();
    }
    return pq.peek();
}

参考答案:(5ms)

public int findKthLargest(int[] nums, int k) {
    if (nums.length == 1) {
        return nums[0];
    }

    int max = nums[0];
    int min = nums[0];

    for (int i : nums) {
        max = i > max ? i : max;
        min = i < min ? i : min;
    }

    int[] arrs = new int[max - min + 1];

    for (int i : nums) {
        arrs[max - i]++;
    }

    int pos = 0;
    for (int i = 0; i < arrs.length; i++) {
        pos += arrs[i];
        if (pos >= k) {
            return max - i;
        }
    }

    return nums[0];
}

还看到一个简单粗暴的,也是服了:(4ms)

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

而且我随机生成了一个100万数据的随机数组,来测试这个简单粗暴的方法的效率,发现当数据量上去之后,排序这个操作变得繁琐,我自己测试的时候,上面三个方法,第三个大概比第一个(我自己写的方法)多花仅4倍的时间;

239. 滑动窗口最大值(类似剑指Offer面试题59)

参考答案:(88ms)

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) return new int[0];
    int[] res = new int[nums.length - k + 1];
    ArrayDeque<Integer> deque = new ArrayDeque<Integer>();

    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peek() < i - k + 1) // Ensure deque's size doesn't exceed k
            deque.poll();

        // Remove numbers smaller than a[i] from right(a[i-1]) to left, to make the first number in the deque the largest one in the window         
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.pollLast();

        deque.offer(i);// Offer the current index to the deque's tail

        if (i >= k - 1)// Starts recording when i is big enough to make the window has k elements 
            res[index++] = nums[deque.peek()];
    }
    return res;
}

参考答案2:(9ms)

public int[] maxSlidingWindow(int[] nums, int k) {
/*
思想:依次遍历数组,有效范围在长度k内寻找当前最大值,在用result数组来依次存储当前长度K内的最大值;
     若在当前轮中出现新增的nums[end]大于curMax,直接替换即可;
     如果当前轮curMax不是新增的nums[end],在新的范围内重置curMax.
*/
    if (nums.length == 0 || k <= 0)
        return new int[0];
    int curMax = Integer.MIN_VALUE;
    for (int i = 0; i < k; i++) {
        if (nums[i] > curMax)
            curMax = nums[i];
    }
    int[] ans = new int[nums.length - k + 1];
    ans[0] = curMax;

    for (int start = 1; start + k - 1 < nums.length; start++) {
        int end = start + k - 1;
        if (nums[end] > curMax)
            curMax = nums[end];
        else if (nums[start - 1] == curMax) {//新增的不大于curMax,新范围内重置
            curMax = Integer.MIN_VALUE;
            for (int i = start; i <= end; i++) {
                if (nums[i] > curMax)
                    curMax = nums[i];
            }
        }
        ans[start] = curMax;
    }
    return ans;
}

264. 丑数 II(剑指Offer面试题49)

参考答案:(7ms)

public int nthUglyNumber(int n) {
    // 正确性判断
    if (n < 1 || n > 1690) {
        return -1;
    }
    int[] ugly = new int[n];
    ugly[0] = 1;
    int index2 = 0, index3 = 0, index5 = 0;
    int factor2 = 2, factor3 = 3, factor5 = 5;
    for (int i = 1; i < n; i++) {
        int min = Math.min(Math.min(factor2, factor3), factor5);
        ugly[i] = min;
        if (factor2 == min)
            factor2 = 2 * ugly[++index2];
        if (factor3 == min)
            factor3 = 3 * ugly[++index3];
        if (factor5 == min)
            factor5 = 5 * ugly[++index5];
    }
    return ugly[n - 1];
}

如果采用逐个判断每个整数是不是丑数的解法,直观但不够高效,所以我们就需要换一种思路,我的第一反应就是这其中一定有什么规律,但是尝试着找了一下,没找到…看了看答案才幡然醒悟,前面提到的算法之所以效率低,很大程度上是因为不管一个数是不是丑数,我们都要对它进行计算,接下来我们试着找到一种只计算丑数的方法,而不在非丑数的整数上花费时间,根据丑数的定义,丑数应该是另一个丑数乘以2、3或者5的结果(1除外),因此,我们可以创建一个数组,里面的数字是排好序的丑数,每个丑数都是前面的丑数乘以2、3或者5得到的,也就是上面的算法了..

295.数据流的中位数(剑指Offer面试题41)

参考答案:(219ms)

public class MedianFinder {

    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if (minHeap.size() - maxHeap.size() > 0) {
            maxHeap.add(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

思路:这道题的实现思路有很多,比如我们可以在插入的时候就将每个元素插入到正确的位置上,这样返回中位数的时候就会是一个O(1)的操作,下面列举一张表来说明不同实现的复杂度具体是多少:
数据结构 | 插入的时间复杂度 | 得到中位数的时间复杂度
:– | :– | :–
没有排序的数组 | O(1) | O(n)
排序的数组 | O(n) | O(1)
排序的链表 | O(n) | O(1)
二叉搜索树 | 平均O(logn),最差O(n) | 平均O(logn),最差O(n)
AVL树 | O(logn) | O(logn)
最大堆和最小堆 | O(logn) | O(logn)

AVL树是一种很高效的数据结构,但是在大多数的语言中都没有现成的实现,所以考虑用最大堆和最小堆,对于一个已经排好序的数据容器,我们可以从中间分开分成两个部分,其中拿P1指向左半部分最大的元素,拿P2指向有半部分最小的元素,如果能够保证数据容器左边的数据都小于右边的数据,那么即使左、右两边内部的数据没有排序,我们仍然可以根据左边最大的数和右边最大的数得到中位数:

如何快速从一个数据容器中找出最大数呢?我们可以使用最大堆来实现这个数据容器,因为堆顶的元素就是最大的元素;同样我们可以使用最小堆来快速找出一个数据容器中最小数。因此按照这个思路我们就可以使用一个最大堆实现左边的数据容器,使用一个最小堆实现右边的数据容器,但是需要注意的是这两个容器的大小差值不能超过1;

347. 前K个高频元素(类似剑指Offer面试题40)

参考答案:(131ms)

public List<Integer> topKFrequent(int[] nums, int k) {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    // 保存频率
    for (int num : nums) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }

    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));
    for (int key : map.keySet()) {
        if (pq.size() < k) {
            pq.add(key);
        } else if (map.get(key) > map.get(pq.peek())) {
            pq.remove();
            pq.add(key);
        }
    }

    LinkedList<Integer> res = new LinkedList<>();
    while (!pq.isEmpty()) {
        res.add(pq.remove());
    }
    return res;
}

692. 前K个高频单词

参考答案:(72ms)

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    List<String> candidates = new ArrayList(count.keySet());
    Collections.sort(candidates, (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w1.compareTo(w2) : count.get(w2) - count.get(w1));

    return candidates.subList(0, k);
}

这道题类似于上面的第347题,但是问题出在返回的顺序上,需要自己来定义一个比较器来排序..然后也学到一个写法,就是上面的第一个for循环里,getOrDefault()方法,get√..

参考答案2:(91ms)

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    PriorityQueue<String> heap = new PriorityQueue<String>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
                    w2.compareTo(w1) : count.get(w1) - count.get(w2) );

    for (String word: count.keySet()) {
        heap.offer(word);
        if (heap.size() > k) heap.poll();
    }

    List<String> ans = new ArrayList();
    while (!heap.isEmpty()) ans.add(heap.poll());
    Collections.reverse(ans);
    return ans;
}

这个解法就有点儿类似于上面的347题,其实是大同小异,就是自己不会灵活使用比较器而已,学习到了学习到了√…


简单总结

今天算是很有收获的一天,因为这两种数据结构都是自己特别不熟悉的,特别是在刷了一些LeetCode相关题目之后,对这两种数据有了很不一样的认识,特别是堆的应用,这是一种特别适合用来找第k小/大的特殊的数据结构,并且在Java中居然有直接的实现,这可太棒了,而且今天的效率还算挺高的,满足;

欢迎转载,转载请注明出处!
简书ID:@我没有三颗心脏
github:wmyskxz
欢迎关注公众微信号:wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料

前言:题图无关,现在开始来学习学习树相关的知识

前序文章:

什么是树

树是一种类似于链表的数据结构,不过链表的结点是以线性方式简单地指向其后继结点,而树的一个结点可以指向许多个结点;数是一种典型的非线性结构;树结构是以表达具有层次特性的图结构的一种方法;

相关术语

  • 根节点:根节点是一个没有双亲结点的结点,一棵树中最多有一个根节点(如上图的结点A就是根节点);
  • 边:边表示从双亲结点到孩子结点的链接(如上图中所有的链接);
  • 叶子结点:没有孩子结点的结点叫作叶子结点(如E、J、K、H和I);
  • 兄弟结点:拥有相同双亲结点的所有孩子结点叫作兄弟结点(B、C、D是A的兄弟结点,E、F是B的兄弟结点);
  • 祖先结点:如果存在一条从根节点到结点q的路径,其结点p出现在这条路径上,那么就可以吧结点p叫作结点q的祖先结点,结点q也叫做p的子孙结点(例如,A、C和G是K的祖先结点);
  • 结点的大小:结点的大小是指子孙的个数,包括其自身。(子树C的大小为3);
  • 树的层:位于相同深度的所有结点的集合叫作树的层(B、C和D具有相同的层,上图的结构有0/1/2/3四个层);
  • 结点的深度:是指从根节点到该节点的路径长度(G点的深度为2,A—C—G);
  • 结点的高度:是指从该节点到最深节点的路径长度,树的高度是指从根节点到书中最深结点的路径长度,只含有根节点的树的高度为0。(B的高度为2,B—F—J);
  • 树的高度:是树中所有结点高度的最大值,树的深度是树中所有结点深度的最大值,对于同一棵树,其深度和高度是相同的,但是对于各个结点,其深度和高度不一定相同;

二叉树

如果一棵树中的每个结点有0,1或者2个孩子结点,那么这棵树就称为二叉树;空树也是一颗有效的二叉树,一颗二叉树可以看做是由根节点和两棵不相交的子树(分别称为左子树和右子树)组成,如下图所示。

二叉树的类型

严格二叉树:二叉树中的每个节点要么有两个孩子结点,要么没有孩子结点

满二叉树:二叉树中的每个结点恰好有两个孩子结点且所有叶子结点都在同一层

完全二叉树:在定义完全二叉树之前,假定二叉树的高度为h;对于完全二叉树,如果将所有结点从根节点开始从左至右,从上至下,依次编号(假定根节点的编号为1),那么僵得到从1~n(n为结点总数)的完整序列,在遍历过程中对于空指针也赋予编号,如果所有伽椰子结点的深度为h或h-1,且在结点编号序列中没有漏掉任何数字,那么这样的二叉树叫作完全二叉树。

二叉树的应用

  • 编译器中的表达式树;
  • 用于数据压缩算法中的赫夫曼编码树;
  • 支持在集合中查找、插入和删除,其平均时间复杂度为O(lognn)的二叉搜索树(BST);
  • 优先队列(PQ),它支持以对数时间(最坏情况下)对集合中的最小(或最大)数据元素进行搜索和删除;

二叉树的遍历

访问树中所有结点的过程叫作树的遍历,在遍历过程中,每个结点只能被处理一次,尽管其有可能被访问多次;根据结点处理顺序的不同,。可以定义不同的遍历方法,遍历分类可以根据当前节点被处理的顺序来划分:

前序遍历

在前序遍历中,每个结点都是在它的子树遍历之前进行处理,这是最容易理解的便利方法,然而,尽管每个结点在其子树之前进行了处理,但在向下移动的过程仍然需要保留一些信息,以上图为例,首先访问结点1,随后遍历其左子树,最后遍历其右子树,因此当左子树遍历完后,必须要返回到其右子树来继续遍历;为了能够在左子树遍历完成后移动到右子树,必须保留根节点的信息,能够实现该信息存储的抽象数据类型显而易见是栈,由于它是LIFO的结构,所以它可以以逆序来汇过去该信息并返回到右子树;

前序遍历可以如下定义:

  • 访问根节点;
  • 按前序遍历方式遍历左子树;
  • 按前序遍历方式遍历右子树;

利用前序遍历方法上图所示的树的输出序列为:1 2 4 5 3 6 7

void preOrder(BinaryTreeNode root) {
    if (null != root) {
        System.out.println(root.getData());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }
}

中序遍历

在中序遍历中,根节点的访问在两棵子树的遍历中间完成,中序遍历如下定义:

  • 按中序遍历方式遍历左子树;
  • 访问根节点;
  • 按中序遍历方式遍历右子树;

基于中序遍历,上图所示树的中序遍历输出顺序为:4 2 5 1 6 3 7

void inOrder(BinaryTreeNode root) {
    if (null != root) {
        inOrder(root.getLeft());
        System.out.println(root.getData());
        inOrder(root.getRight());
    }
}

后序遍历

在后续遍历中,根节点的访问是在其两棵子树都遍历完成后进行的,后续遍历如下定义:

  • 按后序遍历左子树;
  • 按后序遍历右子树;
  • 访问根节点;

对上图所示的二叉树,后续遍历产生的输出序列为:4 5 2 6 7 3 1

void postOrder(BinaryTreeNode root) {
    if (null != root) {
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.println(root.getData());
    }
}

层次遍历

层次遍历的定义如下:

  • 访问根节点;
  • 在访问第l层时,将l+1层的节点按顺序保存在队列中;
  • 进入下一层并访问该层的所有结点;
  • 重复上述操作直至所有层都访问完;

对于上图所示的二叉树,层次遍历产生的输出序列为:1 2 3 4 5 6 7

void levelOrder(BinaryTreeNode root) {
    BinaryTreeNode temp;
    LoopQueue Q = new LoopQueue();
    if (null == root) {
        return;
    }
    Q.enqueue(root);
    while (!Q.isEmpty()) {
        temp = Q.dequeue();
        // 处理当前节点
        System.out.println(temp.getData());
        if (temp.getLeft()) {
            Q.enqueue(temp.getLeft());
        }
        if (temp.getRight()) {
            Q.enqueue(temp.getRight());
        }
    }
    // 删除队列中的所有数据
    Q.deletequeue();
}

二叉搜索树

在二叉搜索树中,所有左子树结点的元素小于根节点的数据,所有右子树结点的元素大于根节点数据,注意,树中的每个结点都应满足这个性质;

实现自己的二叉搜索树

其中包含了常用的一些方法,包括几种遍历方法还有查询、删除等,仅供参考:

public class BST<E extends Comparable<E>> {

    private class Node{
        public E e;
        public Node left, right;

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    // 向二分搜索树中添加新的元素e
    public void add(E e){
        root = add(root, e);
    }

    // 向以node为根的二分搜索树中插入元素e,递归算法
    // 返回插入新节点后二分搜索树的根
    private Node add(Node node, E e){

        if(node == null){
            size ++;
            return new Node(e);
        }

        if(e.compareTo(node.e) < 0)
            node.left = add(node.left, e);
        else if(e.compareTo(node.e) > 0)
            node.right = add(node.right, e);

        return node;
    }

    // 看二分搜索树中是否包含元素e
    public boolean contains(E e){
        return contains(root, e);
    }

    // 看以node为根的二分搜索树中是否包含元素e, 递归算法
    private boolean contains(Node node, E e){

        if(node == null)
            return false;

        if(e.compareTo(node.e) == 0)
            return true;
        else if(e.compareTo(node.e) < 0)
            return contains(node.left, e);
        else // e.compareTo(node.e) > 0
            return contains(node.right, e);
    }

    // 二分搜索树的前序遍历
    public void preOrder(){
        preOrder(root);
    }

    // 前序遍历以node为根的二分搜索树, 递归算法
    private void preOrder(Node node){

        if(node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    // 二分搜索树的非递归前序遍历
    public void preOrderNR(){

        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);

            if(cur.right != null)
                stack.push(cur.right);
            if(cur.left != null)
                stack.push(cur.left);
        }
    }

    // 二分搜索树的中序遍历
    public void inOrder(){
        inOrder(root);
    }

    // 中序遍历以node为根的二分搜索树, 递归算法
    private void inOrder(Node node){

        if(node == null)
            return;

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    // 二分搜索树的后序遍历
    public void postOrder(){
        postOrder(root);
    }

    // 后序遍历以node为根的二分搜索树, 递归算法
    private void postOrder(Node node){

        if(node == null)
            return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    // 二分搜索树的层序遍历
    public void levelOrder(){

        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.e);

            if(cur.left != null)
                q.add(cur.left);
            if(cur.right != null)
                q.add(cur.right);
        }
    }

    // 寻找二分搜索树的最小元素
    public E minimum(){
        if(size == 0)
            throw new IllegalArgumentException("BST is empty!");

        return minimum(root).e;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node){
        if(node.left == null)
            return node;
        return minimum(node.left);
    }

    // 寻找二分搜索树的最大元素
    public E maximum(){
        if(size == 0)
            throw new IllegalArgumentException("BST is empty");

        return maximum(root).e;
    }

    // 返回以node为根的二分搜索树的最大值所在的节点
    private Node maximum(Node node){
        if(node.right == null)
            return node;

        return maximum(node.right);
    }

    // 从二分搜索树中删除最小值所在节点, 返回最小值
    public E removeMin(){
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    private Node removeMin(Node node){

        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    // 从二分搜索树中删除最大值所在节点
    public E removeMax(){
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    // 删除掉以node为根的二分搜索树中的最大节点
    // 返回删除节点后新的二分搜索树的根
    private Node removeMax(Node node){

        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size --;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

    // 从二分搜索树中删除元素为e的节点
    public void remove(E e){
        root = remove(root, e);
    }

    // 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
    // 返回删除节点后新的二分搜索树的根
    private Node remove(Node node, E e){

        if( node == null )
            return null;

        if( e.compareTo(node.e) < 0 ){
            node.left = remove(node.left , e);
            return node;
        }
        else if(e.compareTo(node.e) > 0 ){
            node.right = remove(node.right, e);
            return node;
        }
        else{   // e.compareTo(node.e) == 0

            // 待删除节点左子树为空的情况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    // 生成以node为根节点,深度为depth的描述二叉树的字符串
    private void generateBSTString(Node node, int depth, StringBuilder res){

        if(node == null){
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + node.e +"\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth){
        StringBuilder res = new StringBuilder();
        for(int i = 0 ; i < depth ; i ++)
            res.append("--");
        return res.toString();
    }
}

LeetCode相关题目整理

94.二叉树的中序遍历

我的答案:(1ms)

public List<Integer> inorderTraversal(TreeNode root) {
    List result = new ArrayList();
    if (null != root) {
        result.addAll(inorderTraversal(root.left));
        result.add(root.val);
        result.addAll(inorderTraversal(root.right));
    }
    return result;
}

参考答案:(0ms)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    traversal(root, list);
    return list;
}

public void traversal(TreeNode root,List<Integer> list) {
    if(root!=null){
        traversal(root.left, list);
        list.add(root.val);
        traversal(root.right, list);
    }
}

98. 验证二叉搜索树

我的答案:(53ms)

private static int INT_MIN = Integer.MIN_VALUE;
private static int INT_MAX = Integer.MAX_VALUE;

public boolean isValidBST(TreeNode root) {
    // 如果节点为空则满足二叉搜索树条件
    if (null == root) {
        return true;
    }
    // 如果左孩子结点大于了根节点则返回false
    if (null != root.left && findMax(root.left) > root.val) {
        return false;
    }
    // 如果右孩子结点小于了根节点则返回false
    if (null != root.right && findMin(root.right) < root.val) {
        return false;
    }
    // 递归判断左子树和右子树,若其中有一颗不是BST树,则返回false
    if (!isValidBST(root.left) || !isValidBST(root.right)) {
        return false;
    }
    // 通过所有判断则是一颗BST树
    return true;
}

/**
 * 找到一颗非空树中的最大值
 *
 * @param root
 * @return
 */
private int findMax(TreeNode root) {
    int maxVal = INT_MIN;
    int leftMaxVal = INT_MIN;
    int rightMaxVal = INT_MIN;
    if (null != root) {
        // 最大值默认等于当前节点值
        maxVal = root.val;
        leftMaxVal = findMax(root.left);
        rightMaxVal = findMax(root.right);
        // maxVal等于当前maxVal与leftMaxVal中较大的一个
        maxVal = maxVal > leftMaxVal ? maxVal : leftMaxVal;
        // maxVal等于当前maxVal与rightMaxVal中较大的一个
        maxVal = maxVal > rightMaxVal ? maxVal : rightMaxVal;
    }
    return maxVal;
}

/**
 * 找到一颗非空树的最小值
 *
 * @param root
 * @return
 */
private int findMin(TreeNode root) {
    int minVal = INT_MAX;
    int leftMinVal = INT_MAX;
    int rightMinVal = INT_MAX;
    if (null != root) {
        // 最小值默认为当前节点值
        minVal = root.val;
        leftMinVal = findMin(root.left);
        rightMinVal = findMin(root.right);
        // minVal等于当前minVal与leftMinVal中较小的一个
        minVal = minVal < leftMinVal ? minVal : leftMinVal;
        // minVal等于当前minVal与rightMinVal中较小的一个
        minVal = minVal < rightMinVal ? minVal : rightMinVal;
    }
    return minVal;
}

自己写的时候提交错了很多次..没有掌握到二分搜索树的精髓..

参考答案:(2ms)

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean valid(TreeNode root, long low, long high) {
    if (root == null) return true;
    if (root.val <= low || root.val >= high) return false;
    return valid(root.left, low, root.val) && valid(root.right, root.val, high);
}

这答案写得我服了..真服..

101. 对称二叉树(剑指Offer面试题28)

参考答案:(12ms)

public boolean isSymmetric(TreeNode root) {
    return isSymmetric(root, root);
}

public boolean isSymmetric(TreeNode root1, TreeNode root2) {
    if (null == root1 && null == root2) {
        return true;
    }
    if (null == root1 || null == root2) {
        return false;
    }
    if (root1.val != root2.val) {
        return false;
    }
    return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
}

自己做的思路是使用中序遍历来判断(转成数组之后是对称的),但是出了很多问题,就是需要考虑null值,中序遍历中并不能很好地把一棵树保存为一个完整二叉树的样子..所以看了下参考答案..写得服..

104. 二叉树的最大深度(剑指Offer面试题55)

我的答案:(3ms)

public int maxDepth(TreeNode root) {
    int leftHeight, rightHeight;
    if (null == root) {
        return 0;
    } else { // 计算每个子树的高度
        leftHeight = maxDepth(root.left);
        rightHeight = maxDepth(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
}

参考答案:(0ms)

public int maxDepth(TreeNode root) {
    if(root==null)
        return 0;
    return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
}

105. 从前序与中序遍历序列构造二叉树(剑指Offer面试题7)

参考答案:(2ms)

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || preorder.length == 0) {
        return null;
    }
    return buildTree(preorder, inorder, 0, 0, inorder.length - 1);
}

private TreeNode buildTree(int[] preorder, int[] inorder, int ps, int is, int ie) {
    int val = preorder[ps];
    TreeNode node = new TreeNode(val);
    int iRoot = ie;
    while (iRoot > is) {
        if (val == inorder[iRoot]) {
            break;
        }
        iRoot--;
    }

    if (iRoot > is) {
        node.left = buildTree(preorder, inorder, ps + 1, is, iRoot - 1);
    }

    if (iRoot < ie) {
        node.right = buildTree(preorder, inorder, ps + 1 + (iRoot - is), iRoot + 1, ie);
    }
    return node;
}

思路是这样的:在二叉树的前序遍历序列中,第一个数字总是树的根节点的值,但在中序遍历序列中,根节点的值保存在序列的中间,左子树的节点的值位于根节点的值的左边,而右子树则相反,然后既然找到了左右子树我们又可以使用同样的方法在前序和中序中分别构建左右子树,这样我们就能够使用递归的方法完成;(上面算法中的ps、is、ie分别表示前序的开始位置,中序的开始位置和中序的结束位置;)

113. 路径总和 II(剑指Offer面试题34)

参考答案:(3ms)

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<Integer> nodeList = new ArrayList<Integer>();
    List<List<Integer>> sumList = new ArrayList<List<Integer>>();

    if (root == null) {
        return sumList;
    }
    pathSum2(root, sum, sumList, nodeList);

    return sumList;
}

public void pathSum2(TreeNode root, int target,
                     List<List<Integer>> sumList, List<Integer> nodeList) {
    if (root.left == null && root.right == null) {
        nodeList.add(root.val);
        int sum = 0;
        for (Integer integer : nodeList) {
            sum += integer;
        }
        if (sum == target) {
            sumList.add(new ArrayList<Integer>(nodeList));
        }
        return;
    }
    nodeList.add(root.val);
    if (root.left != null) {
        pathSum2(root.left, target, sumList, nodeList);
        nodeList.remove(nodeList.size() - 1);
    }
    if (root.right != null) {
        pathSum2(root.right, target, sumList, nodeList);
        nodeList.remove(nodeList.size() - 1);
    }
}

230. 二叉搜索树中第K小的元素(类似剑指Offer面试题54)

我的答案:(23ms)

public int kthSmallest(TreeNode root, int k) {
    // 正确性判断
    if (null == root || k < 1) {
        return -1;
    }
    List<Integer> result = preOrder(root);
    // 从小到大排序
    Collections.sort(result);
    return result.get(k - 1);
}

/**
 * 遍历整棵树并返回一个List
 *
 * @param root
 * @return
 */
private List<Integer> preOrder(TreeNode root) {
    List result = new ArrayList();
    if (null != root) {
        result.add(root.val);
        result.addAll(preOrder(root.left));
        result.addAll(preOrder(root.right));
    }
    return result;
}

贼蠢,完全没有用到二叉搜索树的特性

参考答案:(1ms)

public int kthSmallest(TreeNode root, int k) {
    int count = countNodes(root.left);

    if (k <= count) {
        return kthSmallest(root.left, k);
    } else if (k > count + 1) {
        return kthSmallest(root.right, k - 1 - count);
    }
    return root.val;
}

public int countNodes(TreeNode n) {
    if (n == null) return 0;
    return 1 + countNodes(n.left) + countNodes(n.right);
}

449. 序列化二叉搜索树(类似剑指Offer面试题37)

参考答案:(12ms)

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuffer sb = new StringBuffer();
    preOrder(root,sb);
    return sb.toString();
}
private static void preOrder(TreeNode root, StringBuffer sb){
    if(root==null)
        return;
    sb.append(root.val).append('#');
    preOrder(root.left,sb);
    preOrder(root.right,sb);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if(data==null)
        return null;
    int val =0;
    TreeNode root = null;
    for(int i=0;i<data.length();i++){
        if(data.charAt(i)!='#'){
            val = val*10+(data.charAt(i)-'0');
        }else{
            root = insert(root,val);
            val=0;
        }
    }
    return root;
}
private static TreeNode insert(TreeNode root,int val){
    if(root==null)
        return new TreeNode(val);
    if(root.val<val)
        root.right = insert(root.right,val);
    else
        root.left = insert(root.left,val);
    return root;
}

572. 另一个树的子树(类似剑指Offer面试题26)

参考答案:(15ms)

public boolean isSubtree(TreeNode s, TreeNode t) {
    // Write your code here
    if (s == null) {
        return t == null;
    }

    if (s.val == t.val && isSametree(s, t)) {
        return true;
    }

    return isSubtree(s.left, t) | isSubtree(s.right, t);
}

private boolean isSametree(TreeNode s, TreeNode t) {
    if (s == null) {
        return t == null;
    }
    if (t == null) {
        return false;
    }

    if (s.val != t.val) {
        return false;
    }

    return isSametree(s.left, t.left) & isSametree(s.right, t.right);
}

我的第一个反应还是去把两棵树的前序遍历的数组弄出来然后判断是否为子集,但是树这样的天然递归结构这样写很自然…


简单总结

还是只是简单复习了一下树的相关知识吧,通过刷LeetCode题目还有参照着剑指Offer对二叉树、二叉搜索树仅仅这两种结构有了一个较深的认识,因为后续还会继续用到,所以这里简单复习一下也无所谓,不过看着题目倒是感觉这样的结构很容易考面试题啊,因为这些结构既重要考点又多…

欢迎转载,转载请注明出处!
简书ID:@我没有三颗心脏
github:wmyskxz
欢迎关注公众微信号:wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料

前言:题图无关,只是好看,接下来就来复习一下栈和队列的相关知识

前序文章:

什么是栈

栈是一种用于存储数据的简单数据结构(与链表类似)。数据入栈的次序是栈的关键。可以把一桶桶装的薯片看作是一个栈的例子,当薯片做好之后,它们会依次被添加到桶里,每一片都会是当前的最上面一片,而每次我们取的时候也是取的最上面的那一片,规定你不能破坏桶也不能把底部捅穿,所以第一个放入桶的薯片只能最后一个从桶里取出;

定义:栈(Stack)是一个有序线性表,只能在表的一端(称为栈顶,top)执行插入和删除操作。最后插入的元素将第一个被删除,所以栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out)线性表;

两个改变栈的操作都有专用名称。一个称为入栈(push),表示在栈中插入一个元素;另一个称为出栈(pop),表示从栈中删除一个元素。试图对一个空栈执行栈操作称为下溢(underflow);试图对一个满栈执行栈操作称为溢出(overflow)。通常,溢出和下溢均认为是异常;

栈的应用

  • 无处不在的Undo操作(撤销);
  • 程序调用的系统栈;
  • 括号/符号匹配;
  • 等等等等….

栈抽象数据类型

下面给出栈抽象数据类型中的操作,为了简单起见,假设数据类型为整型;

栈的主要操作

  • void push(int data):将data(数据)插入栈;
  • int pop():删除并返回最后一个插入栈的元素;

栈的辅助操作

  • int top():返回最后一个插入栈的元素,但不删除;
  • int size():返回存储在栈中元素的个数;
  • int isEmpty():判断栈中是否有元素;
  • int isStackFull():判断栈中是否存满元素;

动态数组简单实现栈结构

我们结合之前创建的Array类,我们能够很好的创建属于我们自己的动态数组实现的栈结构,对于用户来说,我们只需要完成我们的相关操作,并且知道我能够不断地往里添加元素而不出错就行了,所以我们先来定义一个通用的栈接口:

public interface Stack<E> {
    int getSize();
    boolean isEmepty();
    void push(E e);
    E pop();
    E top();
}

然后我们往之前的动态数组中添加两个用户友好的方法:

public E getLast() {
    return get(size - 1);
}

public E getFirst() {
    return get(0);
}

然后实现自己的动态数组为底层的栈结构就轻松多了:

public class ArrayStack<E> implements Stack<E> {

    Array<E> array;

    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmepty() {
        return array.isEmpty();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E top() {
        return array.getLast();
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append("[");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }
}

简单复杂度分析

从代码中可以看出,几乎所有的时间复杂度都为O(1)级别,比较特别的是push()pop()操作可能涉及到底层数组的扩容或缩容的操作,所以是均摊下来的复杂度;


队列

什么是队列

队列是一种用于存储数据的数据结构(与链表和栈类似),数据到达的次序是队列的关键;在日常生活中队列是指从序列的开始按照顺序等待服务的一队人或物;

定义:队列是一种只能在一端插入(队尾),在另一端删除(队首)的有序线性表。队列中第一个插入的元素也是第一个被删除的元素,所以队列是一种先进先出(FIFO,First In First Out)或后进后出(LiLO,Last In Last Out)线性表;

与栈类似,两个改变队列的操作各有专用名称;在队列中插入一个元素,称为入队(EnQueue),从队列中删除一个元素,称为出队(DeQueue);试图对一个空队列执行出队操作称为下溢(underflow),试图对一个满队列执行入队操作称为溢出(overflow);通常认为溢出和下溢是异常。

队列的一些应用举例

  • 操作系统根据(具有相同优先级的)任务到达的顺序调度任务(例如打印队列);
  • 模拟现实世界中的队列,如售票柜台前的队伍,或者任何需要先来先服务的场景;
  • 多道程序设计;
  • 异步数据传输(文件输入输出、管道、套接字);
  • 等等等等…

动态数组简单实现队列结构

我们仍然定义一个Queue接口来说明我们队列中常用的一些方法:

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

借由我们之前自己实现的动态数组,那么我们的队列就很简单了:

public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void enqueue(E e){
        array.addLast(e);
    }

    @Override
    public E dequeue(){
        return array.removeFirst();
    }

    @Override
    public E getFront(){
        return array.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

简单的复杂度分析

  • void enquque(E):O(1)(均摊)
  • E dequeue()O(n)
  • E front():O(1)
  • int getSize():O(1)
  • boolean isEmpty():O(1)

实现自己的循环队列

循环队列的实现其实就是维护了一个front和一个tail分别指向头和尾,然后需要特别注意的呢是判定队满和队空的条件:

  • 队空:front == tail,这没啥好说的;
  • 队满:tail + 1 == front,这里其实是有意浪费了一个空间,不然就判定不了到底是队空还是队满了,因为条件都一样…
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public boolean isEmpty(){
        return front == tail;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public void enqueue(E e){

        if((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

    @Override
    public E dequeue(){

        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return ret;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[(i + front) % data.length];

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

简单复杂度分析

  • void enquque(E):O(1)(均摊)
  • E dequeue()O(1)(均摊)
  • E front():O(1)
  • int getSize():O(1)
  • boolean isEmpty():O(1)

简单数组队列和循环队列的简单比较

我们来简单对比一下两个队列的性能吧,这里直接上代码:

// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
private static double testQueue(Queue<Integer> q, int opCount){

    long startTime = System.nanoTime();

    Random random = new Random();
    for(int i = 0 ; i < opCount ; i ++)
        q.enqueue(random.nextInt(Integer.MAX_VALUE));
    for(int i = 0 ; i < opCount ; i ++)
        q.dequeue();

    long endTime = System.nanoTime();

    return (endTime - startTime) / 1000000000.0;
}

public static void main(String[] args) {

    int opCount = 100000;

    ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
    double time1 = testQueue(arrayQueue, opCount);
    System.out.println("ArrayQueue, time: " + time1 + " s");

    LoopQueue<Integer> loopQueue = new LoopQueue<>();
    double time2 = testQueue(loopQueue, opCount);
    System.out.println("LoopQueue, time: " + time2 + " s");
}

我这里的测试结果是这样的,大家也就可见一斑啦:

其实ArrayQueue慢主要是因为出栈时每次都需要把整个结构往前挪一下


LeetCode 相关题目整理

20.有效的括号

我的答案:(10ms)

public boolean isValid(String s) {

    // 正确性判断
    if (null == s || s.length() == 1) {
        return false;
    }

    Stack<Character> stack = new Stack<>();
    // 遍历输入的字符
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 如果为左括号则push进栈
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }

            char topChar = stack.pop();
            if (c == ')' && topChar != '(') {
                return false;
            }
            if (c == ']' && topChar != '[') {
                return false;
            }
            if (c == '}' && topChar != '{') {
                return false;
            }
        }
    }

    // 最后栈为空才能返回true
    return stack.isEmpty();
}

参考答案:(8ms)

public boolean isValid(String s) {

    // 正确性判断
    if (0 == s.length()) {
        return true;
    }
    if (s.length() % 2 == 1) {
        return false;
    }

    Stack<Character> stack = new Stack();
    char[] cs = s.toCharArray();
    for (int i = 0; i < cs.length; i++) {
        if (cs[i] == '(' || cs[i] == '[' || cs[i] == '{') {
            stack.push(cs[i]);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char c = stack.pop();
            if ((cs[i] == ')' && c == '(') || (cs[i] == '}' && c == '{') || (cs[i] == ']' && c == '[')) {
            } else {
                return false;
            }
        }
    }

    return stack.isEmpty();
}

155. 最小栈(剑指Offer面试题30)

参考答案(107ms)

class MinStack {

    // 数据栈,用于存放插入的数据
    private Stack<Integer> dataStack;
    // 最小数位置栈,存放数据栈中最小的数的位置
    private Stack<Integer> minStack;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        this.dataStack = new Stack<>();
        this.minStack = new Stack<>();
    }

    /**
     * 元素入栈
     *
     * @param x 入栈的元素
     */
    public void push(int x) {

        dataStack.push(x);

        // 如果最小栈是空的,只要将元素入栈
        if (minStack.isEmpty()) {
            minStack.push(x);
        }
        // 如果最小栈中有数据
        else {
            minStack.push(Math.min(x, minStack.peek()));
        }
    }

    /**
     * 出栈方法
     */
    public void pop() {
        // 如果栈已经为空,则返回(LeetCode不能抛异常...)
        if (dataStack.isEmpty()) {
            return;
        }

        // 如果有数据,最小数位置栈和数据栈必定是有相同的元素个数,
        // 两个栈同时出栈
        minStack.pop();
        dataStack.pop();
    }

    /**
     * 返回栈顶元素
     *
     * @return 栈顶元素
     */
    public int top() {
        return dataStack.peek();
    }

    /**
     * 获取栈中的最小元素
     *
     * @return 栈中的最小元素
     */
    public int getMin() {
        // 如果最小数公位置栈已经为空(数据栈中已经没有数据了),则抛出异常
        if (minStack.isEmpty()) {
            return 0;
        }

        // 获取数据占中的最小元素,并且返回结果
        return minStack.peek();
    }
}

改进答案:

上面求解方法的主要问题在于,每次push操作时,minStack也执行了一次push操作(新元素或当前的最小元素),也就是说,重复执行了最小值的入栈操作,所以现在我们来修改算法降低空间复杂度。仍然需要设置一个minStack,但是只有当从dataStack中出栈的元素等于minStack栈顶元素时,才对minStack执行出栈的操作;也只有当dataStack入栈的元素小于或等于当前最小值时,才对minStack执行入栈操作,下面就简单写一下了主要看一下出栈和入栈实现的逻辑就好了:

class MinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MinStack() {
        this.dataStack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int x) {
        dataStack.push(x);
        if (minStack.isEmpty() || minStack.peek() >= (Integer) x) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (dataStack.isEmpty()) {
            return;
        }
        Integer minTop = minStack.peek();
        Integer dataTop = dataStack.peek();
        if (minTop.intValue() == dataTop.intValue()) {
            minStack.pop();
        }
        dataStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

225. 用队列实现栈

我的答案:(118ms)

class MyStack {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        if (queue1.isEmpty()) {
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        int size;
        if (!queue1.isEmpty()) {
            size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        } else {
            size = queue2.size();
            for (int i = 0; i < size - 1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    /**
     * Get the top element.
     */
    public int top() {
        int size;
        if (!queue1.isEmpty()) {
            size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                queue2.offer(queue1.poll());
            }
            int result = queue1.peek();
            queue2.offer(queue1.poll());
            return result;
        } else {
            size = queue2.size();
            for (int i = 0; i < size - 1; i++) {
                queue1.offer(queue2.poll());
            }
            int result = queue2.peek();
            queue1.offer(queue2.poll());
            return result;
        }
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

参考答案:(121ms)

class MyStack {
    Queue<Integer> q;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        this.q = new LinkedList<Integer>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        q.add(x);
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        int size = q.size();
        for (int i = 0; i < size - 1; i++) {
            q.add(q.remove());
        }
        return q.remove();
    }

    /**
     * Get the top element.
     */
    public int top() {
        int size = q.size();
        for (int i = 0; i < size - 1; i++) {
            q.add(q.remove());
        }
        int ret = q.remove();
        q.add(ret);
        return ret;
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return q.isEmpty();
    }
}

确实写得简洁啊,这样一来我就使用一个队列和两个队列都掌握啦,开心~

232.用栈实现队列(剑指Offer面试题9)

参考答案:(72ms)

class MyQueue {
    Stack<Integer> pushstack;
    Stack<Integer> popstack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        this.pushstack = new Stack();
        this.popstack = new Stack();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        pushstack.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (popstack.isEmpty()) {
            while (!pushstack.isEmpty()) {
                popstack.push(pushstack.pop());
            }
        }
        return popstack.pop();
    }


    /**
     * Get the front element.
     */
    public int peek() {
        if (popstack.isEmpty()) {
            while (!pushstack.isEmpty()) {
                popstack.push(pushstack.pop());
            }
        }
        return popstack.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return pushstack.isEmpty() && popstack.isEmpty();
    }
}

其他题目整理

剑指Offer面试题31:栈的压入、弹出序列

题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列{1,2,3,4,5}是某栈的压栈序列,序列{4,5,3,2,1}是该压栈序列对应的一个弹出序列,但{4,3,5,1,2}就不可能是该压栈序列的弹出序列。

参考答案:(原文链接:https://blog.csdn.net/derrantcm/article/details/46691083)

public class Test22 {
    /**
     * 输入两个整数序列,第一个序列表示栈的压入顺序,请判断二个序列是否为该栈的弹出顺序。
     * 假设压入栈的所有数字均不相等。例如序列1 、2、3 、4、5 是某栈压栈序列,
     * 序列4、5、3、2、1是该压栈序列对应的一个弹出序列,
     * 但4、3、5、1、2就不可能是该压棋序列的弹出序列。
     * 【与书本的的方法不同】
     *
     * @param push 入栈序列
     * @param pop  出栈序列
     * @return true:出栈序列是入栈序列的一个弹出顺序
     */
    public static boolean isPopOrder(int[] push, int[] pop) {
        // 输入校验,参数不能为空,并且两个数组中必须有数字,并且两个数组中的数字个数相同
        // 否则返回false
        if (push == null || pop == null || pop.length == 0 || push.length == 0 || push.length != pop.length) {
            return false;
        }

        // 经过上面的参数校验,两个数组中一定有数据,且数据数目相等
        // 用于存放入栈时的数据
        Stack<Integer> stack = new Stack<>();
        // 用于记录入栈数组元素的处理位置
        int pushIndex = 0;
        // 用于记录出栈数组元素的处理位置
        int popIndex = 0;
        // 如果还有出栈元素要处理
        while (popIndex < pop.length) {
            // 入栈元素还未全部入栈的条件下,如果栈为空,或者栈顶的元素不与当前处理的相等,则一直进行栈操作,
            // 直到入栈元素全部入栈或者找到了一个与当出栈元素相等的元素
            while (pushIndex < push.length && (stack.isEmpty() || stack.peek() != pop[popIndex])) {
                // 入栈数组中的元素入栈
                stack.push(push[pushIndex]);
                // 指向下一个要处理的入栈元素
                pushIndex++;
            }

            // 如果在上一步的入栈过程中找到了与出栈的元素相等的元素
            if (stack.peek() == pop[popIndex]) {
                // 将元素出栈
                stack.pop();
                // 处理下一个出栈元素
                popIndex++;
            }
            // 如果没有找到与出栈元素相等的元素,说明这个出栈顺序是不合法的
            // 就返回false
            else {
                return false;
            }
        }

        // 下面的语句总是成立的
        // return stack.isEmpty();

        // 为什么可以直接返回true:对上面的外层while进行分析可知道,对每一个入栈的元素,
        // 在stack栈中,通过一些入栈操作,总可以在栈顶上找到与入栈元素值相同的元素,
        // 这就说明了这个出栈的顺序是入栈顺序的一个弹出队列,这也可以解释为什么stack.isEmpty()
        // 总是返回true,所有的入栈元素都可以进栈,并且可以被匹配到,之后就弹出,最后栈中就无元素。
        return true;
    }

    /**
     * 输入两个整数序列,第一个序列表示栈的压入顺序,请判断二个序列是否为该栈的弹出顺序。
     * 【按书本上的思路进行求解,两者相差不大】
     *
     * @param push 入栈序列
     * @param pop  出栈序列
     * @return true:出栈序列是入栈序列的一个弹出顺序
     */
    public static boolean isPopOrder2(int[] push, int[] pop) {

        // 用于记录判断出栈顺序是不是入栈顺的一个出栈序列,默认false
        boolean isPossible = false;

        // 当入栈和出栈数组者都不为空,并且都有数据,并且数据个数都相等
        if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
            // 用于存放入栈时的数据
            Stack<Integer> stack = new Stack<>();
            // 记录下一个要处理的入栈元素的位置
            int nextPush = 0;
            // 记录下一个要处理的出栈元素的位置
            int nextPop = 0;
            // 如果出栈元素没有处理完就继续进行处理
            while (nextPop < pop.length) {
                // 如果栈为空或者栈顶的元素与当前处理的出栈元素不相同,一直进行操作
                while (stack.isEmpty() || stack.peek() != pop[nextPop]) {
                    // 如果入栈的元素已经全部入栈了,就退出内层循环
                    if (nextPush >= push.length) {
                        break;
                    }

                    // 执行到此处说明还有入栈元素可以入栈
                    // 即将元素入栈
                    stack.push(push[nextPush]);
                    // 指向下一个要处理的入栈元素的位置
                    nextPush++;
                }

                // 执行到此处有两种情况:
                // 第一种:在栈顶上找到了一个与入栈元素相等的元素
                // 第二种:在栈顶上没有找到一个与入栈元素相等的元素,而且输入栈的元素已经全部入栈了

                // 对于第二种情况就说弹出栈的顺序是不符合要求的,退出外层循环
                if (stack.peek() != pop[nextPop]) {
                    break;
                }

                // 对应到第一种情况:需要要栈的栈顶元素弹出
                stack.pop();
                // 指向下一个要处理的出栈元素的位置
                nextPop++;
            }

            // 执行到此处有两种情况
            // 第一种:外层while循环的在第一种情况下退出,
            // 第二种:所有的出栈元素都被正确匹配

            // 对于出现的第一种情况其stack.isEmpty()必不为空,原因为分析如下:
            // 所有的入栈元素一定会入栈,但是只有匹配的情况下才会出栈,
            // 匹配的次数最多与入栈元素个数元素相同(两个数组的长度相等),如果有不匹配的元素,
            // 必然会使出栈的次数比入栈的次数少,这样栈中至少会有一个元素
            // 对于第二种情况其stack.isEmpty()一定为空
            // 所以书本上的nextPop == pop.length(pNextPop-pPop==nLength)是多余的
            if (stack.isEmpty()) {
                isPossible = true;
            }
        }

        return isPossible;
    }

    public static void main(String[] args) {
        int[] push = {1, 2, 3, 4, 5};
        int[] pop1 = {4, 5, 3, 2, 1};
        int[] pop2 = {3, 5, 4, 2, 1};
        int[] pop3 = {4, 3, 5, 1, 2};
        int[] pop4 = {3, 5, 4, 1, 2};

        System.out.println("true: " + isPopOrder(push, pop1));
        System.out.println("true: " + isPopOrder(push, pop2));
        System.out.println("false: " + isPopOrder(push, pop3));
        System.out.println("false: " + isPopOrder(push, pop4));

        int[] push5 = {1};
        int[] pop5 = {2};
        System.out.println("false: " + isPopOrder(push5, pop5));

        int[] push6 = {1};
        int[] pop6 = {1};
        System.out.println("true: " + isPopOrder(push6, pop6));

        System.out.println("false: " + isPopOrder(null, null));

        // 测试方法2
        System.out.println();
        System.out.println("true: " + isPopOrder2(push, pop1));
        System.out.println("true: " + isPopOrder2(push, pop2));
        System.out.println("false: " + isPopOrder2(push, pop3));
        System.out.println("false: " + isPopOrder2(push, pop4));
        System.out.println("false: " + isPopOrder2(push5, pop5));
        System.out.println("true: " + isPopOrder2(push6, pop6));
        System.out.println("false: " + isPopOrder2(null, null));
    }
}

简单总结

栈和队列的应用远不止上面学习到的那些,实现方式也有很多种,现在也只是暂时学到这里,通过刷LeetCode也加深了我对于这两种数据结构的认识,不过自己还需要去熟悉了解一下计算机系统关于栈的应用这方面的知识,因为栈这种结构本身就很适合用来保存CPU现场之类的工作,还是抓紧时间吧,过两天还考试,这两天就先复习啦…

欢迎转载,转载请注明出处!
简书ID:@我没有三颗心脏
github:wmyskxz
欢迎关注公众微信号:wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料

前言:终于到了疯狂学习数据结构的时候,换个好看的题图,开始吧..

数组

什么是数组?

数组简单来说就是将所有的数据排成一排存放在系统分配的一个内存块上,通过使用特定元素的索引作为数组的下标,可以在常数时间内访问数组元素的这么一个结构;

为什么能在常数时间内访问数组元素?

为了访问一个数组元素,该元素的内存地址需要计算其距离数组基地址的偏移量。需要用一个乘法计算偏移量,再加上基地址,就可以获得某个元素的内存地址。首先计算元素数据类型的存储大小,然后将它乘以元素在数组中的索引,最后加上基地址,就可以计算出该索引位置元素的地址了;整个过程可以看到需要一次乘法一次加法就完成了,而这两个运算的执行时间都是常数时间,所以可以认为数组访问操作能在常数时间内完成;

数组的优点

  • 简单且易用;
  • 访问元素快(常数时间);

数组的缺点

  • 大小固定:数组的大小是静态的(在使用前必须制定数组的大小);
  • 分配一个连续空间块:数组初始分配空间时,有时候无法分配能存储整个数组的内存空间(当数组规模太大时);
  • 基于位置的插入操作实现复杂:如果要在数组中的给定位置插入元素,那么可能就会需要移动存储在数组中的其他元素,这样才能腾出指定的位置来放插入的新元素;而如果在数组的开始位置插入元素,那么这样的移动操作开销就会很大。

关于数组的一些问题思考

1)在索引没有语义的情况下如何表示没有的元素?

我们创建的数组的索引可以有语义也可以没有语义,比如我现在只是单纯的想存放100,98,96这三个数字,那么它们保存在索引为0,1,2的这几个地方或者其他地方都可以,无论它们之间的顺序怎样我都不关心,因为它们的索引是没有语义的我只是想把它们存起来而已;但是如果它们变成了学号为1,2,3这几个同学对应的成绩,那么它们的索引就有了语义,索引0对应了学号为1的同学的成绩,索引1对应了学号2的同学,索引2对应了学号3的同学,因为数组的最大的优点是访问元素是在常数时间,所以我们使用数组最好就是在索引有语义的情况下;

好了,那么如果在索引没有语义的情况下,我们如何表示没有的元素呢?例如上图中,对于用户而言,访问索引为3和4的数组元素是违法的,因为它们根本就不存在,我们如何表示没有的元素呢?

表示为0或者-1?

2)如何添加元素和删除元素呢?

我们知道,数组的明显缺点是在创建之前需要提前声明好要使用的空间,那么当我们空间满了该如何处理呢?又该如何删除元素呢?在Java中提供给我们的默认数组是不支持这些功能的,我们需要开发属于自己的数组类才行;

使用泛型封装自己的数组类

我们需要自己创建一个Array类,并实现一些增删改查的功能,大体的结构如下:

public class Array<E>{
    private E[] data;
    private int size;
    /* 一些成员方法 */
}

我们需要一个成员变量来保存我们的数据,这里是data,然后需要一个int类型来存放我们的有效元素的个数,在这里我们没有必要再多定义一个表示数组空间的变量,因为这里的空间大小就是data.length

默认的构造函数

我们需要创建一些方法来初始化我们的数组,那肯定是需要传一个capacity来表示数组的容量嘛:

// 构造函数,传入数组的容量capacity构造Array
public Array(int capacity) {
    data = (E[]) new Object[capacity];
    size = 0;
}

当然我们也需要创建一个默认的构造函数来为不知道初始该定义多少的用户一个默认大小的数组:

// 无参数的构造函数,默认数组的容量capacity=10
public Array() {
    this(10);
}

这里演示的话给个10差不多了,实际可能会更复杂一些…

成员方法

就是增删改查嘛,不过这里需要注意的是,为了实现我们自己的动态数组,在增加和删除中,我们对临界值进行了判断,动态的增加或者缩小数组的大小,而且提供了一些常用友好的方法给用户;

// 获取数组的容量
public int getCapacity() {
    return data.length;
}

// 获取数组中的元素个数
public int getSize() {
    return size;
}

// 返回数组是否为空
public boolean isEmpty() {
    return size == 0;
}

// 在index索引的位置插入一个新元素e
public void add(int index, E e) {

    if (index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

    if (size == data.length)
        resize(2 * data.length);

    for (int i = size - 1; i >= index; i--)
        data[i + 1] = data[i];

    data[index] = e;

    size++;
}

// 向所有元素后添加一个新元素
public void addLast(E e) {
    add(size, e);
}

// 在所有元素前添加一个新元素
public void addFirst(E e) {
    add(0, e);
}

// 获取index索引位置的元素
public E get(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get failed. Index is illegal.");
    return data[index];
}

// 修改index索引位置的元素为e
public void set(int index, E e) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Set failed. Index is illegal.");
    data[index] = e;
}

// 查找数组中是否有元素e
public boolean contains(E e) {
    for (int i = 0; i < size; i++) {
        if (data[i].equals(e))
            return true;
    }
    return false;
}

// 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
public int find(E e) {
    for (int i = 0; i < size; i++) {
        if (data[i].equals(e))
            return i;
    }
    return -1;
}

// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    E ret = data[index];
    for (int i = index + 1; i < size; i++)
        data[i - 1] = data[i];
    size--;
    data[size] = null; // loitering objects != memory leak

    if (size == data.length / 4 && data.length / 2 != 0)
        resize(data.length / 2);
    return ret;
}

// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst() {
    return remove(0);
}

// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast() {
    return remove(size - 1);
}

// 从数组中删除元素e
public void removeElement(E e) {
    int index = find(e);
    if (index != -1)
        remove(index);
}

@Override
public String toString() {

    StringBuilder res = new StringBuilder();
    res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
    res.append('[');
    for (int i = 0; i < size; i++) {
        res.append(data[i]);
        if (i != size - 1)
            res.append(", ");
    }
    res.append(']');
    return res.toString();
}

// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity) {

    E[] newData = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++)
        newData[i] = data[i];
    data = newData;
}
  • 注意:为了更好的展示代码而不太浪费空间,所以这里使用//的风格来注释代码;
  • 特别注意:remove方法中,缩小数组的判断条件为size == data.length / 4 && data.length / 2 != 0,这是为了防止复杂度抖动和安全性;

简单时间复杂度分析

添加操作

在添加操作中,我们可以明显看到,addLast()方法是与n无关的,所以为O(1)复杂度;而addFirst()add()方法都涉及到挪动数组元素,所以都是O(n)复杂度,包括resize()方法;综合起来添加操作的复杂度就是O(n)

删除操作

在删除操作中,与添加操作同理,综合来看删除操作的复杂度就是O(n)

修改操作

在修改操作中,如果我们知道了需要修改元素的索引,那么我们就可以在常数时间内找到元素并进行修改操作,所以很容易的知道这个操作时一个复杂度为O(1)的操作,所以修改操作的复杂度就是O(1);但另外一种情况是我们不知道元素的索引,那么我们就需要先去查询这个元素,我把这归结到查询操作中去;

查询操作

在查询操作中,如果我们已知索引,那么复杂度为O(1);如果未知索引,我们需要遍历整个数组,那么复杂度为O(n)级别;

总结

以上我们简单分析了我们自己创建的数组类的复杂度:

  • 增加:O(n);
  • 删除:O(n);
  • 修改:已知索引 O(1);未知索引 O(n);
  • 查询:已知索引 O(1);未知索引 O(n);

均摊复杂度

如果细心的同学应该可以注意到,在增加和删除的复杂度分析中,如果我们都只是对最后一个元素进行相应的操作的话,那么对应的O(n)的复杂度显然是不合理的,我们之所以将他们的复杂度定义为O(n),就是因为在我们通常的复杂度分析中我们需要考虑最坏的情况,也就是对应的需要使用resize()方法扩容的情况,但是这样的情况并不是每一次都出现,所以我们需要更加合理的来分析我们的复杂度,这里提出的概念就是:均摊复杂度

假设我们现在的capacity5,并且每一次的添加操作都使用addLast()方法,那么我们在使用了五次addLast()方法之后就会触发一次resize()方法,在前五次的addLast()方法中我们总共进行了五次基本操作,也就是给数组的末尾添加上一个元素,在进行第六次addLast()方法的时候,触发resize()方法,就需要进行一次元素的转移,共5次操作(转移五个元素嘛),然后再在末尾加上一个元素,也就是总共进行了11次操作

也就是说:6次addLast()操作,触发resize()方法,总共进行了11次操作,平均下来,每次addLast()操作,进行了2次基本操作(约等于);那么依照上面的假设我们可以进一步推广为:假设capacitynn+1addLast()操作,触发resize()方法,总共进行了2n+1次基本操作,平均来讲,每次addLast()操作,进行了2次基本操作,这样也就意味着,均摊下来的addLast()方法的复杂度为O(1),而不是之前分析的O(n),这样的均摊复杂度显然比最坏复杂度来得更有意义,因为不是每一次的操作都是最坏的情况!

同理,我们看removeLast()对应的均摊复杂度也为O(1);

复杂度震荡

在我们的remove方法中,我们判断缩小容量的条件为size == data.length / 4 && data.length / 2 != 0,这样是为了防止复杂度震荡和安全性(因为缩小到一定的时候容量可能为1),这又是怎么一回事呢?我们考虑一下将条件改为size == data.length / 2的时候,出现的如下图这样的情况:

当我们数组已经满元素的情况下,使用一次addLast方法,因为触发resize,数组容量扩容为当前的两倍,所以此时复杂度为O(n);这时候我们立即使用removeLast,因为此时的容量等于n/2,所以会马上产生缩小容量的操作,此时复杂度为O(n);我们之前明明通过均摊复杂度分析出我们的两个操作都为O(1),而此时却产生了震荡,为了避免这样的操作,我们需要懒操作一下,也就是在remove的时候不要立即缩容,而是等到size == capacity / 4的时候再缩小一半,这样就有效的解决了复杂度震荡的问题;

Java中的ArrayList的扩容

上面我们已经实现了自己的数组类,我们也顺便看看Java中的ArrayList是怎么写的,其他的方法可以自己去看看,这里提出来一个grow()的方法,来看看ArrayList是怎么实现动态扩容的:

从上面的源码我们可以看到ArrayList默认增容是增加当前容量的0.5倍(>> 1即乘以0.5)


链表

什么是链表

链表是一种用于存储数据集合的数据结构,它是最简单的动态数据结构,我们在上面虽然实现了动态数组,但这仅仅是对于用户而言,其实底层还是维护的一个静态的数组,它之所以是动态的是因为我们在add和remove的时候进行了相应判断动态扩容或缩容而已,而链表则是真正意义上动态的数据结构;

链表的优点

  • 真正的动态,不需要处理固定容量的问题;
  • 能够在常数时间内扩展容量;

对比我们的数组,当创建数组时,我们必须分配能存储一定数量元素的内存,如果向数组中添加更多的元素,那么必须创建一个新的数组,然后把原数组中的元素复制到新数组中去,这将花费大量的时间;当然也可以通过给数组预先设定一个足够大的空间来防止上述时间的发生,但是这个方法可能会因为分配超过用户需要的空间而造成很大的内存浪费;而对于链表,初始时仅需要分配一个元素的存储空间,并且添加新的元素也很容易,不需要做任何内存复制和重新分配的操作;

链表的缺点

  • 丧失了随机访问的能力;
  • 链表中的额外指针引用需要浪费内存;

链表有许多不足。链表的主要缺点在于访问单个元素的时间开销问题;数组是随时存取的,即存取数组中任一元素的时间开销为O(1),而链表在最差情况下访问一个元素的开销为O(n);数组在存取时间方面的另一个优点是内存的空间局部性,由于数组定义为连续的内存块,所以任何数组元素与其邻居是物理相邻的,这极大得益于现代CPU的缓存模式;

链表和数组的简单对比

  • 数组最好用于索引有语意的情况,最大的优点:支持快速查询
  • 链表不适用于索引有语意的情况,最大的优点:动态

实现自己的链表类

public class LinkedList<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    // 获取链表中的元素个数
    public int getSize() {
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作,练习用:)
    public void add(int index, E e) {

        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        prev.next = new Node(e, prev.next);
        size++;
    }

    // 在链表头添加新的元素e
    public void addFirst(E e) {
        add(0, e);
    }

    // 在链表末尾添加新的元素e
    public void addLast(E e) {
        add(size, e);
    }

    // 获得链表的第index(0-based)个位置的元素
    // 在链表中不是一个常用的操作,练习用:)
    public E get(int index) {

        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Illegal index.");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        return cur.e;
    }

    // 获得链表的第一个元素
    public E getFirst() {
        return get(0);
    }

    // 获得链表的最后一个元素
    public E getLast() {
        return get(size - 1);
    }

    // 修改链表的第index(0-based)个位置的元素为e
    // 在链表中不是一个常用的操作,练习用:)
    public void set(int index, E e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Update failed. Illegal index.");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        cur.e = e;
    }

    // 查找链表中是否有元素e
    public boolean contains(E e) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    // 从链表中删除index(0-based)位置的元素, 返回删除的元素
    // 在链表中不是一个常用的操作,练习用:)
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        // E ret = findNode(index).e; // 两次遍历

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size--;

        return retNode.e;
    }

    // 从链表中删除第一个元素, 返回删除的元素
    public E removeFirst() {
        return remove(0);
    }

    // 从链表中删除最后一个元素, 返回删除的元素
    public E removeLast() {
        return remove(size - 1);
    }

    // 从链表中删除元素e
    public void removeElement(E e) {

        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.e.equals(e))
                break;
            prev = prev.next;
        }

        if (prev.next != null) {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        Node cur = dummyHead.next;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }
}

链表虚拟头结点的作用

  • 为了屏蔽掉链表头结点的特殊性;
    因为头结点是没有前序结点的,所以我们不管是删除还是增加操作都要对头结点进行单独的判断,为了我们编写逻辑的方便,引入了一个虚拟头结点的概念;

简单复杂度分析

我们从链表的操作中可以很容易的看出,对于增删改查这几个操作的复杂度都是O(n)的,但是如果我们只是对链表头进行增/删/查的操作的话,那么它的复杂度就是O(1)的,这里也可以看出来我们的链表适合干的事情了..


LeetCode相关题目参考

1.两数之和

参考答案:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int [] res = new int[2];
        if(numbers==null||numbers.length<2)
            return res;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0; i < numbers.length; i++){
            if(!map.containsKey(target-numbers[i])){
                map.put(numbers[i],i);
            }else{
                res[0]= map.get(target-numbers[i]);
                res[1]= i;
                break;
            }
        }
        return res;
    }
}

2.两数相加

参考答案:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

19.删除链表的倒数第N个节点(剑指Offer面试题22)

我的答案:(13ms)

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 正确性判断
    if (null == head || null == head.next) {
        return null;
    }

    int num = 0;

    // 定义一个虚拟头结点方便遍历链表
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;

    ListNode prev = dummyHead;
    // 一次遍历找到链表的总数
    while (null != prev.next) {
        num++;
        prev = prev.next;
    }

    // 二次遍历删除对应的节点
    prev = dummyHead;
    for (int i = 0; i < num - n; i++) {
        prev = prev.next;
    }// end for:找到了删除节点的前序节点
    ListNode delNode = prev.next;
    prev.next = prev.next.next;
    delNode.next = null;

    // 返回头结点
    return dummyHead.next;
}

我的答案2:(16ms)

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 正确性判断
    if (null == head || null == head.next) {
        return null;
    }

    HashMap<Integer, ListNode> map = new HashMap<>();

    // 定义一个虚拟头结点方便遍历链表
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;

    ListNode prev = dummyHead;
    map.put(0, dummyHead);
    // 一次遍历,将序号与ListNode对应存入map中
    for (int i = 1; null != prev.next; i++, prev = prev.next) {
        map.put(i, prev.next);
    }
    // 删除对应的节点
    int delNodeNum = map.size() - n;
    ListNode delNode = map.get(delNodeNum);
    prev = map.get(delNodeNum - 1);
    prev.next = prev.next.next;
    delNode.next = null;// help GC

    // 返回头结点
    return dummyHead.next;
}

参考答案:(26ms)

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 正确性判断
    if (null == head || null == head.next) {
        return null;
    }

    // 定义虚拟头结点方便遍历
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;

    // 定义快慢两个节点
    ListNode fast = dummyHead;
    ListNode slow = dummyHead;

    // 让fast先跑到第n个位置
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // 再让两个一起移动,当fast为尾节点时slow的位置即删除元素的位置
    while (null != fast) {
        fast = fast.next;
        slow = slow.next;
    }

    ListNode delNode = slow.next;
    slow.next = slow.next.next;
    delNode.next = null;// help GC.

    return dummyHead.next;
}

21.合并两个有序链表(剑指Offer面试题25)

我的答案:(13ms)

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    // 正确性判断
    if (null == l1) {
        return l2;
    }
    if (null == l2) {
        return l1;
    }

    // 定义一个虚拟头结点方便遍历
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = l1;
    ListNode pre = dummyHead;

    // 遍历l1链表
    int len1 = 0;
    while (null != pre.next) {
        len1++;
        pre = pre.next;
    }

    int[] nums1 = new int[len1];

    // 保存l1链表的数据
    pre = dummyHead;
    for (int i = 0; i < len1; i++) {
        nums1[i] = pre.next.val;
        pre = pre.next;
    }

    // 遍历l2链表
    int len2 = 0;
    dummyHead.next = l2;
    pre = dummyHead;
    while (null != pre.next) {
        len2++;
        pre = pre.next;
    }

    int[] nums2 = new int[len2];

    // 保存l2链表的数据
    pre = dummyHead;
    for (int i = 0; i < len2; i++) {
        nums2[i] = pre.next.val;
        pre = pre.next;
    }

    int[] nums = new int[len1 + len2];
    // 将两个链表的数据整合并排序
    System.arraycopy(nums1, 0, nums, 0, len1);
    System.arraycopy(nums2, 0, nums, len1, len2);
    Arrays.sort(nums);

    // 拼接一个链表
    ListNode dummy = new ListNode(-1);
    pre = dummy;
    for (int i = 0; i < nums.length; i++) {
        ListNode node = new ListNode(nums[i]);
        pre.next = node;
        pre = pre.next;
    }

    return dummy.next;
}

参考答案:(15ms)

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    ListNode head = null;
    if (l1.val < l2.val) {
        head = l1;
        head.next = mergeTwoLists(l1.next, l2);
    } else {
        head = l2;
        head.next = mergeTwoLists(l1, l2.next);
    }
    return head;
}

74.搜索二维矩阵(剑指Offer面试题4)

参考答案:(8ms)

public boolean searchMatrix(int[][] matrix, int target) {

    // 正确性判断
    if (null == matrix || 0 == matrix.length) {
        return false;
    }
    if (null == matrix[0] || 0 == matrix[0].length) {
        return false;
    }

    int row = matrix.length;
    int col = matrix[0].length;

    int start = 0, end = row * col - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        int number = matrix[mid / col][mid % col];
        if (number == target) {
            return true;
        } else if (number > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return false;
}

141.环形链表

我的答案:(14ms)

public boolean hasCycle(ListNode head) {

    // 正确条件判断
    if (null == head || null == head.next) {
        return false;
    }

    // 引入虚拟头结点
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;

    HashMap<ListNode, Integer> map = new HashMap<>();
    ListNode prev = dummyHead;
    // 遍历链表
    while (null != prev.next) {
        if (map.containsKey(prev.next)) {
            return true;
        } else {
            map.put(prev.next, prev.next.val);
            prev = prev.next;
        }
    }
    // 如果遍历到了链表尾巴都没找到则返回false
    return false;
}

参考答案:(3ms)

public boolean hasCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null){
        // move 2 steps
        fast = fast.next.next;

        // move 1 step
        slow = slow.next;

        if(fast == slow)
            return true;
    }
    return false;
}

147.对链表进行插入排序

参考答案:(38ms)

public ListNode insertionSortList(ListNode head) {

    // 正确性判断
    if (null == head || null == head.next) {
        return head;
    }

    // 定义一个新的节点,这个节点的作用是一个一个把head开头的链表插入到dummy开头的链表里
    ListNode dummy = new ListNode(-1);

    // 类似于冒泡排序法的遍历整个链表
    while (null != head) {
        ListNode pre = dummy;
        while (null != pre.next && pre.next.val < head.val) {
            pre = pre.next;
        }
        ListNode temp = head.next;
        head.next = pre.next;
        pre.next = head;
        head = temp;
    }

    return dummy.next;
}

148.排序链表

我的答案:(829ms)

public ListNode sortList(ListNode head) {

    // 正确性判断
    if (null == head || null == head.next) {
        return head;
    }

    // 引入虚拟头结点方便遍历
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;

    List<Integer> vals = new ArrayList<>();
    ListNode prev = dummyHead;

    // 遍历一遍数组,将数据存入排好序存入vals集合中
    while (null != prev.next) {
        // 每一次都将val值插入到正确的地方
        int index = 0;
        for (int i = 0; i < vals.size(); i++) {
            if (prev.next.val >= vals.get(i)) {
                index = i + 1;
            }
        }
        vals.add(index, prev.next.val);
        prev = prev.next;
    }

    // 连接链表
    prev = dummyHead;
    for (int i = 0; i < vals.size(); i++) {
        ListNode node = new ListNode(vals.get(i));
        prev.next = node;
        prev = prev.next;
    }

    return dummyHead.next;
}

参考答案:(4ms)

public ListNode sortList(ListNode head) {

    // 正确性判断
    if (null == head || null == head.next) {
        return head;
    }

    // 第一次遍历:找到链表长度
    int len = 0;
    ListNode cur = head;
    while (null != cur) {
        len++;
        cur = cur.next;
    }

    // 第二次遍历:保存链表的值
    int[] nums = new int[len];
    cur = head;
    for (int i = 0; i < len; i++) {
        nums[i] = cur.val;
        cur = cur.next;
    }

    // 第三次遍历:改变链表的值
    Arrays.sort(nums);
    cur = head;
    for (int i = 0; i < len; i++) {
        cur.val = nums[i];
        cur = cur.next;
    }

    return head;
}

这里想吐槽一下:因为上面的算法遍历了三次链表,我想着使用ArrayList来少一次遍历结果发现运算速度达到了20ms左右..时间好像都花在了ArrayList转数组这个操作上了…这或许就是传说中的负优化吧…

203.删除链表中的节点(剑指Offer面试题18)

参考答案:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 定义一个虚拟头结点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }

        return dummyHead.next;
    }
}

206.反转链表(剑指Offer面试题6、面试题24)

我的答案:(7ms)

public ListNode reverseList(ListNode head) {

    // 正确性判断
    if (null == head || null == head.next) {
        return head;
    }

    // 定义一个虚拟头结点
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;

    HashMap<Integer, ListNode> map = new HashMap<>();
    ListNode prev = dummyHead;
    // 存储节点顺序信息
    for (int i = 0; null != prev.next; i++) {
        map.put(i, prev.next);
        prev = prev.next;
    }
    int listSize = map.size();
    // 反转链表
    for (int i = listSize - 1; i > 0; i--) {
        map.get(i).next = map.get(i - 1);
    }
    map.get(0).next = null;

    // 返回头结点
    return map.get(listSize - 1);
}

参考答案:(0ms)

public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    while (null != head) {
        ListNode temp = head;
        head = head.next;
        temp.next = pre;
        pre = temp;
    }

    return pre;
}

442.数组中重复的数据(剑指Offer面试题3)

我的答案:(56ms)

public List<Integer> findDuplicates(int[] nums) {
    List<Integer> result = new ArrayList<>();

    // 正确性判断
    if (null == nums || 0 == nums.length) {
        return result;
    }

    // 创建一个HashMap,K值存位置,V值存数据
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        // 如果存在重复的V值那么则有重复的元素存在
        if (map.containsKey(nums[i])) {
            result.add(nums[i]);
        }
        map.put(nums[i], i);
    }
    return result;
}

参考答案:(14ms)

public List<Integer> findDuplicates(int[] nums) {
    List<Integer> res = new ArrayList<>();
    if (nums == null || nums.length == 0) return res;
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) nums[index] *= -1;
        else {
            res.add(index + 1);
        }
    }
    return res;
}

上面这个方法我DEBUG了一会儿终于搞懂了,如果有两个重复的数字,那么nums[index]位置的数字一定是一个复数,但是如果这个index值超过了nums.length,就会报错啊..这个只能算一个巧解吧…


简单总结

刷题还是挺有成就感的,像这样复习一遍下来感觉自己还是挺有收获的,特别是在算法方面有了一些神奇的体验,然后呢数据结构这方面也通过刷题有了不一样的理解和见解,就希望自己能抓紧点儿时间吧,加油;

欢迎转载,转载请注明出处!
简书ID:@我没有三颗心脏
github:wmyskxz
欢迎关注公众微信号:wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料