algorithm004-01 · melody-li · Oct 21, 2019 · Oct 14, 2019 · Oct 17, 2019 · Oct 18, 2019
diff --git a/Week 01/id_586/11-container-with-most-water.c b/Week 01/id_586/11-container-with-most-water.c
@@ -0,0 +1,45 @@
+int maxArea(int* height, int heightSize){
+#if 0
+    /* 1. 暴力求解 */
+    int i = 0;
+    int j = 0;
+    int max = 0;
+    int area = 0;
+    int h = 0;
+
+    for (; i < heightSize; i++) {
+        for (j = i + 1; j < heightSize; j++) {
+            h = (height[i] < height[j] ? height[i] : height[j]);
+            area = (j - i) * h;
+            if (max < area)
+                max = area;
+        }
+    }
+
+    return max;
+#else
+    /* 双指针法 */
+    /* 重点在于理解双指针的移动，每次都移动较短的指针 */
+
+    int i = 0;
+    int j = heightSize - 1;
+
+    int max = 0;
+    int area = 0;
+    int h = 0;
+
+    while (i < j) {
+        h = (height[i] < height[j] ? height[i] : height[j]);
+        area = (j - i) * h;
+        if (max < area) max = area;
+        //if (height[i] < height[j])
+        //    i++;
+        // else
+        //    j--;
+        while ((height[i] <= h) && i < j) i++;
+        while ((height[j] <= h) && i < j) j--;
+    }
+
+    return max;
+#endif
+}
diff --git a/Week 01/id_586/141-linked-list-cycle.c b/Week 01/id_586/141-linked-list-cycle.c
@@ -0,0 +1,32 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     struct ListNode *next;
+ * };
+ */
+
+/*
+ * 使用的是快慢指针的方法
+ * */
+bool hasCycle(struct ListNode *head) {
+    struct ListNode *slow = head;
+    struct ListNode *fast = head;
+
+    if (!head || !head->next) return 0;
+
+    while (slow && fast) {
+        slow = slow->next;
+        fast = fast->next;
+
+        if (!fast)
+            return 0;
+
+        fast = fast->next;
+
+        if (slow == fast)
+            return 1;
+    }
+
+    return 0;
+}
diff --git a/Week 01/id_586/142-linked-list-cycle-ii.c b/Week 01/id_586/142-linked-list-cycle-ii.c
@@ -0,0 +1,44 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     struct ListNode *next;
+ * };
+ */
+struct ListNode *detectCycle(struct ListNode *head) {
+    if (head == NULL || head->next == NULL)
+        return NULL;
+
+    struct ListNode *fast = head;
+    struct ListNode *slow = head;
+    struct ListNode *meet = NULL;
+
+    while (fast) {
+        slow = slow->next;
+        fast = fast->next;
+
+        if (!fast) {
+            return false;
+        }
+
+        fast = fast->next;
+
+        if (fast == slow) {
+            meet = fast;
+            break;
+        }
+    }
+
+    if (meet == NULL)
+        return NULL;
+
+    while (head && meet) {
+        if (head == meet) {
+            return head;
+        }
+        head = head->next;
+        meet = meet->next;
+    }
+
+    return NULL;
+}
diff --git a/Week 01/id_586/206-reverse-linked-list.c b/Week 01/id_586/206-reverse-linked-list.c
@@ -0,0 +1,24 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     struct ListNode *next;
+ * };
+ */
+
+/* 1. 使用一个 new_head 作为翻转链表的头指针的，遍历给定的链表，
+ * 2. 把遍历的元素使用头插的方法，插入链表，
+ * 3. 返回 new_head */
+struct ListNode* reverseList(struct ListNode* head){
+    struct ListNode *new_head = NULL;
+
+    while (head) {
+        struct ListNode *tmp = head;
+        head = head->next;
+        tmp->next = new_head;
+        new_head = tmp;
+    }
+
+    return new_head;
+}
+
diff --git a/Week 01/id_586/21-merge-two-sorted-lists.c b/Week 01/id_586/21-merge-two-sorted-lists.c
@@ -0,0 +1,35 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     struct ListNode *next;
+ * };
+ */
+
+
+struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
+    if (!l1) return l2;
+    if (!l2) return l1;
+
+    struct ListNode dummy;
+    struct ListNode *prev = &dummy;
+
+    while (l1 && l2) {
+        if (l1->val < l2->val) {
+            prev->next = l1;
+            l1 = l1->next;
+        } else {
+            prev->next = l2;
+            l2 = l2->next;
+        }
+
+        prev = prev->next;
+    }
+
+    if (l1)
+        prev->next = l1;
+    if (l2)
+        prev->next = l2;
+
+    return dummy.next;
+} 
diff --git a/Week 01/id_586/24-swap-nodes-in-pairs.c b/Week 01/id_586/24-swap-nodes-in-pairs.c
@@ -0,0 +1,39 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     struct ListNode *next;
+ * };
+ */
+
+/*
+ * 1. 先保存需要替换的指向的内容
+ * 2. 依次修改指针个指向
+ * 3. 调整新的头节点
+ * */
+struct ListNode* swapPairs(struct ListNode* head){
+    struct ListNode dummy;
+    struct ListNode *prev;
+    struct ListNode* n1 = NULL;
+    struct ListNode* n2 = NULL;
+    struct ListNode* last = NULL;
+
+    dummy.next = head;
+    prev = &dummy;
+
+    while (head && head->next) {
+        n1 = head;
+        n2 = head->next;
+        last = head->next->next;
+
+        prev->next = n2;
+        n2->next = n1;
+        n1->next = last;
+
+        prev = n1;
+        head = last;
+    }
+
+    return dummy.next;
+}
+
diff --git a/Week 01/id_586/26-remove-duplicates-from-sorted-array.c b/Week 01/id_586/26-remove-duplicates-from-sorted-array.c
@@ -0,0 +1,18 @@
+/* 双指针法:
+ *  两个指针 ii 和 jj，其中 ii 是慢指针，而 jj 是快指针。只要 nums[i] = nums[j]nums[i]=nums[j]，我们就增加 jj 以跳过重复项
+ */
+int removeDuplicates(int* nums, int numsSize){
+    if (numsSize <= 0) return 0;
+
+    int i = 0;
+    int j = 0;
+
+    for (j = 1; j < numsSize; j++) {
+        if (nums[i] != nums[j]) {
+            i++;
+            nums[i] = nums[j];
+        }
+    }
+
+    return i + 1;
+}
diff --git a/Week 01/id_586/42-trapping-rain-water.cc b/Week 01/id_586/42-trapping-rain-water.cc
@@ -0,0 +1,39 @@
+class Solution {
+public:
+/*
+我们可以不用像方法 2 那样存储最大高度，而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。
+
+我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 \text{ans}ans 。
+
+算法
+
+使用栈来存储条形块的索引下标。
+遍历数组：
+当栈非空且 height[current]>height[st.top()]
+意味着栈中元素可以被弹出。弹出栈顶元素 top。
+计算当前元素和栈顶元素的距离，准备进行填充操作
+distance=current−st.top()−1
+找出界定高度
+bounded_height=min(height[current],height[st.top()])−height[top]
+往答案中累加积水量 ans+=distance×bounded_height
+将当前索引下标入栈
+将 current 移动到下个位置
+*/
+    int trap(vector<int>& height) {
+        int ans = 0, current = 0;
+        stack<int> st;
+        while (current < height.size()) {
+            while (!st.empty() && height[current] > height[st.top()]) {
+                int top = st.top();
+                st.pop();
+                if (st.empty())
+                    break;
+                int distance = current - st.top() - 1;
+                int bounded_height = min(height[current], height[st.top()]) - height[top];
+                ans += distance * bounded_height;
+            }
+            st.push(current++);
+        }
+        return ans;
+    }
+};
diff --git a/Week 01/id_586/641-design-circular-deque.cc b/Week 01/id_586/641-design-circular-deque.cc
@@ -0,0 +1,91 @@
+class MyCircularDeque {
+private:
+    vector<int> buffer;
+    int cnt;
+    int k;
+    int front;
+    int rear;
+public:
+    /** Initialize your data structure here. Set the size of the deque to be k. */
+    MyCircularDeque(int k) : buffer(k, 0), cnt(0), k(k), front(k - 1), rear(0) {
+    }
+
+    /** Adds an item at the front of Deque. Return true if the operation is successful. */
+    bool insertFront(int value) {
+        if (cnt == k) return false;
+
+        buffer[front] = value;
+        front = (front - 1 + k) % k;
+        ++cnt;
+
+        return true;
+    }
+
+    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
+    bool insertLast(int value) {
+        if (cnt == k) return false;
+
+        buffer[rear] = value;
+        rear = (rear + 1) % k;
+        ++cnt;
+
+        return true;
+    }
+
+    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
+    bool deleteFront() {
+        if (cnt == 0) return false;
+
+        front = (front + 1) % k;
+        --cnt;
+
+        return true;
+    }
+
+    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
+    bool deleteLast() {
+        if (cnt == 0) return false;
+
+        rear = (rear - 1 + k) % k;
+        --cnt;
+
+        return true;
+    }
+
+    /** Get the front item from the deque. */
+    int getFront() {
+        if (cnt == 0) return -1;
+
+        return buffer[(front + 1) % k];
+    }
+
+    /** Get the last item from the deque. */
+    int getRear() {
+        if (cnt == 0) return -1;
+
+        return buffer[(rear - 1 + k) % k];
+    }
+
+    /** Checks whether the circular deque is empty or not. */
+    bool isEmpty() {
+        return cnt == 0;
+    }
+
+    /** Checks whether the circular deque is full or not. */
+    bool isFull() {
+        return cnt == k;
+    }
+};
+
+/**
+ * Your MyCircularDeque object will be instantiated and called as such:
+ * MyCircularDeque* obj = new MyCircularDeque(k);
+ * bool param_1 = obj->insertFront(value);
+ * bool param_2 = obj->insertLast(value);
+ * bool param_3 = obj->deleteFront();
+ * bool param_4 = obj->deleteLast();
+ * int param_5 = obj->getFront();
+ * int param_6 = obj->getRear();
+ * bool param_7 = obj->isEmpty();
+ * bool param_8 = obj->isFull();
+ */