Posted on | Edited on | In ,

俩分法的时间复杂度

效率很高，时间复杂度是O(logN)。但是条件也比较苛刻

  1. 必须是有序数组的，支持通过下表随机访问。如果用链表会退化成时间复杂度O(n)
  2. 数组必须有序，所以在查找前需要对数组进行排序，
  3. 数量太小不适合二分查找法。因为在数据量小的时候LogN不见得比遍历数组要快
  4. 数量太大不适合二分查找法，因为数组要申请一片连续空间的内存如果太大，可能内存会不够用。

二分查找法的俩种实现方式

递归

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
public int search(int[] a, int dest) {
    int l = 0;
    int h = a.length - 1;

    if (l == h) {
        return a[l] == dest ? l : -1;
    }

    //开始查找每次取出一半
    return search(a, l, h, dest);
}

private int search(int[] a, int l, int h, int dest) {
    if (l >= h) {
        return a[l] == dest ? l : -1;
    }

    //取中点，如果==跳出递归，如果a[mid]>dest 下一次就是l--mid-1，反之下一次是mid+1,high
    int mid = l + ((h - l) >> 1);
    if (a[mid]==dest){
        return mid;
    }else if(a[mid]>dest){
        return search(a,l,mid-1,dest);
    }else{
        //a[mid]<dest
        return search(a,mid+1,h,dest);
    }
}

循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int search(int[] a, int dest) {
    int l = 0;
    int h = a.length - 1;

    if (l == h) {
        return a[l] == dest ? l : -1;
    }

    //循环查找
    while (l <= h) {
        int mid = l + (h - l) / 2;
        if (a[mid] == dest) {
            return mid;
        } else if (a[mid] < dest) {
            l=mid+1;
        }else{
           h=mid-1;
        }

    }
    return -1;
}

例子：算一个数的平方跟

这到例子主要是讲解，二分法的解决思路，先确认查找范围x比1大1–x,如果x在0和1之间0–1,然后用二分法求解mid最接近结果。

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
public double squart(double x, int n) {
    //快速返回
    if (x == 0 || x == 1) {
        return x;
    }

    double l = 1;
    double h = x;
    //如果x在0->1之间
    if (x > 0 && x < 1) {
        l = 0;
        h = 1;
    }

    long base = 1;
    int i = 1;
    while (i <= n) {
        base = base * 10;
        i++;
    }
    //递归调用
    double ret = squart(x, l, h, 1.00f / base);

    return new BigDecimal(ret).setScale(n, BigDecimal.ROUND_HALF_UP).doubleValue();
}

//二分查找
private double squart(double x, double l, double h, float p) {
    if (l >= h) {
        return l;
    }

    double mid = l + (h - l) / 2;

    if (mid * mid > x) {
        return squart(x, l, mid, p);
    } else if (mid * mid < x) {
        return squart(x, mid, h, p);
    } else {
        return mid;
    }

}

二分法变形查找

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112


public static int searchLastEq(int a[], int d) {
    int l = 0;
    int h = a.length - 1;

    while (l <= h) {
        int m = l + ((h - l) >> 1);
        if (a[m] > d) {
            h = m - 1;
        } else if (a[m] < d) {
            l = m + 1;
        } else {
            //注意找最后一个eq所以如果相等就判断后一位是否相等如果不相等返回，如果相等，说明要取的值在右边，l=m+1
            if (m == a.length - 1 || a[m + 1] != d) {
                System.out.printf("最后个相等%s的Index=%s,v=%s\n", d, m, a[m]);
                return m;
            }
            l = m + 1;
        }
    }

    System.out.println("最后一个相等的没找到");
    return -1;
}

public static int searchFirstEq(int a[], int d) {
    int l = 0;
    int h = a.length - 1;

    while (l <= h) {
        int m = l + ((h - l) >> 1);
        if (a[m] > d) {
            h = m - 1;
        } else if (a[m] < d) {
            l = m + 1;
        } else {
            //注意找第一个eq所以如果相等就判断前一位是否相等如果不相等返回，如果相等，说明要取的值在左边，h=m-1
            if (m == 0 || a[m - 1] != d) {
                System.out.printf("第一个相等%s的Index=%s,v=%s\n", d, m, a[m]);
                return m;
            }
            h = m - 1;
        }
    }

    System.out.println("第一个相等的没找到");
    return -1;
}

