写在22WN最后一个project完结之后

Apr 13th 2022

前言

本周终于做完了 370，281 两门课的 Project4，虽然并没有如释重负的感觉（因为后面就是 Final），但还是有点小开心。这篇博文就总结一下这次的两个 p4。

Cache

模拟一个简单的 Cache 运行，并且和 p1 写的 simulator 链接。需要考虑两种大情况，hit 和 miss，并且在 miss 时分类讨论是否有 empty block，难点应该是地址的转换。

Debug 教训

我写了一个比较离谱的 bug，if else 中都有 return，然后在 if else 结束之后写了一段对 LRU 的操作，如图：

导致对 LRU 的操作没有执行。

Pokemon

大概设定是你是一名宝可梦训练家，要收集齐所有宝可梦。从一些设定上看得出这个 Project 的作者应该是个资深的宝可梦的玩家，比如，二周目可以使用飞行（随意连接地图上的两个点），一周目如果要下海，必须先捕捉一只岸边的宝可梦获得冲浪技能。

PartA 本质上是写一个有限制的 MST，在搜寻目标点周围相邻点标记距离时增加一个 coast 和 sea 的判断（至少有一方在 coast 或两点都在 land），如果不符合则不标记两点之间的 d。MST 的本质是逐步选择和 SubGraph 最近的点并且逐步扩大 SubGraph，直到访问所有点。

PartB&C 关于 TSP（traveling salesperson problem），即找到一条最优的路径访问所有点后并回到起始点构成一个环（Hamiltonian cycle）。

PartB 需要完成一个 FastTSP（TSP Heuristics），即更快的找到一条相对接近 Optimal TSP 的路径。我使用了 Arbitrary Insertion 的方法。

随机选择第一个点 i
找到离 i 最近的第二个点 j，将路径设为 i -> j -> i。
对所有剩余的点进行循环，每次循环找到一个点加入当前的环（cost 最小），即遍历所有的 j 和 j-1 计算 (j -> candidate -> j-1) - (j -> j-1) cost 最小时即为最优点。
*具体可见 281NotesC22Page37

PartC 需要找到最优的 TSP，并尽可能优化算法，代码核心为 GenPerm（遍历所有可能的排列），为了尽可能增加效率，需要应用 Branch and Bound 的算法。那此时我们就需要考虑，如何得到算法需要的 upperBound 和 lowerBound？显然，upperBound 就是 PartB 的结果，lowerBound 的估计方法则是先找到两条 arm 一条从剩余点连接到 current path 的起始点，一条从剩余点连接到 current 的结尾点，并对剩余点计算 MST（minimum）。将 arm，current cost， MST 相加，结果极为 Lower Bound（在本问题可以视为最低 cost）。如下图所示：

Debug 教训

我起初并没有用 tempDis 保存 distance，而是直接在 += 时调用 distancs[][]，但此时因为 swap，OPTpath[i]中的数据已经改变，+-的数据错误。

Summary

LeetCode Daily Question 20

Apr 8th 2022

4 月 8 日每日一题

题目：1245. Tree Diameter

The diameter of a tree is the maximum number of edges on any path connecting two nodes of the tree. For example, here are three sample trees and their diameters. In each case, the longest path is bolded and shown in purple. Note that there may be more than one longest path.

Implement the diameter() function, which computes the diameter of a binary tree represented by a pointer to an object of the BinaryTreeNode class. Assume that nullptr represents an empty tree or a missing child. You may write helper functions.

思路

本道题是关于 tree 的递归题目。首先对问题进行分解，寻找问题和子问题的关系。
我们需要获得当前最大的 Diameter，它可能来自当前节点，左节点或右节点。
即 tempDia = max (leftDia, rightDia, tempDia)。而 Dia 等于 leftHeight + rightHeight + 1。
因此，我们需要先计算 height，height 等于 1 + max(leftHeight, rightHeight)。
为了将时间复杂度简化到 On，建立 struct 同时储存 Hight 和当前 Diameter，在一个递归函数中可以同时完成上面提到的两个问题。
临界条件为 nullpointer，返回{1,1}.

代码

#define min(a,b)            (((a) < (b)) ? (a) : (b))
#define max(a,b)            (((a) > (b)) ? (a) : (b))

