乐趣区

ARTS打卡活动第一周

jiezi

这是我第一次打卡，目的就是希望自己一直保持学习的状态，每天都了解一些新的技术；同时这也是我第一篇博客，写得不好还请见谅！

1.Algorithm 做一个 leetcode 的算法题

542.01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

解答：首先很容易就想到 DP，dist[i,j]=min(dist[i-1,j]+1, disti+1+1, disti+1, disti+1, disti), 每个点与它的邻接点对比，取最小的，扫描每一行每一列，直到没有变更为止，代码如下：

class Solution
{
public:
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
    {vector<vector<int>> ret(matrix.size());
        int max = 10001;
        for (int i = 0; i < matrix.size(); i++)
        {vector<int> vRow(matrix[i].size());
            for (int j = 0; j < matrix[i].size(); j++)
            {vRow[j] = matrix[i][j] == 0 ? 0 : max;
            }
            ret[i] = vRow;
        }
        bool b = true;
        while (b)
        {
            b = false;
            for (int i = 0; i < matrix.size(); i++)
            {for (int j = 0; j < matrix[i].size(); j++)
                {
                    //up
                    if (i - 1 >= 0 && ret[i][j] > ret[i - 1][j] + 1)
                    {
                        b = true;
                        ret[i][j] = ret[i - 1][j] + 1;
                    }
                    //down
                    if (i + 1 < matrix.size() && ret[i][j] > ret[i + 1][j] + 1)
                    {
                        b = true;
                        ret[i][j] = ret[i + 1][j] + 1;
                    }
                    //left
                    if (j - 1 >= 0 && ret[i][j] > ret[i][j - 1] + 1)
                    {
                        b = true;
                        ret[i][j] = ret[i][j - 1] + 1;
                    }
                    //right
                    if (j + 1 < matrix[i].size() && ret[i][j] > ret[i][j + 1] + 1)
                    {
                        b = true;
                        ret[i][j] = ret[i][j + 1] + 1;
                    }
                }
            }
        }
        return ret;
    }
};

这种算法的时间复杂度为 O(r*c*k)，其中 r 和 c 分别为行数和列数，k 是迭代的次数，如果 0 和 1 都相距很近的话，这个算法很快就迭代完成，然而如果 0 和 1 相距很远，比如矩阵只有左上角存在一个 0，那么右下角的 1 需要迭代约(r+c)/ 2 次，这样最糟的情况时间复杂度会上升一个级别，代码提交，耗时 188ms；

于是想另外一种算法减少冗余的计算，很容易就想到每个 0 点就像水里的波浪一样，一步一步的往四周扩散，每一次扩散（距离 +1），得到的结果就是最终结果，于是就联想到 BFS 算法，代码如下（耗时 168ms）：

class Solution
{
public:
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
    {int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>> ret(row, vector<int>(col, -1));
        struct Point{
            int x;
            int y;
            public:
            Point(int _x, int _y) {
                x = _x;
                y = _y;
            }
            Point() {
                x = 0;
                y = 0;
            }
        };
        struct Point p[10001];
        int l = 0, r  = 0;
        for (int i = 0; i < row; i++)
        {for (int j = 0; j < col; j++)
            {if (matrix[i][j] == 0) {ret[i][j] = 0;
                    p[r++] = Point(i, j);
                }
            }
        }
        Point diff[4] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        while (l < r) {Point cur = p[l++];
            int nextDist = ret[cur.x][cur.y] + 1;
            for (int i = 0; i < 4; i++) {int newX = cur.x + diff[i].x;
                int newY = cur.y + diff[i].y;
                if (newX >=0 && newX < row && newY >= 0 && newY < col && ret[newX][newY] == -1) {ret[newX][newY] = nextDist;
                    p[r++] = Point(newX, newY);
                    }
            }
        }
        return ret;
    }
};

这里有个点需要注意下，就是定义结构数组 struct Point p[10001]，一开始我的 Point 结构只定义带参数的构造函数，然后这句 p[10001]的定义编译不过，网上查了下结构数组的定义，一大堆文章的解决方案都是定义数组的同时初始化数组，但我这里显然没办法初始化。后面想到既然没有初始化数据，那是否需要定义一个默认的无参数构造函数，果然加上之后编译通过了。

2.Review 阅读并点评至少一篇英文技术文章

这周阅读的文章是 GameDev Protips: How To Survive As An Indie Developer，作者 Daniel Doan 提出，作为一个游戏独立开发者，想要在游戏行业中生存下来，需要学会以下几点：

  1. 关注你熟悉的领域。如果你是逻辑性很强的，那就选择成为程序员，如果不擅长编码的，可以做美术，如果你熟悉财务和市场相关的知识，可以做游戏发行；
  2. 游戏尽量简洁。一开始堆大量粗糙的功能，先不考虑能否按时完成，就算完成质量也很糟，用户体验和市场效果都不好。正确的做法是从玩家角度出发，玩家操作要尽量简单，容易上手，这样玩家才能享受游戏的乐趣；
  3. 学会舍弃。当某些需求消耗你大量的时间、精力或者金钱，但它又不是核心的功能需求，那就有必要考虑舍弃它。因为我们的时间、技术、金钱等资源是有限的，需要把有限的资源花在重要的需求上，这是项目管理要做的事情；
  4. 善于寻求帮助 因为我们每个人都不是万能的，我们有自己擅长的领域，但是还有很多其他方面的知识我们是不懂的，这个时候就需要向外寻求帮助，把自己不擅长的部分外包出去。比如我不懂美术，可以请美术外包，我不懂推广，可以将游戏交给游戏发行公司进行推广。

3.Tip 学习至少一个技术技巧

最近开始用 vscode（以前习惯用 sublime），这里分享几个我觉得比较常用的快捷键和设置吧

  • 在当前文件中快速定位接口的定义，Ctrl+Shift+O，然后输入关键字进行模糊搜索
  • 通过文件名快速在当前文件目录下查找该文件，Ctrl+P，然后输入文件名关键字进行模糊匹配
  • 跳转到接口的定义后，可以通过 Alt+←返回，类似的，通过 Alt+→往前跳转
  • 格式化代码，选中需要格式化的代码块后，Ctrl+K+ F 就可以
  • 修改代码 Tab 的缩进长度，File->Preferences->Settings，修改 Commonly Used 里面的 Editor：Tab Size. 然而有些时候修改了却没有生效，那是因为 Editor:Detect Indentation 被勾上了，它选中的意思是如果检测到原来代码的 Tab 缩进是 2，就算设置了 4，vscode 会临时改为 2，需要把这个选项去掉

4.Share 分享一篇有观点和思考的技术文章

分享一篇关于服务调用的文章
终于有人把服务调用说清楚了

退出移动版