/**
 * ..a[m]...6,7,d,9.....-->7
 *
 * @param a
 * @param d
 * @return
 */
public static int searchRecentLte(int a[], int d) {
    int l = 0;
    int h = a.length;

    while (l <= h) {
        int m = l + ((h - l) >> 1);

        //如题，找d左边的第一值，当a[m]<=d的时候说明m在左边，然后一直往右边找，直到找到后面大于d的返回，
        // 如果右边依然<=d，说明要找的值还在右边，二分法l=m+1
        // 如果a[m]>d，不符合条件说明要找的值在m的左边，需要h=m-1
        if (a[m] <= d) {
            if (m == 0 || a[m + 1] > d) {
                System.out.printf("最后(最近的小于等于)小于等于%s的数的(Index=%s,v=%s)\n", d, m, a[m]);
                return m;
            }
            l = m + 1;
        } else {
            h = m - 1;
        }

    }
    return -1;
}

/**
 * .....6,7,d,9..a[m]...-->9
 *
 * @param a
 * @param d
 * @return
 */
public static int searchRecentGte(int a[], int d) {
    int l = 0;
    int h = a.length - 1;

    while (l <= h) {
        int m = l + ((h - l) >> 1);
        //如题：找d右边的第一个值，如果a[m]>=d，要一直向左找，找到m==0或者m的左边小于d的数，返回m
        // 如果a[m-1]依然大于d，说明要照的数在左边，h=m-1
        // 如果a[m]<d，说明要照的数在右边，l=m+1
        if(a[m]>=d){
            if(m==0|| a[m-1]<d){
                System.out.printf("第一个(最近的大于等于)大于等于%s的数的(Index=%s,v=%s)\n", d, m, a[m]);
                return m;
            }
            h=m-1;
        }else{
            //a[m]<d
            l=m+1;
        }

    }

    return -1;
}

课后作业-leetcode33

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
    public static void main(String[] args) {
        int[] a = new int[]{4, 5, 6, 7, 0, 1, 2};
        int target = 5;
        System.out.println(search(a, target));
    }

    public static int search(int[] a, int d) {
        int l = 0;
        int h = a.length - 1;


        while (l <= h) {
            if (a[l] == d) {
                return l;
            }
            if (a[h] == d) {
                return h;
            }
            int m = l + ((h - l) >> 1);
            if (a[m] == d) {
                return m;
            }
            if (a[m] > a[l]) {
                if (a[m] > d) {
                    if (a[l] < d) {
                        h = m - 1;
                    } else {
                        l = m + 1;
                    }
                } else {
//                    a[m]<d
                    l = m + 1;
                }
            } else {
                //a[m]<a[l]
                if (a[m] > d) {
                    h = m - 1;
                } else {
                    //a[m]<d
                    if (a[h] > d) {
                        l = m + 1;

                    } else {
                        h = m - 1;
                    }
                }
            }
        }
        return -1;
    }

Posted on | Edited on | In ,

线性排序

因为下面几种排序的事件复杂度接近O(n)，所以我们称其为线性排序

桶排序

将数据有小到达分成m个桶，每个桶内n个元素，然后分别对每个桶进行快速排序，由于桶是有序的，所以在排序完成后不用在排序了。

时间复杂度分析

最好时间复杂度

1
每个桶元素是n/m=>O(m * n/m * logn/m)=>O(n*logn/m)，假设到m和n接近时候，时间复杂度是O(n)

最坏时间复杂度：当几乎所有数据都几种在一个桶内时候，复杂度会退化为O(nlogn)

桶排序的试用场景：外部排序

比如有一个10G的用户数据的文件，对某一项属性排序，内存只有几百MB，我们无法将数据都加载到内存中，我们可以利用桶排序，先扫描文件确认属性的范围，将属性分为m个范围，并且分为m个文件，分别将数据插入到这些文件中，之后对这些文件分别排序。当然如果遇到分布不均匀的情况还要继续划分。

如：比如用户10个GB的订单文件，按照金额排序。

计数排序

代码如下：

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

