缺失数字

给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

1
2
3
4
5
6
7
8
9
10

示例 1:

输入: [3,0,1]
输出: 2
示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

这道题很简单,但是解答方法很灵活

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
int missingNumber(vector<int>& nums) {
// 利用下标找出缺失的数字,需要两次遍历
vector<char> list(nums.size()+1,0);

for (int i = 0; i < nums.size(); i++)
{
list[nums[i]] = 1;
}

for (auto i = 0 ; i < list.size(); i++)
{
if (list[i] == 0) {
return i;
}
}
return 0;
}
};

最初我想到的方法是这样的,但是它的效果不是很理想,查看评论区发现有更好的方案

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int missingNumber(vector<int>& nums) {
int size = nums.size();
int res = size * (size - 1) / 2;
// 只有一个数字不存在,并且除了这个数以外都是连续的,只需要数列求和减去已有的即可
for (int i = 0; i < nums.size() ; i++)
{
res -= nums[i];
}
return res;
}
};

字母异位词分组

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

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

题目

最开始我想直接使用字符串总的ascii码作为判断是否由相同字母组成,但是对于一部分具有相同ascii码的字符串行不通,只好使用经过一定排列后的字符串作为区分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, int> index; // 哈希表,提高查找速度
int rel = 0;
string sorted;
for (auto i = 0; i < strs.size(); i++)
{
sorted = strs[i];
sort(sorted.begin(), sorted.end());
if (index.find(sorted) == index.end()) {
index[sorted] = rel;
res.push_back(vector<string>());
rel++;
}
res[index[sorted]].push_back(strs[i]);
}

return res;
}
};

金字塔转换矩阵

现在,我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。

使用三元组表示金字塔的堆砌规则如下:

对于三元组(A, B, C) ,“C”为顶层方块,方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当且仅当(A, B, C)是被允许的三元组,我们才可以将其堆砌上。

初始时,给定金字塔的基层 bottom,用一个字符串表示。一个允许的三元组列表 allowed,每个三元组用一个长度为 3 的字符串表示。

如果可以由基层一直堆到塔尖就返回 true ,否则返回 false 。

1
2
3
4
5
6
7
8
9
10
11
输入:bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出:true
解析:
可以堆砌成这样的金字塔:
A
/ \
G E
/ \ / \
B C D

因为符合('B', 'C', 'G'), ('C', 'D', 'E') 和 ('G', 'E', 'A') 三种规则。

题目

这题我想了好久啊,我还以为是个二叉树的问题。。。。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
unordered_map<string, vector<char>> map;

void init(vector<string>& allowed) {
for (size_t i = 0; i < allowed.size(); i++)
{
map[allowed[i].substr(0, 2)].push_back(allowed[i][2]);
}
}
bool pyramidTransition(string bottom, vector<string>& allowed) {
this->init(allowed);
return loop(bottom, "", 0);

}
bool loop(string bottom, string layer, int count) {

int length = layer.size();

if (bottom.size() == 1) // 到达顶部
{
return true;
}

if (length == bottom.size() - 1) { //成功
return loop(layer, "", 0);
}

if (count == length - 1) { // 超过尝试次数
return false;
}

string key = bottom.substr(count, 2);

if (map.find(key) == map.end()) // key不存在
{
return false;
}
int size = map[key].size();
for (int i = 0; i < size; i++)
{
if (loop(bottom, layer + map[key][i], count + 1)) { // 尝试深度+1 最底层有四个时只能最多尝试三次
return true;
}

}
return false;
}
};

被围绕的区域

给定一个二维的矩阵,包含 ‘X’ 和 ‘O’(字母 O)。

找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

1
2
3
4
5
6
7
8
9
10
11
12
13
示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后,矩阵变为:

X X X X
X X X X
X X X X
X O X X

题目

这道题目很简单,只需要搜索即可获得不错的效果

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
void solve(vector<vector<char>>& board) {
vector<int> keepX, keepY;

if (board.empty()) {
return;
}
// 遍历第一行和最后一行

for (int j = 0; j < board[0].size(); j++)
{
findKeepPostiton(keepX, keepY, board, 0, j);
findKeepPostiton(keepX, keepY, board, board.size() - 1, j);

}
// 遍历侧边两行
for (int i = 0; i < board.size(); i++)
{
findKeepPostiton(keepX, keepY, board, i, 0);
findKeepPostiton(keepX, keepY, board, i, board[0].size()-1);
}
for (int j = 0; j < board[0].size(); j++)
{
for (int i = 0; i < board.size(); i++)
{
board[i][j] = 'X'; // 将所有位置填充
}
}

for (int i = 0; i < keepX.size(); i++)
{
board[keepX[i]][keepY[i]] = 'O'; // 还原之前的O
}


}
void findKeepPostiton(vector<int>& x, vector<int>& y, vector<vector<char>>& board, int thisx, int thisy) {
if (thisx >= board.size() || thisx < 0) {
return;
}
if (thisy >= board[0].size() || thisy < 0) {
return;
}
if (board[thisx][thisy] == 'O') {
board[thisx][thisy] = 'X';
x.push_back(thisx);
y.push_back(thisy);
findKeepPostiton(x, y, board, thisx + 1, thisy);
findKeepPostiton(x, y, board, thisx - 1, thisy);
findKeepPostiton(x, y, board, thisx, thisy + 1);
findKeepPostiton(x, y, board, thisx, thisy - 1);
}

}

};

最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

1
2
3
4
5
6
7
8
9
10
11
示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

题目

这道题刚开始我准备使用搜索,但是这是不行的,会超出时间限制,只好使用动态规划的方法来解决

基本思路是遍历,然后将每一个位置填充为到达这个位置的最近距离(在从右和从下之间选择),由于左侧和上侧比较特殊,先计算沿着左侧和上侧走的距离

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
30
31
32
33
34
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int maxX = grid.size();
int maxY = grid[0].size();
// 横向
for (size_t i = 1; i < maxY; i++)
{
grid[0][i] = grid[0][i - 1] + grid[0][i]; // 将上一步的值加到下一步上,这样每一块的值就代表到达这块位置的路径长度
}
// 纵向
for (size_t i = 1; i < maxX; i++)
{
grid[i][0] = grid[i - 1][0] + grid[i][0]; // 同理

}
// 遍历中间
for (size_t i = 1; i < maxX; i++)
{
for (size_t j = 1; j < maxY; j++)
{
int a = grid[i - 1][j];
int b = grid[i][j - 1];
if (a < b) { // 在从左走和从右走之间选择最少的那一条路径
grid[i][j] = grid[i][j] + a;
}
else {
grid[i][j] = grid[i][j] + b;
}
}
}
return grid[maxX - 1][maxY - 1];
}
};