struct BinaryTreeNode {
  BinaryTreeNode* left;
  BinaryTreeNode* right;
  int value;
  BinaryTreeNode(int n) : left{nullptr}, right{nullptr}, value{n} {}
};

struct NodeInfo{
    int height;
    int diameter;
};

NodeInfo helper(const BinaryTreeNode* tree){
    if(!tree){
        return NodeInfo{0,0};
    }
    NodeInfo left = helper(tree->left);
    NodeInfo right = helper(tree->right);
    int childrenDia = max(left.diameter, right.diameter);
    int selfDia = 1 + left.height + right.height;
    int tempDia = max(childrenDia, selfDia);
    return NodeInfo{ 1 + max(left.height , right.height), tempDia};
}

int diameter(const BinaryTreeNode* tree) {
    return helper(tree).diameter;
}

dailyQuestion, tree

LeetCode Daily Question 19

Apr 8th 2022

4 月 8 日每日一题

题目：130. Surrounded Regions

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

1
2
3

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

思路

今天这道题和昨天的差不多，在昨天的代码上做一些改动即可。即为进入 BFS 增加一个限制条件（必须在边界），在 BFS 中做好标记。最后循环一遍，将做好标记的点改为 O，其余改为 X。
等下再做一道放上来，这个和昨天的太像了…

代码

class Solution {
public:
    struct dequePoint
    {
        uint32_t x = 0;
        uint32_t y = 0;
    };

    bool valid(std::vector<std::vector<char>>& board, uint32_t x, uint32_t y){
        if(x >= 0 && x < board[0].size() && y >= 0 && y < board.size())
            return board[y][x] == 'O' ? true : false;
        return false;
    }
    bool valid1(std::vector<std::vector<char>>& board, uint32_t x, uint32_t y){
        if(x >= 0 && x < board[0].size() && y >= 0 && y < board.size())
            return true;
        return false;
    }

    void bfsHelper(std::vector<std::vector<char>>& board, uint32_t x, uint32_t y){
        queue<dequePoint> queue;
        queue.push(dequePoint{x,y});
        board[y][x] = 'x';
        while(!queue.empty()){
            x = queue.front().x;
            y = queue.front().y;
            queue.pop();
            if(valid(board, x - 1, y)){
                queue.push(dequePoint{x - 1,y});
                board[y][x - 1] = 'x';
            }
            if(valid(board, x + 1, y)){
                queue.push(dequePoint{x + 1,y});
                board[y][x + 1] = 'x';
            }
            if(valid(board, x, y - 1)){
                queue.push(dequePoint{x,y - 1});
                board[y - 1][x] = 'x';
            }
            if(valid(board, x, y + 1)){
                queue.push(dequePoint{x,y + 1});
                board[y + 1][x] = 'x';
            }
        }
    }

    void solve(std::vector<std::vector<char>>& board) {
        for(uint32_t y = 0; y < board.size(); y++){
            for(uint32_t x = 0; x < board[0].size(); x++){
                if(!valid1(board, x - 1, y) || !valid1(board, x + 1, y) ||
                   !valid1(board, x, y - 1) || !valid1(board, x, y + 1)){
                    if(board[y][x] == 'O'){
                        bfsHelper(board, x, y);
                    }
                }
            }
        }
        for(uint32_t y = 0; y < board.size(); y++){
            for(uint32_t x = 0; x < board[0].size(); x++){
                if(board[y][x] == 'x')
                    board[y][x] = 'O';
                else
                    board[y][x] = 'X';
            }
        }
    }
};

BFS, dailyQuestion

LeetCode Daily Question 18

Apr 7th 2022

4 月 7 日每日一题

题目：Number of Islands:

In this problem, you will be implementing the number of islands() function, as shown below:
int number_of_islands(std::vector<std::vector> &grid);
This function takes in a 2-D grid map filled with land (represented using the character ’o’) and water (represented using the character ’.’) and returns the number of islands that exist in the map. An island is formed by connecting adjacent land characters either horizontally or vertically. In other words, if two land characters are adjacent to each other horizontally or vertically, then they are a part of the same island.

思路

今天这道题并不是 leetcode，做法和昨天的 547 类似，在主函数遍历地图所有点，遇到新的地图时调用 BFS。本道题 BFS 使用了 queue 的写法。

代码

struct dequePoint
{
    uint32_t x = 0;
    uint32_t y = 0;
};

