algorithm 相关问题

渐近比较 lg(lg* n) 和 2^(lg*n )

有人可以帮我找到两个函数 lg(lg*(n)) 和 (2lg*n) 之间的 O、o、Ω、ω 或 Ɵ 关系吗？

在 C 中实现 Miller-Rabin

我正在尝试在 C99 中实现 Miller-Rabin 素性测试，但在使其正常工作时遇到了一些问题。我制作了一个小型测试集来验证实施是否有效，...

Hackerrank 子数组求和问题 - 测试用例超时

这是 hackerrank 的一个问题，我有一个解决方案，但有一些测试用例由于超出时间限制而失败。我不知道更好的解决方案。 求子数组中元素的总和（i...

优先级队列不能很好地与compare()配合使用

我设计了一个优先级队列，但它不适用于某些测试用例。 #包括 #包括 #包括 使用命名空间 std； 模板 我设计了一个优先级队列，但它不适用于某些测试用例。 #include <iostream> #include <algorithm> #include <vector> using namespace std; template <class T1, class T2> class priorityQueue { private : vector<T1> dataContainer; class Compare { public: // Compare two elements . bool operator()(const T1& a, const T1& b) const { return a > b; } }; public : priorityQueue(vector<T1>& myV): dataContainer(myV) {make_heap(dataContainer.begin(), dataContainer.end(), Compare());} bool empty() const { return dataContainer.empty(); } // get the size of the queue size_t size() const { return dataContainer.size(); } // get the element with the highest priority in the queue T1& top(){ return dataContainer.front();} // push an element into the qeueu void enQueue(T1& element) { dataContainer.push_back(element); push_heap(dataContainer.begin(), dataContainer.end(), Compare()); } // pop the element with the highest priority in the qeueu void deQueue() { pop_heap(dataContainer.begin(), dataContainer.end(), Compare()); dataContainer.erase(dataContainer.begin()); } void printQ() { typename vector<T1>::iterator itr ; cout << "the priorityQueue is : " << endl ; for (itr = dataContainer.begin() ; itr != dataContainer.end(); ++itr) { cout << *itr << "\t" ; } cout << endl ; } }; int main() { vector<int> aa; int a[4] = {5, 8, 3, 2}; aa.assign(a, a+4); priorityQueue<int, bool> myQ(aa); myQ.printQ(); return 0; } 比较类不能更改优先级顺序。 a > b 的输出应该是 2 3 5 8 。 谢谢 在dequeue()操作中，你必须删除last元素： void deQueue() { pop_heap(dataContainer.begin(), dataContainer.end(), Compare()); dataContainer.pop_back(); }

Julia PLSQ - 整数关系算法 - 有人愤怒地使用过它吗？

我正在尝试使用 LLL 或 PLSQ 整数关系算法之一来获得真正最优的解决方案，以解决为 Remez 逼近多项式寻找固定长度尾数系数的问题...

如何计算最小公分母

我找不到任何东西，也许是因为我的英语。我想找到几个数字的最小除法值。 在德语中，它被称为：http://de.wikipedia.org/wiki/Hauptnenner 我想知道...

证明或反证：连通但不完全图中存在三个顶点a、b、c，且满足a和b有公共邻居c

在一个不完全的连通图中，我们能否找到a、b、c表示的三个顶点，使得a与b相邻，b与c相邻，但a和c不是邻居？ 这是一个图论问题...

平衡二叉树与平衡二叉搜索树

对于每个操作，平衡二叉搜索树会比平衡二叉树更快地完成任务吗？ 寻找树中最小的项目。 我认为平衡 BST...

哈希表实现的扩展索引

我使用哈希表作为 C 项目的主要数据结构。我使用 SipHash 的实现作为哈希函数。我使用链表来处理冲突。给定元素的索引...

逻辑门的真值是1101

有没有办法找到逻辑门或如何从想要的真值表中制作更复杂的门/位运算符 我希望有这个真值表： 0 0 = 1 0 1 = 1 1 0 = 0 1 1 = 1

沿着每个级别的最大节点值在树中查找路径的算法

我正在寻找一种算法，可以沿着每个级别的最大节点值在树中找到一条路径。下图说明了该问题： 如果一个级别上的所有节点都有唯一的值...

如何获取对一系列 std::vector 元素的 const 引用？

