数据结构及算法遗忘知识点.md · zhusir/interviewDoc

## 排序
#### 时间/空间复杂度
时间复杂度：logN
空间复杂度：logN

#### 代码实现

public static void quickSort(int[] num, int start, int end) {
	//健壮性
        if (start < end && start >= 0 && end <= num.length - 1) {
            int left = start;
            int right = end;
            int base = num[left];

while (left < right) {
                while (left < right && num[right] >= base) right--;
                num[left] = num[right];

while (left < right && num[left] <= base) left++;
                num[right] = num[left];

num[left] = base;
                //目前指针指在left
                quickSort(num, start, left - 1);
                quickSort(num, left + 1, end);
            }
        }
    }

适用场景：

- **数据量大**
- 待排序数据是**无序**的
- 但是它是不稳定的，如果需要稳定，则使用归并排序

### 三向快排
快排存在的问题：   
实际使用中，数组内会有很多**重复**的元素，按理来说快排递归到某一步，它的子数组内元素相等，其实就不用排序了，但是快排依旧会递归，三向快排就是为了解决这个问题，可以将时间复杂度从O(Nlogn)降到**线性级别O(N)**，它将数组分为三个区域：

- lt:表示小于基准元素
- et:表示**等于**基准元素
- gt:表示大于基准元素

### 归并排序
归并的思想：将数组一分为二，使左边有序，右边也有序，再把左右两边组合起来，一直递归，递归的到数列只有一个元素就认为是有序的

归并：归，即递归，递归的调用自己，实现左边有序和右边有序，并，即合并，使得排好序的两个数组合并  
两个数列合并的思路：  
	1.对比数列的第一个元素谁大谁小，将小的元素赋值给新的数组，再次比较  
	2.如果任何一个数列为空则把另一个数列的元素全部赋值到新数组的后面
归并排序的重点在于在合并两个数组的时候使用**System.arrayCopy()**

时间复杂度：logN
空间复杂度：N

#### 代码实现
	//这里的temp数组其实可以写在merge方法中，当作参数传递进来的目的是不再merge代码中重复创建对象，减少时间，内存消耗
	public static void mergeSort(int[] num, int left, int right,int[] temp) {
    if (left < right) {
        //mid的作用就是将一个数组分为两个部分
        int mid = (left + right) / 2;
        //将左边数组不断拆分
        mergeSort(num, left, mid,temp);
        //将右边数组不断拆分
        mergeSort(num, mid + 1, right,temp);

//左右归并
        merge(num, left, mid, right,temp);
	   	 }
	}

//目的是将两个数列合并
	public static void merge(int[] num, int left, int mid, int right,int[] temp) {
    int i = left,n = mid+1;

//临时数组下标
    int k = 0;

//选择两个数组中最小的,特别注意循环条件
    while (i <= mid && n <= right) {
        temp[k++] = num[i] <= num[n] ? num[i++] : num[n++];
    }

//左边不空，则将左边的全部赋值到temp
    while (i <= mid) {
        temp[k++] = num[i++];
    }

//右边不空
    while (n <= right) {
        temp[k++] = num[n++];
    }

//把临时数组中的值添加到原数组，这里是从left开始，相当于是数组合并
    System.arraycopy(temp, 0, num, left , k);
   	}

适用场景

- **算法要求稳定**
- 数据量较大

