一、二叉树中序遍历
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
};
二、二叉树层序遍历
广度优先
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector <vector <int>> ret;
if (!root) {
return ret;
}
queue <TreeNode*> q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
ret.push_back(vector <int> ());
for (int i = 1; i <= currentLevelSize; ++i) {
auto node = q.front(); q.pop();
ret.back().push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
};
三、翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
四、反转链表
五、岛屿数量
image.png我们可以将二维网格看成一个无向图,竖直或水平相邻的 11 之间有边相连。
为了求出岛屿的数量,我们可以扫描整个二维网格。如果一个位置为 11,则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中,每个搜索到的 11 都会被重新标记为 00。
最终岛屿的数量就是我们进行深度优先搜索的次数。
class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
};
class Solution:
def dfs(self, grid, r, c):
grid[r][c] = 0
nr, nc = len(grid), len(grid[0])
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
self.dfs(grid, x, y)
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
self.dfs(grid, r, c)
return num_islands
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
grid[r][c] = "0"
neighbors = collections.deque([(r, c)])
while neighbors:
row, col = neighbors.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islands
六、买卖股票的最佳时机
七、全排列
image.pngclass Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有数都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
八、比较版本号
image.pngimage.png
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
ver1 = version1.split('.')
ver2 = version2.split('.')
# 用int可以去除前导零
len1 = len(ver1)
len2 = len(ver2)
if len1 > len2:
ver2.extend(['0'] * (len1 - len2))
if len2 > len1:
ver1.extend(['0'] * (len2 - len1))
for i in range(max(len1, len2)):
if int(ver1[i]) > int(ver2[i]):
return 1
elif int(ver1[i]) < int(ver2[i]):
return - 1
return 0
print(Solution().compareVersion(version1 = "1", version2 = "1.1"))
九、验证IPV4
image.pngimage.png
十、目标和
image.pngimage.png
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (S > sum) return 0; // 此时没有方案
if ((S + sum) % 2 == 1) return 0; // 此时没有方案
int bagSize = (S + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if (target+s)&1: return 0
V = (target+s) >> 1
f = [1] + [0]*V
for n in nums:
for i in range(V, n-1, -1):
f[i] += f[i-n]
return f[-1]
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
long sum = 0;
for (const int &it : nums) sum += it;
if ((S + sum) % 2 == 1 || S > sum) return 0;
S = (S + sum) / 2;
int *dp = new int[S + 1];
memset(dp, 0, (S + 1) * sizeof(int));
dp[0] = 1;
for (const int &it : nums) {
for (int j = S; j >= it; j--)
dp[j] += dp[j - it];
}
int ans = dp[S];
delete[] dp;
return ans;
}
};
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
return dfs(nums, S, 0);
}
int dfs(vector<int> &nums, uint target, int left) {
if (target == 0 && left == nums.size()) return 1;
if (left >= nums.size()) return 0;
int ans = 0;
ans += dfs(nums, target - nums[left], left + 1);
ans += dfs(nums, target + nums[left], left + 1);
return ans;
}
};
十一、网格最短路径
image.png image.pngstruct Nagato {
int x, y;
int rest;
Nagato(int _x, int _y, int _r): x(_x), y(_y), rest(_r) {}
};
class Solution {
private:
static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
if (m == 1 && n == 1) {
return 0;
}
k = min(k, m + n - 3);
bool visited[m][n][k + 1];
memset(visited, false, sizeof(visited));
queue<Nagato> q;
q.emplace(0, 0, k);
visited[0][0][k] = true;
for (int step = 1; q.size() > 0; ++step) {
int cnt = q.size();
for (int _ = 0; _ < cnt; ++_) {
Nagato cur = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = cur.x + dirs[i][0];
int ny = cur.y + dirs[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 0 && !visited[nx][ny][cur.rest]) {
if (nx == m - 1 && ny == n - 1) {
return step;
}
q.emplace(nx, ny, cur.rest);
visited[nx][ny][cur.rest] = true;
}
else if (grid[nx][ny] == 1 && cur.rest > 0 && !visited[nx][ny][cur.rest - 1]) {
q.emplace(nx, ny, cur.rest - 1);
visited[nx][ny][cur.rest - 1] = true;
}
}
}
}
}
return -1;
}
};
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if m == 1 and n == 1:
return 0
k = min(k, m + n - 3)
visited = set([(0, 0, k)])
q = collections.deque([(0, 0, k)])
step = 0
while len(q) > 0:
step += 1
cnt = len(q)
for _ in range(cnt):
x, y, rest = q.popleft()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] == 0 and (nx, ny, rest) not in visited:
if nx == m - 1 and ny == n - 1:
return step
q.append((nx, ny, rest))
visited.add((nx, ny, rest))
elif grid[nx][ny] == 1 and rest > 0 and (nx, ny, rest - 1) not in visited:
q.append((nx, ny, rest - 1))
visited.add((nx, ny, rest - 1))
return -1
网友评论