2020-4-13

617076674 · 617076674 · commit 6956565acea3 · 2020-04-13T10:22:11.000+08:00
diff --git a/question_linked_list_cycle_lcci/ListNode.java b/question_linked_list_cycle_lcci/ListNode.java
@@ -0,0 +1,11 @@
+package question_linked_list_cycle_lcci;
+
+public class ListNode {
+    int val;
+
+    ListNode next;
+
+    ListNode(int x) {
+        val = x;
+    }
+}
diff --git a/question_linked_list_cycle_lcci/Solution.java b/question_linked_list_cycle_lcci/Solution.java
@@ -0,0 +1,27 @@
+package question_linked_list_cycle_lcci;
+
+/**
+ * https://leetcode-cn.com/problems/linked-list-cycle-lcci/
+ *
+ * 时间复杂度是O(n)，其中n为链表中的节点个数。空间复杂度是O(1)。
+ *
+ * 执行用时：0ms，击败100.00%。消耗内存：39.7MB，击败100.00%。
+ */
+public class Solution {
+    public ListNode detectCycle(ListNode head) {
+        ListNode cur1 = head, cur2 = head;
+        do {
+            if (cur2 == null || cur2.next == null) {
+                return null;
+            }
+            cur1 = cur1.next;
+            cur2 = cur2.next.next;
+        } while (cur1 != cur2);
+        cur1 = head;
+        while (cur1 != cur2) {
+            cur1 = cur1.next;
+            cur2 = cur2.next;
+        }
+        return cur1;
+    }
+}
diff --git a/question_min_stack_lcci/MinStack.java b/question_min_stack_lcci/MinStack.java
@@ -0,0 +1,40 @@
+package question_min_stack_lcci;
+
+import java.util.Stack;
+
+/**
+ * https://leetcode-cn.com/problems/min-stack-lcci/
+ *
+ * 执行用时：19ms，击败77.11%。消耗内存：41.7MB，击败100.00%。
+ */
+public class MinStack {
+    private Stack<Integer> stack1, stack2;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+        stack1 = new Stack<>();
+        stack2 = new Stack<>();
+    }
+    
+    public void push(int x) {
+        stack1.push(x);
+        if (stack2.isEmpty()) {
+            stack2.push(x);
+        } else {
+            stack2.push(Math.min(x, stack2.peek()));
+        }
+    }
+    
+    public void pop() {
+        stack1.pop();
+        stack2.pop();
+    }
+    
+    public int top() {
+        return stack1.peek();
+    }
+    
+    public int getMin() {
+        return stack2.peek();
+    }
+}
diff --git a/question_three_in_one_lcci/TripleInOne.java b/question_three_in_one_lcci/TripleInOne.java
@@ -0,0 +1,40 @@
+package question_three_in_one_lcci;
+
+/**
+ * https://leetcode-cn.com/problems/three-in-one-lcci/
+ *
+ * 执行用时：12ms，击败99.73%。消耗内存：48.9MB，击败100.00%。
+ */
+public class TripleInOne {
+    private int[] nums, curs;
+
+    public TripleInOne(int stackSize) {
+        nums = new int[3 * stackSize];
+        curs = new int[] {0, stackSize, 2 * stackSize};
+    }
+
+    public void push(int stackNum, int value) {
+        if (curs[stackNum] == (stackNum + 1) * nums.length / 3) {
+            return;
+        }
+        nums[curs[stackNum]++] = value;
+    }
+
+    public int pop(int stackNum) {
+        if (isEmpty(stackNum)) {
+            return -1;
+        }
+        return nums[--curs[stackNum]];
+    }
+
+    public int peek(int stackNum) {
+        if (isEmpty(stackNum)) {
+            return -1;
+        }
+        return nums[curs[stackNum] - 1];
+    }
+
+    public boolean isEmpty(int stackNum) {
+        return curs[stackNum] == stackNum * nums.length / 3;
+    }
+}
