leetcode题解-1227-风机座位分配概率

发表于 2019-10-31 | 更新于 2019-11-03 | 分类于刷题

My way

习惯不是很好。。最开始试答案试出来结果的。

$1/n$, $1/2$, 然后得到正确解。。

因为第一眼看上去就是组合数学题，就类似你买彩票，先买后买的顺序不影响概率。

简单思路

为什么试$1/n$，以为要考虑的是$n$个状态取1个。

后来发现应该是$1/2$，感觉解释起来就有问题了。

水氷/Leoooooo/winterock way

简单递推dp的思路，在此略作修改。

状态定义：

\[ \begin{align*} & i:\ 第i个入座的人 \\ & n:\ 一共有n个座位 \\ & f[i]:\ 第i个入座的人，坐到自己位置上的概率 \\ \end{align*} \]

*状态转移方程：

\[ \begin{align*} f[i] = 1/n + (n-2)/n * f(n-1) \end{align*} \]

Leoooooo给出的推导过程：

$$ \[\begin{alignat}{1} f(n) = & 1/n & // \text{1st person picks his own seat, probability = 1/n} \\ &+ 1/n * 0 & // \text{1st person picks last one's seat, probability = 1/n} \\ &+ (n-2)/n * & // \text{1st person picks one of seat from 2nd to (n-1)th, probability = (n-2)/n} \\ &( \\ &\ \ \ 1/(n-2) * f(n-1) & // \text{1st person pick 2nd's seat, 2nd person becomes the new "careless" person, and there are n-1 seats left. it becomes subproblem of n-1.}\\ &\ \ \ 1/(n-2) * f(n-2) & // \text{1st person pick 3rd's seat, 2nd person will pick his own seat, 3nd person becomes the new "careless" person, and there are n-2 seats left. it becomes subproblem of n-2.}\\ &\ \ \ ......\\ &\ \ \ 1/(n-2) * f(2) & // \text{1st person pick (n-1)th's seat, (n-1)th person becomes the new "careless" person, there are 2 seats left.}\\ &) \\ \\ => & f(n) = 1/n & \text{\{when $n <= 2$\}} \\ & f(n) = 1/n + 1/n * ( f(n-1) + f(n-2) + f(n-3) + ... + f(2) ) & \text{\{when $n > 2$\}} \\ \end{alignat}\] $$

根据winterock给出的解释，简单来说:

按照条件概率，分成3种情况，在此以1号为例子：

$1/n$, 第1个人，选择了自己的座位，则对$2,...,n$位置空出来了，他们必然可以做到自己的位置，即$n$可以坐到自己的位置；
$1/n*0$, 第1个人坐到$n$位置上，则$n$必然坐不到自己位置上；
$(n-2)/n * (...)$ ，这个情况，简单来说就是，如果$i$坐到$k$位置上，则$(i,\ k)$里的人都能坐到自己位置上来，因为每个人看到自己位置空的时候必然坐上来。具体举例不展开了，很容易想明白。

证明结论为$f(n)=1/2$:

\[ \begin{align*} & \text{When}\ n <= 2 \\ & \ f(n) = 1/n \\ & \text{When}\ n > 2\ \text{(all these 5 formulas are correct, we can choose any one of them)} \\ & \ f(n) = 1/n + 1/n * ( f(n-1) + f(n-2) + f(n-3) + ... + f(2) ) \\ & \ f(n+1) = f(n)\\ & \ f(n) = 1/n + (n-2)/n * f(n) \\ & \ f(n) = 1/n + (n-2)/n * f(n-1) \ \text{is correct too since} f(n) == f(n-1) \\ & \ f(n) = 1/2 \\ \end{align*} \]

class Solution {
public:
    double nthPersonGetsNthSeat(int n)
    {
        double f[n+1];
        f[1] = 1;
        if(n == 1)
            return 1;
        for (int i = 2; i <= n; ++i)
            f[i] = (1 + (i - 2) * f[i - 1]) / (double)i;
        return f[n];
    }
};

总结

怎么求出合理的递推式用于状态转移方程。
- 这里是用了 条件概率来入手。
- 然后通过思考发现了这样一个规律:
  - 如果$i$坐到$k$位置上，则$(i,\ k)$里的人都能坐到自己位置上来，因为每个人看到自己位置空的时候必然坐上来。
有没有从组合数学的思路的解法呢？

Reference

水氷 leetcode 解

Leoooooo 状态转移方程详解

winterock 状态转移方程详解

leetcode题解-120-三角形最小路径

发表于 2019-10-31 | 更新于 2019-11-03 | 分类于刷题

题目

My way

很简单的二维dp思路，每一层的元素依赖于上一层同列元素和上一层前一列元素。

二维DP

状态定义：

\[ \begin{align*} & i:\ 行号 \\ & j:\ 列号 \\ & triangle[i][j]:\ 原始三角形上的i行,\ j列的数字 \\ & dp[i][j]:\ dp数组的i行,\ j列上的数字 \\ & 0 <= i == j <= n, n为行数 \end{align*} \]

状态转移方程:

\[ dp[i][j] = triangle[i][j] + min\{dp[i-1][j-1],\ dp[i-1][j] \} \]

Base case:

\[ dp[i][j] = triangle[i][j],\ \text{if $i == 0$ and $j == 0$} \]

Corner case:

\[ dp[i][j] = triangle[i][j] + dp[i-1][j],\ \text{if $j == 0$} \\ dp[i][j] = triangle[i][j] + dp[i-1][j-1],\ \text{if $i == j$} \]

C++实现

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>> dp(triangle);

        for (int i = 0; i < triangle.size(); ++i)
        {
            for (int j = 0; j < triangle[i].size(); ++j)
            {
                if (i == 0 && j == 0)
                {
                    dp[i][j] = triangle[0][0];
                }
                else if (i != 0 && j == 0)
                {
                    dp[i][j] = triangle[i][j] + dp[i-1][j];
                }
                else if (i == j)
                {
                    dp[i][j] = triangle[i][j] + dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j]);
                }
            }
        }

        return *min_element(dp[triangle.size()-1].begin(), dp[triangle.size()-1].end());
    }
};

