Celery's Blog

0%

LeetCode-Day15

发表于 Valine：

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hashmap;
        for(auto s : strs){
            string temp = s;
            sort(temp.begin(), temp.end());
            hashmap[temp].push_back(s);
        }
        int len = hashmap.size();
        vector<vector<string>> ans(len);
        int index = 0;
        for(auto i : hashmap){
            ans[index] = i.second;
            ++ index;
        }
        return ans;
    }
};

解释：该题目的难点就在于如何将异位词对应于一个标签，这个时候就用到了sort，将每一个单词按照从小到大排序完，对应于map的key，然后如果出现异位词时，则他们的标签是一样的（即单词排完序之后是一样的）。

54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

1
2
3
4
5
6
7
输入:
[
 [ 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
输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty()) {
            return ans;
        }
        int u = 0, d = matrix.size() - 1, l = 0, r = matrix[0].size() - 1;
        while(true) {
            for(int i = l;i <= r;++i) {
                ans.push_back(matrix[u][i]);
            }
            if(++u > d) break;
            for(int i = u;i <= d;++i) {
                ans.push_back(matrix[i][r]);
            }
            if(--r < l) break;
            for(int i = r;i >= l;--i) {
                ans.push_back(matrix[d][i]);
            }
            if(--d < u) break;
            for(int i = d;i >= u;--i) {
                ans.push_back(matrix[i][l]);
            }
            if(++l > r) break;
        }
        return ans;
    }
};

解释：

这里的方法不需要记录已经走过的路径，所以执行用时和内存消耗都相对较小

  • 首先设定上下左右边界
  • 其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界
  • 判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案
  • 若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理
  • 不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

1
2
3
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

1
2
3
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int last = n - 1;
        for(int i = n - 1; i >= 0; --i){
            if(i + nums[i] >= last){
                last = i;
            }
        }
        return !last;
    }
};

贪心算法：

从最后一个位置开始，然后看前面的位置能否跳到当前位置及其后面，如果可以，就将最后的位置往前移动。