优先队列基本介绍

​ 优先队列又叫做堆，他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠，本层不满就不能堆放下一层。并且优先队列还有一个特点就是如果他是大根堆那么父节点不小于子节点，如果是小根堆父节点不大于子节点。这也是一个递归定义。

Read More

选择排序：

​ 选择排序一般来说就是，我们 始终从中右边的序列中找出那些最小的元素，放在左侧，这样我们就能保证左边始终有序。

​ 但是这个算法的复杂度比较高，为
$$
n^2/2
$$
​ 那为什么是这个值，假若我们放一张 n x n 的表格，然后我们在排序的过程中用灰色表示不变的元素，然后用黑色表示变化的元素。这样一来我们会发现这个表格是一个以对角线分隔的一个矩阵。很统一看到我们进行了二分之一的 n^2 扫描。

Read More

​ 在我们需要判断某一些事物之间是否存在一定的关系的时候，我们最好的办法不是使用图而是使用并查集。因为我们关心的是他们之间是否有关系，而不是关心的他们到底存在怎样的关系。

​ 并查集，简单来说就是 n 个集合，我们通过 union 操作来建立两个节点之间的关系。通过 connected 来判断两个节点之间的关系。那么现在我们知道了 并查集的基本操作就是 union 和 connected 。

Read More

​ 今年的微机原理的老师竟然叫许鹏飞，这个我也没什么好吐槽的。本来上学期以来对伟明哥教的计算机组成原理还是蛮感兴趣的，最后成绩也还不错。没想到今年又学一点计算机的基本原理和体系结构能丰富一下自己对计算机的理解增长一点见识。不过到目前为止计算机的知识我都是没增长多少，对这个老师的态度真的不是很好。首先他说他是经管院的考研考到计算机专业的，当时还是挺佩服的。

Read More

​ 今年的微机原理的老师竟然叫许鹏飞，这个我也没什么好吐槽的。本来上学期以来对伟明哥教的计算机组成原理还是蛮感兴趣的，最后成绩也还不错。没想到今年又学一点计算机的基本原理和体系结构能丰富一下自己对计算机的理解增长一点见识。不过到目前为止计算机的知识我都是没增长多少，对这个老师的态度真的不是很好。首先他说他是经管院的考研考到计算机专业的，当时还是挺佩服的。

Read More

1.二叉树的性质

1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点

2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点

3.度为 0 的节点数等于度为 2 的节点数加 1

Read More

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题目的意思大概就是有一个数组，数组里面装的就是正整数，你要去访问各个数组，但是这些数组相邻元素不可同时访问，从而获取最大的和

思路

还是 dp 动态规划 ：我们首先就想当前是头还是不偷，从而推断下一步，不管别的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class HouseRobber {
    public int rob(int[] nums) {
        int no=0;
        int yes=0;
        for (int num : nums) {
            int lastNo=no;
            no=Math.max(yes,no);
            yes=lastNo+num;
        }
        return Math.max(yes, no);
    }
    public int rob1(int[] nums) {
        int[][] dp=new int[nums.length+1][2];
        for (int i = 1; i < nums.length; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+nums[i];
        }
        return Math.max(dp[nums.length][0],dp[nums.length][1]);
    }
}

Write a program to find the node at which the intersection of two singly linked lists begins.


For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3
begin to intersect at node c1.


Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

两个思路:

一个就是把链表转化成一个有环链表 这样的话我们就可以当做那个有环的求入点问题了 但是人家说了不能修改链表的结构很抱歉没办法使用

第二个思路就是既然是这个入点是重复的那么我们就找出重复元素即可 这样自然想到了 hash 表

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62

