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;
    }
};

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());
    }
};