捕获黑皇后需要的最少移动次数(medium)做题过程总之就是一堆分类讨论。没做完,太烦了。
算法概述原题
本题要求为给出车、象、黑皇后的位置,黑皇后不动,看车和象需要多少步到黑皇后的位置。就是分类讨论。
时间复杂度为O(1)
空间复杂度为O(1)
JAVA123456789101112131415161718class Solution { public int min...
棋盘上有效移动组合的数目(hard)做题过程一开始没有读懂题目,以为是用回溯,后面又看了一下题目,还有按照时间每秒一步,每次只能往某个固定方向移动,而且只需要考虑一些特定的矛盾情形,那么就感觉需要推导出公式,就没做下去了,看了题解还是枚举,其实就和推导公式一个类型了。
算法概述原题
本题要求为给出一张8*8的棋盘,棋盘上有“车”,“后”,“象”等棋子,每个棋子,每秒按照一个固定的方向移动一...
检查棋盘方格颜色是否相同(easy)做题过程观察规律,得到规律。
算法概述原题
本题要求为给出字符串代表棋盘上格子位置,判断颜色是否一样。距离为偶则颜色一样,为奇则不一样。
时间复杂度为O(1)
空间复杂度为O(1)
JAVA123456789class Solution { public boolean checkTwoChessboards(String coord...
N皇后 II做题过程和N皇后思路一模一样,甚至还不需要构建棋盘,简单了很多,还是N皇后的思路,直接手撕了。
算法概述原题
时间和空间复杂度都与N皇后一致,N皇后也不会把棋盘纳入复杂度考虑。
JAVA1234567891011121314151617181920212223242526272829class Solution { int res=0; public in...
N皇后做题过程一开始想的就是 三个哈希集合 用来存不可访问位置,但后面发现更高效的解法根本 不用这么多变量 ,其实可以很高效的搞定,然后记了一遍,默了一遍,又让GPT给我矫正了一下错误,除去语法,思路是对的,还比原解更精简了一点。
算法概述原题
就是用一维数组存储每行皇后的位置,然后每次创建新的一行的皇后的位置的时候,遍历之前所有行,检查是否合适(是否会被攻击),其实还是有一点点浪费时间的...
判断是否可以赢得数字游戏(easy)做题过程直接一次遍历+计算两位数总和、一位数总和、总和,然后比较前两者是否小于第三者的一半,但实际上,只需要算前面两个,判断它们相不相等,因为 目标数组的范围不到三位数 。
算法概述原题
本题要求判断爱丽丝只取两位数或者一位数能不能赢取剩下数字的鲍勃。但实际上因为给定了数组最大值范围,所以完全可以 优化判断条件和减少临时变量使用 。
时间复杂度为O(n...
单调数组对的题目 II(hard)做题过程一开始我想的是用 双指针为基础的优化算法 ,然后感觉不太对,后面绝对可以试试看 多维动态规划(二维) ,又想了一下就没深思,就跳过去了,最后突然觉得 回溯 应该能写,结果还应该是 多维动态规划 。总之, 没做出来 。
算法概述原题
本题要求为给出一个数组,求出由两个非严格递增和非严格递减的数组相加能得到对应索引元素的可能有多少。使用 二维动态规划 ...
只出现一次的数字算法概述原题
本题要求为在给出的由一个出现一次的数字和其他出现两次的数字中找到那个出现一次的(要求时间复杂度为O(n),空间复杂度为O(1))。使用 位运算 解决。
JAVA12345678910class Solution { public int singleNumber(int[] nums) { int single = 0;...
不同路径算法概述原题
本题要求为统计二维矩阵中从左上角出发到右下角的所有可能。其实没区别的。
时间复杂度为O(mn):一次遍历
空间复杂度为O(n):经过优化
JAVA1234567891011121314class Solution { public int uniquePaths(int m, int n) { int[] cur = new...
爬楼梯算法概述原题
本题要求为在给定每次只能上一层或二层楼梯时,上n层楼梯有多少种选择。解法采取 动态规划 ,子问题结构为 前一次跨了一次楼梯和跨了两次楼梯代表的排列的和 。
时间复杂度为O(n):一共n级阶梯,每次都被当作为一个子问题
空间复杂度为O(1):无额外数据结构
JAVA1234567891011121314class Solution { public i...