public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
// 外层循环控制选择排序的轮数
for (int i = 0; i < n - 1; i++) {
// 假设当前轮次的第一个元素是最小的
int minIndex = i;
// 内层循环在未排序的部分中找到最小元素的索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将找到的最小元素与当前轮次的第一个元素交换位置
swap(arr, i, minIndex);
}
}
// 辅助方法用于交换数组中的两个元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public class CountingSort {
public static void countingSort(int[] arr) {
int n = arr.length;
// 找到数组中的最大值，确定计数数组的大小
int max = findMax(arr);
// 初始化计数数组，大小为最大值加一
int[] count = new int[max + 1];
// 统计每个元素的出现次数
for (int value : arr) {
count[value]++;
}
// 根据计数数组重构原始数组
int index = 0;
for (int i = 0; i <= max; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
private static int findMax(int[] arr) {
int max = arr[0];
for (int value : arr) {
if (value > max) {
max = value;
}
}
return max;
}
计数排序的时间复杂度为 O(n + k)，其中 n 是数组的长度，k 是数组中元素的范围（最大值减最小值加一）。
public class HeapSort {
public static void heapSort(int[] arr) {
//不包含n
int n = arr.length;
// 构建最大堆，从最后一个非叶子节点开始向上调整
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 从堆顶依次取出最大元素，将堆重新调整为最大堆
for (int i = n - 1; i > 0; i--) {
// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换
swap(arr, 0, i);
// 调整剩余部分为最大堆，剩余部分不包含i
heapify(arr, i, 0);
}
}
//调整i这个节点，比较他跟他的子节点，并递归继续调整被交换的larget节点
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值的索引为当前节点
int leftChild = 2 * i + 1; // 左子节点的索引
int rightChild = 2 * i + 2; // 右子节点的索引
// 如果左子节点比当前节点大，则更新最大值的索引 ，为什么要小于n呢？是因为不包含n
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
// 如果右子节点比当前节点大，则更新最大值的索引
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
// 如果最大值的索引不等于当前节点，交换它们并递归调整子树
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
技巧
二维前缀和？
单调队列?
计算n/t的结果，如果有余数则+1，可以简化为(n+t-1)/t 非常巧妙
检查整数的类型：正整数，负整数，符号
int * int 的值需要用long来存储。
链表求倒数可以用栈
求最大公约数，碾转相除法：
public int gcd(int a, int b) {
return b != 0 ? gcd(b, a % b) : a;
}
//数字范围按位与----选择数字范围的公共二进制前缀
public int rangeBitwiseAnd(int left, int right) {
while (left < right) {
// 抹去最右边的 1
right = right & (right - 1);
}
return right;
}
public int hammingWeight(int n) {
int cnt=0;
while(n!=0){
cnt += (n & 1);
n >>>= 1;
}
return cnt;
}
//Brian Kernighan 算法
public class Solution {
public int hammingWeight(int n) {
int ret = 0;
//移除最右的1
while (n != 0) {
n &= n - 1;
ret++;
}
return ret;
}
}
二分查找
二分查找特定的值：
while(left <= right) left=mid+1, right=mid-1;
当left,right边界条件都可能满足的情况下使用left <=right
while: left <=right的时候，一定是left=mid+1;right=mid-1; 否则会出现循环的情况。
当非搜索特定值的时候使用left < right, 如果 int mid=(left+right)/2;则 left=mid+1; right=mid 否则可能会出现遗漏的情况。
public int searchInsert(int[] nums, int target) {
int left=0;
int right = nums.length-1;
while(left <=right){
int mid=(left+right)/2;
if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
return left;
}
// 两次二分查找，分开查找第一个和最后一个
// 时间复杂度 O(log n), 空间复杂度 O(1)
// [1,2,3,3,3,3,4,5,9]
public int[] searchRange2(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int first = -1;
int last = -1;
// 找第一个等于target的位置
while (left <= right) {
int middle = (left + right) / 2;
if (nums[middle] == target) {
first = middle;
right = middle - 1; //重点
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
// 最后一个等于target的位置
left = 0;
right = nums.length - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (nums[middle] == target) {
last = middle;
left = middle + 1; //重点
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return new int[]{first, last};
}
字符串匹配算法
暴力匹配
KMP算法
KMP**算法在大规模文本匹配中具有较高的效率，尤其在一些大数据处理场景下表现优越。
KMP算法步骤：
初始化文本串指针 i 和模式串指针 j。
若当前字符匹配，则 i 和 j 同时后移。
若当前字符不匹配，根据 next[j] 调整 j 的位置。
重复步骤2-3，直到找到匹配或文本串遍历完。
public static int KmpSearch(String str1, String str2) {
int[] next = KMP_next(str2);
//遍历
for (int i = 0, j = 0; i < str1.length(); i++) {
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {
return i - j + 1;
}
}
return -1;
}
//获取到一个字符串的部分匹配值
public static int[] KMP_next(String dest) {
//创建一个数组next，保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0;//如果字符串是长度为1 部分匹配值就是0
for (int i = 1, j = 0; i < dest.length(); i++) {
//当dest.charAt(j) != dest.charAt(i)，我们需要从next[j-1]获取新的j
//直到我们发现有dest.charAt(j) == dest.charAt(i)成立才停止
while (j > 0 && dest.charAt(j) != dest.charAt(i)) {
j = next[j - 1];
}
//当dest.charAt(j) == dest.charAt(i)满足时，部分匹配值就是+1
if (dest.charAt(j) == dest.charAt(i)) {
j++;
}
next[i] = j;
}
return next;
}
Boyer-Moore 算法
Boyer-Moore 算法是一种用于字符串搜索的高效算法，于 1977 年由 Robert S. Boyer 和 J Strother Moore 提出。该算法在实际应用中通常比其他字符串搜索算法更快。
public class ManacherAlgorithm {
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
// 预处理字符串，使其变成奇数长度
String processedString = preprocessString(s);
int n = processedString.length();
int[] p = new int[n];
int center = 0, right = 0; // 当前回文串的中心和右边界
for (int i = 1; i < n - 1; i++) {
int mirror = 2 * center - i; // 计算 i 关于 center 的对称位置
if (right > i) {
p[i] = Math.min(right - i, p[mirror]);
}
// 尝试扩展回文串
while (processedString.charAt(i + p[i] + 1) == processedString.charAt(i - p[i] - 1)) {
p[i]++;
}
// 更新 center 和 right
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
// 找到最长回文子串的中心和半径
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
// 提取最长回文子串
int start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}
private static String preprocessString(String s) {
StringBuilder sb = new StringBuilder("#");
for (char c : s.toCharArray()) {
sb.append(c).append("#");
}
return sb.toString();
}
public static void main(String[] args) {
String s = "babad";
System.out.println("Longest Palindrome: " + longestPalindrome(s));
}
}