发表于
字数统计: 1,019 | 阅读时长 ≈ 5

数组

额外链接

* 寻找数组中第二小的元素

priorityQueue 堆

1.排序

1
2
3
4
public static int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}1234

时间复杂度为O(nlog(n))。

2.通过堆

1
2
3
4
5
6
7
8
9
10
11
12
public static int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);
    for (int i : nums) {
        q.offer(i);

        if (q.size() > k) {
            q.poll();
        }
    }

    return q.peek();
}123456789101112

时间复杂度为O(nlog(k))，空间复杂度为 O(k) 。

3.快排

若k在基准左边，则在左边快排序，否则在右边快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static int findKthLargest(int[] nums, int k) {
    if (k < 1 || nums == null) {
        return 0;
    }

    return getKth(nums.length - k + 1, nums, 0, nums.length - 1);
}

public static int getKth(int k, int[] nums, int start, int end) {

    int pivot = nums[end];

    int left = start;
    int right = end;

    while (true) {

        while (nums[left] < pivot && left < right) {
            left++;
        }

        while (nums[right] >= pivot && right > left) {
            right--;
        }

        if (left == right) {
            break;
        }

        swap(nums, left, right);
    }

    swap(nums, left, end);

    if (k == left + 1) {
        return pivot;
    } else if (k < left + 1) {
        return getKth(k, nums, start, left - 1);
    } else {
        return getKth(k, nums, left + 1, end);
    }
}

public static void swap(int[] nums, int n1, int n2) {
    int tmp = nums[n1];
    nums[n1] = nums[n2];
    nums[n2] = tmp;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

平均时间复杂度为O(n)，最坏情况下为O(n^2)。

——————————- 本文来自 -似曾相识燕归来 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/hzh_csdn/article/details/53446211?utm_source=copy

* 找到数组中第一个不重复出现的整数

合并两个有序数组

重新排列数组中的正值和负值

栈

使用栈计算后缀表达式

逆波兰式：

(a+b)*c-(a+b)/e的后缀表达式为：ab+c*ab+e/-

对栈的元素进行排序

原栈：s1，准备一个辅助栈s2

  1. s1第一次出栈，不进行比较，直接放到s2
  2. 当s1非空，每次从s1弹出a，将s2中顺序不符的值都弹回s1
  3. 将a压入s2
  4. 刚才弹回s1的值都弹回到s2
  5. 若s1空则完成了排序。

判断表达式是否括号平衡

使用栈实现队列

队列

使用队列表示栈

假设有个一串数字a,b,c,d顺序入栈，出来的结果应该是d，c，b，a,有两个队列Q1，Q2，

​ 第一步:随便找一个空的队列Q1，将a放入到Q1，此时Q2中数据为空，Q1里面有a。

​ 第二步:找到空的队列Q2,将b放入，并将 Q1里面的值（a）全部输出，加入到Q2中，此时Q1为空，Q2里面有b,a。

​ 第三步:将c放入到空的队列Q1中，将Q2里面的值（b,a）全部输出,放入到Q1中，此时Q2里面值为空，Q1里面有c,b,a。

​ ……

不断循环就可以用两个队列实现一个栈的功能

对队列的前k个元素倒序

使用队列生成从1到n的二进制数

链表

链表反转

检测链表的环

快慢指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 判断单链表是否存在环
 * @param head
 * @return
 */
public static <T> boolean isLoopList(ListNode<T> head){
    ListNode<T> slowPointer, fastPointer;

    //使用快慢指针，慢指针每次向前一步，快指针每次两步
    slowPointer = fastPointer = head;
    while(fastPointer != null && fastPointer.next != null){		// 若到尾节点则说明无环
        slowPointer = slowPointer.next;			// 1步
        fastPointer = fastPointer.next.next;	// 2步

        //两指针相遇则有环
        if(slowPointer == fastPointer){
            return true;
        }
    }
    return false;
}

https://blog.csdn.net/u010983881/article/details/78896293

返回链表倒数的第N个节点

创建两个指向head的指针p q，让p遍历，p先开始移动，p走到第n-1个节点后，p q 一起往后移动

删除聊表中的重复项

图

广度优先、深度优先搜索

图是否为树

计算边数

找到两个顶点的最短路径

树

求树高度

二叉搜索树中第K大的值

查找与根节点距离K的节点

在二叉树中查找给定节点的祖先节点

字典树

哈希表