K次乘运算后的最终数组 I(easy)做题过程本来觉得easy不应该要用到小根堆,毕竟上一道是hard,但发现还是小根堆,虽然模拟通得过。
算法概述原题
本体要求为取当前数组中最前面的最小值,乘以给定数字,对次操作重复K次,返回原地操作的结果。 小根堆 。
时间复杂度为O(Klogn):重新排序
空间复杂度为O(n)
JAVA1234567891011121314151617181920...
购买物品的最大开销(hard)做题过程模拟没做出来,就是没想到怎么做吧。
算法概述原题
本题要求为给出二维矩阵代表各个商店的各种商品价格(非严格递减),只能从后往前买商品,计算最大开销。通过 最小堆 存放当前所有商店的最后一个值,每次推出堆顶时同步向前移动索引。
时间复杂度为O(mnlogm):一次遍历+建堆
空间复杂度为O(m):堆
JAVA1234567891011121314151...
半有序排列(easy)做题过程没有想到什么优化,也确实也没有什么优化。
算法概述原题
本题要求为求某一数组中将首元素和末尾元素移动到相应位置所需的操作次数,每次操作可交换两个相邻的元素位置。 模拟 。
时间复杂度为O(n)
空间复杂度为O(1)
JAVA12345678910111213141516class Solution { public int semiOrder...
骑士拨号器(medium)
做题过程
思路有的很快,但是因为测试集的数据会非常大,忘记给dp声明成long了,其实就是前面“骑士在棋盘上的概率”加个continue就行。
算法概述
原题
本题要求为把一个骑士放在拨号盘上,给定步数,计算有多少种号码的可能。使用 动态规划 。
时间复杂度为O(n)
空间复杂度为O(n):还有棋盘大小的常系数
JAVA
123456789101112...
判断国际象棋棋盘中的一个格子的颜色(easy)做题过程还是用了差值来求,题目本身很简单,但这样求解极其不优雅且冗长。
算法概述原题
本题要求为给出格子坐标,判断格子元素。可用 位运算 简单完成。
时间复杂度为O(n)
空间复杂度为O(1)
JAVA123456class Solution { public boolean squareIsWhite(String coo...
删除有序数组中的重复元素 II(medium)做题过程过了一会儿才想出来用双指针,但是还是对如何组织代码没有思路,ε=(´ο`*)))唉。
算法概述原题
本题要求为删除出现两次以上的元素的重复项,只保留出现两次的状态,原地操作数组,返回最终长度。使用 双指针(快慢指针) 。
时间复杂度为O(n):双指针
空间复杂度为O(1):要求
JAVA1234567891011121314...
变为棋盘(hard)做题过程这个太偏向于找规律,太偏向于数学,之后再说
骑士在棋盘上的概率(medium)做题过程我认为用dfs或者bfs都可以解决这个问题,无非就是累加然后做除法,但结果发现,深度优先搜索占用的线程将会 指数级上升 ,类似一个多叉树结构同时遍历,而不是逐个子树自顶到底,然后再回到根节点,而且无法完成这一过程,因为 不知道有多少步 ,所以会引发 多线程更新彼此冲突覆盖 的问题。所以还是要用动态规划,一个一个子问题的走。
算法概述原题
本题要求为...
可以被一步捕获的棋子数(easy)做题过程一开始想的就是一个循环里用四个指针,然后想的是一个行遍历一个列遍历,最后发现太麻烦了,处理相对关系,还是要用四个for分开来遍历,既然时间复杂度没有区别,为什么不分离解耦呢?
算法概述原题
本题要求为给出一个棋盘,判断棋盘上的车在一步内有多少个可吃的棋子的可能(可能被象阻挡)。
时间复杂度为
空间复杂度为O(1)
JAVA12345678910...