1.题目一:实现 pow(x, n) ,即计算 x 的 n 次幂函数。
示例 1:
1 | 输入: 2.00000, 10 |
原题链接:https://leetcode-cn.com/problems/powx-n
如果利用常规方法用迭代或者递归来累乘的话那么会超时(用普通累乘递归时间复杂度为O(n),空间复杂度为O(n),用普通迭代时间复杂度为O(n),空间复杂度为O(1)),所以可以使用二分的方法
x^n=x^(n/2)*x(n/2)*x^(n%2);
Java:
1 | class Solution { |
还有一种方法他是利用了2进制的方法
将n->二进制数字,假设n为9,二进制数为1001那么x^9=x^8*x^1;可以利用二进制的思想来解决
jva:
1 | class Solution { |
2.N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:
1 | 输入:4 |
解释: 4 皇后问题存在两个不同的解法。
提示:
皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
链接:https://leetcode-cn.com/problems/n-queens
N皇后是一个经典利用回溯来解决的一个问题,可以从第一行开始放棋子,进行判断棋子是否可以放置,可以的话继续往下走,直到n个棋子都放置完成了,且满足放置条件的就算成功,且保存放入集合内。
时间复杂度O(n!),空间复杂度O(n)
1 | class Solution{ |
官方方法一:
1 | class Solution{ |
官方方法二:(利用了位运算)
1 | class Solution { |
3.N皇后二:
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给定一个整数 n,返回 n 皇后不同的解决方案的数量。
解题思路:和题目二一样利用回溯思想可以解决问题,相较于第二题少了对数组的保存
方法一:
1 | class Solution{ |
方法二:
1 | class Solution{ |
时间复杂度O(n!)
空间复杂度O(n)
4.螺旋矩阵:给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
示例 1:
1 | 输入: |
链接:https://leetcode-cn.com/problems/spiral-matrix
思路:通过模拟的方法来模拟出顺时针读取数据的方式发现了规律我们设置四个点rowhard[行的起点]=0,colhard[列的起点]=0,rowend[行的终点]=row.length-1,colend[列的终点]=col.length-1,从(rowhard,colhard)开始,先扫描第一行的数组里面的值,并读取并保存到list里面扫描到了终点之后,行的起点就+1,从新的起点(rowhard,colend)开始扫描列,扫描完了之后列的终点-1,然后从新的起点开始(rowend,colend),又开始行的扫描,扫描完之后行的终点-1,从新的起点(rowend,colhard)开始扫描,这四个步骤组成了一个循环,如果终极出现了起点大于终点那么说明数组的所有数据都已经扫描完毕了,那么应该结束循环。最后将数据集合返回。
1 | class Solution{ |
时间复杂度O(n^2);
空间复杂度O(1);
5.螺旋矩阵2:给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
1 | 输入: 3 |
链接:https://leetcode-cn.com/problems/spiral-matrix-ii
思路:题五和题四一样运用模拟的思路可以解析,不过与四不同的是这个是一个正方形矩阵,相对而言更加特殊(不需要去判断是否起点>大于中点,因为是正方矩形只要一边起点大于终点,另一边马上也会,他就不会继续给数组赋值,如果是长方形矩阵那么需要添加判断),可以直接模拟顺时针得到数组的row,col将依次递增的数填入数组,最后返回数组。
1 | class Solution{ |
时间复杂度O(n^2)
空间复杂度O(1)
总结:这五道题目所涉及的算法有分治、回溯、模拟、位运算,四大点,尤其是回溯与分治的思想在很多地方都用的着,这很有利于减少代码运行的时间复杂度。