12th-March

To-do List

• [x] 算法

  • [x] graph

• [ ] 项目

  • [x] cmu15445
  • [ ] mit6.824
  • [ ] mit6.081

• [ ] 八股

  • [ ] 操作系统
  • [ ] 计算机网络
  • [ ] 数据库
  • [ ] redis

• [ ] 日常总结

1.算法

图论

(1)leetcode被围绕的区域

题面：

解答：从边缘的点开始dfs，先标记为’A’,再重新遍历修改

void dfs(vector<vector<char>> &board, int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'A';
        if (i - 1 >= 0 && board[i-1][j] == 'O') dfs(board, i - 1, j);
        if (j - 1 >= 0 && board[i][j-1] == 'O') dfs(board, i, j - 1);
        if (i + 1 < n && board[i+1][j] == 'O') dfs(board, i + 1, j);
        if (j + 1 < m && board[i][j+1] == 'O') dfs(board, i, j + 1);
    }

(2)leetcode课程表

题面：

题解：主要是拓扑排序，要是自己写可能就记录每个点的入度？然后从0开始，再一个一个遍历。但是其他题解是dfs，仔细想了想确实精妙。从一个点开始dfs，遍历他所有的节点，然后记录状态，最后记录当前节点，并放入答案中。

dfs重要代码：

void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
}

2.项目

cmu15445

Query Planning

emmm懒得总结了 大概就是说logical优化和physical优化

3.八股

今天没看。。。下次再说

4.总结

今天搞的有点少。。主要是晚上全在鼓捣这玩意，先好好准备一下周末的蚂蚁笔试，饿了么也可以

投递进度

公司	进度	备注
腾讯	已投递	等捞？
字节	已投递
百度	无消息 已投递
蚂蚁	3.16笔试
美团	笔试完
阿里云	已投递