Oyasumi1024

2.4万

lnyx

dushucheng0901
Caesar123

L-China

yxc的小迷妹

qweqasdzxc

Silvervale

zhyou

Oyasumi1024
21小时前

# BFS

class Solution {
public:
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
vector<vector<char>> g;
queue<pair<int, int>> q;
int n, m;

void bfs(int x, int y)
{
q.push({x, y});
g[x][y] = '#';  // 标记点(x,y)已经被访问过了

while (q.size())
{
auto t = q.front();
q.pop();

for (int i = 0; i < 4; i ++ )
{
int a = t.first + dx[i];
int b = t.second + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#' || g[a][b] == '0')   continue;
q.push({a, b});
g[a][b] = '#';  // 标记点(a,b)已经被访问过了
}
}
}

int numIslands(vector<vector<char>>& grid) {
g = grid;
if (g.empty() || g[0].empty())  return 0;
n = g.size(), m = g[0].size();

int res = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
// 如果点(i,j)没有被访问过 并且 它是陆地
if (g[i][j] != '#' && g[i][j] == '1')
{
bfs(i, j);
res ++ ;
}
}
}

return res;
}
};


# DFS

class Solution {
public:
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
vector<vector<char>> g;
queue<pair<int, int>> q;
int n, m;

void dfs(int x, int y)
{
g[x][y] = '#';

for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#' || g[a][b] == '0') continue;
dfs(a, b);
}
}

int numIslands(vector<vector<char>>& grid) {
g = grid;
if (g.empty() || g[0].empty())  return 0;
n = g.size(), m = g[0].size();

int res = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
if (g[i][j] != '#' && g[i][j] == '1')
{
dfs(i, j);
res ++ ;
}
}
}

return res;
}
};


Oyasumi1024
21小时前

# DFS

class Solution {
public:
vector<int> res;

void dfs(TreeNode *root, int dep)
{
if (!root)  return ;
if (dep == res.size())  res.push_back(root->val);

if (root->right)    dfs(root->right, dep + 1);
if (root->left )    dfs(root->left, dep + 1);
}

vector<int> rightSideView(TreeNode* root) {
if (!root)  return {};

dfs(root, 0);
return res;
}
};


# BFS

class Solution {
public:

vector<int> rightSideView(TreeNode* root) {
if (!root)  return {};
vector<int> res;
queue<TreeNode*> q;
q.push(root);

while (q.size())
{
int s = q.size();
for (int i = 0; i < s; i ++ )
{
auto t = q.front();
q.pop();

// 当前层的最后一个节点
if (i == s - 1)  res.push_back(t->val);

if (t->left)    q.push(t->left);
if (t->right)   q.push(t->right);
}
}

return res;
}
};


// 一维数组
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (!n )    return 0;
if (n == 1 )     return nums[0];
vector<int> f(n);
f[0] = nums[0];
f[1] = max(nums[0], nums[1]);

for (int i = 2; i < n; i ++ ) {
f[i] = max(f[i - 1], f[i - 2] + nums[i]);
}

return f[n - 1];
}
};

// 空间优化
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (!n )    return 0;
if (n == 1 )     return nums[0];
vector<int> f(n);
int first = nums[0], second = max(nums[0], nums[1]);

for (int i = 2; i < n; i ++ )
{
int tmp = second;
second = max(second, first + nums[i]);
first = tmp;
}

return second;
}
};


// 位运算
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
for (int i = 0; i < 32; i ++ )
if (n >> i & 1)
res ++ ;

return res;
}
};

// lowbit
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while (n)
{
n -= n & -n;
res ++ ;
}
return res;
}
};


class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; i ++ )  res = (res << 1) + (n >> i & 1);
return res;
}
};


class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};