一维DP

如何仅使用$O(n)$大小的额外空间呢？

因为每一行的状态仅依赖于上一行的状态，故可将二维DP to 一维DP.

对空间复杂度进行优化。

状态定义：

\[ \begin{align*} & i:\ 行号 \\ & j:\ 列号 \\ & triangle[i][j]:\ 原始三角形上的i行,\ j列的数字 \\ & dp[k]:\ dp数组的第k个数字 \\ & 0 <= j <= i <= k == n, n为行数 \\ \end{align*} \]

状态转移方程:

\[ dp[j] = triangle[i][j] + min\{dp[j-1], dp[j]\} \]

Base case:

\[ dp[j] = triangle[i][j],\ \text{if $i == 0$ and $j == 0$} \]

Corner case:

\[ dp[j] = triangle[i][j] + dp[j],\ \text{if $j == 0$} \\ dp[j] = triangle[i][j] + dp[j-1],\ \text{if $i == j$} \]

C++实现

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.size());

        for (int i = 0; i <= triangle.size() - 1; ++i)
        {
            for (int j = triangle[i].size() - 1; j >= 0; --j)
            {
                if (i == 0 && j == 0)
                {
                    dp[j] = triangle[0][0];
                }
                else if (i != 0 && j == 0)
                {
                    dp[j] = triangle[i][j] + dp[j];
                }
                else if (i == j)
                {
                    dp[j] = triangle[i][j] + dp[j-1];
                }
                else
                {
                    dp[j] = triangle[i][j] + min(dp[j-1], dp[j]);
                }
            }
        }

        return *min_element(dp.begin(), dp.end());
    }
};

Elon way

关键能有这个思路上的转变：

自顶向下最短距离 <=> 自底向上最短距离

自顶向下, 记忆化搜索

思路类似上面 二维DP。
还利用了树的遍历思维解决问题

class Solution {
    int row;
    Integer[][] memo;

    public int minimumTotal(List<List<Integer>> triangle) {
        row = triangle.size();
        memo = new Integer[row][row];
        return helper(0,0, triangle);
    }
    private int helper(int level, int c, List<List<Integer>> triangle){
        // System.out.println("helper: level="+ level+ " c=" + c);
        if (memo[level][c]!=null)
            return memo[level][c];
        if (level==row-1){
            return memo[level][c] = triangle.get(level).get(c);
        }
        int left = helper(level+1, c, triangle);
        int right = helper(level+1, c+1, triangle);
        return memo[level][c] = Math.min(left, right) + triangle.get(level).get(c);
    }
}

自底向上, DP

public int minimumTotal(List<List<Integer>> triangle) {
    int row = triangle.size();
    int[] minlen = new int[row+1];
    for (int level = row-1;level>=0;level--){
        for (int i = 0;i<=level;i++){   //第i行有i+1个数字
            minlen[i] = Math.min(minlen[i], minlen[i+1]) + triangle.get(level).get(i);
        }
    }
    return minlen[0];
}

总结

这里的自顶向下，自底向上 感觉就是我之前所理解的二维DP。不过我是采用非递归方式实现的，而这里是递归方式实现的。
*思考题目后，思路上的转变:
- 自顶向下最短距离 <=> 自底向上最短距离
以及多多尝试 递归方式实现此类DP。

Reference

Elon leetcode解法

extended

How to find minimum value from vector? [closed]

