LeetCode155（最小栈）

发表于 2019-07-09 | 分类于算法， LeetCode

题目：

　　设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
　　push(x) – 将元素 x 推入栈中。
　　pop() – 删除栈顶的元素。
　　top() – 获取栈顶元素。
　　getMin() – 检索栈中的最小元素。

思路：

　　需要维护一个辅助栈，使该辅助栈的栈顶元素保持为栈的最小元素。

代码：

class MinStack {
	Deque<Integer> stack1;
	Deque<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void push(int x) {
        stack1.push(x);
        if (stack2.isEmpty()) {
			stack2.push(x);
		}else if (stack2.peek() < x) {
			stack2.push(stack2.peek());
		}else {
			stack2.push(x);
		}
    }
    
    public void pop() {
    	// 最好加入空指针处理
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int getMin() {
        return stack2.peek();
    }
}

复杂度分析及总结：

　　时间复杂度：
　　　　O(1)。
　　空间复杂度：
　　　　O(n)。辅助栈需要大小为n的空间。

LeetCode148（排序链表）

发表于 2019-07-08 | 分类于算法， LeetCode

题目：

　　在O(nlogn)时间复杂度和常数级空间复杂度下，对链表进行排序。

思路：

　　时间复杂度为O(nlogn)，想到归并排序，但空间复杂度为常数级仍然存疑。

代码：

public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
			return head;
		}
        ListNode mid = getMid(head);
        ListNode right = mid.next;
        mid.next = null;
        return merge(sortList(head), sortList(right));
    }
	public ListNode getMid(ListNode head) {
		ListNode fastNode = head;
		ListNode slowNode = head;
		while(fastNode.next != null && fastNode.next.next != null) {
			fastNode = fastNode.next.next;
			slowNode = slowNode.next;
		}
		return slowNode;
	}
	public ListNode merge(ListNode head1,ListNode head2) {
		ListNode node1 = head1;
		ListNode node2 = head2;
		ListNode head;
		if (node1.val < node2.val) {
			head = node1;
			node1 = node1.next;
		}else {
			head = node2;
			node2 = node2.next;
		}
		ListNode node = head;
		while(node1 != null && node2 != null) {
			if (node1.val < node2.val) {
				node.next = node1;
				node1 = node1.next;
			}else {
				node.next = node2;
				node2 = node2.next;
			}
			node = node.next;
		}
		if (node1 != null) {
			node.next = node1;
		}
		if (node2 != null) {
			node.next = node2;
		}
		return head;
	}

复杂度分析及总结：

时间复杂度：
　　O(nlogn)。与数组的归并排序类似。
空间复杂度：
　　O(logn)。由于链表的归并排序不需要用到临时空间，故而起所需的空间仅仅为递归栈所消耗的空间。

排序算法总结

发表于 2019-07-08 | 分类于算法，算法杂谈

一、

思路：

　　归并排序是分治法和递归的典型应用。归并排序分为两种实现方法：自顶向下和自底向上。自顶向下先归后并，即先将待排序数组递归分割，然后将分割后的数组进行合并排序；而自底向上没有使用递归，而是直接使用迭代“手动”进行分割，然后进行合并排序。自底向上由于没有使用递归，减少了栈空间的使用。

代码：

top to bottom:

public static void mergeSort(int[] arr) {
		int low = 0;
		int high = arr.length - 1;
		split(arr, low, high);
	}
	public static void split(int[] arr,int low,int high) {
		if (low < high) {
			int mid = (low + high)/2;
			split(arr, low, mid);
			split(arr, mid+1, high);
			merge(arr, low, mid, high);
		}
	}
	public static void merge(int [] arr,int low,int mid,int high) {
		int[] temp = new int[high - low + 1];
		int k = 0;
		int i = low;
		int j = mid + 1;
		while(i <= mid && j <= high) {
			if (arr[i] < arr[j]) {
				temp[k++] = arr[i++];
			}else {
				temp[k++] = arr[j++];
			}
		}
		while(i <= mid) {
			temp[k++] = arr[i++];
		}
		while(j <= high) {
			temp[k++] = arr[j++];
		}
		for(int l = low;l <= high;l++) {
			arr[l] = temp[l-low];
		}
	}

bottom to top：

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
public void mergeSort1(int[] arr) {
	if (arr == null || arr.length == 0) {
		return;
	}
	int k = 1;
	while(k < arr.length) {
		mergePass(arr, k);
		k = k*2;
	}
}
public void mergePass(int[] arr,int k) {
	int start = 0;
	while(start + 2*k - 1 < arr.length) {
		int mid = start + k -1;
		int high = start + 2*k - 1;
		merge(arr, start, mid, high);
		start = start + 2*k;
	}
	if (start + k - 1 < arr.length) {
		merge(arr, start, start + k - 1, arr.length - 1);
	}
}
public static void merge(int[] arr,int low,int mid,int high) {
	int[] temp = new int[high-low+1];
	int i = low;
	int j = mid+1;
	int m = 0;
	while(i <= mid && j<=high) {
		if (arr[i] <= arr[j]) {
			temp[m++] = arr[i++];
		}else {
			temp[m++] = arr[j++];
		}
	}
	while(i <= mid) {
		temp[m++] = arr[i++];
	}
	while(j <= high) {
		temp[m++] = arr[j++];
	}
	for(int k = 0;k < temp.length;k++) {
		arr[k+low] = temp[k];
	}
}

复杂度分析及总结：

时间复杂度：
　　O(nlogn)。由于递归深度为logn，每层递归需要进行n次比较，所以时间复杂度为O(nlogn)。
空间复杂度：
　　O(n)。由于递归深度为logn，且在合并时会创建大小为n的临时数组，所以空间复杂度为O(n)+O(logn)，即O(n)。

参考文献：

　　《大话数据结构》
　　https://www.cnblogs.com/yongh/p/9965913.html

LeetCode141(判断是否为环形链表)

发表于 2019-07-07 | 分类于算法， LeetCode

题目：

　　给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从0开始）。如果 pos 是 -1，则在该链表中没有环。

思路：

　　典型的双指针问题，同时也可以利用额外空间来解决此问题。

代码：

1.双指针

public boolean hasCycle(ListNode head) {
       ListNode fastNode = head;
       ListNode slowNode = head;
       while(fastNode != null && slowNode != null && fastNode.next != null) {
       	fastNode = fastNode.next.next;
       	slowNode = slowNode.next;
       	if (fastNode == slowNode) {
			return true;
		}
       }
       return false;
   }

2.利用Set（暂时不给出）

第一篇博客

发表于 2019-07-05

HelloWorld!