有趣的算法04

有趣的算法04

​ 为提升算法、编程能力，开始刷LeetCode，一些于我有益的题记录在此系列中（或许对大佬们而言尽是些简单的题，还请见谅）。同时感谢解题区的大佬们。

The essence of mathematics lies in its freedom. --Cantor

[生命游戏]

【题目描述】

• 生命游戏，是英国数学家约翰.何顿.康威在1970年发明的细胞自动机。

• 每个细胞有一个初始状态：1表示为活细胞(live)，0为死细胞(dead)。每个细胞的下一状态，由当前其八邻域的细胞状态决定：

  1. 如果周围八个位置的活细胞数小于2，则该位置活细胞死亡；

     1. 如果周围八个位置的活细胞数为2或3，则该位置活细胞仍然存活；
     2. 如果周围八个位置的活细胞数大于3，则该位置活细胞死亡；
     3. 如果周围八个位置的活细胞数等于3，则该位置死细胞复活。
• 根据当前的细胞状态，得到下一状态的细胞情况。详细请参LeetCode 289. 生命游戏

【解法思路】

1. 题目比较简单，但还是很有趣的一道题，有点像卷积操作呢。不做思考，直接用最直接暴力的方法求解。

   public:
       void gameOfLife(vector<vector<int>>& board) {
           vector<vector<int>> ans(board);
   
           int dx[8] = {1,1,1,0,0,-1,-1,-1};
           int dy[8] = {1,-1,0,1,-1,1,-1,0};
   
           for(int i=0; i<board.size(); i++){
               for(int j=0; j<board[0].size(); j++){
                   int count = 0;
                   for(int k=0; k<8; k++){
                       int x = i+dx[k];
                       int y = j+dy[k];
                       if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && board[x][y]==1) count++; 
                   }
   
                   if(count<2) ans[i][j]=0;
                   else if(count>3) ans[i][j]=0;
                   else if(count==3) ans[i][j]=1;
               }
           }
           board = ans;
           return;
       }

2. 但进一步思考，能不能将原本的两个二维数组减少为一个，来降低空间复杂度呢？显然是可以的呢（用两位来记录，一位为当前，一位为之后的一个状态）。

   public:
       void gameOfLife(vector<vector<int>>& board) {
           int dx[8] = {1,1,1,0,0,-1,-1,-1};
           int dy[8] = {1,-1,0,1,-1,1,-1,0};
   
           for(int i=0; i<board.size(); i++){
               for(int j=0; j<board[0].size(); j++){
                   int count = 0;
                   for(int k=0; k<8; k++){
                       int x = i+dx[k];
                       int y = j+dy[k];
                       if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && board[x][y]%2==1) count++; 
                   }
   
                   if(count==2&&board[i][j]%2==1) board[i][j]=3;
                   else if(count==3) board[i][j]=2+board[i][j]%2;
               }
           }
           
           for(int i=0; i<board.size(); i++){
               for(int j=0; j<board[0].size(); j++){
                   board[i][j] >>= 1;
               }
           }
   
           return;
       }

[接雨水]

【题目描述】

• 给定一串非负整数，表示该宽度处柱子的高度，求下雨时能接住多少雨水。详细请参考LeetCode 42. 接雨水

【解法思路】

• 这道题理清了解法思路后，就变简单了，先找到最高的位置，然后从两端向最高处计算求和。

  public:
      int trap(vector<int>& height) {
          int maxPos = max_element(height.begin(),height.end()) - height.begin(); 
          int maxH = 0;
          int ans = 0;
  
          for(int i=0; i<maxPos; i++){
              if(maxH>height[i]) ans += maxH-height[i];
              else maxH = height[i];
          }
  
          maxH=0;
          for(int i=height.size()-1; i>maxPos; i--){
              if(maxH>height[i]) ans += maxH-height[i];
              else maxH = height[i];
          }
  
          return ans;
      }

[编辑距离]

【题目描述】

• 给定两个单词$word1$和$word2$，求将$word1$变为$word2$所使用的最少操作数(可以插入、删除、替换)。详细请参考LeetCode 72. 编辑距离

【解法思路】

• 这题有点头疼诶，只能透过评论区的题解来学习了呢(嘤嘤嘤我太差了)。

• 算法主要通过一个状态的前一个状态，来推断下一步的最小操作数，首先如图建立表格$cost$

  0	1	2	3	4	5
  1
  2
  3
  4

  • 表格中，列、列分别表示$word1$和$word2$的字母数；
  • 每一格$(x,y)$，表示将$word1[0..x]$变为$word2[0..y]$所用的最小操作数；
  • 初始化两边，如图所示；

  • 之后对每个$[x,y]$处：

    • 若$word1[x]==word2[y]$，则$cost[x,y]==cost[x-1,y-1]$；
    • 否则，$cost[x,y]$为$1+\min(cost[x-1,y-1],\min(cost[x,y-1],cost[x-1,y]))$

• 代码如下，

  public:
      int minDistance(string word1, string word2) {
          int len1 = word1.length();
          int len2 = word2.length();
  
          vector<vector<int>> cost(len1+1, vector<int>(len2+1));
  
          for(int i=0; i<=len1; i++) cost[i][0]=i;
          for(int j=0; j<=len2; j++) cost[0][j]=j;
          for(int i=1; i<=len1; i++){
              for(int j=1; j<=len2; j++){
                  if(word1[i-1]==word2[j-1])
                      cost[i][j] = cost[i-1][j-1];
                  else
                      cost[i][j] = 1+min(cost[i-1][j-1], min(cost[i][j-1],cost[i-1][j]));
              }
          }
  
          return cost[len1][len2];
      }

四月份LeetCode的打卡好难啊，难受~