数据结构1. 有数组 B[M](无重复元素) 1.1:输出从中取 k 个元素的组合 1.2:输出从中取 k 个元素的排列 1.3: 给定一个W和N,从B中找出k个元素,使这k个元素 之和小于等于 W 且 k 小于等于 N;输出结果中与 W 最接近 的那个 2. 给定一个矩阵 a[M][N],类似 1111011 0001000 0011010 1010011 1111100 输出所有为 0 的区域面积。如图有 4 个区域都为 0,面积分 别为 6 6 2 2
时间: 2023-05-31 10:01:30 浏览: 58
1.1:输出从中取 k 个元素的组合
使用回溯法,每次递归时选择当前元素或跳过当前元素,直到选择了 k 个元素为止。
代码:
void combination(vector<int>& nums, int k, vector<int>& cur, int start, vector<vector<int>>& res) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = start; i < nums.size(); i++) {
cur.push_back(nums[i]);
combination(nums, k, cur, i + 1, res);
cur.pop_back();
}
}
vector<vector<int>> getCombination(vector<int>& nums, int k) {
vector<vector<int>> res;
vector<int> cur;
combination(nums, k, cur, 0, res);
return res;
}
1.2:输出从中取 k 个元素的排列
同样使用回溯法,每次递归时选择当前元素或跳过当前元素,直到选择了 k 个元素为止。需要注意的是,每次选择一个元素后,需要在下一次递归中排除已经选择的元素。
代码:
void permutation(vector<int>& nums, int k, vector<int>& cur, vector<vector<int>>& res) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (find(cur.begin(), cur.end(), nums[i]) != cur.end()) continue;
cur.push_back(nums[i]);
permutation(nums, k, cur, res);
cur.pop_back();
}
}
vector<vector<int>> getPermutation(vector<int>& nums, int k) {
vector<vector<int>> res;
vector<int> cur;
permutation(nums, k, cur, res);
return res;
}
1.3:给定一个W和N,从B中找出k个元素,使这k个元素之和小于等于 W 且 k 小于等于 N;输出结果中与 W 最接近 的那个
使用动态规划,设 dp[i][j] 表示从前 i 个元素中取 j 个元素的最大和,则有:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + nums[i-1])
其中 nums[i-1] 表示第 i 个元素的值。需要注意的是,当 j > i 时,dp[i][j] 的值应该为 0。
遍历 dp[N][1], dp[N][2], ..., dp[N][N],找到最接近 W 的值即可。
代码:
int getClosestSum(vector<int>& nums, int W, int N) {
vector<vector<int>> dp(N+1, vector<int>(N+1));
for (int i = 0; i <= N; i++) dp[0][i] = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
if (j > nums.size() || i > nums.size()) dp[i][j] = 0;
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + nums[i-1]);
}
}
int closest = INT_MAX;
for (int i = 1; i <= N; i++) {
if (dp[N][i] <= W && W - dp[N][i] < W - closest) {
closest = dp[N][i];
}
}
return closest;
}
2. 给定一个矩阵 a[M][N],类似 1111011 0001000 0011010 1010011 1111100 输出所有为 0 的区域面积。
使用深度优先搜索,遍历矩阵中的每一个元素,如果当前元素为 0,则从该元素开始进行深度优先搜索,将所有相邻的 0 都标记为已访问过,直到所有相邻的 0 都被标记为已访问过,此时就找到了一个面积为 k 的 0 区域。
代码:
void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int i, int j, int& area) {
if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size() || visited[i][j] || matrix[i][j] == 1) return;
visited[i][j] = true;
area++;
dfs(matrix, visited, i+1, j, area);
dfs(matrix, visited, i-1, j, area);
dfs(matrix, visited, i, j+1, area);
dfs(matrix, visited, i, j-1, area);
}
int getZeroArea(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && matrix[i][j] == 0) {
int area = 0;
dfs(matrix, visited, i, j, area);
res += area;
}
}
}
return res;
}