20221003题目:无效访问的userId

/**
 * 20221003题目:
 * 如果出现下述两种情况(任一条件满足,同时满足就算两次无效访问)表示访问无效,
 * 找出无效访问的userId,并按照userId出现的不合法访问次数倒序排序
 * - 同一用户访问时间间隔小于3s
 * - 同一用户10s连续访问三次
 * 限定时间一个自然日
 * 
 * 时间复杂度o(n^^2)
 * 空间复杂度o(n)
 */

解答:指针法

  • step1:计算 用户-访问时间map
  • step2:为每个用户计算不合法访问次数,维护三个指针移动
  • step3:将UserAndNum实体按照userId出现的不合法访问次数倒序排序,取UserId并返回

时间空间复杂度:

  • 时间复杂度o(n^^2)
  • 空间复杂度o(n)

20221010题目:一次性走完所有的道路的散步路线

/**
 * 20221010题目:
 * 天气凉快了,大家都喜欢饭后在园区进行散步,园区的道路四通八达,
 * 大家都有自己习惯的散步路线,那有没有什么路线是可以一次性走完所有的道路而不重复的呢,
 * 下面是个简单的园区线路图,每一条双向箭头都表示了一条道路,可以双向通行,但只能走一次,
 * 那么如果我们从大棚(A)出发,有没有路线可以一次性走完所有的道路,又回到大棚的呢,
 * 如果有的话,请列举所有的路线,以每个地点的字母排列出来,例如:ABCDEF
 * 
 * 判断欧拉回路
 * 存在欧拉回路充要条件:当且仅当图是连通的而且每个顶点的度是偶数
 */

image-20221107195545138

解答:

时间空间复杂度:


20221031题目:设计数独并证明有唯一解

/**
 * 入门:设计9*9规模的数独游戏的初始化算法(随机设置初盘数字数量)
 * 进阶(选答):证明具有唯一解
 * <p>
 * 数独的生成总体思路是挖洞法。
 * 首先在二维数组第一行随机填充1-9 9个数字,
 * 然后将这9个数字随机分布到整个二维数组中,
 * 然后使用求解数独的算法对此时的数组进行求解,得到一个完整的数独,
 * 然后按照用户输入的提示数量进行随机挖洞,得到最终的数独题目。
 *
 * @description 数独生成和求解
 * @limit 支持从1-80的数字提示数量
 * @method 深度优先搜索/回溯法
 */

解答:深度优先搜索/回溯法

时间空间复杂度:


20221107题目:果园采摘最大价格

/**
 * 20221107题目:
 * 村⾥的每个⼈都能够到果园⾥去采摘,但规定每棵树上只能采摘1个果⼦(假设每棵树上的果⼦数量⽆
 * 限,每个⼈都能采到)。为了避免⼤家挤在⼀起产⽣踩踏事件,果园还规定在某颗果树采摘完后不允
 * 许采摘相邻(浅蓝⾊部分为⽰例)的果树,同时不能回头采已经⾛过的果树。现在假设市场上苹果的
 * 价格是4元/个,梨的价格是3元/个,桃⼦的价格是2元/个。
 */

image-20221107200224391

解答:动态规划

时间空间复杂度:

* 对于m*n矩阵
* 时间复杂度:o(m*n)
* 空间复杂度:o(m*n*2)