leetCode进阶算法题+解析（六）
字母异位词分组
题目：给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
思路：数组代替下标的方式拆分每个单词。然后相同组成的放到一个list，不同的单独放。暂时思路就是这样，具体的我写写的时候会完善。我先去实现了。
额，实现是实现完了，就是和一开始的计划大不相同了。。哈哈。因为这道题确实可以数组代替下标来判断两个单词是否异位，但是这样就是两个数组的比较，太麻烦了，所以我这里换了个思路，直接排序字符串比较。而且用map判重，这样可以省略好多麻烦的操作（其实这个也麻烦，不过都有现成的api所以显得很简单），反正大概思路就是这样，然后一次提交成功了，直接贴代码：
class Solution {
HashMap<String,List<String>> res;
public List<List<String>> groupAnagrams(String[] strs) {
res = new HashMap<String,List<String>>();
for(String s : strs){
f(s);
}
List<List<String>> l = new ArrayList<List<String>> ();
for(List<String> value : res.values()){
l.add(value);
}
return l;
}
public void f(String s){
char[] c = s.toCharArray();
Arrays.sort(c);
String key = new String(c);
if(res.containsKey(key)){
List<String> list = res.get(key);
list.add(s);
res.put(key,list);
}else{
List<String> list = new ArrayList<String>();
list.add(s);
res.put(key,list);
}
}
}
本来我写的时候还觉得代码性能不会太好呢，因为各种排序，各种map 的containsKey判断，但是没想到性能超过了百分之九十八的人。但是虽然这种方式做完了，但是我仍然觉得其实我最开始的数组比较的方式也是可以实现的，不过太麻烦了我就没那么写。这道题就这么过吧。
Pow(x,n)
题目：实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
思路：这个题其实感觉很简单啊，不考虑溢出的话。就是遍历n次，每次乘自己。最后n是正的直接返回，n是负得1除得数。我去用测试案例试试怎么实现。
这个可以理解，接近于0
溢出所以是inf？
好了，这个题暴力解法很简单，但是超时。所以应该还是要简化简化的。至于怎么简化，我再想想。
emmmm....这就是一个简单的幂的公式，我记得在数据结构这本书的第一章就学了。如图，这个特性。我们在次可以用到。只要算出x的n/2次方，再乘方就可以了。其实上个方法也是对的，但是超时挡不住啊。
image.png
我直接贴代码：
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
double current_product = x;
for (long i = N; i > 0; i /= 2) {
if ((i % 2) == 1) {
ans = ans * current_product;
}
current_product = current_product * current_product;
}
return ans;
}
}
这道题其实很简单，所以也不多说了，直接下一题吧。
螺旋矩阵
题目：给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
思路:这道题我觉得比昨天做的那个原地旋转数组的要简单的多。然后这个题目目前的思路就是上下左右四个指针代表当前旋转到的外围点。其实语言表述很复杂，但是做起来应该很明了， 我去实现下。
做出来了，思路还行。超过百分之百的人。我直接贴代码：
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
int n = matrix.length;
if(n==0) return res;
int m = matrix[0].length;
int u = 0;
int b = n-1;
int l = 0;
int r = m-1;
//当前方向。0是往右 1是往下 2是往左 3是往上
int d = 0;
while(u<=b && l<=r){
if(d==0){
for(int i = l;i<=r;i++){
res.add(matrix[u][i]);
}
if(u==b) return res;
u++;
d++;
}
if(d==1){
for(int i = u;i<=b;i++){
res.add(matrix[i][r]);
}
if(r==l) return res;
r--;
d++;
}
if(d==2){
for(int i = r;i>=l;i--){
res.add(matrix[b][i]);
}
if(b==u) return res;
b--;
d++;
}
if(d==3){
for(int i = b;i>=u;i--){
res.add(matrix[i][l]);
}
if(l==r) return res;
l++;
d=0;
}
}
return res;
}
}
解释一下完整的思路:首先从最外圈开始转圈往res里add。d代表方向。然后每次add完一行，这行（如果是左边则l++。右边则r--.上面则u++，下面则b--）要去了。最后遍历完的标志为左右重合或者上下重合。
然后因为这个性能已经第一了，所以我就不看题解了。简单看了下评论，大概思路都是这样，只不过别人处理的比较优雅，看上去代码更简洁。不过无伤大雅，这个题就这样了。
跳跃游戏
题目：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
思路：这个题乍一看不难，其实我感觉需要判断的是能不能越过0.因为只要不是0就能往后跳，只有到某点是0，前面的所有元素都跳不过这个0才会false。其实我觉得这个应该算是一个标准的动态规划的题了。从第一个元素开始，第一个元素值范围内都是可选/不选。选了继续往下。如果最长值大于等于数组长度是true。不然是false。
额，这道题本来我想用动态规划来写的，但是想来想去没写出来并且开始怀疑自己是不是思路错了。因为一方面动态规划需要计算的太多了。每个格子可以跳跃的所有情况。需要的是每一个分支的走向。，另一方面看到了给的示例。到0那里就卡死了，其实应该是有规律的。所以我直接在群里讨论了这个题，最终被一种取巧的思路解出来了。
说一下思路：这个题其实思路就是从后往前遍历。首先最后一个点肯定是可以的，哪怕是0也是true，所以不用管最后一个节点。其次就是倒数第二个节点开始，每个节点判断是否能到最后一个节点，如果是的话，则前面的节点只要能到达这个节点就行了。最后遍历一遍，如果说第一个节点也就是下标是9的节点是可以到达的则true。第一个节点不可以到达则false。
其实只要明白思路代码是很简单的，我直接贴代码了：
class Solution {
public boolean canJump(int[] nums) {
int res = nums.length-1;
for(int i = nums.length-2;i>=0;i--){
if(nums[i]+i>=res){
res = i;
}
}
return res==0;
}
}
如果说是不可以到达的，比如示例二中的那个0，则会在那个元素就卡死了，后面的都进不了if里，res的结果会是3。
反正这道题我感觉就是拨开云雾的感觉。如果我不会各种所谓的算法可能还好一点，不用想什么动态规划，回溯之类的，直接按照题面上的意思考虑，可能有机会还想到这种做法。但是没有如果，一开始想着动规，回溯，思路越来越乱。还是在群友的提点下才算是做出来，每次做题都觉得学到些什么。
这篇文章就这样了。然后这篇文是大年三十开始写的，今天初二才算是写完了，挺不容易的。如果稍微帮到你了记得点个喜欢点个关注，也祝大家新年快乐！！！今年肺炎严重，希望大家别总出去溜达，健健康康的吧！