public int[] sort(int[] a) {
    //查找最大值
    int max = getMax(a);
    int[] countArray = new int[max + 1];

    //分桶（申请一个数组），从0---max每个值一个桶，并且做累加
    for (int i = 0; i < a.length; i++) {
        countArray[a[i]] = countArray[a[i]] + 1;
    }

    //遍历桶给桶做累加，记录从min-->max，每个值包含他之前的值总共有多少个，用于后面的排序
    int sum = countArray[0];
    for (int i = 1; i < countArray.length; i++) {
        sum += countArray[i];
        countArray[i] = sum;
    }

    //申请额外空间
    int[] ret=new int[a.length];
    //轮询要排序数组a,a的值就是桶的下标。
    // 1.找到a[i]在countArray中对应的count值；
    // 2.这个(count-1)值对应的是排序之后数组的该值的index，将a[i]插入到新数组的ret[count-1]
    // 3.count--;
    for (int i = 0; i < a.length; i++) {
        int v = a[i];
        int count = countArray[v]-1;
        ret[count] = v;
        countArray[v] =count;
    }

    return ret;
}

private int getMax(int[] a) {
    int ret = a[0];
    for (int i = 1; i < a.length; i++) {
        if (ret <= a[i]) {
            ret = a[i];
        }
    }
    return ret;
}

思路如图：
avator

  1. 找到原数组最大值，申请一个countArray[max+1]
  2. 记录countArray中记录原数组a的每个值的个数，并且对countArray数组每一项求和。这个值就是排序之后的每个元素的下标最大值+1。（意思是这个元素在排序之后的数组中包含他的位置）
  3. 遍历数组a,取v=a[i]的值，取countArray中的count，然后v插入到排序后的数组r的count-1中。

适用场景

  1. 只能给正整数排序
  2. 只能给范围不大的数组排序，比如范围k比数组n大很多那就不合适了

Posted on | Edited on | In ,

防止变量的共享

在声明一个变量时候要通过方法的封装暴露对象的修改和查询操作，以此为入口来控制变量的并发，对于不变的对象尽量声明成final类型，告诉别人这个便利不会被改变。

识别共享变量的条件

防止变量之间的竞态问题，比如下面的代码：设置了上限和下限，这里有个隐含的条件上限一定要>=下限,虽然变量声明成了AtomicLong，但是在并发的时候需改时候遇到if条件可能会造成下限高于上限的问题。原因在于条件判断和修改结果不是原子操作，这是个典型的竞态问题。修改方案是set方法加synchronized

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
public class SafeWM {
  // 库存上限
  private final AtomicLong upper =
        new AtomicLong(0);
  // 库存下限
  private final AtomicLong lower =
        new AtomicLong(0);
  // 设置库存上限
  void setUpper(long v){
    // 检查参数合法性
    if (v < lower.get()) {
      throw new IllegalArgumentException();
    }
    upper.set(v);
  }
  // 设置库存下限
  void setLower(long v){
    // 检查参数合法性
    if (v > upper.get()) {
      throw new IllegalArgumentException();
    }
    lower.set(v);
  }
  // 省略其他业务代码
}

制定并发访问策略

  1. 防止共享
  2. 采取不变模式。这样修改一个对象就是创建了一个新对象
  3. 利用管程和其他并发工具来

要注意几点

  1. 采用成熟的工具类避免重复开发轮子
  2. 尽量避免使用低级原语入synchronized、lock等方式，而是采用并罚保
  3. 尽量以并发安全为主，尽量避免过早优化代码

Posted on | Edited on | In ,

如何选择一种排序算法

算法的执行效率

  • 最好、最坏、平均时间复杂度：需要根据要排序数据的大小、以及是否接近有序来考虑时间复杂度。
  • 考虑时间复杂度的系数、常量、低阶：对于通一时间复杂度的数据要考虑这些。
  • 比较次数和交换次数：基于比较的排序涉及到数据的交换所以要考虑比较次数和交换次数。

算法的内存消耗

原地排序指空间复杂度是O(1)的排序，我们在选择的时候也要针对硬件考虑算法的空间复杂度

算法的稳定性

指如果数据有俩个相等的元素，当排序后者俩个相等元素之间的顺序没发生改变，我们管他叫稳定的排序。相反则是不稳定的排序。

算法稳定性的意义以及用法，对于一个对象按照俩个属性维度排序。如：对于一个账户的金额排序，金额相等的按照时间倒序。

  1. 我们可以先按照时间倒叙排序，得到时间倒叙排序的列表；

  2. 用稳定性排序算法按照金额大小进行排序，由于是稳定性的排序算法所以金额相等的数据原有顺序不变依然是时间倒叙。

    规律：先按照第二个属性排序（即xx相等，按照xx排序），在按照第一个属性排序。

