常用算法魔板
快速排序
/**
* 快排模板
* @param q 要排序的数组
* @param l 数组第一个元素下标：0
* @param r 数组最后一个元素下标：num - 1
*/
public static void quickSort(int[] q, int l, int r) {
//判边界：如果数组为空或就一个元素就直接返回
if (l >= r) {
return;
}
//确定分界点：从数组中取出一个数：这里取中间值
int x = q[l + r >> 1];
//定义两个指针分别指向边界的左右两侧：以调整区间
int i = l - 1;
int j = r + 1;
//比较指针下标对应的值
while (i < j) {
//先移动指针：再和分界点比较
do i++;
while (q[i] < x);
do j--;
while (q[j] > x);
//交换下标对应的值
if (i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
//递归处理左右两段
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
归并排序
/**
* 归并排序模板
* @param arr 要排序的数组
* @param l 数组第一个元素下标：0
* @param r 数组最后一个元素下标：length - 1
*/
public static void mergeSort(int[] arr, int l, int r) {
//判边界：如果数组为空或就一个元素就直接返回
if (l >= r) {
return;
}
//确定分界点：取数组中间值的下标
int mid = l + r >> 1;
//递归排序左边和右边
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
//定义两个指针分别指向两个数组的最左侧：以方便合并
int i = l, j = mid + 1;
//作为临时数组的下标计数
int k = 0;
//临时数组, 用于临时存储[l,r]区间内排好序的数据
int[] temp = new int[r - l + 1];
//通过指针比较两数组的值：进行归并
while (i <= mid && j <= r) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
//当一个数组比较完后：将另一个数组剩下的元素添加到临时数组后
while (i <= mid)
temp[k++] = arr[i++];
while (j <= r)
temp[k++] = arr[j++];
//将归并后的数据赋值原数组
for (i = l, j = 0; i <= r; i++, j++)
arr[i] = temp[j];
}
二分查找
/**
* 使用二分代码模板：非递归方式二分:找到数组中指定数字的起始位置和终止位置(找全部)
* @param arr 要查找的数组
* @param l 数组第一个元素下标：0
* @param r 数组最后一个元素下标：length - 1
* @param k 要查找的值
* @return
*/
private static void search(int[] arr, int l, int r, int k){
//二分模板查找：查找左边界
while(l < r){
int mid = l + r >> 1;
if(arr[mid] >= k){
r = mid;
}else {
l = mid + 1;
}
}
//跳出循环时, l == r, 判断数组中是否存在指定数字
if(arr[l] != k){
//数组中不存在指定数字
System.out.println("-1 -1");
}else {
System.out.print(l + " ");
//存在指定数字：初始化 l 和 r, 查找右边界
l = 0;
r = arr.length - 1;
while(l < r){
int mid = 1 + l + r >> 1;
if(arr[mid] <= k){
l = mid;
}else {
r = mid - 1;
}
}
System.out.println(l);
}
}
高精度加减乘除
/**
* 高精度加法运算
* 需要先将数放到集合中(按照个位放第一个的顺序)
* @param A 第一个数的集合
* @param B 第二个数的集合
* @return 返回个位数在第一个的集合(反转即是结果)
*/
public static List<Integer> add(List<Integer> A, List<Integer> B){
//判断哪个数的位数大：按位数大的处理
if (A.size() < B.size())
return add(B, A);
//结果集
List<Integer> C = new ArrayList<>();
//进位
int t = 0;
//加法运算：按位数较多的数处理
for (int i = 0; i < A.size(); i ++)
{
t += A.get(i);
if (i < B.size())
t += B.get(i);
C.add(t % 10);
t /= 10;
}
if (t > 0)
C.add(t);
return C;
}
/**
* 高精度减法运算
* 需要先将数放到集合中(按照个位放第一个的顺序)
* 注意：要保证传递进来的第一个数大于第二个数(如果第一个数小：就算第二减第一加负号)
* 减负数 = 加正数
* @param A 第一个数的集合
* @param B 第二个数的集合
* @return 返回个位数在第一个的集合(反转即是结果)
*/
public static List<Integer> sub(List<Integer> A, List<Integer> B){
//结果集
List<Integer> C = new ArrayList<>();
//减法运算：按位数较多的数处理
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A.get(i) - t;
if (i < B.size())
t -= B.get(i);
C.add((t + 10) % 10);
if (t < 0)
t = 1;
else
t = 0;
}
while (C.size() > 1 && C.get(C.size()-1)==0)
C.remove(C.size()-1);
return C;
}
/**
* 高精度乘低精度
* 需要先将高精度数放到集合中(按照个位放第一个的顺序)
* @param A 高精度数的集合
* @param b 低精度数
* @return 返回个位数在第一个的集合(反转即是结果)
*/
public static List<Integer> mul(List<Integer> A, int b){
List<Integer> C = new ArrayList<Integer>();
int t = 0;
for (int i = 0; i < A.size() || t > 0; i ++ )
{
if (i < A.size())
t += A.get(i) * b;
C.add(t % 10);
t /= 10;
}
while (C.size() > 1 && C.get(C.size() - 1) == 0)
C.remove(C.size() - 1);
return C;
}
/**
* 高精度除以低精度
* 需要先将高精度数放到集合中(按照个位放第一个的顺序)
* @param A 高精度数的集合
* @param b 低精度数
* @param r 余数
* @return 返回个位数在第一个的集合(反转即是结果)
*/
public static List<Integer> div(List<Integer> A, int b,int r){
List<Integer> C = new ArrayList<Integer>();
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A.get(i);
C.add(r / b);
r %= b;
}
//反转
Collections.reverse(C);
//去前导0
while (C.size() > 1 && C.get(C.size()-1) == 0)
C.remove(C.size()-1);
return C;
}
位运算
/**
* 求n的第k位数字: n >> k & 1 k:最右边第一位是0
* @param n 整数
* @param k k:最右边第一位是0
* @return n转换为二进制后的第k位数字(k从右边开始计数)
*/
public int findK(int n,int k){
return n >> k & 1;
}
/**
* 返回n(二进制)的最后一位 1
* @param n 整数
* @return 返回n的二进制数最后为1及后面的数(包括1)
* java中结果又自动转化为十进制数
*/
public static int lowBit(int n){
return n & -n;
}
区间合并
/**
* 可以得到合并后的区间结果集
* @param list :ArrayList中存储的是数组：每个数组中存储2个数：每个区间的左端点[0]和右端点[1]
* @return 返回合并后的区间个数即：集合大小
*/
public static int merge(ArrayList<int[]> list){
//结果集合
ArrayList<int[]> res = new ArrayList<>();
//先对集合中存储的数组按照区间的左端点排序
list.sort(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
//根据左端点区间判断：给定一个默认区间
int l = Integer.MIN_VALUE;
int r = Integer.MIN_VALUE;
//遍历集合
for(int[] itme : list){
//如果新区间的左端点 > 上一个区间的右端点
if(itme[0] > r){
if(l != Integer.MIN_VALUE){
//找到了新区间，就将老区间添加(不直接加新区间，因为新区间端点还没确定)
res.add(new int []{l,r});
}
l = itme[0];
r = itme[1];
}else {
//新区间的左端点 <= 上一个区间的右端点:合并：更新右端点
r = Math.max(r,itme[1]); //取新区间的右端点和老区间的右端点较大的那个
}
}
//最后一个合并区间,判断条件防止list为空
if (l != Integer.MIN_VALUE){
res.add(new int[]{l,r});
}
for(int[] temp : res){
for(int i = 0;i < temp.length;i++){
System.out.println(temp[i] + " ");
}
}
return res.size();
}
集合中元素去重复
/**
* 集合中元素去重复
* @param list
* @return 从左开始没有重复元素的下标
*/
public static int unique(List<Integer> list) {
//先排序
Collections.sort(list);
int j = 0;
for (int i = 0; i < list.size(); i++) {
if (i == 0 || list.get(i) != list.get(i - 1)) {
list.set(j, list.get(i));
j++;
}
}
return j;
//1 2 2 3 3 3 4 5 6 6 去重复前的集合
//1 2 3 4 5 6 res = 6 去重之后无重复元素的个数
//1 2 3 4 5 6 4 5 6 6 去重复后的集合
}
KMP字符串匹配
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(reader.readLine()); //子串长度
String P = reader.readLine(); //子串
char[] p = new char[n + 1]; //存储子串
//注意下标从1开始
for (int i = 1; i <= n; i++)
p[i] = P.charAt(i - 1);
int m = Integer.parseInt(reader.readLine()); //字符串长度
String S = reader.readLine(); //字符串
char[] s = new char[m + 1]; //存储字符串
//注意下标从1开始
for (int i = 1; i <= m; i++)
s[i] = S.charAt(i - 1);
// 构造前缀数组:即next[]数组 //只需要字串
int prefix[] = new int[n + 1];
for (int i = 2, j = 0; i <= n; i++) {
//i从2开始，因为prefix[1]肯定为0
while (j != 0 && p[i] != p[j + 1])
j = prefix[j];
if (p[i] == p[j + 1])
j++;
prefix[i] = j;
}
// kmp匹配
for (int i = 1, j = 0; i <= m; i++) {
while (j != 0 && s[i] != p[j + 1]) {
j = prefix[j]; // s[i] != p[j + 1]即不匹配，则往后移动
}
if (s[i] == p[j + 1])
j++; // 匹配时将j++进行下一个字符得匹配
if (j == n) { // 匹配了n字符了即代表完全匹配了
//输出的是所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。
System.out.print(i - n +" ");
j = prefix[j]; // 完全匹配后继续搜索
}
}
}
字符串哈希:适用于不同区间的字符串比较
/**
* 字符串哈希:就是把一个字符串映射成一个数字
* 求到一个字符串中任意两个区间的子串是否相同
* 转换为求两个区间子串的哈希值是否相等
* 求[L,R]字符串的哈希值
* @param l : 左边界
* @param r ：右边界
* @return ：[L,R]字符串的哈希值
*/
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
String[] s = read.readLine().split(" ");
//字符串长度
int n = Integer.valueOf(s[0]);
int t = Integer.valueOf(s[1]); //询问次数
//给定的字符串
String w = read.readLine();
//P为权重：131为经验值：即P=131或13331时：哈希冲突的可能性最小
int P = 131;
//由于前缀值的值很大：所以应该将数组中的数据定义为long型
long[] h = new long[n + 10]; //h[]存放字符串的前缀值
long[] p = new long[n + 10]; //p[]存放各个位数的相应权值
p[0] = 1; //最开始的权值必须赋值为1
//计算每个位上的相应权值
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * P; //计算每个位上的相应权值
//最新加入的数的权值为p的0次：所以直接加上str[i]即可
h[i] = h[i - 1] * P + w.charAt(i - 1); //计算字符串前缀值
}
while(t-- > 0){
s = read.readLine().split(" ");
int l1 = Integer.valueOf(s[0]); int r1 = Integer.valueOf(s[1]);
int l2 = Integer.valueOf(s[2]); int r2 = Integer.valueOf(s[3]);
String out = h[r1] - h[l1 - 1] * p[r1 - l1 + 1] == h[r2] - h[l2 - 1] * p[r2 - l2 + 1] ? "Yes" : "No";
System.out.println(out);
}
}
dfs求一个数的全排列
static int n; //需要搜索的个数(给定的数字)
static int[] path; //path[]用于保存路径
static boolean[] st; //用于记录：该步是否已经走过
public static void dfs(int u){
if(u==n){ //一条路搜索完成
for(int i=0;i<n;i++){
System.out.print(path[i]+" "); //输出结果
}
System.out.println();
return;
}
//控制位置：一次循环代表一个位置
for(int i=1;i<=n;i++){ //未搜素完成则继续尝试 即一条走到底为止
if(!st[i]) { //判断是否走过
path[u] = i; //标记当前步防止重复
st[i] = true; //保存当前路径
dfs(u + 1); //进行下一步搜索
st[i] = false; //恢复现场 否则会影响下一条路的搜索
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); //3
path = new int[n]; //3
st = new boolean[n+1]; //4
dfs(0); //从第0个位置开始搜索
}
评论