kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是,kotori有强迫症,她不允许两个不同的正整数取出相同的素因子。
她想知道,最终所有取出的数的和的最小值是多少?
注:若 a mod k==0,则称 k 是 a 的因子。若一个数有且仅有两个因子,则称其是素数。显然1只有一个因子,不是素数。
思路:将每个数的质因子求出来,然后进行dfs找寻答案,不用考虑最小是因为根据题意找出来必然就是最小答案。
#include
using namespace std;
int n;
int a[1010];//正整数的值
int mi=1e9;
//判断是否为质数
bool primer(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0){
return false;
}
}
return true;
}
void dfs(int x,set<int> s,int temp){
if(x==n){
mi=min(mi,temp);
return;
}
for(int i=2;i<=a[x];i++){
if(a[x]%i==0 && primer(i)&&!s.count(i)){
s.insert(i);
dfs(x+1,s,temp+i);
s.erase(i);
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
set<int> s;
dfs(0,s,0);
if(mi==1e9)cout<<-1;
else cout<<mi;
return 0;
}
矩阵中多处聚集着1,要想统计1聚集的堆数而不重复统计,那我们可以考虑每次找到一堆相邻的1,就将其全部改成0,而将所有相邻的1改成0的步骤又可以使用深度优先搜索(dfs):当我们遇到矩阵的某个元素为1时,首先将其置为了0,然后查看与它相邻的上下左右四个方向,如果这四个方向任意相邻元素为1,则进入该元素,进入该元素之后我们发现又回到了刚刚的子问题,又是把这一片相邻区域的1全部置为0,因此可以用递归实现。
class Solution {
public:
//深度优先遍历与i,j相邻的所有1
void dfs(vector<vector<char>>& grid, int i, int j) {
int n = grid.size();
int m = grid[0].size();
//置为0
grid[i][j] = '0';
//后续四个方向遍历
if(i - 1 >= 0 && grid[i - 1][j] == '1')
dfs(grid, i - 1, j);
if(i + 1 < n && grid[i + 1][j] == '1')
dfs(grid, i + 1,j);
if(j - 1 >= 0 && grid[i][j - 1] == '1')
dfs(grid, i, j - 1);
if(j + 1 < m && grid[i][j + 1] == '1')
dfs(grid, i, j + 1);
}
int solve(vector<vector<char> >& grid) {
int n = grid.size();
//空矩阵的情况
if (n == 0)
return 0;
int m = grid[0].size();
//记录岛屿数
int count = 0;
//遍历矩阵
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
//遍历到1的情况
if(grid[i][j] == '1'){
//计数
count++;
//将与这个1相邻的所有1置为0
dfs(grid, i, j);
}
}
}
return count;
}
};
时间复杂度:O(nm),其中m、n为矩阵的长和宽,需要遍历整个矩阵,每次dfs搜索需要经过每个值为1的元素,但是最坏情况下也只是将整个矩阵变成0,因此相当于最坏遍历矩阵2次
空间复杂度:O(nm),最坏情况下整个矩阵都是1,递归栈深度为mn
class Solution {
public:
int solve(vector<vector<char> >& grid) {
int n = grid.size();
//空矩阵的情况
if(n == 0)
return 0;
int m = grid[0].size();
//记录岛屿数
int count = 0;
//遍历矩阵
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
//遇到1要将这个1及与其相邻的1都置为0
if(grid[i][j] == '1'){
//岛屿数增加
count++;
grid[i][j] = '0';
//记录后续bfs的坐标
queue<pair<int, int>> q;
q.push({i, j});
//bfs
while(!q.empty()){
auto temp = q.front();
q.pop();
int row = temp.first;
int col = temp.second;
//四个方向依次检查:不越界且为1
if(row - 1 >= 0 && grid[row - 1][col] == '1'){
q.push({row - 1, col});
grid[row - 1][col] = '0';
}
if(row + 1 < n && grid[row + 1][col] == '1'){
q.push({row + 1, col});
grid[row + 1][col] = '0';
}
if(col - 1 >= 0 && grid[row][col - 1] == '1'){
q.push({row, col - 1});
grid[row][col - 1] = '0';
}
if(col + 1 < m && grid[row][col + 1] == '1'){
q.push({row, col + 1});
grid[row][col + 1] = '0';
}
}
}
}
}
return count;
}
};
时间复杂度:O(nm),其中m、n为矩阵的长和宽,需要遍历整个矩阵,每次bfs搜索需要经过每个值为1的元素,但是最坏情况下也只是将整个矩阵变成0,因此相当于最坏遍历矩阵2次
空间复杂度:(min(n,m)),bfs最坏情况队列大小为长和宽的较小值