leetcode题解-64-最小路径和

发表于 2019-10-30 | 更新于 2019-11-03 | 分类于刷题

My way

第一眼感觉就是一个当前表格状态依赖于左边表格状态和上边表格状态的二维DP题。

状态定义：

\[ \begin{align*} & i:\ 表示第i行 \\ & j:\ 表示第j列 \\ & [i,\ j]:\ 表示第i行，j列上的数字\\ & grid[i][j]:\ 表示原始网格上第i行，j列上的数字\\ & dp[i][j]:\ 表示经过某些步之后，达到第i行，j列的时候，这个数字和的最小值\\ \end{align*} \]

状态转移方程：

\[ \begin{align*} & dp[i][j] = grid[i][j] + max(df[i-1][j],\ df[i][j-1]) \end{align*} \]

Base Case:

\[ \begin{align*} & df[0][0] = grid[0][0] \end{align*} \]

Corner Case:

\[ \begin{align*} & df[i][j] = grid[i][j] + df[i, j-1],\ \text{if $j-1$ == 0} \\ & df[i][j] = grid[i][j] + df[i-1, j],\ \text{if $j-1$ == 0} \end{align*} \]

C++实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<vector<int>> vvi(grid);

        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (i == 0 && j == 0)
                {
                    vvi[i][j] = grid[i][j];
                }
                else if (i == 0)
                {
                    vvi[i][j] = grid[i][j] + vvi[i][j-1];
                }
                else if (j == 0)
                {
                    vvi[i][j] = grid[i][j] + vvi[i-1][j];
                }
                else 
                {
                    vvi[i][j] = grid[i][j] + min(vvi[i-1][j], vvi[i][j-1]);
                }
            } 
        }
        return vvi[m-1][n-1];
    }
};

可以试试斜着遍历

!对于$m*n\ array$来说，不太好实现。

有一个思路就是补成正方形之后，然后以对角线的方式倾斜遍历数组。

官方解

1.暴力

不做解释了。

2.二维DP

类似我的思路。

3.一维DP

因为这里每个阶段的状态仅依赖上一个表格状态和左一个表格的状态，

再加上我们利用按行遍历的方式，依次求出每一行对应的$dp[i][j]$，然后得到结果。

官方Java解

public class Solution {
   public int minPathSum(int[][] grid) {
       int[] dp = new int[grid[0].length];
       for (int i = grid.length - 1; i >= 0; i--) {
           for (int j = grid[0].length - 1; j >= 0; j--) {
               if(i == grid.length - 1 && j != grid[0].length - 1)
                   dp[j] = grid[i][j] +  dp[j + 1];
               else if(j == grid[0].length - 1 && i != grid.length - 1)
                   dp[j] = grid[i][j] + dp[j];
               else if(j != grid[0].length - 1 && i != grid.length - 1)
                   dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
               else
                   dp[j] = grid[i][j];
           }
       }
       return dp[0];
   }
}

重上到下，C++实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<int> dp(grid[0].size());

        for (int i = 0; i < grid.size(); ++i)
        {
            for (int j = 0; j < grid[0].size(); ++j)
            {
                if (i == 0 && j == 0)
                {
                    dp[j] = grid[0][0];
                }
                else if (i == 0 && j != 0)
                {
                    dp[j] = grid[i][j] + dp[j-1]; 
                }
                else if (i != 0 && j == 0)
                {
                    dp[j] = grid[i][j] + dp[j];
                }
                else 
                {
                    dp[j] = grid[i][j] + min(dp[j], dp[j-1]);
                }
            }
        }

        return dp[grid[0].size()-1];
    }
};

Reference

leetcode 官方解

extended

Traverse an array diagonally

Traverse 2D m*n Array (Matrix) Diagonally

leetcode题解-96-不同的二叉搜索树

发表于 2019-10-29 | 更新于 2019-11-03 | 分类于刷题

题目

官方解

思考题目中，输入为$n$，表示由$n$个节点来构成二叉搜索树。

可以考虑到的是，每个子树的根节点不同，则为一个新的子树结构(包括 叶节点)。

所以要考虑到如何从 根节点 入手，以及对于当前根节点的左右子树的递推的方式解决。

动态规划

状态定义：

考虑到涉及到 输入节点个数$n$ 和所取 根节点$i$，可以定义如下： \[ \begin{align*} & F(i,\ n) = \text{以$i$为根节点，长度为$n$的二叉搜索树的树的个数} \\ & G(n) = \text{长度为$n$的二叉搜索树的树的个数} \\ \end{align*} \] 可以得到如下

状态转移方程/递推公式：

\[ \begin{align*} & G(n) = \sum_{i=1}^{n}F(i,\ n) \\ & F(i,\ n) = G(i-1) * G(n-i),\ 因为同一长度n的二叉搜索树个数一样 \\ & so\ we\ get: \\ & G(n) = \sum_{i=1}^{n}\{G(i-1) * G(n-i)\} \\ & 0 <= i <= n \end{align*} \]