我想从 std::vector 获取一系列元素并将它们存储为 const-ref，因为我只想读取但不想修改它们。 #包括 #包括 ...

std::sort 和 std::stable_sort 有什么区别？

我想知道 std::sort 和 std::stable_sort 在功能、内存和硬件方面有何不同？该文档提到“将 [first,last) 范围内的元素排序为

划分数组，使子数组最大值之和最小化

我只能想到一个蛮力的方法来解决这个问题。有兴趣看看 Algo SO 社区会提出什么。 给出一个 arr a 和一个整数 x (1 我只能想一个蛮力的方法来解决这个问题。有兴趣看看 Algo SO 社区会提出什么。 给出一个arr a和一个整数x（1s1, s2....sx ）使得max(s1) + max(s2)....+ max(sx)的总和是子数组总和的所有可能组合中的最小值（参见下面的示例）。返回一个带有x-的数组1 个索引包含发生分割的索引 i（不包括）a[0:i], a[i+1:i2], a[i2+1: i3].....a[ix:]。 示例： a = [10,30,40,20,50] x = 2 return = [1] 将索引 1 处的数组拆分为 [10] 和 [30,40,20,50] 会产生 max([10]) + max([30,40,20,50]) = 60，这是所有其他分割数组的方法中的最小值。 其他可能的分裂 - 无法在索引 0 处拆分，因为那样只会产生 1 个数组且 x = 2 在索引 2 处分割 = max([10,30]) + max([40,20,50]) = 80 在索引 3 处拆分将得到 90 在索引 4 处拆分将得到 90 不允许在索引 5 处进行分割，因为这样只会产生 1 个数组且 x = 2 这是一个动态规划问题。 首先建立以下数据结构。 for each position in the array for each count of how many splits (current max, sum of maxes, position of last split) 例如，在您的问题中，数据结构将如下所示： [ # One group, no splits [(10, 10, 0)], # 2 groups, 1 split [(30, 30, 0), (30, 40, 1)], [(40, 40, 0), (40, 50, 1), (40, 80, 2)], [(40, 40, 0), (20, 50, 1), (20, 70, 3)], [(50, 50, 0), (50, 60, 1), (50, 100, 2)], # the choices are equal ] 这可以通过简单的双循环来创建。 您从 [[(a[0], a[0], 0)]] 开始。 要找出 i, j 条目，您必须考虑在 (i-1, j-1) 条目之后开始一个新组，或者将当前元素添加到 (i-1, j) 条目中的最后一个组。 一旦有了这个，就从数组的最后一个位置和所需的分割数开始。 数据结构告诉您最后一个分割在哪里，您可以转到该位置并向下一个分割找到之前的分割所在的位置。 沿着饼干屑的踪迹往回走，你会发现所有的裂缝。 在您的示例中，(len(a), x)条目位于(4, 1)并且具有值(50, 60, 1)。 上一个条目位于 (1, 0) 且具有值 (10, 10, 0)。 我们忽略边界处的分割并得到 [1] 作为答案。 如果你想制作x=3，那么你可以从(50, 100, 2)开始，返回到(40, 50, 1)，然后到(10, 10, 0)并得到答案[1, 2]。 为了使 Max(sx) 变得尽可能小，我们应该始终努力创建数字尽可能小的子数组。因此，只需将输入列表划分为具有最小可能值的单元素列表即可： arr = [10,30,40,20,50] n = 2 a = [] def subarray(a): r = [] while (len(r) <= n-2): r.append(a[:1]) a = a[1:] r.append(a) return r def calculate(a): r = 0 for i in subarray(a): r += i[-1] return r print(calculate(arr)) 如果您可以将其构造为使用记忆化，那么蛮力并没有那么糟糕。 该方法递归地进行左右分割，以确定将每个左侧前缀与右侧少一个分割的最佳解决方案相结合的最佳解决方案。 由于这将多次计算相同的右侧分割，因此记忆（将过去的结果保留在内存中以供重用）将使大多数探索分支短路。 from functools import lru_cache from itertools import accumulate def minMaxSum(A,x): @lru_cache() # memoization for def findBest(start,splits): # best split from start position to end of A R = A[start:] # right-side/remaining elements # base cases (no recursion) if splits == 1: return max(R),[R] if splits == len(R): return sum(R),[[r] for r in R] # progressively increasing size of left side subarray bestSum = sum(R)+1 maxLeft = 0 for i,r in enumerate(R[:len(R)-splits+1],1): if r >= bestSum: break # won't improve on best at this point maxLeft = max(maxLeft,r) # max for left side subSum,subArrays = findBest(start+i,splits-1) # recurse right side subSum += maxLeft if subSum>=bestSum: continue # track improvement to best solution bestSum = subSum bestSplit = [R[:i],*subArrays] # left side + best right side solution return bestSum,bestSplit # convert to break indexes and return solution maxSum,subArrays = findBest(0,x) breaks = list(accumulate(map(len,subArrays)))[:-1] return breaks,maxSum,subArrays 输出： print(*minMaxSum([10,30,40,20,50],2)) # [1] 60 [[10], [30, 40, 20, 50]] print(*minMaxSum([10,30,40,20,50],3)) # [1, 2] 90 [[10], [30], [40, 20, 50]] print(*minMaxSum([40,30,40,20,50],3)) # [3, 4] 110 [[40, 30, 40], [20], [50]] print(*minMaxSum([40,25,30,45,40,20,35,50],5)) # [1, 2, 5, 6] 180 [[40], [25], [30, 45, 40], [20], [35, 50]] A = [i%5+1 for i in range(37)] x = 11 print(*minMaxSum(A,x)) # [1, 2, 5, 6, 7, 10, 11, 12, 35, 36] 27 # [[1], [2], [3, 4, 5], [1], [2], [3, 4, 5], [1], [2], # [3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5], [1], [2]] 可以使用带回溯的递归（然后可以转换为DP进行优化） class Solution { static int ans=Integer.MAX_VALUE; public static void main(String[] args) { ans=Integer.MAX_VALUE; int[] nums = {10, 5, 9,3,8}; int K = 3; // 2D array to store the max value of all possible subarrays //maxValue[i][j]=maximum value in subarray i...j int[][] maxValue = new int[nums.length][nums.length]; for(int i=0;i<nums.length;i++){ int max=nums[i]; for(int j=i;j>=0;j--){ if(nums[j]>max){ max=nums[j]; } maxValue[j][i]=max; } } findMinSum(maxValue,0,nums.length-1,K-1,0); System.out.println(ans); } public static void findMinSum(int[][] maxValue,int startIndex,int endIndex,int k,int sumSoFar){ System.out.println("startIndex="+startIndex+" sumSoFar="+sumSoFar); if(k==0){ // no more subarrays to be divided so use the max in this array itself sumSoFar+=maxValue[startIndex][endIndex]; if(sumSoFar<ans){ ans=sumSoFar; } } else { for(int index=startIndex;index<=endIndex-k;index++){ // consider all possible starting point and leave space for // upcoming array partitions(endIndex-k) findMinSum(maxValue,index+1,endIndex,k-1,sumSoFar+maxValue[startIndex][index]); } } } }

如何使用相邻交换解决字典顺序最小排列？

解决以下问题应该采取什么方法？找不到解决的方法。 给定一个整数数组，找到您可以生成的该数组按字典顺序排列的最小排列...

算法：最大计数器

我有以下问题： 您有 N 个计数器，最初设置为 0，并且您对它们有两种可能的操作： increase(X) - 计数器 X 加 1， max_counter - 所有计数器...

为什么空列表输出的乘积是“1”？

我正在使用“math”包中的“prod”方法来查找列表的乘积。不知怎的，我不明白为什么下面的操作的输出是 1，尽管它是一个空列表。 从数学导入产品 一个=...

Codility PermMissingElem

我的解决方案在 Codility 上的正确率只有 40%。 我做错了什么？ 这是测试结果（https://codility.com/demo/results/trainingU7KSSG-YNX/） 问题： 零索引数组 A 包含...

查找给定图的所有第二条路径

这是一个面试问题。我有一个包含从 1 到 n 的 n 个节点的图。 图表使用 2 个列表表示，from 列表和 to 列表。一条边连接 from[i] 到 to[i] 的点。 假设最大

使用图的Horn SAT算法

对于某些受限类别的逻辑公式，可满足性问题可以在多项式时间甚至线性时间内有效解决。其中一类是 Horn 公式，它仅由