chrisxyq/algorithm

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
 * 
 * 判断欧拉回路
 * 存在欧拉回路充要条件：当且仅当图是连通的而且每个顶点的度是偶数
 */

解答：

时间空间复杂度：

---

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

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

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

时间空间复杂度：

---

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

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

解答：动态规划

时间空间复杂度：

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