经典算法整理


经典算法整理

算法思想:

​ 1.在待排序的元素任取一个元素作为主元(通常选第一个元素,但最的选择方法是从待排序元素中随机选取一个作为基准),称为基准元素;

​ 2.将待排序的元素进行分区,比基准元素大的元素放在它的右边,比其小的放在它的左边;

​ 3.对左右两个分区重复以上步骤直到所有元素都排好序。

快速排序

两种partition方案:

第一种:

img img img img

第二种:

img img img img

随机pivot:

	public static void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int p = partition(arr, left, right, true);
			quickSort(arr, left, p - 1);
			quickSort(arr, p + 1, right);
		}
	}

	private static int partition(int[] arr, int left, int right, boolean isRandomPivot) {
		int pivot = isRandomPivot ? randomPivot(arr, left, right) : arr[left];
		int l = left;
		int r = right;
		while (l < r) {
			while (l < r && arr[r] >= pivot)
				r--;
			arr[l] = arr[r];
			while (l < r && arr[l] < pivot)
				l++;
			arr[r] = arr[l];
		}
		arr[l] = pivot;
		return l;
	}

	private static int randomPivot(int[] arr, int left, int right) {
		int r = new Random().nextInt(right - left + 1) + left;
		int temp = arr[left];
		arr[left] = arr[r];
		arr[r] = temp;
		return arr[left];
	}

三数取中法:

private static int partition2(int[] arr, int left, int right) {
		int pivot = median3(arr, left, right);
		int l = left;
		int r = right - 1;
		// arr[left],arr[right]在本轮次上已经在正确的位置,right-1位置存放pivot
		while (l < r) {
			// 遇到相等时都停止,可以做到均匀的划分
			while (arr[--r] > pivot)
				;
			while (arr[++l] < pivot)
				;
			if (l < r) {
				swap(arr, l, r);
			}
		}
		// 主元归位
		swap(arr, l, right - 1);
		return l;
	}

	private static int median3(int[] arr, int left, int right) {
		int mid = (left + right) >> 1;
		// arr[left] <= arr[mid] <= arr[right]
		if (arr[left] > arr[mid]) {
			swap(arr, left, mid);
		}
		if (arr[left] > arr[right]) {
			swap(arr, left, right);
		}
		if (arr[mid] > arr[right]) {
			swap(arr, mid, right);
		}
		// 主元存放在right-1位置
		swap(arr, mid, right - 1);
		return arr[right - 1];
	}
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

堆排序

算法思想: 堆是完全二叉树的一种:每个结点的值都大于或等于其左右孩子叫大顶堆;每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。 堆上的操作有建堆以及堆调整

堆排序正是利用堆这种数据结构而设计的一种排序算法,以升序为例,堆排序的基本思想是:

整体主要由建堆,堆调整两部分组成。其中构建初始堆经推导复杂度为O(n),在重建堆的过程中,要重复n-1次,每次是(lgn), 所以总的时间复杂度是O(nlgn)

代码实现:

public static void headSort(int[] arr) {
		// 1.构建大顶堆
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			heapify(arr, i, arr.length);
		}
		// 2.交换堆顶元素与末尾元素+调整堆结构
		for (int size = arr.length - 1; size > 0; size--) {
			swap(arr, 0, size);
			heapify(arr, 0, size);
		}
	}

	// 调整堆
	public static void heapify(int[] arr, int i, int length) {
		int left = 2 * i + 1;
		int right = left + 1;

		if (left >= length || right >= length) {
			return;
		}
		// 求根结点,子结点中的最大值的下标
		int max = max(arr, left, right, i);

		// 如果最大不是根,则根和最大交换
		if (max != i) {
			swap(arr, i, max);
			// 递归过程
			heapify(arr, max, length);
		}
	}

归并排序

算法思想: 归并排序是利用分治的思想实现的排序方法。该算法策略是将序列分成两半,对每一半分别进行排序,这个过程可以是递归。待它们分别排好序之后,合并这两个已经有序的序列。 分治过程:

img

代码实现:

void merge(int arr[], int low, int mid, int high) {
		int Lsize = mid - low + 1;
		int Rsize = high - mid ;
		for (int i = 0; i < Lsize; i++) {
			L[i] = arr[low + i];
		}
		for (int i = 0; i < Rsize; i++) {
			R[i] = arr[mid + i + 1];
		}
		L[Lsize] = 0x0FFFFFFF;
		R[Rsize] = 0x0FFFFFFF;
		for (int k = low, i = 0, j = 0; k <= high; k++) {
			if (L[i] <= R[j]) {
				arr[k] = L[i++];
			} else {
				arr[k] = R[j++];
			}
		}
}
void merge_sort(int arr[], int low, int high){
    int mid = 0;
    if(low<high){
        mid = (low+high)/2; 
        merge_sort(arr, low, mid);
        merge_sort(arr, mid+1,high);
        merge(arr,low,mid,high);
    }
}

