算法笔记

堆排序原理  堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。 第一步 构造初始堆 假设给定无序序列结构如下 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。 第二步 得到完整的排序序列将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大 ...

说明  因为平时不是很常用二分法排序，但是有时候会有要求使用二分法排序，所以就把板子放在这里可以直接参考，照着这个样子可以进行适当的改动。 代码  这里用一个整数数组进行示范，比较清晰明了。 1234567891011121314151617181920212223int[] arr = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1}; for (int i = 1; i < arr.length; i++) { int temp = arr[i]; //要插入的第i个元素 int low = 0; int high = i - 1; //插入目标元素的前 i-1 个元素 ...

题目概要题目描述给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。 你可以 任意多次交换 在 pairs 中任意一对索引处的字符。 返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。 输入描述12345一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。1 <= s.length <= 10^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengths 中只含有小写英文字母 输出描述1返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。 测试样例样例1: 输入-输出 ...

如题，直接上代码这次这个是从学长那边打听到的面试的题目以及自己在做OJ题目的过程中碰到了1234567891011121314151617181920212223242526272829303132//包含自身也算祖先//有三种情况: 1.一个结点在左子树,另一个结点在右子树(公共祖先是root) //2.两个结点都在左子树或者都在右子树 //3.其中有个结点是root(公共祖先则是root) //因为题中已经说明有树,所以不考虑root为null情况 public TreeNode lowestcommomAncestor(TreeNode root, TreeNode p, TreeNode q){ if(root == p || root == q){ //其中有个结点是root,则公共祖先是root ...

关于后缀数组的一些说明  本文撰写的目的在于做题时发现经常会有题目出现后缀数组的解法，而普通的暴力解法容易引起超时，所以特意在网上学了后缀数组，但是感觉网站的一些版本都不是特别清晰，所以在自己的博客中打算自己写一个份算法教程。 遇事不决上代码请先欣赏Cpp的代码：1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAX=1e6+5;int n,m;int tax[MAX],rak[MAX],tp[MAX],sa[MAX];char s[MAX];void sort(in ...