算法的有序度和逆序度

一个数组中，有顺序的元素个数较为有序度。相反，则成为逆序度。一个完全有序的数据我们称他为满有序度。公式是：逆序度=满有序度-有序度。
排序实际上是减少逆序度最终达到满有序度的过程

冒泡排序

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

    public int[] sort(int[] array) {
        //第一层循环没循环一次冒泡一次，如果某一次没有发生位置变化说明数组已经完全有序，停止冒泡needBuuble
        for (int i = 0; i < array.length; i++) {
            boolean needBuuble=false;
            for (int j = i + 1; j < array.length-i; j++) {
                int tmp = array[j];
                if (array[i] > array[j]) {
                    array[j] = array[i];
                    array[i] = tmp;
                    needBuuble=true;
                }
            }
            if(!needBuuble){
                return array;
            }
        }
        return array;
    }
}

算法分析

时间复杂度：最好的情况是数组完全有序，只做一次循环就退出。最坏的时间复杂度是O(n*n),完全倒序需要都交换一次。

空间复杂度：相邻俩个元素比较交换，没有用到额外的空间属于O(1)

算法稳定性：俩个元素相同，不交换位置所以是算法稳定。

注：如果不优化，时间复杂度就是O(n*n).

选择排序

选择排序，循环数组，每次都找到数组最小值，然后和当前元素互换位置，知道结束，

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
public class SelectionSorts {

    /**
     * 选择排序，循环数组，每次都找到数组最小值，然后和当前元素互换位置，知道结束，
     * 时间负责度最好O(n*n)，最坏O(n*n)，平均都是O(n*n)，且不稳定
     * @param a
     * @return
     */
    public int[] sort(int[] a) {
        for (int i = 0; i < a.length; i++) {

            //记录最小值和索引
            int min=a[i];
            int minIdx=i;

            //循环查找最小值
            for(int j=i+1;j<a.length;j++){
                if(a[j]<min){
                    min=a[j];
                    minIdx=j;
                }
            }

            //如果当前值不是最小值，最小值和当前值互换位置
            if(i!=minIdx){
                int tmp=a[minIdx];
                a[minIdx]=a[i];
                a[i]=tmp;
            }
        }

        return a;
    }

}

选择排序-算法分析

时间复杂度：时间负责度最好O(nn)，最坏O(nn)，平均都是O(n*n)

空间复杂度：没有用到额外的空间属于O(1)

算法稳定性：不稳定每次都要交换位置，如果值相等也可能在交换后改变顺序

归并排序

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
public void sort(int a[], int start, int end) {
       if (start >= end) {
           return;
       }

       //利用分治思想递归
       int mid = (start + end) / 2;
       sort(a, start, mid);
       sort(a, mid + 1, end);

       merge(a, start, mid, end);
   }

   private void merge(int[] a, int start, int mid, int end) {
       //临时数组等于a里start-->end
       int[] tmp = new int[end - start + 1];//注意：一定是end-start+1，因为这是Index,长度要+1（0--2长度是3）
       int k = 0;

       //给tmp赋值，逻辑是i从start-->mid，j从mid+1-->end
       int i = start;
       int j = mid + 1;
       while (i <= mid && j <= end) {
           tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
       }

       //剩余补进临时数组
       while (i <= mid) {
           tmp[k++] = a[i++];
       }
       while (j <= end) {
           tmp[k++] = a[j++];
       }

       //将临时数据写入到a中
       for (int x = 0; x < tmp.length; x++) {
           a[start + x] = tmp[x];
       }
   }

归并排序 算法分析

时间复杂度：时间负责度最好O(nlogn)，最坏O(nnlogn)，平均都是O(nnlogn)

空间复杂度：每次merge都需要开辟一块空间但是每次都释放掉，空间复杂度就是O(n)

算法稳定性：稳定

快速排序

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
/**
 * 获取数组的一个标志位（交换区点一般是数组最后一位，小于这个点的在左边，大于的在右边）
 *
 * @param a
 * @param s
 * @param e
 */
private void sort(int[] a, int s, int e) {
    if (s >= e) {
        return;
    }

    int poivt = poivt(a, s, e);
    sort(a, s, poivt - 1);//排序取到分区点后，分区点-1，参与排序
    sort(a, poivt, e);//从分区点到终点排序
}

