寻找峰值
峰值元素是指其值大于左右相邻值的元素
方法一: 线性扫描
public int findPeakElement(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1])
return i;
}
return nums.length - 1;
}
方法二：递归二分查找
我们可以将 nums 数组中的任何给定序列视为交替的升序和降序序列。通过利用这一点，以及“可以返回任何一个峰作为结果”的要求，我们可以利用二分查找来找到所需的峰值元素。
我们对二分查找进行一点修改。首先从数组 nums 中找到中间的元素 mid若该元素恰好位于降序序列或者一个局部下降坡度中，则说明峰值会在本元素的左边
就这样，我们不断地缩小搜索空间，直到搜索空间中只有一个元素，该元素即为峰值元素
public class Solution {
public int findPeakElement(int[] nums) {
return search(nums, 0, nums.length - 1);
}
public int search(int[] nums, int l, int r) {
if (l == r)
return l;
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
return search(nums, l, mid);
return search(nums, mid + 1, r);
}
}
找出这个重复的数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
方法一：二分查找
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length;
int l = 1, r = n - 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt <= mid) {
l = mid + 1;
} else {
r = mid - 1;
ans = mid;
}
}
return ans;
}
}
最优
int temp;
for(int i=0;i<nums.length;i++){
while (nums[i]!=i){
if(nums[i]==nums[nums[i]]){
return nums[i];
}
temp=nums[i];
nums[i]=nums[temp];
nums[temp]=temp;
}
}
return -1;
方法二：二进制
这个方法我们来将所有数二进制展开按位考虑如何找出重复的数，如果我们能确定重复数每一位是 1 还是 0 就可以按位还原出重复的数是什么。
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length, ans = 0;
int bit_max = 31;
while (((n - 1) >> bit_max) == 0) {
bit_max -= 1;
}
for (int bit = 0; bit <= bit_max; ++bit) {
int x = 0, y = 0;
for (int i = 0; i < n; ++i) {
if ((nums[i] & (1 << bit)) != 0) {
x += 1;
}
if (i >= 1 && ((i & (1 << bit)) != 0)) {
y += 1;
}
}
if (x > y) {
ans |= 1 << bit;
}
}
return ans;
}
}
方法三：快慢指针
我们先设置慢指针
slow 和快指针
fast ，慢指针每次走一步，快指针每次走两步
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
二分法
class Solution {
public int missingNumber(int[] nums) {
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] == m) i = m + 1;
else j = m - 1;
}
return i;
}
}
旋转数组的最小数字
排序数组的查找问题首先考虑使用 二分法 解决，其可将遍历法的 线性级别 时间复杂度降低至 对数级别
public int minArray(int[] numbers) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int m = (i + j) / 2;
if (numbers[m] > numbers[j]) i = m + 1;//m 一定在 左排序数组
else if (numbers[m] < numbers[j]) j = m;//m 一定在 右排序数组 中
else j–;
}
return numbers[i];
}
二分查找
全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
在排序数组中查找数字
二分查找，找到左右闭合区间即可
重点在边界的限制上
class Solution {
public int search(int[] nums, int target) {
// 搜索右边界 right
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] <= target) i = m + 1;
else j = m - 1;
}
int right = i;
// 若数组中无 target ，则提前返回
if(j >= 0 && nums[j] != target) return 0;
// 搜索左边界 right
i = 0; j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] < target) i = m + 1;
else j = m - 1;
}
int left = j;
return right - left - 1;
}
}
查找value下标
给定一个有序的数组，查找value第一次出现的下标，不存在返回-1。
int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n - 1;
while (left <= right)
{
int middle = left + ((right - left) >> 1);
if (array[middle] >= value) //因为是找到最小的等值下标，所以等于号放在这里
right = middle - 1;
else
left = middle + 1;
}
return array[right + 1] == value ? right + 1 : -1;
}
如果问题改为查找value最后一次出现的下标呢？只需改动两个位置：
1.if (array[middle] >= value)中的等号去掉；
2.return中right+1改为left-1。
给定一个有序的数组，查找最接近value且大于value的数的下标（如果该数存在多个，返回第一个下标），不存在返回-1。
int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n - 1;
while (left <= right)
{
int middle = left + ((right - left) >> 1);
if (array[middle] > value)
right = middle - 1;
else
left = middle + 1;
}
return array[right + 1] > value ? right + 1 : -1;
}
如果问题改为查找最接近value且小于value的数的下标（如果该数存在多个，返回最后一个下标）呢？只需改动两个位置：
1.if (array[middle] > value)加入一个等号；
2.return array[right + 1] > value ? right + 1 : -1;改为return array[left-1] < value ? left - 1 : -1;。
总结
二分算法所操作的区间，是左闭右开，还是左闭右闭，需要在循环体跳出判断中，以及每次修改left,，right区间值这两个地方保持一致，否则就可能出错。
给一个数组，找出这样一些数，这个数左边的数都比它小，右边的数都比它大
排序
冒泡排序
思想：每次遍历，相邻两个比较大小，修改位置
复杂度：n平方
function maopao(arr) {
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length; j++) {
if (arr[i] > arr[j]) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
插入排序
思想：每次往最小数组里插入一个数据，并保证数组是排序的
(1) 将这个序列的第一个元素R0视为一个有序序列；
(2) 依次把 , , … , 插入到这个有序序列中；
(3) 将插入到有序序列中时，前 i-1 个数是有序的，将和 ~ 从后往前进行比较，确定要插入的位置。
public static int[] insertSOrt(int[] arr) {
int len = arr.length;
int preIndex,cur;
for (int i = 0; i < len; i++) {
preIndex = i - 1;
cur = arr[i];
while (preIndex > 0 && arr[preIndex] > cur) {
arr[preIndex +1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = cur;
}
return arr;
}
归并排序
作为一种典型的分而治之思想的算法应用
将一个数组排序，可以先递归的将它分成两半分别排序，然后再将结果归并起来。
缺点：需要额外的空间
从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这
些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得
到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。
这样就得到了我们想要的排序结果
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
// 分开
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
// 合并
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
快速排序
分而治之思想在排序算法。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
先是把第一个挖出来，作为基值；然后先是从右向左，对比基值，如果如果小，那么放到坑里；然后在从左往右对比基值，如果大，那么放到坑里；当换完一轮了后，把基值放到坑里；然后在根据基值，分左右两组，递归排序；
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比
另外一部分的所有数据都要小，继续对长度较短的序列进行同样的分割，最后到
达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故
减少了比较次数，降低了排序时间。
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找寻基准数据的正确索引位置
int index = getIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
quickSort(arr, low, index - 1); // 左半边排序
quickSort(arr, index + 1, high); // 右半边排序
}
}
private static int getIndex(int[] arr, int low, int high) {
// 基准数据
int tmp = arr[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && arr[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
arr[low] = tmp;
return low; // 返回tmp的正确位置
}
拓扑排序
它是对有向图的顶点排成一个线性序列。
堆排序（大顶堆、小顶堆）
堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大
值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将
剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执
行，便能得到一个有序序列了
var len; //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { //建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { //堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
桶排序
知道最大最小值，可以生成一个最大最小值的一个桶的map，key是值，value是出现的次数
for(i=1;i<=n;i++)//循环读入n个数，并进行桶排序
{
scanf("%d",&t); //把每一个数读到变量t中
book[t]++; //进行计数，对编号为t的桶放一个小旗子
}
for(i=1000;i>=0;i--) //依次判断编号1000~0的桶
for(j=1;j<=book[i];j++) //出现了几次就将桶的编号打印几次
printf("%d ",i);
getchar();getchar();
计数排序
按指定要求排序后输出
给字符串，内含很多整数，按指定要求排序后输出指定位置上的整数；
两个有序数组，找出合并后的中位数
获取数组中最值（最大值/最小值）
分治 + 最小堆排序的思想
局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，
与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除
，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。
原理是最小堆排序
https://blog.csdn.net/zyq522376829/article/details/47686867
求数组中第k大的数
建立一个大小为K的最小堆，堆顶就是第K大的数
例如，假设有10个数，要求求第3大的数，第一步选取任意的3个数，比如说是前3个，
将这3个数建成最小堆，然后从第4个数开始，与堆顶
的数比较，如果比堆顶的数要小，那么这个数就不要，如果比堆顶的数大，
则舍弃当前的堆顶而将这个数作为新的堆顶，并再去维护堆
旋转数组查找；
public static int minNumberInRotateArray(int[] rotateArray)
{
if (rotateArray.Length == 0) return 0;
else if (rotateArray.Length == 1||rotateArray[0]<rotateArray[rotateArray.Length-1]) return rotateArray[0];
else
{
int low = 0;
int high = rotateArray.Length - 1;
while (low<=high)
{
int mid = (int)Math.Floor((double)(low + high) / 2);
if (rotateArray[mid] > rotateArray[0]) low = mid + 1;
else if (rotateArray[mid] < rotateArray[0]) high = mid - 1;
else low = low + 1;
}
return low == rotateArray.Length ? rotateArray[low - 1] : rotateArray[low];
}
}
##常见算法
广度优先搜索
深度优先搜索
递归
回溯
贪婪算法
动态规划
线性规划
区间规划
约束规划
自底向上
自定向下
搜索技巧
回溯
递归
剪枝
基础技巧
分治
倍增
二分
贪心
模拟
- 加油站
- LRU缓存机制
- 快乐数
- 生命游戏
- 两整数之和
- Fizz Buzz
两个人掷硬币，先得到正面的人赢，游戏到有人赢结束。问先掷硬币的人赢的概率