1.Character deletion
class Solution {
public:
/**
* @param str: The first string given
* @param sub: The given second string
* @return: Returns the deleted string
*/
string CharacterDeletion(string &str, string &sub) {
// write your code here
char buf[256] = { 0 };
for (int i = 0; i < sub.size(); i++)
{
buf[sub[i]]++;
}
string ret;
for (int i = 0; i < str.size(); i++)
{
if (buf[str[i]] == 0)
ret += str[i];
}
return ret;
}
};
2.扫雷 一个dfs
class Solution {
public:
/**
* @param Mine_map: an array represents the map.
* @param Start: the start position.
* @return: return an array including all reachable positions.
*/
using pii = pair<int,int>;
vector<vector<int>> Mine_sweeping(vector<vector<int>> &Mine_map, vector<int> &Start) {
// write your code here
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
queue<pii> q;
q.emplace(Start[0],Start[1]);
int n=Mine_map.size(),m=Mine_map[0].size();
auto check = [&](int x,int y){
return x >= 0 && x < n && y>=0 && y<m;
};
set<vector<int>> temp;
while(q.size()){
auto t = q.front();
q.pop();
int i=t.first,j=t.second;
temp.insert(vector<int>{i,j});
if(!Mine_map[i][j]) continue;
Mine_map[i][j] = 0;
for(int k=0;k<4;k++){
int x = i + dx[k];
int y = j + dy[k];
if(check(x,y)) q.emplace(x,y);
}
}
return vector<vector<int>>(temp.begin(),temp.end());
}
};
3.旅行计划
class Solution {
public:
/**
* @param arr: the distance between any two cities
* @return: the minimum distance Alice needs to walk to complete the travel plan
*/
int travelPlan(vector<vector<int>> &arr) {
// Write your code here.
int n = arr.size();
vector<int> a;
for(int i=1;i<n;i++) a.emplace_back(i);
int ans =INT_MAX;
do{
int mini = 0,now = 0;
for(auto nxt : a){
mini += arr[now][nxt];
now = nxt;
}
ans = min(ans,mini + arr[now][0]);
}while(next_permutation(a.begin(),a.end()));
return ans;
}
};