private int poivt(int[] a, int s, int e) {
    int swapIdx = s;//交换区为s，随着数组循环移动
    int flag = a[e];//设置flag即最后交换区

    //s-->e-1,循环到交换区前
    for (int i = s; i <= e - 1; i++) {
        //即时小于也要交换，让swpIdx后移
        if (a[i] <= flag) {
            int tmp = a[i];
            a[i] = a[swapIdx];
            a[swapIdx] = tmp;
            swapIdx++;//扩大前半部分
        }
    }

    //最后将flag移动到此次poivt点并且返回交换区点
    int tmp = a[swapIdx];
    a[swapIdx] = flag;
    a[e] = tmp;

    return swapIdx;
}

快排复杂度分析

Posted on | Edited on | In ,

队列的作用和实际使用场景

循环队列

特点：

  • 没有数组队列在扩容时候O(n)的数据迁移工作
  • 当(tail+1)%n=head时候队列满,当head==tail的时候队列空
  • 因为是环状，所以被enqueue一个元素，tail=(tail+1)%n,每dequeue一个元素，head=(head+1)%n
  • 缺点：tail不能存数据
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
public class CircleQueuqe {
    private String[] array;
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    public CircleQueuqe(int size) {
        this.size = size;
        array = new String[size];
    }

    public void enque(String s) {
        //尾指针下一个指向head队列满
        if ((tail + 1) % size == head) {
            throw new RuntimeException("CircleQueuqe has full");
        }

        array[tail] = s;
        //环状的下一个位置是 tail+1取模
        tail = (tail + 1) % size;
    }

    public String deques() {
        if(head==tail){
            throw new RuntimeException("CircleQueuqe has empty");
        }

        String ret=array[head];
        head=(head+1)%size;

        return ret;
    }

    public String[] getArray() {
        return array;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "CircleQueuqe{" +
                "array=" + Arrays.toString(array) +
                ", head=" + head +
                ", tail=" + tail +
                ", size=" + size +
                '}';
    }
}

Posted on | Edited on | In ,

什么样的问题可以用递归解决

  1. 可以将一个问题分解成若干子问题
  2. 主要问题和子问题之间的处理过程是一样的。
  3. 存在递归终止条件

如何写一个递归程序

  1. 分解问题，推导出递推公式
  2. 找到程序的出口，即递归结果

递归程序的注意事项

  1. 防止堆栈溢出–增加深度的参数
  2. 防止重复计算–增加散列表等方式记录计算结果如果有计算结果直接返回

例子：斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private Map<Integer, Long> map = new HashMap<>();

/**
 * 递推公式f(n)=f(n-1)+f(n-2)，结果：n==1 return 1 n==2 return 1
 * @param n
 * @return
 */
public long cal(int n) {
    //递归结果
    if (n == 1 || n == 2) {
        return 1;
    }

    //记录结果避免重复计算,如果没有这个会特别的满
    if (map.containsKey(n)) {
        return map.get(n);
    }

    //计算
    long ret = cal(n - 1) + cal(n - 2);
    map.put(n, ret);
    return ret;
}

Posted on | Edited on | In ,

链表

链表特点，内存不连续，包含后置或者前置节点的指针，修改的时间复杂度O(1),查找的时间复杂度O(n)；

链表的注意

  • 建议增加哨兵节点减少难度（head tail，这样在修改链表时候不用判断头结点和最后一个节点）
  • 防止指针丢失和溢出
  • 注意边界处理（Null,只有一个节点，只有俩个节点）

代码练习

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/**
 * @Author: liuhaoeric
 * Create time: 2019/03/23
 * Description:
 */
public class Node {
    private Integer val;
    public Node next;
    public Node prev;

    public Node(Integer val) {
        this.val = val;
    }

    public Integer getVal() {
        return val;
    }

    public Node getNext() {
        return next;
    }

    public Node getPrev() {
        return prev;
    }

    @Override
    public String toString() {
        return "Node{" +
                "node=" + val +
                ", next=" + next +
                '}';
    }

