sogetsu

分类

题解(5)

/ 注册

全部文章（共5篇）

减绳子

题目描述给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的...

2020-03-14

2 873

和为S连续正数

看大家都是用双指针，我来写一种其他方法吧，纯数学解法假设从n开始，到n+k，连续k+1个数的和等于S,则有计算得到由n>=1得到k的范围因此只需对1->k遍历，找到满足上述公式（整除）的k，自然可以计算出对应的开始数字n，代码如下： class Solution { public: ...

2020-03-10

0 523

连续子数组的最大和

动态规划问题假设数组为则整个字符串的最大子串和为：又因为：使用自底向上的计算过程，逐次计算Sk的值，取其中的最大值，即为解 class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { ...

2020-03-06

3 799

最小的K个数

经典问题，3种解法：先排序，再取前k个数，平均时间复杂度O(nlogn) 使用最小堆，建堆完成后依次交换第一个和第i个元素（i=n,n-1,...,n-k）得到k个最小值，平均时间复杂度O(n+k) 使用快排的patition子程序，逐步逼近第k个数所在的位置，期望平均时间复杂度O(n)，但是前...

2020-03-05

0 573

二叉搜索树的后序遍历

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析：一棵二叉搜索树的后序遍历结果，必然是其中序遍历顺序入栈的其中一种出栈序列实现：先对输入进行排序获取中序遍历结果，然后使用栈模拟遍历过程，最后栈为空，...

2020-03-04

0 582