Base case:

\[ \begin{align*} & G(0) = 0\\ & G(1) = 1\\ & 0 <= i <= n \end{align*} \]

$G[0] = 0$，

一方面说明 空树也是一种二叉搜索树。
一方面为了 构造的递推式中涉及到乘法，要保证乘积因子不为0才可。

public class Solution {
  public int numTrees(int n) {
    int[] G = new int[n + 1];
    G[0] = 1;
    G[1] = 1;

    for (int i = 2; i <= n; ++i) {
      for (int j = 1; j <= i; ++j) {
        G[i] += G[j - 1] * G[i - j];
      }
    }
    return G[n];
  }
}

数学way

数学归纳法：

可以归纳得出：$G(n)$的值被称为Catalan数$C_n$。

定义如下： \[ \begin{align*} & C_0 = 1, \\ & C_{n+1} = \frac{2(2n+1)}{n+2} C_n \end{align*} \]

class Solution {
  public int numTrees(int n) {
    // Note: we should use long here instead of int, otherwise overflow
    long C = 1;
    for (int i = 0; i < n; ++i) {
      C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return (int) C;
  }
}

总结

要考虑到二叉搜索树的基本定义之一
- 左子树上的值 < 根节点 < 右子树上的值
- 空树也是二叉搜索树的一种
*如何摸索出状态定义的中的2个状态：$n$, $i$.
- 题目已给条件中的状态有: 构成二叉搜索树的序列长度$n$。
- 考虑到子树的根节点不同，影响到二叉搜索树的结构，所以推测出: $i$是$[0,\ n]$中取的一个值作为根节点。
*Catalan数，一个组合数学问题常常涉及到的。

Reference

leetcode官方解

wikipidia-cn: catalan number

baidu baike: 卡特兰数

extended

C++ memory model

C memory model

leetcode题解-1221-分割平衡字符串

发表于 2019-10-28 | 更新于 2019-11-03 | 分类于刷题

题目

虽然打的是 贪心算法 的tag，但是我感觉实际上是括号匹配的简单变种。

解法

括号匹配/栈的做法

考虑L, R分别对应左右两个括号。

利用stack的push, pop和括号匹配的基本思路来完成。

栈为空，push当前元素。
top元素等于当前元素，push当前元素，否则pop top元素。
栈为空，平衡次数+1。

PS: 注意思路实现是带有先后顺序的。

class Solution {
public:
    int balancedStringSplit(string s) {
        int count = 0;
        stack<char> sc;
        for (int i = 0; i < s.size(); ++i)
        {
            char c = s[i];
            
            if (sc.empty() || c == sc.top())
            {
                sc.push(c);
            }
            else
            {
                sc.pop();
            }

            if (sc.empty())
            {
                ++count;
            }
        }

        return count;
    }
};

利用数字计数代替括号匹配做法

因为这里不同于括号匹配需要是一个<>的匹配状态，可以是LR, RL, LLRR, RRLL，

也就是说可以看成一个简单版本的括号匹配过程，

因为不需要要求L, R之间的先后关系，所以可以通过 数字计数 取代掉 栈括号匹配 的过程。

若当前元素为L, 计数++num；为R, 计数--num;
若num == 0, 则平衡次数+1。

class Solution {
public:
    int balancedStringSplit(string s) {
        int num = 0; 
        int count = 0;

        for (auto it = s.begin(); it < s.end(); ++it)
        {
            if (*it == 'L')
            {
                ++num;
            }
            else
            {
                --num;
            }

            if (num == 0)
            {
                ++count;
            }
        }

        return count;
    }
};

总结

这题提及的"尽可能多的平衡字符串分割“ + 实例，说明了这里的字符串分割是不存在前后分割出的字符串结果有交集的。
- 可以思考到，正常的从头到尾的一次遍历即可。
提及的” ‘L’和'R'字符的数量是相同的 ", 并没有提及到 L和R要有前后顺序的关系
- 可以思考到，利用 数字计数法 代替 括号匹配法。

Reference

Karua leetcode 题解

amanehayashi leetcode 题解

Extended

std::stack

STL header stack

iterator library

leetcode题解: 877.石子游戏

发表于 2019-10-27 | 更新于 2019-11-03 | 分类于刷题

题目

官方解

数学way

直接从官方解处摘抄过来，很有意思的数学归纳证明思想。如下：

显然，亚历克斯总是赢得 2 堆时的游戏。通过一些努力，我们可以获知她总是赢得 4 堆时的游戏。

如果亚历克斯最初获得第一堆，她总是可以拿第三堆。如果她最初取到第四堆，她总是可以取第二堆。第一 + 第三，第二 + 第四中的至少一组是更大的，所以她总能获胜。

我们可以将这个想法扩展到 N 堆的情况下。设第一、第三、第五、第七桩是白色的，第二、第四、第六、第八桩是黑色的。亚历克斯总是可以拿到所有白色桩或所有黑色桩，其中一种颜色具有的石头数量必定大于另一种颜色的。

因此，亚历克斯总能赢得比赛。

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

综评最高解

在dp解释上强于官方解，简要摘取部分过程，详细见reference处。

对于$piles=[3, 9, 1, 2]$,

定义状态：

\[ dp[i][j].fir\ or\ dp[i][j].sec\\ 其中：\\ 0 <= i < piles.length, i相当于石子堆最左堆\\ i <= j < piles.length, j相当于石子堆最右堆 \] 其中， \[ dp[i][j].fir表示，对于piles[i...j]这部分石子，先手能获得的最高分数 \\ dp[i][j].sec表示，对于piles[i...j]这部分石子，后手能获得的最高分数 \]

状态转移方程为：

\[ dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec) \\ \]