    /**
     * 找中间节点
     *
     * @param node
     * @return
     */
    public static Node findMid(Node node) {
        if (node == null || node.next == null || node.next.next == null) {
            return node;
        }

        Node slow = node;
        Node fast = node;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    /**
     * 可用快慢指针找是否有环
     *
     * @param node
     * @return
     */
    public static boolean checkNodeLoop(Node node) {
        if (node == null || node.next == null) {
            return false;
        }

        Set<Integer> set = new HashSet<>();
        Node cur = node;

        while (cur != null) {
            if (set.contains(cur.val)) {
                return true;
            }
            set.add(cur.val);
            cur = cur.next;
        }

        return false;
    }

    /**
     * 有序俩表合并
     *
     * @param a
     * @param b
     * @return
     */
    public static Node merge(Node a, Node b) {
        Node head = new Node(null);
        Node ret = head;

        Node cura = a;
        Node curb = b;
        while (cura != null && curb != null) {
            if (cura.val < curb.val) {
                ret.next = cura;
                cura = cura.next;
            } else {
                ret.next = curb;
                curb = curb.next;
            }
            ret = ret.next;
        }

        if (cura != null) {
            ret.next = cura;
        }
        if (curb != null) {
            ret.next = curb;
        }
        return head.next;
    }

    /**
     * 删除倒数第几个节点
     *
     * @return
     */
    public static Node removeNodeByDescPosition(Node a, int position) {
        if (a == null) {
            return null;
        }
        List<Node> list = new ArrayList<>();

        Node head = new Node(null);
        head.next = a;
        Node tmp = head;
        while (tmp != null) {
            list.add(tmp);
            tmp = tmp.next;
        }
        //超过限制
        if (position >= list.size()) {
            return head.next;
        }

        //找到要删的节点的前置节点
        Node n;
        int nodeidx = list.size() - position;
        n = list.get(nodeidx - 1);
        n.next = n.next.next;
        return head.next;
    }

    public static Node reverseNode(Node node) {
        return null;
    }

    public static void main(String[] args) {
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        Node e = new Node(5);
        Node f = new Node(6);
        Node g = new Node(7);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;
        f.next = g;

//        System.out.println(Node.findMid(a));
//
//        System.out.println(Node.checkNodeLoop(a));
//
//
//        Node a1 = new Node(0);
//        Node b1 = new Node(2);
//        Node c1 = new Node(4);
//        Node d1 = new Node(6);
//        Node e1 = new Node(8);
//        Node f1 = new Node(10);
//        Node g1 = new Node(11);
//        a1.next = b1;
//        b1.next = c1;
//        c1.next = d1;
//        d1.next = e1;
//        e1.next = f1;
//        f1.next = g1;
//
//        System.out.println(Node.merge(a, a1));

        System.out.println(Node.removeNodeByDescPosition(new Node(10), 1));
    }
}

Posted on | Edited on | In ,

为什么要使用多线程

我们评价一个操作系统性能好的系统往往是俩点低延迟、高吞吐。做到这俩点，往往需要一优化算法，二有效利用硬件。对于一不在此讨论的范畴，而硬件利用率大致往往分俩类，即cpu的利用率，和i/o的利用。
单线程时代：我们的程序往往是cpu和io设备相互配合执行，所以一个单线程的程序执行cpu操作时候io就要停下来等待cpu完成，为了提高io和cpu的利用率，操作系统为我们提供了多线程技术。
线程1处理cpu的计算，线程2处理io请求。处理玩io请求后在切换回来，这样利用率就得到了提高

线程多了就一定快么

针对我们程序的特点分为，io密集型和计算密集型俩种。如果io操作执行的比例比较大就是io密集型，如果cpu计算的比例比较大就是计算密集型。
在单核时代，对于计算密集型的业务增加线程反而会拖慢程序执行效率，因为只有一个核，所以同时只能有一个线程在运行，增加线程反而加大了线程切换的损耗。
在多核时代，对于计算密集型的业务是可以通过增加线程提高性能的，但是设置应该是cpu的核数+1，充分利用起cpu。
对于io密集型的业务，由于一般io的耗时比cpu要多的多，那么线程往往是cpu的核数*io耗时/cpu耗时+1。

Posted on | Edited on | In ,

方法是如何被执行

例如下面的程序

1
2
3
int a = 7；
int[] b = fibonacci(a);
int[] c = b;

当jvm调用fibonacci(a)时，通过cpu的寄存器找到方法的地址。cpu支持一种栈结构，他和方法息息相关，所以一般叫做调用栈。
栈这种数据结构的特点是后进先出，所以当一个遇到方法嵌套时候比如a–>b–>c，那么入栈的时候就是c–>b–>a，执行顺序也是c–>b–>a。

方法中的局部变量

方法实际上是以栈帧为单位入栈的，一个方法从入口到返回都在一个栈帧中，栈帧和方法的生命周期是一样的，当方法结束，栈帧也就失效了，而方法中的局部变量都是保存在栈帧中的，他的生命周期也是在方法内部。且为了线程之间不相互干扰，每个线程都有一个独立的栈帧。综上，栈帧是线程安全的。

这种方式有个名词叫线程封闭，即仅在单线程内访问数据，不共享就没有线程安全的问题。例如：我们常用的数据库连接池，connection的方法并没有声明线程安全，我们在使用中都是在一个方法内获取conenection，查询数据，关闭connecton，这这种线程封闭方式来解决线程安全的问题。

Posted on | Edited on | In ,

操作系统的线程生命周期

初始状态，可运行状态，运行状态，终止状态，休眠状态，他们之间的转化关系如图：

avator

