算法数据结构（三十六）----四边形不等式技巧

2024-06-13 12:18
文章标签 算法 技巧 数据结构 不等式 四边形 三十六

本文主要是介绍算法数据结构（三十六）----四边形不等式技巧，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目一

给定一个非负数组arr，长度为N，

那么有N-1种方案可以把arr切成左右两部分

每一种方案都有，min{左部分累加和，右部分累加和}

求这么多方案中，min{左部分累加和，右部分累加和}的最大值是多少？

整个过程要求时间复杂度O(N)

//暴力求解
public static int bestSplit1(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int N = arr.length;int ans = 0;for (int s = 0; s < N - 1; s++) {int sumL = 0;for (int L = 0; L <= s; L++) {sumL += arr[L];}int sumR = 0;for (int R = s + 1; R < N; R++) {sumR += arr[R];}ans = Math.max(ans, Math.min(sumL, sumR));}return ans;}
//切点不回退
public static int bestSplit2(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int N = arr.length;int sumAll = 0;for (int num : arr) {sumAll += num;}int ans = 0;int sumL = 0;// [0...s]  [s+1...N-1]for (int s = 0; s < N - 1; s++) {sumL += arr[s];int sumR = sumAll - sumL;ans = Math.max(ans, Math.min(sumL, sumR));}return ans;}

题目二

 把题目一中提到的，

min{左部分累加和，右部分累加和}，定义为S(N-1)，也就是说：

S(N-1)：在arr[0…N-1]范围上，做最优划分所得到的min{左部分累加和，右部分累加和}的最大值

现在要求返回一个长度为N的s数组，

s[i] =在arr[0…i]范围上，做最优划分所得到的min{左部分累加和，右部分累加和}的最大值

得到整个s数组的过程，做到时间复杂度O(N)

//暴力求解
public static int[] bestSplit1(int[] arr) {if (arr == null || arr.length == 0) {return new int[0];}int N = arr.length;int[] ans = new int[N];ans[0] = 0;for (int range = 1; range < N; range++) {for (int s = 0; s < range; s++) {int sumL = 0;for (int L = 0; L <= s; L++) {sumL += arr[L];}int sumR = 0;for (int R = s + 1; R <= range; R++) {sumR += arr[R];}ans[range] = Math.max(ans[range], Math.min(sumL, sumR));}}return ans;}
// 求原来的数组arr中，arr[L...R]的累加和public static int sum(int[] sum, int L, int R) {return sum[R + 1] - sum[L];}public static int[] bestSplit2(int[] arr) {if (arr == null || arr.length == 0) {return new int[0];}int N = arr.length;int[] ans = new int[N];ans[0] = 0;int[] sum = new int[N + 1];for (int i = 0; i < N; i++) {sum[i + 1] = sum[i] + arr[i];}for (int range = 1; range < N; range++) {for (int s = 0; s < range; s++) {int sumL = sum(sum, 0, s);int sumR = sum(sum, s + 1, range);ans[range] = Math.max(ans[range], Math.min(sumL, sumR));}}return ans;}

 

//前缀和数组
public static int[] bestSplit3(int[] arr) {if (arr == null || arr.length == 0) {return new int[0];}int N = arr.length;int[] ans = new int[N];ans[0] = 0;// arr =   {5, 3, 1, 3}//          0  1  2  3// sum ={0, 5, 8, 9, 12}//       0  1  2  3   4// 0~2 ->  sum[3] - sum[0]// 1~3 ->  sum[4] - sum[1]int[] sum = new int[N + 1];for (int i = 0; i < N; i++) {sum[i + 1] = sum[i] + arr[i];}// 最优划分// 0~range-1上，最优划分是左部分[0~best]  右部分[best+1~range-1]int best = 0;for (int range = 1; range < N; range++) {while (best + 1 < range) {int before = Math.min(sum(sum, 0, best), sum(sum, best + 1, range));int after = Math.min(sum(sum, 0, best + 1), sum(sum, best + 2, range));// 注意，一定要是>=，只是>会出错// 课上会讲解if (after >= before) {best++;} else {break;}}ans[range] = Math.min(sum(sum, 0, best), sum(sum, best + 1, range));}return ans;}

四边形不等式技巧特征

 1，两个可变参数的区间划分问题

2，每个格子有枚举行为

3，当两个可变参数固定一个，另一个参数和答案之间存在单调性关系

4，而且两组单调关系是反向的：(升 升，降 降)  (升 降，降 升)

5，能否获得指导枚举优化的位置对：上+右，或者，左+下

 四边形不等式技巧注意点

1，不要证明！用对数器验证！

2，枚举的时候面对最优答案相等的时候怎么处理？用对数器都试试！

3，可以把时间复杂度降低一阶

O(N^3) -> O(N^2)

O(N^2 * M) -> O(N * M)

O(N * M^2) -> O(N * M)

4，四边形不等式有些时候是最优解，有些时候不是

不是的原因：尝试思路，在根儿上不够好

 题目三

摆放着n堆石子。现要将石子有次序地合并成一堆

规定每次只能选相邻的2堆石子合并成新的一堆，

并将新的一堆石子数记为该次合并的得分

求出将n堆石子合并成一堆的最小得分（或最大得分）合并方案 

public static int[] sum(int[] arr) {int N = arr.length;int[] s = new int[N + 1];s[0] = 0;for (int i = 0; i < N; i++) {s[i + 1] = s[i] + arr[i];}return s;}public static int w(int[] s, int l, int r) {return s[r + 1] - s[l];}public static int min1(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int N = arr.length;int[] s = sum(arr);return process1(0, N - 1, s);}public static int process1(int L, int R, int[] s) {if (L == R) {return 0;}int next = Integer.MAX_VALUE;for (int leftEnd = L; leftEnd < R; leftEnd++) {next = Math.min(next, process1(L, leftEnd, s) + process1(leftEnd + 1, R, s));}return next + w(s, L, R);}

 定义dp[L][R]为arr L...R最优划分情况下，最优合并方案下的最小代价

public static int min2(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int N = arr.length;int[] s = sum(arr);int[][] dp = new int[N][N];// dp[i][i] = 0for (int L = N - 2; L >= 0; L--) {for (int R = L + 1; R < N; R++) {int next = Integer.MAX_VALUE;// dp(L..leftEnd)  + dp[leftEnd+1...R]  + 累加和[L...R]for (int leftEnd = L; leftEnd < R; leftEnd++) {next = Math.min(next, dp[L][leftEnd] + dp[leftEnd + 1][R]);}dp[L][R] = next + w(s, L, R);}}return dp[0][N - 1];}

 

//四边形不等式优化
public static int min3(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int N = arr.length;int[] s = sum(arr);int[][] dp = new int[N][N];int[][] best = new int[N][N];for (int i = 0; i < N - 1; i++) {best[i][i + 1] = i;dp[i][i + 1] = w(s, i, i + 1);}for (int L = N - 3; L >= 0; L--) {for (int R = L + 2; R < N; R++) {int next = Integer.MAX_VALUE;int choose = -1;for (int leftEnd = best[L][R - 1]; leftEnd <= best[L + 1][R]; leftEnd++) {int cur = dp[L][leftEnd] + dp[leftEnd + 1][R];if (cur <= next) {next = cur;choose = leftEnd;}}best[L][R] = choose;dp[L][R] = next + w(s, L, R);}}return dp[0][N - 1];}

 题目四

https://leetcode.com/problems/split-array-largest-sum/

给定一个整型数组 arr，数组中的每个值都为正数，表示完成一幅画作需要的时间，再 给定 一个整数 num，表示画匠的数量，每个画匠只能画连在一起的画作。所有的画家 并行工作，请 返回完成所有的画作需要的最少时间。

【举例】

arr=[3,1,4]，num=2。

最好的分配方式为第一个画匠画 3 和 1，所需时间为 4。第二个画匠画 4，所需时间 为 4。 因为并行工作，所以最少时间为 4。如果分配方式为第一个画匠画 3，所需时 间为 3。第二个画 匠画 1 和 4，所需的时间为 5。那么最少时间为 5，显然没有第一 种分配方式好。所以返回 4。

arr=[1,1,1,4,3]，num=3。

最好的分配方式为第一个画匠画前三个 1，所需时间为 3。第二个画匠画 4，所需时间 为 4。 第三个画匠画 3，所需时间为 3。返回 4。

// 求原数组arr[L...R]的累加和public static int sum(int[] sum, int L, int R) {return sum[R + 1] - sum[L];}// 不优化枚举的动态规划方法，O(N^2 * K)public static int splitArray1(int[] nums, int K) {int N = nums.length;int[] sum = new int[N + 1];for (int i = 0; i < N; i++) {sum[i + 1] = sum[i] + nums[i];}int[][] dp = new int[N][K + 1];for (int j = 1; j <= K; j++) {dp[0][j] = nums[0];}for (int i = 1; i < N; i++) {dp[i][1] = sum(sum, 0, i);}// 每一行从上往下// 每一列从左往右// 根本不去凑优化位置对儿！for (int i = 1; i < N; i++) {for (int j = 2; j <= K; j++) {int ans = Integer.MAX_VALUE;// 枚举是完全不优化的！for (int leftEnd = 0; leftEnd <= i; leftEnd++) {int leftCost = leftEnd == -1 ? 0 : dp[leftEnd][j - 1];int rightCost = leftEnd == i ? 0 : sum(sum, leftEnd + 1, i);int cur = Math.max(leftCost, rightCost);if (cur < ans) {ans = cur;}}dp[i][j] = ans;}}return dp[N - 1][K];}
// 课上现场写的方法，用了枚举优化，O(N * K)public static int splitArray2(int[] nums, int K) {int N = nums.length;int[] sum = new int[N + 1];for (int i = 0; i < N; i++) {sum[i + 1] = sum[i] + nums[i];}int[][] dp = new int[N][K + 1];int[][] best = new int[N][K + 1];for (int j = 1; j <= K; j++) {dp[0][j] = nums[0];best[0][j] = -1;}for (int i = 1; i < N; i++) {dp[i][1] = sum(sum, 0, i);best[i][1] = -1;}// 从第2列开始，从左往右// 每一列，从下往上// 为什么这样的顺序？因为要去凑（左，下）优化位置对儿！for (int j = 2; j <= K; j++) {for (int i = N - 1; i >= 1; i--) {int down = best[i][j - 1];// 如果i==N-1，则不优化上限int up = i == N - 1 ? N - 1 : best[i + 1][j];int ans = Integer.MAX_VALUE;int bestChoose = -1;for (int leftEnd = down; leftEnd <= up; leftEnd++) {int leftCost = leftEnd == -1 ? 0 : dp[leftEnd][j - 1];int rightCost = leftEnd == i ? 0 : sum(sum, leftEnd + 1, i);int cur = Math.max(leftCost, rightCost);// 注意下面的if一定是 < 课上的错误就是此处！当时写的 <= ！// 也就是说，只有取得明显的好处才移动！// 举个例子来说明，比如[2,6,4,4]，3个画匠时候，如下两种方案都是最优:// (2,6) (4) 两个画匠负责 | (4) 最后一个画匠负责// (2,6) (4,4)两个画匠负责 | 最后一个画匠什么也不负责// 第一种方案划分为，[0~2] [3~3]// 第二种方案划分为，[0~3] [无]// 两种方案的答案都是8，但是划分点位置一定不要移动!// 只有明显取得好处时(<)，划分点位置才移动!// 也就是说后面的方案如果==前面的最优，不要移动！只有优于前面的最优，才移动// 比如上面的两个方案，如果你移动到了方案二，你会得到:// [2,6,4,4] 三个画匠时，最优为[0~3](前两个画家) [无](最后一个画家)，// 最优划分点为3位置(best[3][3])// 那么当4个画匠时，也就是求解dp[3][4]时// 因为best[3][3] = 3，这个值提供了dp[3][4]的下限// 而事实上dp[3][4]的最优划分为:// [0~2]（三个画家处理） [3~3] (一个画家处理)，此时最优解为6// 所以，你就得不到dp[3][4]的最优解了，因为划分点已经越过2了// 提供了对数器验证，你可以改成<=，对数器和leetcode都过不了// 这里是<，对数器和leetcode都能通过// 这里面会让同学们感到困惑的点：// 为啥==的时候，不移动，只有<的时候，才移动呢？例子懂了，但是道理何在？// 哈哈哈哈哈，看了邮局选址问题，你更懵，请看42节！if (cur < ans) {ans = cur;bestChoose = leftEnd;}}dp[i][j] = ans;best[i][j] = bestChoose;}}return dp[N - 1][K];}

 题目五

一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组arr，每个值表示 居民点的一维坐标，再给定一个正数 num，表示邮局数量。选择num个居民点建立num个 邮局，使所有的居民点到最近邮局的总距离最短，返回最短的总距离

【举例】

arr=[1,2,3,4,5,1000]，num=2。

第一个邮局建立在 3 位置，第二个邮局建立在 1000 位置。那么 1 位置到邮局的距离 为 2， 2 位置到邮局距离为 1，3 位置到邮局的距离为 0，4 位置到邮局的距离为 1， 5 位置到邮局的距 离为 2，1000 位置到邮局的距离为 0。这种方案下的总距离为 6， 其他任何方案的总距离都不会 比该方案的总距离更短，所以返回6

dp[i][j] 表示范围0~4的时候，给3个邮局的答案

//普通dp算法
public static int min1(int[] arr, int num) {if (arr == null || num < 1 || arr.length < num) {return 0;}int N = arr.length;int[][] w = new int[N + 1][N + 1];for (int L = 0; L < N; L++) {for (int R = L + 1; R < N; R++) {w[L][R] = w[L][R - 1] + arr[R] - arr[(L + R) >> 1];}}int[][] dp = new int[N][num + 1];for (int i = 0; i < N; i++) {dp[i][1] = w[0][i];}for (int i = 1; i < N; i++) {for (int j = 2; j <= Math.min(i, num); j++) {int ans = Integer.MAX_VALUE;for (int k = 0; k <= i; k++) {ans = Math.min(ans, dp[k][j - 1] + w[k + 1][i]);}dp[i][j] = ans;}}return dp[N - 1][num];}
//四边形不等式优化
public static int min2(int[] arr, int num) {if (arr == null || num < 1 || arr.length < num) {return 0;}int N = arr.length;int[][] w = new int[N + 1][N + 1];for (int L = 0; L < N; L++) {for (int R = L + 1; R < N; R++) {w[L][R] = w[L][R - 1] + arr[R] - arr[(L + R) >> 1];}}int[][] dp = new int[N][num + 1];int[][] best = new int[N][num + 1];for (int i = 0; i < N; i++) {dp[i][1] = w[0][i];best[i][1] = -1;}for (int j = 2; j <= num; j++) {for (int i = N - 1; i >= j; i--) {int down = best[i][j - 1];int up = i == N - 1 ? N - 1 : best[i + 1][j];int ans = Integer.MAX_VALUE;int bestChoose = -1;for (int leftEnd = down; leftEnd <= up; leftEnd++) {int leftCost = leftEnd == -1 ? 0 : dp[leftEnd][j - 1];int rightCost = leftEnd == i ? 0 : w[leftEnd + 1][i];int cur = leftCost + rightCost;if (cur <= ans) {ans = cur;bestChoose = leftEnd;}}dp[i][j] = ans;best[i][j] = bestChoose;}}return dp[N - 1][num];}

题目六

https://leetcode.com/problems/super-egg-drop

 一座大楼有 0~N 层，地面算作第 0 层，最高的一层为第 N 层。已知棋子从第 0 层掉落肯定 不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎(1≤i≤N)。给定整数 N 作为楼层数， 再给定整数 K 作为棋子数，返 回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔 的最少次数。一次只能扔一个棋子。

【举例】

N=10，K=1。

返回 10。因为只有 1 棵棋子，所以不得不从第 1 层开始一直试到第 10 层，在最差的情况 下，即第 10 层 是不会摔坏的最高层，最少也要扔 10 次。

N=3，K=2。

返回 2。先在 2 层扔 1 棵棋子，如果碎了，试第 1 层，如果没碎，试第 3 层。 N=105，K=2 返回 14。

第一个棋子先在 14 层扔，碎了则用仅存的一个棋子试 1~13。 若没碎，第一个棋子继续在 27 层扔，碎了则 用仅存的一个棋子试 15~26。 若没碎，第一个棋子继续在 39 层扔，碎了则用仅存的一个棋子试 28~38。 若 没碎，第一个棋子继续在 50 层扔，碎了则用仅存的一个棋子试 40~49。 若没碎，第一个棋子继续在 60 层扔， 碎了则用仅存的一个棋子试 51~59。 若没碎，第一个棋子继续在 69 层扔，碎了则用仅存的一个棋子试 61~68。 若没碎，第一个棋子继续在 77 层扔，碎了则用仅存的一个棋子试 70~76。 若没碎，第一个棋子继续在 84 层 扔，碎了则用仅存的一个棋子试 78~83。 若没碎，第一个棋子继续在 90 层扔，碎了则用仅存的一个棋子试 85~89。 若没碎，第一个棋子继续在 95 层扔，碎了则用仅存的一个棋子试 91~94。 若没碎，第一个棋子继续 在 99 层扔，碎了则用仅存的一个棋子试 96~98。 若没碎，第一个棋子继续在 102 层扔，碎了则用仅存的一 个棋子试 100、101。 若没碎，第一个棋子继续在 104 层扔，碎了则用仅存的一个棋子试 103。 若没碎，第 一个棋子继续在 105 层扔，若到这一步还没碎，那么 105 便是结果。 

//超时
public static int superEggDrop1(int kChess, int nLevel) {if (nLevel < 1 || kChess < 1) {return 0;}return Process1(nLevel, kChess);}// rest还剩多少层楼需要去验证// k还有多少颗棋子能够使用// 一定要验证出最高的不会碎的楼层！但是每次都是坏运气。// 返回至少需要扔几次？public static int Process1(int rest, int k) {if (rest == 0) {return 0;}if (k == 1) {return rest;}int min = Integer.MAX_VALUE;for (int i = 1; i != rest + 1; i++) { // 第一次扔的时候，仍在了i层min = Math.min(min, Math.max(Process1(i - 1, k - 1), Process1(rest - i, k)));}return min + 1;}
//普通dp  超时
public static int superEggDrop2(int kChess, int nLevel) {if (nLevel < 1 || kChess < 1) {return 0;}if (kChess == 1) {return nLevel;}int[][] dp = new int[nLevel + 1][kChess + 1];for (int i = 1; i != dp.length; i++) {dp[i][1] = i;}for (int i = 1; i != dp.length; i++) {for (int j = 2; j != dp[0].length; j++) {int min = Integer.MAX_VALUE;for (int k = 1; k != i + 1; k++) {min = Math.min(min, Math.max(dp[k - 1][j - 1], dp[i - k][j]));}dp[i][j] = min + 1;}}return dp[nLevel][kChess];}

//四边形不等式优化  勉强通过
public static int superEggDrop3(int kChess, int nLevel) {if (nLevel < 1 || kChess < 1) {return 0;}if (kChess == 1) {return nLevel;}int[][] dp = new int[nLevel + 1][kChess + 1];for (int i = 1; i != dp.length; i++) {dp[i][1] = i;}int[][] best = new int[nLevel + 1][kChess + 1];for (int i = 1; i != dp[0].length; i++) {dp[1][i] = 1;best[1][i] = 1;}for (int i = 2; i < nLevel + 1; i++) {for (int j = kChess; j > 1; j--) {int ans = Integer.MAX_VALUE;int bestChoose = -1;int down = best[i - 1][j];int up = j == kChess ? i : best[i][j + 1];for (int first = down; first <= up; first++) {int cur = Math.max(dp[first - 1][j - 1], dp[i - first][j]);if (cur <= ans) {ans = cur;bestChoose = first;}}dp[i][j] = ans + 1;best[i][j] = bestChoose;}}return dp[nLevel][kChess];}

dp[i][j]我有i个棋子，扔j次，能搞定多少层 

//四边形不等式优化
public static int superEggDrop4(int kChess, int nLevel) {if (nLevel < 1 || kChess < 1) {return 0;}int[] dp = new int[kChess];int res = 0;while (true) {res++;int previous = 0;for (int i = 0; i < dp.length; i++) {int tmp = dp[i];dp[i] = dp[i] + previous + 1;previous = tmp;if (dp[i] >= nLevel) {return res;}}}}
//优化常数项
public static int superEggDrop5(int kChess, int nLevel) {if (nLevel < 1 || kChess < 1) {return 0;}int bsTimes = log2N(nLevel) + 1;if (kChess >= bsTimes) {return bsTimes;}int[] dp = new int[kChess];int res = 0;while (true) {res++;int previous = 0;for (int i = 0; i < dp.length; i++) {int tmp = dp[i];dp[i] = dp[i] + previous + 1;previous = tmp;if (dp[i] >= nLevel) {return res;}}}}public static int log2N(int n) {int res = -1;while (n != 0) {res++;n >>>= 1;}return res;}

 

这篇关于算法数据结构（三十六）----四边形不等式技巧的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1057275。

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2