$$ \[\begin{align*} & if 先手选择左边: dp[i][j].sec = dp[i+1][j].fir \\ & if 先手选择右边: dp[i][j].sec = dp[i][j-1].fir \\ & 解释：\\ & 我作为后手，要等先手先选择，有两种情况： \\ & 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j] \\ & 此时轮到我，我变成了先手；\\ & 如果先手选择了最右边那堆，给我剩下了 piles[i...j-1] \\ & 此时轮到我，我变成了先手。\\ \end{align*}\] $$

base case

\[ \begin{align*} & dp[i][j].fir = piles[i] \\ & dp[i][j].sec = 0 \\ & 其中 0 <= i == j < n \\ & 解释：i 和 j 相等就是说面前只有一堆石头 piles[i] \\ & 那么显然先手的得分为 piles[i] \\ & 后手没有石头拿了，得分为 0 \\ \end{align*} \]

这里需要注意一点，我们发现 $base\ case$是斜着的，而且我们推算 dp[i][j] 时需要用到 dp[i+1][j] 和 dp[i][j-1]：

所以说算法不能简单的一行一行遍历 dp 数组，而要斜着遍历数组：

实现

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();

        // initialize dp array
        vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(n, make_pair(0, 0)));

        // fill with base case
        for (int i = 0; i < n; ++i)
        {
            dp[i][i].first = piles[i];
            dp[i][i].second = 0;
        }

        // traverse array in a diagonal way
        for (int l = 2; l <= n; ++l)
        {
            for (int i = 0; i <= n - l; ++i)
            {
                int j = i + l - 1;

                // 先手选择最左边或者最右边的分数
                int left = piles[i] + dp[i+1][j].second;
                int right = piles[j] + dp[i][j-1].second;

                // 套用状态转移方程
                if (left > right)
                {
                    dp[i][j].first = left;
                    dp[i][j].second = dp[i+1][j].first;
                }
                else
                {
                    dp[i][j].first = right;
                    dp[i][j].second = dp[i][j-1].first;
                }
            }
        }
        pair<int, int> res(dp[0][n-1]);

        return res.first - res.second;
    }
};

综评Java实现

/* 返回游戏最后先手和后手的得分之差 */
int stoneGame(int[] piles) {
    int n = piles.length;
    // 初始化 dp 数组
    Pair[][] dp = new Pair[n][n];
    for (int i = 0; i < n; i++) 
        for (int j = i; j < n; j++)
            dp[i][j] = new Pair(0, 0);
    // 填入 base case
    for (int i = 0; i < n; i++) {
        dp[i][i].fir = piles[i];
        dp[i][i].sec = 0;
    }
    // 斜着遍历数组
    for (int l = 2; l <= n; l++) {
        for (int i = 0; i <= n - l; i++) {
            int j = l + i - 1;
            // 先手选择最左边或最右边的分数
            int left = piles[i] + dp[i+1][j].sec;
            int right = piles[j] + dp[i][j-1].sec;
            // 套用状态转移方程
            if (left > right) {
                dp[i][j].fir = left;
                dp[i][j].sec = dp[i+1][j].fir;
            } else {
                dp[i][j].fir = right;
                dp[i][j].sec = dp[i][j-1].fir;
            }
        }
    }
    Pair res = dp[0][n-1];
    return res.fir - res.sec;
}

总结

