001 基础
- 多块代码合在一起,只看最高复杂度的运算
- 时间复杂度
- 常数次数,1,2,3---,时间复杂度都是O(1)
- n,2n,3n---,常数*n次,时间复杂度都是O(n)
- 常见递归算法时间复杂度
- 二分查找 时间复杂度是 O(logn)
- 二叉树遍历 时间复杂度是 O(n)
- 排序查找 时间复杂度是 O(n)
- 快排,归并排序 时间复杂度是 O(nlogn)
002 数组及链表
数组
- 数组是内存里连续的一段存储区域.通过数组下标可以随机的访问任意一个元素.
- 访问任意数组元素的时间复杂度是O(1)
- 为了保证数组元素在内存中的连续性,插入和删除数组元素,时间复杂度是O(n)
链表
- 单链表
- 双链表
- 插入和删除的时间复杂度是O(1)
- 查找的时间复杂度是O(n),因为必须从链表头部遍历查找
003 几道题
反转单链表
Assume that we have linked list 1 > 2 > 3 > 0, we would like to change it to 0 > 1 > 2 > 3.
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode curr = head.next;
head.next = null;
while(curr != null){
ListNode nextTemp = curr.next;
curr.next = head;
head = curr;
curr = nextTemp;
}
return head;
}
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
官方答案分析:
反转最终结果是原始第一节点的next=null;然后原始第二节点的next是原始第一节点----
想象原始第一节点左边1个虚拟的节点prev=null.
这样反转,则原始第一节点的next变为prev,原始第二节点的next变为原始第一节点----
两两交换单链表中的节点/Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
Given 1->2->3->4, you should return the list as 2->1->4->3.
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode result = head.next;
ListNode curr = head;
ListNode prev = null;
while(curr != null && curr.next != null){
ListNode currTemp = curr.next.next;
if(prev != null){
prev.next = curr.next;
}
curr.next.next = curr;
curr.next = currTemp;
prev = curr;
curr = currTemp;
}
return result;
}
}
判断链表是否有环/Linked List Cycle
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos
which represents the position (0-indexed) in the linked list where tail connects to.
If pos is -1, then there is no cycle in the linked list.
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<ListNode>();
while(head != null){
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode curr = head;
Map<ListNode,Boolean> map = new HashMap<ListNode,Boolean>();
while(curr != null){
if(map.get(curr) != null){
return true;
}
map.put(curr,true);
curr = curr.next;
}
return false;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<ListNode>();
while(head != null){
if(!set.add(head)){
return head;
}
head = head.next;
}
return null;
}
}
Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isGroup(ListNode item, int k){
for(int i=0;i<k;i++){
if(item == null) return false;
item = item.next;
}
return true;
}
public ListNode[] reverseCurrGroup(ListNode prev,ListNode group,int k){
ListNode curr = group;
ListNode first = null;
ListNode last = null;
for(int i=0;i<k;i++){
ListNode next = curr.next;
curr.next = first;
first = curr;
curr = next;
}
if(prev != null){
prev.next = first;
}
return new ListNode[]{first,group,curr};
}
public ListNode reverseKGroup(ListNode head, int k) {
if(isGroup(head,k)){
ListNode[] nodes = reverseCurrGroup(null,head,k);
ListNode result = nodes[0];
ListNode prev = nodes[1];
ListNode group = nodes[2];
while(isGroup(group,k)){
nodes = reverseCurrGroup(prev,group,k);
prev = nodes[1];
group = nodes[2];
}
if(prev != null){
prev.next = group;
}
return result;
}else{
return head;
}
}
}
004 栈和队列
- 栈是先进后出
- 队列是先进先出
- 优先队列 PriorityQueue
- 正常入,按照优先级出
- 优先队列实现机制:了解即可
- 用堆(二叉堆 Binary heap,多项式堆 Binomial heap,斐波那契堆 Fibonacci heap)来实现
- 二叉搜索树 Binary Search Tree
- 堆本身的实现有很多
- 堆寻找最高优先级/最大最小元素的效率都比较高,衡量一个堆的性能要看 插入,删除,合并操作的性能
- 二叉堆维护效率很差
- 在java/python中实际使用的堆是斐波拉契堆 或者 使用二叉树来实现
用栈实现队列/Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
class MyQueue {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
public MyQueue() {
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.empty() && s2.empty();
}
}
用队列实现栈/Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
class MyStack {
LinkedList<Integer> q = new LinkedList<Integer>();
public MyStack() {
}
public void push(int x) {
int size = q.size();
q.add(x);
while(size-- > 0){
q.add(q.poll());
}
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.size() == 0;
}
}
005
流式数据中寻找第K大的元素
- 对K个元素进行排序,最佳排序方法是快排,时间复杂度是O(KlogK)
- 优先队列对元素进行自动排序,时间复杂度是 O(logk)
- 在N个元素中寻找第K大的元素
- 方法1.保存K个元素,然后每个新元素和K个中的最小值比较,替换并重新排序
- 如果先保存K个元素,然后进行排序.时间复杂度是 O(klogk)
- 以后每个新元素都和之前保存的K个元素进行比较,大于其中最小的元素min,就将min移除,然后将新元素加入并排序.也就是每一次都需要重新排序.
- 总体时间复杂度是 O(Nklogk)
- 方法2.使用优先队列
- 在java中,优先队列是使用斐波拉契堆实现
- 使用优先队列,保持优先队列中元素数量为K
- 每个新元素和优先队列中最小的进行比较
- 比堆顶元素小,则略过
- 比堆顶元素大,咋删除堆顶元素,将新元素加入优先队列,优先队列会自动进行排序
- 最后返回堆顶元素即可
- 优先队列自动排序时间复杂度是O(logk)
- 总体时间复杂度是 O(Nlogk)
- 由此可见,使用优先队列时间复杂度低,比使用快排整整降低了k倍.
Kth Largest Element in a Stream
Design a class to find the kth largest element in a stream. Note that it is the kth largest
element in the sorted order, not the kth distinct element.
Your KthLargest class will have a constructor which accepts an integer k and an integer array nums,
which contains initial elements from the stream. For each call to the method
KthLargest.add, return the element representing the kth largest element in the stream.
class KthLargest {
PriorityQueue<Integer> queue;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
this.queue = new PriorityQueue<Integer>(k);
for(int val : nums){
add(val);
}
}
public int add(int val) {
if(queue.size() < k){
queue.offer(val);
}else if(queue.peek() < val){
queue.poll();
queue.offer(val);
}
return queue.peek();
}
}