bool valid(std::vector<std::vector<char>>& grid, uint32_t x, uint32_t y){
    if(x >= 0 && x < grid[0].size() && y >= 0 && y < grid.size())
        return grid[y][x] == 'o' ? true : false;
    return false;
}

void bfsHelper(std::vector<std::vector<char>>& grid, uint32_t x, uint32_t y){
    queue<dequePoint> queue;
    queue.push(dequePoint{x,y});
    grid[y][x] = 'x';
    while(!queue.empty()){
        x = queue.front().x;
        y = queue.front().y;
        queue.pop();
        if(valid(grid, x - 1, y)){
            queue.push(dequePoint{x - 1,y});
            grid[y][x - 1] = 'x';
        }
        if(valid(grid, x + 1, y)){
            queue.push(dequePoint{x + 1,y});
            grid[y][x + 1] = 'x';
        }
        if(valid(grid, x, y - 1)){
            queue.push(dequePoint{x,y - 1});
            grid[y - 1][x] = 'x';
        }
        if(valid(grid, x, y + 1)){
            queue.push(dequePoint{x,y + 1});
            grid[y + 1][x] = 'x';
        }
    }
}

int number_of_islands(std::vector<std::vector<char>>& grid) {
    uint32_t islandNum = 0;
    for(uint32_t i = 0; i < grid.size(); i++){
        for(uint32_t j = 0; j < grid[0].size(); j++){
            if(grid[i][j] == 'o'){
                islandNum++;
                bfsHelper(grid, j, i);
            }
        }
    }
    return static_cast<int>(islandNum);
}

BFS, dailyQuestion

LeetCode Daily Question 17

Apr 6th 2022

4 月 6 日每日一题

题目：547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

思路

遍历所有 vertex，如果当前 vertex 为 unvisited，num++，并且使用 dfs 遍历该所有和该节点在一个 province 的节点，并把他们标记为 visited。dfs 结束后回到原函数继续对剩余 vertex 进行遍历。

代码

class Solution {
public:
    void dfsHelper(vector<vector<int>>& isConnected, vector<bool>& visited, int i){
        visited[i] =true;
        for(int j = 0; j < isConnected.size(); j++){
            if(isConnected[i][j] && !visited[j]){
                dfsHelper(isConnected, visited, j);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<bool> visited(isConnected.size(),false);
        int circleNum = 0;
        for(int i = 0; i < visited.size(); i++){
            if(!visited[i]){
                circleNum++;
                dfsHelper(isConnected, visited, i);
            }
        }
        return circleNum;
    }
};

DFS, dailyQuestion

LeetCode Daily Question 16

Mar 30th 2022

3 月 31 日每日一题

题目：560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

思路

因为 constrain 提到 nums 中可能有负数，所以本题无法使用 sliding window（无法保证区间缩小会使 sum 减小）。正确做法是使用一个命名为 prefixNum 的 hashmap 存储每一个 prefixSum 出现的次数。并使用一个 for 循环从 0 - 0， 0 - 1， 0 - 2 逐渐扩大 subarray size，如果当前的 sum - k 的数字可以在 hashmap 中找到，说明当前范围，减去 prefix 的范围可以得到 k，那么此时 res + prefixSum 的 second value。
本题需要考虑三个点，第一个 edge case 是 prefixSum 为 0 例如 1 + 1 为 2， k 为 2，并不需要减去 prefix，所以在开始遍历之前要给 prefixSum = 0 赋 1.
第二，不能先记录 prefixSum 再开始遍历，这样可能会出现 window 比当前区间大的情况。
第三，循环时应该先判断 judge 再记录 prefixSum，以避免 window 是当前区间本身。

代码


class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSum;
        prefixSum[0] = 1;
        size_t size = nums.size();
        int sum = 0;
        int res = 0;
        for(int i = 0; i < size; i++){
            sum += nums[i];
            int judge = sum - k;
            auto iter = prefixSum.find(judge);
            if(iter != prefixSum.end()){
                res += iter->second;
            }
            prefixSum[sum]++;
        }
        return res;
    }
};