二维DP，也是递推问题，但是给人的没有一维DP那么好处理。
- 状态定义，一般涉及到2个状态$i,\ j$。可以用表格法表示，有点类似0-1背包问题。
- 状态转移方程，一般涉及到上一状态的2个状态。
- base case, 我的理解是一般类似于 corner case的存在，是一个需要考虑到的初始条件。
斜着遍历数组，这个在实现的时候，也不是一件非常容易的事情。
- 1
  2
  3
  4
  5
  6
  7
  8
  9
  // traverse array in a diagonal way
  for (int l = 2; l <= n; ++l)
  {
  for (int i = 0; i <= n - l; ++i)
  {
  int j = i + l - 1;
  // ...
  }
  }
  若$n = 4$, 则依次遍历： \[ \begin{align*} & [0,\ 1],\ [1,\ 2], [2,\ 3], [3,\ 4] \\ & [0,\ 2],\ [1,\ 3], [2,\ 4] \\ & [0,\ 3],\ [1,\ 4] \\ & [0,\ 4] \\ \end{align*} \]

Reference

labuladong: leetcode解

leetcode 官方解

extended

std::pair

std::vector

leetcode题解: 1025.除数博弈

发表于 2019-10-24 | 更新于 2019-11-03 | 分类于刷题

题目

My way:

这题靠归纳推理，首先很明显就能看出来偶数的时候Alice赢了；

然后多举了几个例子就发现奇数的时候Bob赢了。

就直接一个条件语句，结束。

但是尝试套dp的做法的时候，没捋清楚，看了综评最高的，基本懂了。

