福大大架构师每日一题

福大大架构师每日一题

/ 注册

全部文章 / 福大大架构师每日一题（共597篇）

2020-09-22：已知两个数的最大公约数和最小公倍数，并且这两个数不能是最大公约数和最小公倍数本身。如何判断这... 来自专栏

2020-09-22：已知两个数的最大公约数和最小公倍数，并且这两个数不能是最大公约数和最小公倍数本身。如何判断这两个数是否存在？福哥答案2020-09-22：#福大大架构师每日一题# 1.如果最小公倍数不能被最大公约数整除，不存在这两个数。2.求【商】=【最小公倍数/最大公约数】。3.判断【商】是...

算法

2020-09-22

3 0

2020-09-21：已知最大公约数和最小公倍数，如何判断这两个数是否存在？来自专栏

福哥答案2020-09-21：#福大大架构师每日一题# 1.如果最大公约数或者最小公倍数有小于1的，不存在这两个数。2.如果最大公约数等于1，存在这两个数。这个步骤可以不要。3.如果最大公约数大于最小公倍数，不存在这两个数。这个步骤可以不要。4.如果最小公倍数不能被最大公约数整除，不存在这两个数。5...

算法

2020-09-21

3 970

2020-09-20：如何判断一个数是质数？来自专栏

福哥答案2020-09-20：#福大大架构师每日一题# 1.试除法。朴素素数筛，埃氏筛，欧拉筛和区间筛。代码采用朴素素数筛。2.费尔马素性测试法法。费马小定理：假如p是质数，a是整数，且a、p互质，那么a的(p-1)次方除以p的余数恒等于1，即：a^(p-1)≡1(mod p)。3.米勒拉宾素性检验...

算法

2020-09-20

3 950

2020-09-18：LRU手撸，说下时间复杂度和空间复杂度。来自专栏

福哥答案2020-09-18：方法：哈希表 + 双向链表。时间复杂度：对于 put 和 get 都是 O(1)。空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。代码用go语言编写，代码如下： package test40_lru import (...

算法

2020-09-18

3 713

2020-09-13：判断一个正整数是a的b次方，a和b是整数，并且大于等于2，如何求解？来自专栏

福哥答案2020-09-13：#福大大架构师每日一题# 首先确定b的范围，b的范围一定在[2,logN]里。然后遍历b，求a的范围，如果范围长度等于0，说明这个正整数是a的b次方。1.遍历b范围。二分法求a，a初始范围是[2,logN]。2的400次方耗时5秒。【有代码】2.遍历b范围。优化二分法求...

算法

2020-09-13

3 515

2020-09-12：手撕代码：最小公倍数，复杂度多少？来自专栏

福哥答案2020-09-12：#福大大架构师每日一题#最大公约数1.【更相减损法】=【等值算法】，避免了取模运算，但是算法性能不稳定，最坏时间复杂度为O(max(a, b)))。2.【辗转相除法】，迭代和递归，时间复杂度不太好计算，可以近似为O(log(max(a, b)))，但是取模运算性能较差。...

算法

2020-09-12

3 841

2020-09-09：裸写算法：两个线程轮流打印数字1-100。来自专栏

福哥答案2020-09-09：方法1：用一个通道，两个go程的代码不一样。方法2：用两个通道，两个go程的代码完全一样。可以扩展成N个go程轮流打印。代码用golang编写，代码如下： package test38_alternateprint import ( "fmt&q...

算法

2020-09-09

3 0

2020-09-03：裸写算法：回形矩阵遍历。来自专栏

福哥答案2020-09-03：方法一：模拟，位图方式。跟方法二一样，区别是辅助矩阵visited用位图节约空间。方法二：模拟。可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，则顺时针旋转，进入下一个方向。判断路径是否进入之前访问过的位...

算法

2020-09-03

3 536

2020-08-30：裸写算法：二叉树两个节点的最近公共祖先。来自专栏

福哥答案2020-08-30： 1.递归算法左节点子函数返回值不空，右节点子函数返回值为空，返回左节点。左节点子函数返回值为空，右节点子函数返回值不空，返回右节点。左节点子函数返回值不空，右节点子函数返回值不空，返回当前节点。复杂度分析：时间复杂度 O(N) ：其中 N 为二叉树节点数；最差情况下...

算法

2020-08-30

3 553

2020-08-26：裸写算法：树的非递归先序遍历。来自专栏

福哥答案2020-08-26：方法 1：迭代算法从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压右孩子再压左孩子。在这个算法中，输出到最终结果的顺序按照 Top->Bottom 和 Left->Right，符合前序遍历的顺序。算法复杂度时间复杂度：访问每个节点恰好...

算法

2020-08-26

3 461