树和图算法

搜索算法

DFS

背包问题dfs解法:

	/**
	 * 
	 * @param w 物品的重量
	 * @param v 物品的价值
	 * @param k 挑选的物品编号
	 * @param curVal 当前已有的价值
	 * @param W 当前剩余载重
	 * @return 最大价值
	 */
	private static int dfsKnapsack(int[] w, int[] v, int k, int curVal, int W) {
		//物品挑选完 | 容量没有剩余 都是边界条件
    if (k == w.length || W <= 0) {
			return curVal;
		}
		return Math.max(dfsKnapsack(w, v, k + 1, curVal + v[k], W - w[k]), 
						dfsKnapsack(w, v, k + 1, curVal, W));
	}

BFS

public static int numIslands(char[][] grid) {
	int res = 0;
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return res;
	int m = grid.length;
	int n = grid[0].length;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == '1') {
				bfs(grid, i, j);
				res += 1;
			}
		}
	}
	return res;
}
protected static void bfs(char[][] grid, int i, int j) {
	//代表上下左右方向
	int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	int m = grid.length;
	int n = grid[0].length;
	Queue<Integer> q = new LinkedList<Integer>();
	grid[i][j] = '0';
	q.add(i * n + j);

	while (!q.isEmpty()) {
		int cur = q.poll();
		int x = cur / n;
		int y = cur % n;
		for (int k = 0; k < 4; k++) {
			int nextX = x + dir[k][0];
			int nextY = y + dir[k][1];
			//将所有一步可达的点置为'0' 并加入queue中,以访问它们可达的点
			if (nextX >= 0 && nextY >= 0 && nextX < m 
				&& nextY < n && grid[nextX][nextY] == '1') {
				grid[nextX][nextY] = '0';
				q.add(nextX * n + nextY);
			}
		}
	}
}

二叉树的遍历

递归方式:

public static void preOrderRecur(Node root) {
		if (root == null) {
			return;
		}
		System.out.print(root.value + " ");
		preOrderRecur(root.left);
		preOrderRecur(root.right);
	}

	public static void inOrderRecur(Node root) {
		if (root == null) {
			return;
		}
		inOrderRecur(root.left);
		System.out.print(root.value + " ");
		inOrderRecur(root.right);
	}

	public static void posOrderRecur(Node root) {
		if (root == null) {
			return;
		}
		posOrderRecur(root.left);
		posOrderRecur(root.right);
		System.out.print(root.value + " ");
	}

非递归方式: 先序: img

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            //先压根结点
            stack.add(root);
            while (!stack.isEmpty()) {
                root = stack.pop();
                list.add(root.val);
                //在压右子树
                if (root.right != null) {
                    stack.push(root.right);
                }
                //再压左子树
                if (root.left != null) {
                    stack.push(root.left);
                }
                //这样出栈顺序就能做到根左右
            }
        }
        return list;           
    }

中序: img

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if(root == null){
            return ans;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(!stack.isEmpty() || cur != null){
            //压左边界 直到为null
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            //弹出一个结点 收集val 并让cur = node.right;
            TreeNode node = stack.pop();
            ans.add(node.val);
            cur = node.right;
        }
        return ans;
    }

后序: img

public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<>();
        if (root != null) {
			Stack<TreeNode> s1 = new Stack<TreeNode>();
			Stack<Integer> data = new Stack<Integer>();
			s1.push(root);
            TreeNode node = null;
			while (!s1.isEmpty()) {
				node = s1.pop();
                //第次弹出元素压入data中 可以保证 根右左顺序
				data.push(node.val);
				if (node.left != null) {
					s1.push(node.left);
				}
				if (node.right != null) {
					s1.push(node.right);
				}
			}
            //出栈收集 左右根顺序
			while (!data.isEmpty()) {
				list.add(data.pop());
			}
		}
        return list;
    }

或者直接用list,每次add到0号的位置

public static List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> list = new ArrayList<>();
	if (root != null) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		TreeNode node = null;
		while (!stack.isEmpty()) {
			node = stack.pop();
			list.add(0, node.val);
			if (node.left != null) {
				stack.push(node.left);
			}
			if (node.right != null) {
				stack.push(node.right);
			}
		}
	}
	return list;
}

最短路径

最小生成树

字符串算法

BM

KMP

next数组:

保存的是以当前字符(不包含)结尾的最长的前缀和后缀