import java.util.HashSet;
import java.util.Set;
class IntersectionOfTwoLinkedLists_1 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null){
            return null;
        }
        ListNode circle=headA;
        ListNode fast=headB;
        ListNode slow=headB;
        while (circle.next!=null){
            circle=circle.next;
        }
        circle.next=headA;
        while (fast!=null&&slow!=null){
            if (fast.next!=null&&fast.next.next!=null){
                fast=fast.next.next;
            }else {
                return null;
            }
            if (slow.next!=null){
                slow=slow.next;
            }else {
                return null;
            }
            if (fast==slow){
                ListNode x=fast;
                ListNode y=headB;
                while(x!=null&&y!=null){
                    x=x.next;
                    y=y.next;
                    if (x==y){
                        return x;
                    }
                }
            }
        }
        return null;
    }
}

class IntersectionOfTwoLinkedLists {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null){
            return null;
        }
        Set<ListNode> nodes=new HashSet<>();
        ListNode listA=headA;
        ListNode listB=headB;
        while (listA!=null){
            nodes.add(listA);
            listA=listA.next;
        }
        while (listB!=null){
            if (!nodes.add(listB)){
                return listB;
            }
            listB=listB.next;
        }
        return null;
    }
}

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

首先考虑下如何将将二个有序数列合并。

Read More

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

分析

一开始使用了复杂度O(n^2)的方法，使用两个指针a, b。a从表头开始一步一步往前走，遇到null则说明没有环，返回false；a每走一步，b从头开始走，如果遇到b==a.next，则说明有环true，如果遇到b==a，则说明暂时没有环，继续循环。

后来找到了复杂度O(n)的方法，使用两个指针slow,fast。两个指针都从表头开始走，slow每次走一步，fast每次走两步，如果fast遇到null，则说明没有环，返回false；如果slow==fast，说明有环，并且此时fast超了slow一圈，返回true。

为什么有环的情况下二者一定会相遇呢？因为fast先进入环，在slow进入之后，如果把slow看作在前面，fast在后面每次循环都向slow靠近1，所以一定会相遇，而不会出现fast直接跳过slow的情况。

扩展问题

在网上搜集了一下这个问题相关的一些问题，思路开阔了不少，总结如下：

1. 环的长度是多少？

2. 如何找到环中第一个节点（即Linked List Cycle II）？

3. 如何将有环的链表变成单链表（解除环）？

4. 如何判断两个单链表是否有交点？如何找到第一个相交的节点？

首先我们看下面这张图：

设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

下面我们来挨个问题分析。

1. 方法一（网上都是这个答案）：

第一次相遇后，让slow,fast继续走，记录到下次相遇时循环了几次。因为当fast第二次到达Z点时，fast走了一圈，slow走了半圈，而当fast第三次到达Z点时，fast走了两圈，slow走了一圈，正好还在Z点相遇。

方法二：

第一次相遇后，让fast停着不走了，slow继续走，记录到下次相遇时循环了几次。

方法三（最简单）：

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

2. 我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

3. 在上一个问题的最后，将c段中Y点之前的那个节点与Y的链接切断即可。

4. 如何判断两个单链表是否有交点？先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。

如何找到第一个相交的节点？求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算），假设L1<L2，用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)步，然后两个一起走，直到二者相遇。

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
49
50
51
52
53
54
55
56
57
58
59
60
61

import org.junit.jupiter.api.Test;

public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        if (head==null||head.next==null){
            return false;
        }
        ListNode outer=head;
        int outCount=0;
        while (outer.next!=null){
            outer=outer.next;
            ListNode current=outer;

            outCount++;
            ListNode inner=head;
            int inCount=0;
            while (inCount<outCount){
                if (inner==current){
                    return true;
                }
                inner=inner.next;
                inCount++;
            }
        }
        return false;
    }

    public boolean hasCycle_1(ListNode head) {
        if (head==null||head.next==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null||fast.next!=null){
            fast=fast.next;
            if (fast==null){
                return false;
            }
            fast=fast.next;
            if (fast==null){
                return false;
            }
            slow=slow.next;
            if (fast==slow){
                return true;
            }
        }
        return false;
    }

    @Test
    void test(){
        ListNode n1=new ListNode(1);
        ListNode n2=new ListNode(2);
        n1.next=n2;
        n2.next=null;
        System.out.println(hasCycle_1(n1));
    }
}