class Solution {
public:
    bool divisorGame(int N) {
        if (!(N & 1))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

综评最高解

1.归纳法：

基本思路：

最终结果应该是占到 2 的赢，占到 1 的输；
若当前为奇数，奇数的约数只能是奇数或者 1，因此下一个一定是偶数；
若当前为偶数，偶数的约数可以是奇数可以是偶数也可以是 1，因此直接减 1，则下一个是奇数；

因此，奇则输，偶则赢。

1
2
3

class Solution:
    def divisorGame(self, N: int) -> bool:
        return N%2==0

2.DP:

定义状态
- $i$: 数字$N$为$i$时；
- $f[i]$: 数字$N$为$i$时，Alice的胜负状况，true为胜，false为负。
定义状态转移方程：

\[ f[i] = \begin{cases} true, & \text{if}\ f[i-j] == false,\ \text{if}\ i\ \%\ j == 0\ \\ & and\ j\ is\ unsigned\ integer\ which \in (0, N) \ \\ false, & \text{otherwise} \end{cases} \]

实现

class Solution {
public:
    bool divisorGame(int N) {
        vector<bool> vi(N+1);

        for (int i = 2; i < N + 1; ++i)
        {
            for (int j = 1; j <= i / 2; ++j)
            {
                if (vi[i-j] == false && i % j == 0)
                {
                    vi[i] = true;
                }
            }
        }


        return vi[N];
    }
};

综评解

class Solution:
    def divisorGame(self, N: int) -> bool:
        target = [0 for i in range(N+1)]
        target[1] = 0 #若爱丽丝抽到1，则爱丽丝输
        if N<=1:
            return False
        else:
        
            target[2] = 1 #若爱丽丝抽到2，则爱丽丝赢
            for i in range(3,N+1):
                for j in range(1,i//2):
                    # 若j是i的余数且target[i-j]为假（0）的话，则代表当前为真（1）
                    if i%j==0 and target[i-j]==0:
                        target[i] = 1
                        break
            return target[N]==1

总结

初等数学review:
- 奇数的因数： {奇数}
- 偶数的因数： {偶数}
- 奇数的最大公因数 = 奇数
目前做到的dp还是简单递推问题，可以简单套换成：
- 状态$i$就是数字为$i$的时候
- $f[i]$就是数字为$i$时候，结果为$f[i]$

Reference

pandawakaka 给出的解

leetcode题解: 338.比特位计数

发表于 2019-10-23 | 更新于 2019-11-03 | 分类于刷题

题目

My way:

这题tag是dp，按着dp的思路写出了状态， 状态转移方程包括 边界条件， 常规情况。

大致思路如下：

定义状态：
- $i$: 数字为$i$时；
- $f[i]$: 数字为i时，$f[i]$表示有多少个1，在数字$i$的二进制表示形式下。
状态转移方程：
- 边界：$f[0] = [\ \ ]$
- 正常情况：(第一时间也拿不出来，通过举例拿到的，)
  
  eg.
  
  $f[1] = 1$
  
  $f[2] = 1$
  
  $f[3] = 1 + 1 = f[2] + f[1]$
  
  $f[4] = 1$
  
  $f[5] = 2 = f[4] + f[1]$
  
  $f[6] = 2 = f[4] + f[2]$
  
  $f[7] = 3 = f[4] + f[2] + f[1]$
  
  得到： \[ f[i] = \begin{cases} [\ \ ], & \text{if}\ i == 0 \\ 1, & \text{if}\ i == 2^m,\ \text{m is unisgned integer} \\ 1 + f[i - j], & \text{if}\ 2^j < i < 2^{j+1},\ \text{j is unsigned integer} \end{cases} \] 合并下情况有： \[ f[i] = 1 + f[i-j],\ \text{if}\ 2^j < i < 2^{j+1},\ \text{j is unsigned integer} \]

然后以Cpp实现了如下：

class Solution {
public:
    vector<int> countBits(int num) {
        if (num == 0)
        {
            return vector<int>{0};
        }
        
        if (num == 1)
        {
            return vector<int> {0, 1};
        }
        
        vector<int> vi {0, 1};
        
        for (int i = 2; i < num+1; ++i)
        {
            int j;
            for (j = 0; pow(2, j) <= i; ++j)
            {}
            j = pow(2, j-1);
                    
            int val;
            if (i-j-1 == -1)
            {
                val = 1;
            }
            else
            {
                val = 1 + vi[i-j];
            }
            vi.push_back(val);
        }
        
        return vi;
    }
};

不过很遗憾这是一种很低效的解法

Standard Way

详细解释见之后reference的官方解释link处，这里只给出最后的思路/状态转移方程和我的一些理解及实现。

1.Pop Count

思路

利用位运算x & (x - 1)来不断消除最右边的一位1，直至数字为0时，可以算出这个数字有多少位1。

PS：确实没想到位运算这块，思维狭隘了。

实现

class Solution {
public:
    vector<int> countBits(int num) {
        if (num == 0)
        {
            return vector<int>{0};
        }
        
        if (num == 1)
        {
            return vector<int> {0, 1};
        }

        vector<int> vi {0, 1, };

        for (int i = 2; i < num + 1; ++i)
        {
            vi.push_back(pop_count(i));
        }

        return vi;
    }

private:
    int pop_count(int num)
    {
        // 通过 x &= x - 1 的位运算操作，来消除掉一个数从左到右的最右边的一个1
        int count;
        for (count = 0; num != 0; ++count)
        {
            num &= num - 1;
        }

        return count;
    }
};

官方解这里利用了 default initialization来implicit初始化未初始化的结果。

public class Solution {
    public int[] countBits(int num) {
        int[] ans = new int[num + 1];
        for (int i = 0; i <= num; ++i)
            ans[i] = popcount(i);
        return ans;
    }
    private int popcount(int x) {
        int count;
        for (count = 0; x != 0; ++count)
          x &= x - 1; //zeroing out the least significant nonzero bit
        return count;
    }
}

2. 动态规划 + 最高有效位

状态转移方程

结合1解法的pop_count $P(x)$函数来，有以下状态转移函数： \[ P(x+b) = P(x) + 1, b= 2^m > x \]

我的理解

能想到最左最高有效位刚好多一个1的情况，这个1在m位的话，则是多了$2^m$值。

实现

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> vi(num+1);
        // 可以不初始化为，gcc, clang下，float, double, size_t, unsigned会由default initialization初始化0
        // 同理, string会初始化为''
        //vi[0] = 0;
        
        int x = 0, b = 1;
        
        // 利用外部循环来找到满足 b = 2^m > x的情况
        // i = 0是因为每4个一循环，给下4个取值
        for ( ; b <= num; b <<= 1, x = 0)
        {
            while (x < b && x + b <= num)
            {
                vi[x+b] = vi[x] + 1;
                ++x;
            }
        }

        return vi;
    }
};

这里官方解的Java实现有个非常巧妙的地方：

利用了 while (b <= num) {...}的外部循环来找到 $b = 2^m > x$ 的$b$值

# standard solution
public class Solution {
    public int[] countBits(int num) {
        int[] ans = new int[num + 1];
        int i = 0, b = 1;
        // [0, b) is calculated
        while (b <= num) {
            // generate [b, 2b) or [b, num) from [0, b)
            while(i < b && i + b <= num){
                ans[i + b] = ans[i] + 1;
                ++i;
            }
            i = 0;   // reset i
            b <<= 1; // b = 2b
        }
        return ans;
    }
}

3. 动态规划 + 最低有效位

状态转移方程

同样基于pop_count()函数 \[ P(x) = P(x/2) + (x\ mod\ 2) \]

我的理解

同理2解法，由最高有效位，想到最低有效位：

实现

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> vi(num+1);

        int i = 1;
        for ( ; i < num + 1; ++i)
        {
            vi[i] = vi[i/2] + (i % 2);
        }

        return vi;
    }
};

这里官方解，利用了位运算来代替已有的/和%运算：

x >> 1 <=> x / 2
x & 1 <=> x % 2