img

求解过程:

一个例子:

img

next[0] = -1
pre = -1
i = 1
while i < next.length:
	if pre == -1 or p[i - 1] == p[pre]:
		next[i++] = ++pre
	 else 
		pre = next[pre]

KMP求解

while i < t.length && j < p.length:
	if j == -1 or t[i] == p[j]:
		i++;j++
	else:
		j = next[j]

一个例子: img

完整算法:

public static int kmp(String T, String P) {
		int[] next = next(P);
		char[] t = T.toCharArray();
		char[] p = P.toCharArray();
		int i = 0, j = 0;
		while (i < t.length && j < p.length) {
			// 如果相等 或者j已经没法回退了
			// 则都接着匹配一下个
			if (j == -1 || t[i] == p[j]) {
				i++;
				j++;
			}
			// j回退至j位置最长前缀的位置
			// 继续和i匹配
			else {
				j = next[j];
			}
		}
		return j == p.length ? i - j : -1;
	}

	public static int[] next(String P) {
		char[] p = P.toCharArray();
		int[] next = new int[p.length];
		next[0] = -1;
		int pre = -1;
		int i = 1;
		while (i < next.length) {
			if (pre == -1 || p[i - 1] == p[pre]) {
				next[i++] = ++pre;
			} else {
				pre = next[pre];
			}
		}
		return next;
	}

扩展问题

Manacher

几个概念

回文半径,回文左右边界: img 两种情况:

代码实现

// #A#B#C#C#E#
	public static char[] manacherString(String str) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < str.length(); i++) {
			sb.append("#");
			sb.append(str.charAt(i));
		}
		sb.append("#");
		return sb.toString().toCharArray();
	}

	public static String manacher(String str) {
		if (str == null || str.length() == 0) {
			return "";
		}
		char[] charArr = manacherString(str);
		int[] radius = new int[charArr.length];
    String res = null;
		int C = -1;
		int R = -1;
		int max = 0;
		int rc = 0;
		for (int i = 0; i != charArr.length; i++) {
			// 区分了当i在回文半径里外时
			radius[i] = R > i ? Math.min(radius[2 * C - i], R - i) : 1;
			while (i + radius[i] < charArr.length && i - radius[i] > -1) {
				// 以点i为中心往外扩
				if (charArr[i + radius[i]] == charArr[i - radius[i]])
					radius[i]++;
				else {
					break;
				}
			}
			// 更新最右回文边界
			if (i + radius[i] > R) {
				R = i + radius[i];
				C = i;
			}
			// 当有更大的回文半径时,记录中心点和最大值
			if (radius[i] > max) {
				max = radius[i];
				rc = i;
			}
		}
		res = String.valueOf(charArr).substring(rc - max + 1, rc + max - 1).replace("#", "");
		return res;
	}

扩展问题

其它算法

使用单调栈解决最大矩形面积

保持栈中元素递增,当要压入的元素小于栈顶元素时,进行计算以当前为界的矩形的面积

    def largestRectangleArea(self, heights):
        s = []
        res = 0
        # 可以保证在最后总会计算
        heights.append(0)
        for i in range(len(heights)):
            # 当前位置小于栈顶位置时计算
            while s and heights[s[-1]] > heights[i]:
                h = heights[s.pop()]
                # i-s[-1]-1 和 i 是底
                area = h * (i-s[-1]-1 if s else i)
                res = max(res,area)
            s.append(i)
        return res

完美洗牌算法

有个长度为2n的数组 {a1, a2, a3, …, an, b1, b2, b3, …, bn} ,希望排序后 {a1, b1, a2, b2, …., an, bn} ,请考虑有无时间复杂度 O(n),空间复杂度 O(1) 的解法。

链接:https://www.jianshu.com/p/9c841ad88ded

如果要排序成这种形式: a1<=a2>=a3<=a4>=a5

则只要将它们排序,再应用完美洗牌算法即可 例:

1 2 3 4 5 6

1 4 2 5 3 6

求两个排序数组的上中位数(长度相等)

img

求两个排序数组的第k小的数(长度不等)

假设一个数组长度为10,一个为17

1<=k<=10 拿出前k个比较进行二分可以了

17<k<=27 23 先比较6号和13号是不是 如果不是,则对6之后和13之后进行二分 (6+13) +4 = 23(淘汰的 +二分出来的)

10<k<=17 13 短数组1-10都有可能 1>12’ 1>3’ 判断3’是不是 如果是则返回,否则进行二分[1,10],[4’,13’] 3+10(淘汰的 +二分出来的)

  #Algorithm 

« 聊一聊线程池 Fuzzy finder(fzf+vim) 使用全指南 »