缺失数字
给定一个包含 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())
{
return false;
}
int size = map[key].size();
for (int i = 0; i < size; i++)
{
if (loop(bottom, layer + map[key][i], count + 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';
}
}
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];
}
};
|
