LeetCode周赛181

作者 Lucyyang 日期 2020-03-23
LeetCode周赛181

昨天打了第181场比赛,居然被第二题坑了半天,扶额叹息,还是要注意复杂度分析啊。此外第三题也算是很常规的题目了,但是稍有些变化,比赛的时候没有做出来,也重点记录下。

第一题

题目:LC1389,按照给定的顺序来排列一个array。

方法:主要使用了vector的insert(pos, val)方法,注意pos输入为一个迭代器。

代码:

class Solution {
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
int n = nums.size();
vector<int> res;
auto it = res.begin();
for(int i = 0; i < n; i++){
it = res.begin() + index[i];
res.insert(it, nums[i]);
}
return res;
}
};

第二题

题目:LC1390,给出一组数中,所有只含4个因子的数的全部因子的和。

方法:注意给出的数据复杂度,如果是O(n2)就已经是109,不可取。**注意求因子时,只需求到sqrt(n)即可,再往后只是重复计算了。**此外还有一个小诀窍,除了1和n本身以外,由于只求到sqrt(n),循环中最多只能算出多余的一个因子,因此可以用last_i进行记录。当发现一个新的因子切last_i不等于0时,可以判断n含有超过4个因子,因此last_i直接置0即可。

代码:

class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int sum = 0;
for(auto n:nums){
int last_i = 0;
for(auto i = 2; i*i <= n; i++){
if(n % i == 0){
if(last_i == 0){
last_i = i;
}else{
last_i = 0;
break;
}
}
}
if(last_i != 0 && last_i != n/last_i) //排除相同情况
sum += 1 + n + last_i + n/last_i;
}
return sum;
}
};

第三题

题目:LC1391,常规但又很有意思的一道题,值得琢磨。

方法:讨论区有bfs,dfs和union find的做法,这里先参考bfs的做法。主要的思路就是,从一个格子出发,把能走通的格子都加入到queue中,并将visited置为true,最后再查看visted[N-1][M-1]是否为true即可。关键问题在于,如何判断两个格子之间是否能够走通:我们先从当前格子出发,按照给定的方向走到指定的格子,再判断从新的格子是否能走回去。如果能走回去,这两个格子就是联通的。可以以第一种和第二种road为例,如果第一种右边或者左边接了第二种road,根据当前所在的road 1是可以走到road 2的,但是根据road 2只能向上或者向下走,无法回到原格子,因此可以是不联通的,其他情况同理。

代码:

class Solution {
public:
vector<vector<pair<int, int>>> dirs = {{{0, -1},{0, 1}},
{{-1, 0},{1, 0}},
{{0, -1},{1, 0}},
{{0, 1},{1, 0}},
{{0, -1},{-1,0}},
{{0, 1},{-1, 0}}
};
bool hasValidPath(vector<vector<int>>& grid) {
int N = grid.size();
int M = grid[0].size();
bool visited[N][M];
memset(visited, 0, sizeof(visited)); // 注意要先全部设为false
queue<pair<int, int>> q;
q.push({0,0});
visited[0][0] = true;
while(!q.empty()){
pair<int, int> cur = q.front();
// cout<<"cur:"<<cur.first<<" "<<cur.second<<endl;
q.pop();
int x = cur.first;
int y = cur.second;
int num = grid[x][y] - 1;
for(auto dir:dirs[num]){
int nx = x + dir.first;
int ny = y + dir.second;
// cout<<"n:"<<nx<<" "<<ny<<endl;
if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny])
continue;
for(auto backdir:dirs[grid[nx][ny]-1]){
// cout<<"1"<<endl;
if(nx + backdir.first == x && ny + backdir.second == y){
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
}
return visited[N-1][M-1];
}
};