错误实例：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSum;
        prefixSum[0] = 1;
        size_t size = nums.size();
        int res = 0;
        for(int i = 0; i < size; i++){
            int sum = 0;
            for(int j = i; j >= 0; j--){
                sum += nums[j];
            }
            int judge = sum - k;
            auto iter = prefixSum.find(judge);
            if(iter != prefixSum.end()){
                res += iter->second;
            }
            prefixSum[sum]++;
        }
        return res;
    }
};

dailyQuestion, hashMap, prefixSum

Summary of Projects for 281&370

Mar 28th 2022

前言

鸽了一周，今天开始恢复更新。就先总结过去一周所做的两个 Project，Pipelined Simulator & SillyQL。

Pipelined Simulator

370 的 p3，大概就是写一些代码模拟 pipeline 的运行过程，利用 Detect and Forward 处理 data Hazard，使用 branch-not-taken 解决 Control Hazard。因为暂时不会使用 c 语言的并行处理，所以利用两个 struct， State 和 newState 来模拟时钟上升沿 state 的瞬时更新。开写之前我其实没有完全理解这个方法，之后修改时又漏掉了 eq，给我造成了很大麻烦。所以教训是要严格遵守 spec 的要求，例如 State 都作为左值，newState 都作为右值。整体而言 p3 难度不算大，我个人比较喜欢这种概念性比较强的 Project。

SillyQL

模拟一个简陋版的 sql，spec 指定了几个功能，首先实现 create，print，insert，remove，delete，然后实现 generate（给一个 col 加 hash/bst 以提高查找速度），join（两个 table 的交集）。写完 generate 之后要对 print 做一些优化（’>’, ‘<’时使用 bst 的 upper_bound， ‘=’ 时使用 hash)。

这里并不需要对 delete 做什么优化，因为‘=’时 remove_if 和使用 hash 查找从后往前 delte 时间复杂度都是 O(n)。delete 结束后需要 rehash/rebst。此处我以为‘=’时可以直接 erase bst 里的 key，这个操作导致了很严重的 bug，因为 bst 的 value 里存储的是每一个 key 对应的 row 的 index，如果某一行被 delete，之后所有 row 的 index 都会前移，所以会导致 bst 存储的 index 完全失效。

p3 算是目前为止我接触的比较大的 project，spec25 页，程序大概 900 行。因为比较缺乏大型 project 的经验，前后写了很久，debug 花了一天半，因此误了好几节 recording。好在程序结构问题，不用做额外的 speed & memory 优化。所以，之后的大型 project 一定要早点开始。安排好时间，起码不要误课，而且一直做一件事效率有点低。。。

总之，相比这学期开始，代码能力也算有一些提升，但还有很长路要走啊…
结尾附图一张

Summary

Take a day off work

Mar 23rd 2022

今天还是不得不请假一天

连续写了三天的 sillyQL，说实话感觉一直做一件事效率真的很低，明天开始会恢复做题并且补一些 recording，希望能在周六前过掉 ag。

LeetCode Daily Question 15

Mar 22nd 2022

3 月 22 日每日一题

题目：287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2
Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

思路

hashmap 应该算这道题的暴力解法，等肝完 281project 之后可能会在这里更新其他方法。

代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_map<int, int> counts;
        for(int i = 0; i < nums.size(); i ++){
            auto &iter = counts[nums[i]];
            iter++;
            if(iter == 2)
                return nums[i];
        }
        return -1;
    }
};

dailyQuestion, hashMap

Take a day off work

Mar 21st 2022

请假一天

又是嗯赶 281，370project 的一天，暂时没时间做 leetCode 了，写完 project 后会在这里更新经验教训。
附图一张

前言

Cache

Debug 教训

Pokemon

Debug 教训

4 月 8 日 每日一题

题目：1245. Tree Diameter

思路

代码

4 月 8 日 每日一题

题目：130. Surrounded Regions

思路

代码

4 月 7 日 每日一题

题目：Number of Islands:

思路

代码

4 月 6 日 每日一题

题目：547. Number of Provinces

思路

代码

3 月 31 日 每日一题

题目：560. Subarray Sum Equals K

思路

代码

前言

Pipelined Simulator

SillyQL

今天还是不得不请假一天

3 月 22 日 每日一题

题目：287. Find the Duplicate Number

思路

代码

请假一天

4 月 8 日每日一题

4 月 8 日每日一题

4 月 7 日每日一题

4 月 6 日每日一题

3 月 31 日每日一题

3 月 22 日每日一题