  • 初始状态:线程被创建，但是还未分配cpu执行的状态。
  • 可运行状态:指线程可以分配cpu执行。
  • 运行状态:有cpu空闲时候分配cpu执行，当线程被分配给cpu执行时候，变为可执行状态。
  • 终止状态:线程执行完成或者异常终止。
  • 休眠状态:线程调用阻塞的api或者等待某个事件执行的时候会变为休眠状态。

jvm将由于将线程的调度交给操作系统，所以将可运行状态和运行状态和在了一起，因为jvm不关心这俩个状态的具体情况。

java线程的生命周期

NEW（初始装填）、RUNABLE（可运行/运行状态）、TERMINATED（终止状态）、BLOCK（阻塞）、WAIT（等待）、TIME_WAIT（有时限等待）

其中BLOCK、WAIT、TIME_WAIT都属于休眠关系

avator

  • NEW:当线程对象被创建出来的时候线程处于该状态，这时候还未对其分配cpu。具体方法是集成Thread类并且实现run方法，或者狗仔一个Thread对象把一个Runnable的接口实现传进去。
  • NEW–>RUNABLE:调用thread.start()方法线程变为RUNABLE状态。
  • RUNABLE–>休眠状态：java的休眠状态有三种BLOCK、WAIT、TIME_WAIT，分别是
    • RUNABLE–>BLOCK：当遇到synchronized代码块时候，如果竞争失败当前线程进入block状态。等待进入到线程又会变为RUNABLE状态，注意在java中如调用到了阻塞的api，是不会切换到block状态的，比如调用io的api，当前线程依然是RUNABLE状态这点要注意。
    • RUNABLE–>WAIT：如下3中情况会让当前线程进入到wait状态
      • object.wait(),没有时间限制的wait，需要调用object.notify()或者object.notifyAll()
      • 调用了其他线程的join()，没有时间限制的join，需要等待当前join的线程终止。
      • 调用了LockSupport.park(),没有事件限制的park，对应的方法是LockSupport.unPark()
    • RUNABLE–>TIME_WAIT：同上就是上面3种情况或者方法的有时间版本
  • RUNABLE–>TERMINATED：
    • 线程执行结束
    • stop()或者interrupt()方法

线程终止的方法

当一个线程执行一个很耗时的逻辑时候，可能会终止该线程的操作，比如并发情况下的网络超时，为了防止资源耗尽往往要终止。上面提到了stop或者interrupt方法

  • stop方法已经不建议使用了，因为会立即杀死线程，同时不会释放synchronized的锁，所以后面的线程都会阻塞。

  • interrupt方法相对来说就会“温柔”很多，它只是对线程了interrupt标记，当调用thread.interrupt()方法有俩种方式退出线程

    • 主动退出：对于一个一直执行的线程来说可以通过判断t1.isInterrupted()来判断是否该终端
    1
    2
    3
    4
    5
    final Thread t1 = new Thread(() -> {
              while(!t1.isInterrupted()){
                  //do something
              }
          });
    • 异常退出：对于执行了wait sleep这种线程我们可以通过异常捕获来判断线程的终端，因为他们会抛出InterruptedException异常
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    final Thread t1 = new Thread(() -> {
             synchronized (lock) {
                 try {
                     lock.wait();
                 } catch (InterruptedException e) {
                     e.printStackTrace();
                     return;
                 }
                 //do something

                 //这时候会输出false因为interrupt会被清除
                 System.out.println(t1.isInterrupted());
             }
         });

注意：当抛出InterruptedException异常后线程的interrupt标记会被清楚如果这时候在判断isInterrupted()方法就又变成了false