public class Solution {
  public int[] countBits(int num) {
      int[] ans = new int[num + 1];
      for (int i = 1; i <= num; ++i)
        ans[i] = ans[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1
      return ans;
  }
}

4.动态规划 + 最后设置位

状态转移方程

同样基于pop_count()函数 \[ P(x) = P(x\ \&\ (x-1)) + 1 \]

我的理解

利用位运算x & (x-1)消除最右边的一位“1”，

使得 x 比 x & (x-1) 少一位“1”，加上这个“1”即可.

实现

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> vi(num+1);
        
        for (int i = 1; i < num + 1; ++i)
        {
            vi[i] = vi[i & (i - 1)] + 1;
        }

        return vi;
    }
};

官方解：

public class Solution {
  public int[] countBits(int num) {
      int[] ans = new int[num + 1];
      for (int i = 1; i <= num; ++i)
        ans[i] = ans[i & (i - 1)] + 1;
      return ans;
  }
}

总结

简单DP，注意定义好状态，写出状态转移方程，然后注意corner case。写成代码即可。
注意涉及到 2进制， 全0 1 的数字， 非负整数, unsigned, size_t, size_type等等，

往位运算上面想。
总结这里的位运算操作，之后考虑全部总结下常见位运算操作, 我记得耗子有篇文章总结了很多这方面的。
- x & (x - 1) 消除 x 的最右边的一位1. (PS: 这一个确实不熟悉，虽然也见过)
- x << 2 <=> x * 2
- x >> 2 <=> x / 2
- x & 1 <=> x % 2
(PS：那篇文章link找不到了)

Reference

leetcode官方解答

Large braces for specifying values of variables by condition

Extended knowledge

std::bitset::bitset in cppreference

How to print (using cout) a number in binary form?

default initialization

lifetime

Why does c++ initialise a std::vector with zeros, but not a std::array?

小结及之后

发表于 2019-10-23 | 分类于杂谈

小结

之前都去打了些结构化数据的比赛，也补了不少基础知识，尽管没有按当初的计划来。

尽管我觉得目前取得成绩不太够用吧，总结下有：

上海电信“添翼杯”成绩预测20名（吐槽下这破比赛结束，官网就没了？？？）
kaggle Instant Gratification solo铜牌
19讯飞反欺诈，初赛第8，复赛a榜14，b榜24
DataCastle 国能日新光伏预测功率第二届第6名

多多少少打了些咸鱼成绩出来。

最惨的还是讯飞，基本上2-3个月天天熬。初赛最后分数还算不错，到了复赛因为数据量太大，导致CatBoost在Shrink Model的时候峰值占用的内存会高到至少100g+和租的辣鸡DBC服务器疯狂卡结果，最后几天把我队的两个模型结果卡住没出来了。以及top3的选手开源了一个高分代码，上分操作与我队有一些重合，拉高了复赛线。

暂时有空抽时间把前面两篇坑了的博客补了，Data Science/ Machine Learning这块考虑暂时就放一段时间了。

之后？

开始刷leetcode和补一些以前干的后台开发相关的活了。

刷下Cpp reference啥啥的，把一些忘了的Cpp相关的东西捡起来；
每天至少龟系刷题1道，先从dp刷起来。1~2个月之后再考虑兔系刷题；
补下APUE那套东西，以前碰过，现在忘了不少；
接触下NoSQL，Redis这套；

PS:

以后写博客就不会那么详细，主要还是自己理解，留下一步一个脚印。

PPS：

至于比赛还打不打，看时间够不够吧，能支撑自己走下去的只有求生欲了。

在调用folds-split进行交叉检验时，使用tqdm记录每折时间

发表于 2019-07-01

Bowen Peng

something about myself and my career development.

My way

简单思路

水氷/Leoooooo/winterock way

状态定义：

*状态转移方程：

Leoooooo给出的推导过程：

证明结论为\(f(n)=1/2\):

总结

Reference

My way

二维DP

状态定义：

状态转移方程:

Base case:

Corner case:

C++实现

一维DP

状态定义：

状态转移方程:

Base case:

Corner case:

C++实现

Elon way

自顶向下, 记忆化搜索

自底向上, DP

总结

Reference

extended

My way

状态定义：

状态转移方程：

Base Case:

Corner Case:

可以试试斜着遍历

官方解

1.暴力

2.二维DP

3.一维DP

官方Java解

重上到下，C++实现

Reference

extended

官方解

动态规划

状态定义：

状态转移方程/递推公式：

Base case:

数学way

数学归纳法：

总结

Reference

extended

解法

括号匹配/栈的做法

PS: 注意思路实现是带有先后顺序的。

利用数字计数代替括号匹配做法

总结

Reference

Extended

官方解

数学way

综评最高解

定义状态：

状态转移方程为：

base case

实现

总结

Reference

extended

My way:

综评最高解

1.归纳法：

2.DP:

实现

总结

Reference

My way:

Standard Way

1.Pop Count

思路