JAVA 知识体系

randian666 · randian666 · commit e45ec2e23af0 · 2019-02-13T09:46:38.000+08:00
diff --git a/README.md b/README.md
@@ -100,6 +100,7 @@
  - [画一个线程的生命周期状态图。](https://blog.csdn.net/houbin0912/article/details/77969563)
  - sleep和wait的区别。
  - sleep和sleep(0)的区别。
+ - [Java 各种锁的小结](https://mp.weixin.qq.com/s/_xazrXa8MBYaz2WaX6BNew)
  - [Lock与Synchronized的区别 。](https://blog.csdn.net/javazejian/article/details/75043422)
  - [synchronized的原理是什么](https://blog.csdn.net/javazejian/article/details/72828483)
  - [量级锁，可重入锁，公平锁，非公平锁，乐观锁，悲观锁。](https://www.toutiao.com/i6630764198357893646/)
diff --git a/src/main/java/com/algorithm/study/demo/datastructure/heap/TopkCount.java b/src/main/java/com/algorithm/study/demo/datastructure/heap/TopkCount.java
@@ -17,7 +17,7 @@ public class TopkCount {
      * @param k
      * @return
      */
-    public static int[] topk(int[] data, int k) {
+    public static int topk(int[] data, int k) {
         PriorityQueue<Integer> queue = new PriorityQueue<>(k);
 
         for (int i = 0; i < data.length; i++) {
@@ -32,18 +32,69 @@ public static int[] topk(int[] data, int k) {
                 }
             }
         }
+        return queue.peek();
+    }
+
+    /**
+     * 手动实现堆然后查找topK
+     * @param nums
+     * @param k
+     * @return
+     */
+    public static int findKthLargest(int[] nums, int k) {
+        //构建一个小顶堆数组
+        int[] out = new int[k];
+        //小顶堆元素数量
+        int count = 0;
+        //循环处理数组
+        for (int i=0;i<nums.length;i++){
+            //数组没有满之前,从下向上调整
+            if(count<k){
+                out[i] = nums[i];
+                count++;
+                down2up(out,i);
+            }else{
+                //数组满了以后，如果新元素大于堆顶则替换堆顶，然后从上向下调整
+                if(nums[i]>out[0]){
+                    out[0] = nums[i];
+                    up2down(out,0);
+                }
+            }
+        }
+        return out[0];
+    }
 
-        int[] result = new int[k];
-        int index = 0;
-        // 遍历完成后，小顶堆的数据就为需要求得的topk的数据
-        while (!queue.isEmpty()) {
-            result[index++] = queue.poll();
+    //从下向上调整,构建小顶堆
+    public static void down2up(int[] nums,int i){
+        int parent = (i-1)/2;
+        while(parent>=0&&nums[i]<nums[parent]){
+            swap(nums,i,parent);
+            i = parent;
+            parent = (i-1)/2;
         }
+    }
+
+    //从上向下调整，构建小顶堆
+    public static void up2down(int[] nums,int p){
+        while(true){
+            int left  = 2*p+1;
+            int right = 2*p+2;
+            int minpos = p;
+            if(left<nums.length&&nums[left]<nums[p]) minpos=left;
+            if(right<nums.length&&nums[right]<nums[minpos]) minpos=right;
+            if(minpos==p) break;
+            swap(nums,p,minpos);
+            p = minpos;
+        }
+    }
 
-        return result;
+    private static void swap(int[] nums, int i, int parent) {
+        int tmp = nums[i];
+        nums[i] = nums[parent];
+        nums[parent] = tmp;
     }
 
     public static void main(String[] args) {
-        System.out.println(JSON.toJSONString(topk(new int[]{1,2,3,4,5},2)));
+        System.out.println(findKthLargest(new int[]{1,2,3,4,5},2));
     }
 }
diff --git a/src/main/java/com/algorithm/study/demo/datastructure/linear/ListNode.java b/src/main/java/com/algorithm/study/demo/datastructure/linear/ListNode.java
@@ -0,0 +1,15 @@
+package com.algorithm.study.demo.datastructure.linear;
+
+/**
+ * 链表数据结构
+ * @Author: liuxun
+ * @CreateDate: 2019/2/12 下午3:43
+ * @Version: 1.0
+ */
+public class ListNode {
+    int val;
+    ListNode next;
+    public ListNode(int val){
+        this.val=val;
+    }
+}
diff --git a/src/main/java/com/algorithm/study/demo/datastructure/linear/MLinkList.java b/src/main/java/com/algorithm/study/demo/datastructure/linear/MLinkList.java
@@ -12,7 +12,7 @@
  */
 public class MLinkList<E> {
     // 定义一个内部类Node，代表链表的节点
-    private class Node {
+    public class Node {
         private E value;// 保存数据
         private Node next;// 指向下个节点的引用
 
@@ -214,17 +214,17 @@ public void reverseLinkedList(){
         System.out.println("反转完毕");
     }
 
-
     public static void main(String[] args) {
-        MLinkList mLinkList=new MLinkList();
-        mLinkList.add("a");
-        mLinkList.add("b");
-        mLinkList.add("c");
-        mLinkList.add("d");
+        MLinkList<Integer> mLinkList=new MLinkList();
+        mLinkList.add(4);
+        mLinkList.add(1);
+        mLinkList.add(8);
+        mLinkList.add(4);
+        mLinkList.add(5);
 //        System.out.println(mLinkList.toString());
 //        mLinkList.delete("b");
-        mLinkList.delete(0);
-        System.out.println(mLinkList.size);
+//        mLinkList.delete(0);
+//        System.out.println(mLinkList.size);
 //        mLinkList.reverseLinkedList();
         System.out.println(mLinkList.toString());
 
diff --git a/src/main/java/com/algorithm/study/demo/datastructure/linear/Solution.java b/src/main/java/com/algorithm/study/demo/datastructure/linear/Solution.java
@@ -0,0 +1,64 @@
+package com.algorithm.study.demo.datastructure.linear;
+
+import org.omg.PortableInterceptor.INACTIVE;
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * @Author: liuxun
+ * @CreateDate: 2019/2/12 下午3:43
+ * @Version: 1.0
+ */
+public class Solution {
+    public static ListNode detectCycle(ListNode head) {
+        ListNode temp=head;
+        ListNode temp2=head;
+        while(temp!=null && temp.next.next!=null){
+            temp2=temp2.next.next;
+            temp=temp.next;
+            if (temp==temp2){
+                ListNode q = head;
+                while(temp2!=q){
+                    temp2=temp2.next;
+                    q=q.next;
+                }
+                return q;
+            }
+        }
+        return null;
+    }
+
+    public static void main(String[] args) {
+        ListNode head=new ListNode(3);
+        ListNode head0=new ListNode(1);
+
+        ListNode head1=new ListNode(2);
+        ListNode head2=new ListNode(-4);
+
+        head.next=head0;
+        head0.next=head1;
+        head1.next=head2;
+        head2.next=head1;
+//        head1.next=head2;
+//        head2.next=head3;
+//        head3.next=head1;
+        ListNode c=Solution.detectCycle(head);
+        System.out.println(c==null?-1:1);
+
+
+    }
+    public boolean containsDuplicate(int[] nums) {
+        if(nums==null || nums.length<2){
+            return false;
+        }
+        Arrays.sort(nums);
+        for(int i=0;i<nums.length-1;i++){
+            if (nums[i]==nums[i+1]){
+                return true;
+            }
+        }
+        return false;
+    }
+}