### 关于算法的时间复杂度及空间复杂度的记忆
排序算法的时间/空间复杂度及稳定性:  
![](http://zhusir.oss-cn-shenzhen.aliyuncs.com/interview/img/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%97%B6%E9%97%B4%3A%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6.png)
时间复杂度记忆：

- 冒泡，选择，插入排序需要两次for循环（第一遍找元素O(n),第二遍找位置O(n)）,所以时间复杂度是O(n^2 ) 
- 快排，归并，堆，希尔基于二分思想，以log2为底，平均时间复杂度为O(n * log(n))第一遍找元素（O（n））,第二遍找位置(logn)

### 堆排序
堆排序的思想：建立大根堆之后，由性质可知，堆顶元素是最大值，此时将堆顶元素与序列的最后一个元素互换，那么此序列的最后一个元素就是最大值，从而就是有序的，然后再调整前面n-1个，最终就是有序的

一共分两步：
1.构建大根堆
2.将堆顶元素与最后一个元素交换，再次调整堆

/**
         * 堆排序方法
         * @param a 待排序数组
         */
        public static void sort(int [] a) {
            // 堆的构造阶段
            int N = a.length;  // 取得节点总数
            for (int i = N / 2; i > 0; i--) {
                sink(a, i, N); // 对所有父节点，从最后一个父节点到根节点，依次下沉排序
            }  // 到这里数组已经完全堆有序
            // 下沉排序阶段
            while (N > 1) {
                exchange(a, 1, N); // 将数组中最大的元素放到数组后端
                N--; // 将最大的节点元素移出堆
                sink(a, 1, N); // 下沉操作，再次实现堆有序
            }
        }

* 下沉操作
         * @param a 待排序数组
         * @param k 堆中的节点位置
         * @param N 堆中的节点总数
         */
        private static void sink (int [] a, int k, int N) {
            while (2 * k <= N) { // 当该节点存在至少一个子节点的时候
                int j = 2 * k;  // 取得左儿子的位置
                if (j < N && less(a, j, j + 1)) {
                    j++;
                } // 取得左儿子和右儿子中的较大者
                if (less(a, k, j)) {  // 当该节点的值小于较大的左儿子的时候
                    exchange(a, k, j); // 交换它和该儿子节点的值
                    k = j; // 取得该儿子节点的位置
                } else {
                    break;
                }
            }
        }

## 栈
- 栈操作很多时候都需要**辅助栈**
- 栈的实现：递归

### 两个栈实现队列
- **入栈操作栈1，出栈操作栈2**
- 出栈时需要判断栈1是否为空，不为空则将元素加入栈2，最后操作栈2返回顶元素

//两个栈模拟一个队列
	    public class StackToQueue  {
	        Stack stack1 = new Stack<>();
	        Stack stack2 = new Stack<>();
	        //模拟push操作，入栈时直接压入Stack1
	        private void push(int value) {
	            stack1.push(value);
	        }
	           //模拟pop操作
	        private int pop() {
	            if (stack2.isEmpty()) {
	                while (!stack1.isEmpty()) {
	                    stack2.push(stack1.pop());       //Stack2为空，将Stack1的元素压入Stack2中
	                }
	            }
	            return stack2.pop();       //Stack2不空，将Stack2中的值弹出
	        }
	    }
    
## 给定一个入栈顺序，在给定一个出栈顺序，判断出栈顺序是否满足要求？

- **辅助栈**
- 使用**peek**判断元素是否相等，相等再使用pop移除元素
- 当**peek相等**时需要**循环**，因为可能连续出栈
	
		public boolean isAccess(int[] push,int[] order) {
		//使用辅助栈
		Stack<Interge> stack = new Stack<Interge>();
		
		//出栈顺序比较的下标
		int index = 0;
		for(int num : push) {
			//不满足比较条件时入栈
			stack.push(num);
			while(!stack.isEmpty() && stack.peek()== pop[index]) {
			stack.pop();
			index++;
			}	
		}
		return stack.isEmpty;	
	}

## 队列

### 两个队列实现一个栈
- 添加时只向队列1添加,移出时也是弹出队列1的队首(队列2不存储元素)
- 弹出时将队列2作为**中转栈**，将队列1的元素size - 1全部移到队列2，然后弹出最后一个元素，然后再将移入队列2的元素移回队列1

public class MyStack {
	
	    private Queue<Integer> queue1 = new LinkedList<Integer>();
	    private Queue<Integer> queue2 = new LinkedList<Integer>();
	    private int top;
	    public MyStack() {
	    }
	
	    public void push(int x) {
	        queue1.add(x);
	        top = x;
	    }
	
	    public int pop() {
	        int length = queue1.size();

for (int i = 1; i < length; i++) {
            queue2.add(queue1.poll());
        }
        int result = queue1.poll();

for (int i = 0; i < length; i++) {
            queue1.add(queue2.poll());
        }
        return result;
	    }
	
	    public int top() {
	        return top;
	    }
	
	    public boolean empty() {
	        return queue1.isEmpty() && queue2.isEmpty();
	    }
		}

### 一个队列实现栈
- 在添加时需要将刚刚添加的数移到队首，这样pop的是队首元素，即栈顶元素  
		class MyStack {
	
	    private Queue<Integer> queue = new LinkedList<>();
	
	    public void push(int x) {
	        queue.add(x);
	        **for (int i=1; i<queue.size(); i++)
	            queue.add(queue.remove());
	    }**
	    //1，2，3，4 --> 4,1,2,3-->4为刚刚push的元素，即队首元素，即栈顶元素
	
	    public void pop() {
	        queue.remove();
	    }
	
	    public int top() {
	        return queue.peek();
	    }
	
	    public boolean empty() {
	        return queue.isEmpty();
	    }
	}

## 树
### 二叉树的层序遍历
	 //层次遍历,采用队列实现
    public static void levelTree(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue queue = new LinkedList<>();  //linkedList是Queue的一个实现类
        queue.add(root);            //将元素加入队列的尾部
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();   //获取队列的头部元素
            System.out.println(temp.value + "->");
            if (temp.left != null) {      //添加左右孩子节点到队列
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
    }

## 判断一棵树是否是镜像对称的？
只需要判断根节点的两个节点值是否相同，同时两个节点的左右节点是否也是对称的，用到一点小技巧，将同一个节点当作两个节点传递

public boolean isSymmetric(TreeNode root) {
	   //根节点当作两个节点传递
	        return isMirror(root,root);
	    }
    
    private boolean isMirror(TreeNode p,TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        return (p.val == q.val) && isMirror(p.left,q.right) &&isMirror(p.right,q.left);    
    }

## 先序,中序,后序遍历
已知树的中序和后序遍历，画出这棵树。  
已知后序遍历，那么**后序遍历的最后一个元素就是根**，知道根以后再通过中序遍历得出左子树和右子树，再次递归。先序遍历也是一样的，先序遍历的第一个元素即根，但是已知先序和后序并不能确定一棵树，因为无法确定左右子树

## 自顶向下和自底向上
自顶向上类似于**先序遍历**，访问了当前节点后，把当前节点的值传递到下一层，比如求二叉树的最大深度，参数应该是这样：(rootNode,depth)

自底向上类似于后序遍历，解决最大深度也有类似的思想，当前节点的深度为h,则最大深度为 maxLength = MAX(left,right) + h

总结：如果能从自身得到什么值，或者可以将值传递到子节点，那么考虑自顶向下；
如果不知道当前节点的信息，但是可以从子节点得出，那么考虑自顶向上

### 树小结
- 很多情况递归解决
- 非递归情况一般使用栈，使用栈时**左孩子先入栈**，根据栈的性质遍历时会先遍历左孩子
- 深度优先使用栈，广度优先使用队列

## 链表
### 链表反转
	
	 //反转链表
    public void reserveLink(){
        Node curNode = first;  // 头结点
        Node preNode = null;   //前一个节点，这里设置为null是因为在反转以后原本尾节点指向null
        while (curNode != null) {
            Node nextNode = curNode.next;         //定义一个节点保存下一个节点
            curNode.next = preNode;    //指针反转，将本来指向下一位的指针指向前一位
            preNode = curNode;  //后移一个节点，因为要遍历整个链表
            curNode = nextNode;  //后移一个节点，因为要遍历整个链表
        }
        first = preNode;            //将头结点指向第一位,因为此时cur为null了
    }

### 链表小结
- 一般需要保存头结点，并且对头结点判空
- 一般需要保存三个节点信息：前一个节点，当前节点，后续节点
- a = a.next -->  a节点向后移一位
- a.next = b.next -->  跳过b节点（链表删除其实就是跳过节点）
- 链表的很多操作需要定义两个指针，一个指向当前节点，一个指向前一个节点

## 广度优先算法（BFS）
使用队列

- 用于树的**层次遍历**
- 找出**最短路径**：第K轮循环访问到目标，则最短路径就是K
- 模板
	- 初始化，先将根节点入队
	- 循环整个队列，条件是队列不空
	- 对队列进行遍历（queue.size），此时队列中的元素是当前层的所有元素
	- 在循环中将访问到的元素加入队列（这是下一层的元素，可以做重复判断，防止节点被重复访问）
	- 最后根节点出队，进入下一层

int BFS(Node root, Node target) {
			    Queue<Node> queue;  // store all nodes which are waiting to be processed
			    int step = 0;       // number of steps neeeded from root to current node
			    // initialize
			    add root to queue;
			    // BFS
			    while (queue is not empty) {
			        step = step + 1;
			        // iterate the nodes which are already in the queue
			        int size = queue.size();
			        for (int i = 0; i < size; ++i) {
			            Node cur = the first node in queue;
			            return step if cur is target;
			            for (Node next : the neighbors of cur) {
			                add next to queue;
			            }
			            remove the first node from queue;
			        }
			    }
			    return -1;          // there is no path from root to target
			}

## 深度优先算法(DFS)
使用栈

- 得到的并不是最短路径
- 使用栈时：右孩子先入栈
- 模板

boolean DFS(int root, int target) {
		    Set<Node> visited;
		    Stack<Node> s;
		    add root to s;
		    while (s is not empty) {
		        Node cur = the top element in s;
		        return true if cur is target;
		        for (Node next : the neighbors of cur) {
		            if (next is not in visited) {
		                add next to s;
		                add next to visited;
		            }
		        }
		        remove cur from s;
		    }
		    return false;
		}

## TOP N问题
- 先排序，再选择，如快排，第K个数，左边比他小，右边比他大
- 堆，堆顶元素就是top K
- 海量数据：拆分后在多台机器上维护堆

## 频率统计问题(最频繁的K个数)
- hashmap:使用hashmap进行频率统计，再使用堆进行选择TOP K
 
## 动态规划
对于走楼梯问题，共有10级台阶，每次只能走1层或2层，求有多少种走法？

- 边界，f(1) = 1,f(2) = 2
- 状态转移公式：f(n) = f(n-1) + f(n-2)
- 最优子结构：f(10)的最优子结构是f(8) 和 f(9)
- 在计算过程中考虑加入hashmap，减少不必要的计算

## 一些技巧
- 求并集，交集：使用Set
- 对于数组类型的题，一般需要先使用Arrays.sort()进行排序，同时Arrays还提供Arrays.qeuals(num[],num[])来判断两个数组是否相等
- 对于字符串反转，一个可以使用栈，另外StringBuilder.reverse
- 对于树结构，要特别关注根节点，因为左子树和右子树其实也可以看做是根，有时候需要根 + 左子树 + 右子树来实现

zhusir/interviewDoc

简介

发行版

贡献者

近期动态

zhusir/interviewDoc .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

zhusir/interviewDoc