凉风起天末

分类

题解(7)

/ 注册

TA的专栏 0篇文章 0人订阅

算法中的数学

0篇文章 0人学习

全部文章（共9篇）

关于使用小顶堆解决Top K问题的平均时间复杂度分析来自专栏

一、问题描述假设数列 B={} 是由 n 个不重复的数字按从小到大有序排列得到的，有序数列 B 是未知的，仅方便后续分析描述，数列 A={} 由数列 B 随机重排列得到，现使用小顶堆算法求数列 A 的第 k 个最大的数，求算法的平均时间复杂度。二、算法分析算法总体分为两个阶段：“堆初始化”与...

2023-10-09

1 1027

题解 | #小红的最小三角形周长#

从数组中寻找周长最小的三角形，常规的思路是先排序，再从小到大依次搜索，再添加一些小优化就OK了。假设最短三角形的三条边依次是a、b、c（a<b<c），通过分析我们可以知道，b、c在排序后的数组中一定是相邻的，因为如果b、c中间还有数据（设为x），那么a、b、x会形成一个更短的三角形，与假...

2023-02-02

3 803

《剑指Offer》条件限制下求“1+2+3+...+n”

O(n)伤不起：模拟二进制运算，绝对不涉及乘法，复杂度为O(logN) 2进制乘法原理与10进制类似，但是2进制更加简单，因为2进制非0即1，所以乘数m的一个二进制位与被乘数n相乘的结果要么是0要么是n本身，只要在实际计算过程中根据m的某个进制位所在的位置对n进行移位就可以了。当然，这里讨论的都是...

乘法短路求值原理二进制

2020-02-02

55 1664

贪吃的小Q

先占个位置，详细思路之后再写；先贴个图片和源码上去： #include <iostream> using namespace std; int first_day_food(int day, int food) { if (day <= 0 || day > ...

递归数学

2020-02-02

2 1151

《剑指Offer》字符流中第一个不重复的字符

一种优化思路：无须次次进行遍历这道题目的大致思路其实都差不多，只不过看了许多答案，发现都是存储了所有字符，然后再进行遍历判断其实并不需要这样。用户 txlstars 的回答和本文的优化相同（绝对不是面向 Ctrl+C 编程的～）字符出现次数的判断（不重复字符）：这个做法大致相同，利用 Hash...

字符流队列复杂度

2020-02-02

57 3652

《剑指Offer》把字符串转换成整数

越界的简单解决方案：让符号位参与运算，并合理利用 INT_MAX/10 众所周知，这道题逻辑并不复杂，只是要判断结果是否出界却有点让人手忙脚乱，这里给出以下两种情景的解决方案（若有发现缺漏之处，望及时指出纠正！）：能够处理最小负数：-2147483648 判断是否超出最小负数 ~ 最大正数的范围...

数值字符串溢出转换

2019-09-16

54 3271

《剑指Offer》二叉搜索树的后序遍历序列

从到，比递归效率更高的方法：上限约束法方法一：递归法递归简单易懂容易实现，先来一次遍历以确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。现在让我们来分析一下递归方法的时间复杂度：二叉搜索树不一定是棵平衡二叉树，因此其树形可能长得奇形怪状，最坏的情况下可能退化成一类似链表的结构，此时我们...

栈复杂度二叉搜索树后序遍历

2019-09-04

89 5776

《剑指Offer》包含min函数的栈

双栈法的优化：压缩还原方法一：简单的双栈法在返回栈中的min值时，如果仅仅使用一个辅助变量min，则其值可能因为min元素被出栈而失效，常规的做法是额外添加一个同步栈（min栈），以保存记录之前所有的min值，相当于是使用了n个辅助变量，所以空间复杂度是O(n)。但是，仅仅使用一两个辅助变量就真...

最小值栈复杂度

2019-08-25

69 3939

《剑指Offer》二维数组中的查找

分享五种解题方法，仅为拓宽思路：（注：如果代码出现了段错误问题，可能是没有考虑到空数组，健壮性也是算法的一部分）一、左下/右上元素移动法：十分简单巧妙，在看了徘徊的路人甲的题解才后知后觉；设M=min(m,n)，N=max(m,n)，复杂度为O(N)，详见链接题解：链接：https://www.n...

C/C++ 折半查找二维有序数组十字分割

2019-08-13

42 3822