头像

wangzitiansky


访客:1249

离线:11小时前


活动打卡代码 AcWing 200. 岛屿数量

wangzitiansky
11小时前

Flood Fill

DFS写法

class Solution {
public:
    int rows;
    int cols;
    int dist[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    void dfs(vector<vector<char>>& g, int row, int col){
        g[row][col] = '0';

        for(int i = 0; i < 4; i ++){
            int nx = row + dist[i][0];
            int ny = col + dist[i][1];
            if(nx >= 0 && nx < rows && ny >= 0 && ny < cols && g[nx][ny] == '1'){
                dfs(g, nx, ny);
            }
        }

    }

    int numIslands(vector<vector<char>>& grid) {
        rows = grid.size();
        if(rows == 0) return 0;
        cols = grid[0].size();
        int cnt = 0;
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    cnt ++;
                } 
            }
        }
        return cnt;
    }
};

BFS 写法

class Solution {
public:
    int rows;
    int cols;
    int dist[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    typedef pair<int, int> PII;

    void dfs(vector<vector<char>>& g, int row, int col){
        queue<PII> q;
        g[row][col] = '0';
        q.push({row, col});
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            int x = t.first;
            int y = t.second;
            for(int i = 0; i < 4; i ++){
                int nx = x + dist[i][0];
                int ny = y + dist[i][1];
                if(nx >= 0 && nx < rows && ny >= 0 && ny < cols && g[nx][ny] == '1'){
                    g[nx][ny] = '0';
                    q.push({nx, ny});
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        rows = grid.size();
        if(rows == 0) return 0;
        cols = grid[0].size();
        int cnt = 0;
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    cnt ++;
                } 
            }
        }
        return cnt;
    }
};


活动打卡代码 LeetCode 198. 打家劫舍

wangzitiansky
11小时前

class Solution {
public:

static const int N = 100010;
int INF = 0x3f3f3f3f;
int f[N][2];

int rob(vector<int>& nums) {
    memset(f, -INF, sizeof f);
    f[0][0] = 0;
    f[0][1] = 0;
    int n = nums.size();
    for(int i = 0; i < n; i ++){
        f[i + 1][1] = f[i][0] + nums[i];
        f[i + 1][0] = max(f[i][0], f[i][1]);
    }
    return max(f[n][0], f[n][1]);
}

};
```



活动打卡代码 LeetCode 191. 位1的个数

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



class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return nullptr;
        // 先考虑头结点要被删除的情况
        while(head && head->val == val) head = head->next;
        ListNode* cur = head;
        ListNode* pre;
        while(cur){
            // 如果当前结点的值是要被删除的值
            while(cur && cur->val == val) {
                // 将结点移动到val的后面
                cur = cur->next;
                pre->next = cur;
            }
            if(cur){
                // 移动 pre 和 cur
                pre = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};



from collections import deque


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        queue = deque()
        queue.append(root)
        res = []
        while queue:
            size = len(queue)
            while size > 0:
                size -= 1
                node  = queue.popleft()
                if size == 0:
                    res.append(node.val)
                children = [node.left, node.right]
                if any(children):
                    for child in children:
                        if child:
                            queue.append(child)
        return res



class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for(int i = 0; i < 32; i ++){
            // 检查此位是不是1 
            if(n >> i & 1){
                // 如果是 则将其对应移位
                res += 1 << (31 - i);
            }
        }
        return res;
    }
};



#include <iostream>
#include <algorithm>


using namespace std;
const int N = 10;
bool st[N];
int a[N];
int f[N];
int n;

void dfs(int u){
    if(u == n){
        for(int i = 0; i < n; i ++) printf("%d ", f[i]);
        puts("");
    }
    for(int i = 0; i < n; i ++){
        if(!st[i]){
            st[i] = true;
            f[u] = a[i];
            dfs(u + 1);
            st[i] = false;
            while(i + 1 < n && a[i + 1] == a[i]) i ++;
        }
    }
}

int main(){

    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);

    sort(a, a + n);

    dfs(0);

}



#include <iostream>


using namespace std;
const int N = 10;
int f[N];
bool st[N];
int n;

void dfs(int u){
    if(n == u){
        for(int i = 0; i < n; i ++) printf("%d ", f[i]);
        puts("");
    }
    for(int i = 1; i <= n; i ++ ){
        if(!st[i]){
            st[i] = true;
            f[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main(){

    scanf("%d", &n);

    dfs(0);

    return 0;
}



#include <iostream>


using namespace std;
const int N = 10;
int f[N];
bool st[N];
int n;

void dfs(int u){
    if(n == u){
        for(int i = 0; i < n; i ++) printf("%d ", f[i]);
        puts("");
    }
    for(int i = 1; i <= n; i ++ ){
        if(!st[i]){
            st[i] = true;
            f[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main(){

    scanf("%d", &n);

    dfs(0);

    return 0;
}



#include <iostream>


using namespace std;
const int N = 20;
bool st[N];
int n;

void dfs(int u){
    if(u > n){
        for(int i = 1; i <= n; i ++){
            if(st[i]) printf("%d ", i);
        }
        printf("\n");
        return;
    }

    st[u] = true;
    dfs(u + 1);

    st[u] = false;
    dfs(u + 1);
}

int main(){

    scanf("%d", &n);

    dfs(1);

}