题目链接:merge-operations-to-turn-array-into-a-palindrome
解法:
用双指针来解决。整体思路是:从数组的左右两边开始看,
这个题还有一个很重要的细节,那就是在不断合并的过程中,合并的元素可能会超出int类型的范围。int类型是4字节32位,10进制最多表示10位。题目给出的array中元素范围是10进制的6位,但不断合并的过程中可能超出。所以得单独定义用于合并的leftSum和rightSum,类型为long。
参考题解:双指针
边界条件:
时间复杂度:O(n)
空间复杂度:O(1)
class Solution {
public:
int minimumOperations(vector<int>& nums) {
int n = nums.size();
int i = 0, j = n - 1;
// 注意这里是long类型,int类型是不行的,因为后面merge的时候,test case会超出32位8字节的限制
// 也因为如此,所以这俩值需要显式地提取出来,通过 nums[left+1] += nums[left] 这种方式来更新是不行的
long leftSum = nums[0], rightSum = nums[j];
int res = 0;
while (i < j) {
if (leftSum > rightSum) {
j--;
rightSum += nums[j];
res++;
} else if (leftSum < rightSum) {
i++;
leftSum += nums[i];
res++;
} else {
i++, j--;
leftSum = nums[i], rightSum = nums[j];
}
}
return res;
}
};
题目链接:number-of-islands
解法:
每块岛屿可以看成相连的一个个节点,只需把所有相连节点遍历殆尽并标上特殊值以记录该节点已访问过,则遍历殆尽时证明一块岛屿已找到。
总体思想是,从1个小岛开始,通过遍历所有垂直和水平方向的节点,把相邻的小岛连接起来变成一整块岛屿,同时标上特殊值用来记录该节点已经访问过了。遍历完毕时,一整块岛屿就找到了。再从另一个小岛开始,继续遍历。
DFS:找到为1的点,然后访问下、上、左、右4个方位(垂直和水平)。如果遇到1,就置为0,表示访问过了,再继续访问下上左右;如果遇到0,那么就是遇到水了,该递归方向返回。如果点的所有递归都返回了,那岛屿数量加1。然后再找下一个为1的点进行DFS。
BFS:找到为1的点,加入队列。弹出后,访问下、上、左、右4个方位(垂直和水平)。如果遇到1,就加入队列。先进先出。
参考题解:LeetCode 200:岛屿数量 Number of Islands - 知乎
边界条件:无
时间复杂度:O(M×N),其中 M 和 N 分别为行数和列数。
空间复杂度:DFS的O(M×N);BFD的O(min(M,N) ),在最坏的情况下(全部为陆地),队列的大小可以达到 min(M,N)。
// DFS
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int ROW = grid.size();
int COL = grid[0].size();
int res = 0;
for (int i=0; i<ROW; i++) {
for (int j=0; j<COL; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j, ROW, COL);
res++;
}
}
}
return res;
}
void dfs(vector<vector<char>>& grid, int i, int j, int ROW, int COL) {
// 递归终止条件
if (i <0 || j < 0 || i >= ROW || j >= COL) return;
if (grid[i][j] == '0') return;
grid[i][j] = '0'; // 置为0,避免再次被搜索
// 依次为下,上,左,右,这4个方向
dfs(grid, i-1, j, ROW, COL);
dfs(grid, i+1, j, ROW, COL);
dfs(grid, i, j-1, ROW, COL);
dfs(grid, i, j+1, ROW, COL);
}
};
// BFS
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int ROW = grid.size();
int COL = grid[0].size();
int res = 0;
for (int i=0; i<ROW; i++) {
for (int j=0; j<COL; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j, ROW, COL);
res++;
}
}
}
return res;
}
void bfs(vector<vector<char>>& grid, int i, int j, int ROW, int COL) {
queue<int> deque;
// 把二维表格展开为一维时的索引
deque.push(i*COL + j);
while (!deque.empty()) {
int idx = deque.front();
deque.pop();
int i = idx / COL, j = idx % COL;
// 别忘了不能越界,要加 (i-1) >= 0 这个条件
if ((i-1) >= 0 && grid[i-1][j] == '1') {
grid[i-1][j] = '0';
deque.push((i-1)*COL + j);
}
if ((i+1) < ROW && grid[i+1][j] == '1') {
grid[i+1][j] = '0';
deque.push((i+1)*COL + j);
}
if ((j-1) >= 0 && grid[i][j-1] == '1') {
grid[i][j-1] = '0';
deque.push(i*COL + j-1);
}
if ((j+1) < COL && grid[i][j+1] == '1') {
grid[i][j+1] = '0';
deque.push(i*COL + j+1);
}
}
}
};
题目链接:number-of-distinct-islands
解法:
这个题的整体思路和【200.岛屿的个数】差不多,只是加了一个记录整块岛屿的形状。
整块岛屿的形状就是每个小岛的形状的列表。而形状定义为相对于左上角第1个小岛的位置的偏移量,这样左上角第一个小岛的位置是(0, 0),下方的小岛则是(-1, 0)。这样,通过DFS或者BFS,可以得到这块岛屿上所有小岛的形状,从而得到整块岛屿的形状列表。
如果两块岛屿相对各自左上角的小岛的位置偏移量的列表相同,那么这两块岛屿形状相同。
要求不同的岛屿,那么就要把形状列表加入set中进行去重。
最后求set的长度即可。
BFS实现的步骤繁琐一些。
参考题解:https://blog.csdn.net/danspace1/article/details/86610850
边界条件:无
时间复杂度:O(mn)
空间复杂度:O(mn)
// DFS
class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int ROW = grid.size();
int COL = grid[0].size();
int res = 0;
// 左上角第1个小岛的位置为(0,0),先记录左上角,再记录其他小岛的位置
set<vector<pair<int,int>>> shapes;
for (int i=0; i<ROW; i++) {
for (int j=0; j<COL; j++) {
if (grid[i][j] == 1) {
vector<pair<int,int>> posVec;
// 左上角第1个小岛的位置为(0,0)
pair<int,int> pos(0, 0);
dfs(grid, i, j, posVec, pos);
shapes.insert(posVec);
res++;
}
}
}
return shapes.size();
}
void dfs(vector<vector<int>>& grid, int i, int j, vector<pair<int,int>>& posVec, pair<int,int>& pos) {
// 递归终止条件
int ROW = grid.size(), COL = grid[0].size();
if (i <0 || j < 0 || i >= ROW || j >= COL) return;
if (grid[i][j] == 0) return;
grid[i][j] = 0; // 置为0,避免再次被搜索
posVec.push_back(pos);
// 依次为下,上,左,右,这4个方向
vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
for (const auto& d: directions) {
// 计算相对左上角小岛的位置
pair<int,int> newPos = {pos.first+d.first, pos.second+d.second};
dfs(grid, i+d.first, j+d.second, posVec, newPos);
}
}
};
// BFS
class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int ROW = grid.size(),COL = grid[0].size(), res = 0;
set<vector<pair<int, int>>> shapes;
for (int i=0; i<ROW; i++) {
for (int j=0; j<COL; j++) {
if (grid[i][j] == 1) {
vector<pair<int,int>> posVec;
pair<int,int> idx(i, j), pos(0, 0);
bfs(grid, idx, posVec, pos);
shapes.insert(posVec);
res++;
}
}
}
return shapes.size();
}
void bfs(vector<vector<int>>& grid, pair<int,int> idx, vector<pair<int,int>>& posVec, pair<int,int>& pos) {
int ROW = grid.size(), COL = grid[0].size();
// 需要两个队列,一个装位置索引,一个装形状
queue<pair<int, int>> deque, posQue;
// 同时记录位置和形状
deque.push(idx), posQue.push(pos);
// 同时加入到整个岛屿的形状列表中
posVec.push_back(pos);
while (!deque.empty()) {
pair<int,int> curIdx = deque.front();
deque.pop();
pair<int,int> curPos = posQue.front();
posQue.pop();
vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
for (const auto& d: directions) {
int row = curIdx.first + d.first;
int col = curIdx.second + d.second;
if (row<0 || col<0 || row>=ROW || col>=COL) continue;
if (grid[row][col] == 0) continue;
grid[row][col] = 0;
pair<int,int> newIdx, newPos;
newIdx = {row, col};
newPos = {curPos.first+d.first, curPos.second+d.second};
deque.push(newIdx), posQue.push(newPos);
posVec.push_back(newPos);
}
}
}
};