algorithm004-01 · melody-li · Oct 21, 2019 · Oct 19, 2019
diff --git a/Week 01/id_011/design-circular-deque.go b/Week 01/id_011/design-circular-deque.go
@@ -0,0 +1,125 @@
+package algorithm00401
+
+type MyCircularDeque struct {
+	len, cap    int
+	front, rear *node
+}
+
+type node struct {
+	val        int
+	prev, next *node
+}
+
+/** Initialize your data structure here. Set the size of the deque to be k. */
+func Constructor(k int) MyCircularDeque {
+	return MyCircularDeque{
+		cap: k,
+	}
+}
+
+/** Adds an item at the front of Deque. Return true if the operation is successful. */
+func (this *MyCircularDeque) InsertFront(value int) bool {
+	if this.IsFull() {
+		return false
+	}
+	n := &node{
+		val: value,
+	}
+	if this.IsEmpty() {
+		this.front, this.rear = n, n
+	} else {
+		n.next = this.front
+		this.front.prev = n
+		this.front = n
+	}
+	this.len++
+	return true
+}
+
+/** Adds an item at the rear of Deque. Return true if the operation is successful. */
+func (this *MyCircularDeque) InsertLast(value int) bool {
+	if this.IsFull() {
+		return false
+	}
+	n := &node{
+		val: value,
+	}
+	if this.IsEmpty() {
+		this.front, this.rear = n, n
+	} else {
+		n.prev = this.rear
+		this.rear.next = n
+		this.rear = n
+	}
+	this.len++
+	return true
+}
+
+/** Deletes an item from the front of Deque. Return true if the operation is successful. */
+func (this *MyCircularDeque) DeleteFront() bool {
+	if this.IsEmpty() {
+		return false
+	}
+	if this.len == 1 {
+		this.front, this.rear = nil, nil
+	} else {
+		this.front = this.front.next
+		this.front.prev = nil
+	}
+	this.len--
+	return true
+}
+
+/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
+func (this *MyCircularDeque) DeleteLast() bool {
+	if this.IsEmpty() {
+		return false
+	}
+	if this.len == 1 {
+		this.front, this.rear = nil, nil
+	} else {
+		this.rear = this.rear.prev
+		this.rear.next = nil
+	}
+	this.len--
+	return true
+}
+
+/** Get the front item from the deque. */
+func (this *MyCircularDeque) GetFront() int {
+	if this.IsEmpty() {
+		return -1
+	}
+	return this.front.val
+}
+
+/** Get the last item from the deque. */
+func (this *MyCircularDeque) GetRear() int {
+	if this.IsEmpty() {
+		return -1
+	}
+	return this.rear.val
+}
+
+/** Checks whether the circular deque is empty or not. */
+func (this *MyCircularDeque) IsEmpty() bool {
+	return this.len == 0
+}
+
+/** Checks whether the circular deque is full or not. */
+func (this *MyCircularDeque) IsFull() bool {
+	return this.len == this.cap
+}
+
+/**
+ * Your MyCircularDeque object will be instantiated and called as such:
+ * obj := Constructor(k);
+ * param_1 := obj.InsertFront(value);
+ * param_2 := obj.InsertLast(value);
+ * param_3 := obj.DeleteFront();
+ * param_4 := obj.DeleteLast();
+ * param_5 := obj.GetFront();
+ * param_6 := obj.GetRear();
+ * param_7 := obj.IsEmpty();
+ * param_8 := obj.IsFull();
+ */
diff --git a/Week 01/id_011/merge-sorted-array.go b/Week 01/id_011/merge-sorted-array.go
@@ -0,0 +1,22 @@
+package algorithm00401
+
+func merge(nums1 []int, m int, nums2 []int, n int) {
+	i := m + n - 1
+	m--
+	n--
+
+	for m >= 0 && n >= 0 {
+		if nums1[m] > nums2[n] {
+			nums1[i] = nums1[m]
+			m--
+		} else {
+			nums1[i] = nums2[n]
+			n--
+		}
+		i--
+	}
+	for n >= 0 {
+		nums1[n] = nums2[n]
+		n--
+	}
+}
diff --git a/Week 01/id_011/merge-two-sorted-lists.go b/Week 01/id_011/merge-two-sorted-lists.go
@@ -0,0 +1,11 @@
+package algorithm00401
+
+func mergeTwoLists(l1, l2 *ListNode) *ListNode {
+	if l1 == nil || (l2 != nil && l1.Val > l2.Val) {
+		l1, l2 = l2, l1
+	}
+	if l1 != nil {
+		l1.Next = mergeTwoLists(l1.Next, l2)
+	}
+	return l1
+}
diff --git a/Week 01/id_011/move-zeroes.go b/Week 01/id_011/move-zeroes.go
@@ -0,0 +1,13 @@
+package algorithm00401
+
+func moveZeroes(nums []int) {
+	k := 0
+	for i := 0; i < len(nums); i++ {
+		if nums[i] != 0 {
+			if k != i {
+				nums[i], nums[k] = nums[k], nums[i]
+			}
+			k++
+		}
+	}
+}
diff --git a/Week 01/id_011/plus-one.go b/Week 01/id_011/plus-one.go
@@ -0,0 +1,15 @@
+package algorithm00401
+
+func plusOne(digits []int) []int {
+	for i := len(digits); i >= 0; i-- {
+		digits[i]++
+		digits[i] %= 10
+		if digits[i] != 0 {
+			return digits
+		}
+	}
+
+	digits = make([]int, len(digits)+1)
+	digits[0] = 1
+	return digits
+}
diff --git a/Week 01/id_011/remove-duplicates-from-sorted-array.go b/Week 01/id_011/remove-duplicates-from-sorted-array.go
@@ -0,0 +1,12 @@
+package algorithm00401
+
+func removeDuplicates(nums []int) int {
+	i := 0
+	for j := 0; j < len(nums); j++ {
+		if nums[i] != nums[j] {
+			i++
+			nums[i] = nums[j]
+		}
+	}
+	return i + 1
+}
diff --git a/Week 01/id_011/rotate-array.go b/Week 01/id_011/rotate-array.go
@@ -0,0 +1,16 @@
+package algorithm00401
+
+func rotate(nums []int, k int) {
+	k %= len(nums)
+	reverse(nums, 0, len(nums)-1)
+	reverse(nums, 0, k-1)
+	reverse(nums, k, len(nums)-1)
+}
+
+func reverse(nums []int, i, j int) {
+	for i < j {
+		nums[i], nums[j] = nums[j], nums[i]
+		i++
+		j--
+	}
+}
diff --git a/Week 01/id_011/two-sum.go b/Week 01/id_011/two-sum.go
@@ -0,0 +1,30 @@
+package algorithm00401
+
+// 对撞指针解法
+func twoSum2(numbers []int, target int) []int {
+	l, r := 0, len(numbers)-1
+	for l < r {
+		if numbers[l]+numbers[r] == target {
+			return []int{l, r}
+		} else if numbers[l]+numbers[r] > target {
+			r--
+		} else {
+			l++
+		}
+	}
+	return nil
+}
+
+// hash 解法
+func twoSum(numbers []int, target int) []int {
+	memo := make(map[int]int)
+	for i := 0; i < len(numbers); i++ {
+		sub := target - nums[i]
+		if j, ok := memo[sub]; ok {
+			return []int{j, i}
+		} else {
+			memo[nums[i]] = i
+		}
+	}
+	return nil
+}