leetcode题解-312-戳气球

发表于 2019-11-04 | 更新于 2019-11-14 | 分类于刷题

My way

很蠢的思路：

选择min值，爆掉，然后循环至结束。

测都不用测。。。

没想到怎么往DP上面套。

ivan_allen 解

思路转变：

气球从头到尾爆炸 <=> 气球从尾到头爆炸

状态转移方程:

\[ dp[i][j] = max(dp[i][j],\ nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j]), \text{if $k \in\ [i,\ j]$} \]

遍历方式：

控制子数组长度len
子数组首尾i, j
使用k对数组分割

二维DP实现：

class Solution {
public:
    int N;
    int maxCoins(vector<int>& nums) {
        
        // 添加哨兵在头尾，因为假如最后只删一个数字的时候，是需要乘以2个1的
        nums.insert(nums.begin(), 1);
        nums.push_back(1);

        int m = nums.size();
        vector<vector<int>> dp(m, vector<int>(m));

        // 只能按长度打表
        // dp[i][j], j - i >= 2
        for (int len = 2; len < m; ++len)
        {
            for (int i = 0; i < m - len; ++i)
            {
                int j = i + len;
                for (int k = i + 1; k < j; ++k)
                {
                    dp[i][j] = max(dp[i][j], nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j]);
                } 
            }
        }

        return dp[0][m-1];
    }

};

总结

思路的转变：
- 气球从头到尾爆炸 <=> 气球从尾到头爆炸
头尾虚拟1的添加 类似于之前虚拟0的添加 和 哨兵的思想

Reference

ivan_allen解

leetcode题解-62-不同路径

发表于 2019-11-04 | 分类于刷题

My way

1. 2维DP

状态转移方程：

\[ \begin{align*} & dp[i][j] = dp[i-1][j] + dp[i][j-1] \\ \end{align*} \]

base case:

\[ \begin{align*} & dp[i][j] = 1,\ \text{if $i==1$ or $j==1$} \\ \end{align*} \]

corner case:

\[ \begin{align*} & dp[i][j] = 1, \text{if $i == 1$ and $j == 1$} \\ & AND \\ & return\ function \end{align*} \]

2. 1维DP

还可以转换成1维DP.

powcai way

组合数学：

PS：这个排列组合的方法其实我想到过，但是没有找出通项公式 :cry:

Reference

powcai 解

leetcode题解-413.等差数列划分

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

My way

状态转移方程:

\[ dp[i][j] = \begin{cases} & 2^{j-i-2}-1 & \text{if $A[i:j]$是等差数列}\\ & dp[i-1][j] + dp[i][j-1] & otherwise\\ \end{cases} \]

官方解

2. 优雅暴力

3. 递归

状态定义：

\[ \begin{align*} & sum:\ 数组A中的所有的等差数列的个数 \\ & slice(A,\ i):\ 求区间(k,\ i)中，而不在区间(k,\ j)中等差数列的个数，其中j<i. \\ & \end{align*} \]

假设知道了$slice(A, i-1)$的值为x, 同时这个区间元素用$[a_0, a_1, a_2, ..., a_{i-1}]$来表示。
若这个区间本身就是一个等差数列，那么这里所有相邻元素之间的差值是相等的。
现加入一个元素$a_i$将区间扩展为$(0,\ i)$，如果扩展之后的区间还是一个等差数列，那么一定存在$a_i - a_{(i-1)} == a_{(i-1)} -a_{(i-2)}$.
故每加入一个新元素，就会多出$ap$个等差数列。其中新增的等差数列的区间为$(0,i), (1,i), ..., (i-2, i)$, 这些区间总数为$x+1$. 这是因为除了区间$(0,i)$之外，其余的区间如$(1,i), (2,i),...,(i-2,i)$都可以对应到之前的区间$(0,i-1), (1,i-1), ...,(i-3,i-1)$上去，其值为$x$.
因此，每次调用slices, 如果第$i$个元素与前一个元素的差值正好等于之前的差值，我们直接就可以算出新增的等差数列的个数$ap$, 同时可以更新$sum$.
但是，如果新元素跟之前一个元素的差值不等于之前的差值，也就不会增加等差数列的个数

public class Solution {
    int sum = 0;
    public int numberOfArithmeticSlices(int[] A) {
        slices(A, A.length - 1);
        return sum;
    }
    public int slices(int[] A, int i) {
        if (i < 2)
            return 0;
        int ap = 0;
        if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
            ap = 1 + slices(A, i - 1);
            sum += ap;
        } else
            slices(A, i - 1);
        return ap;
    }
}

4.DP

状态定义：

\[ \begin{align*} & dp:\ 存储在区间(k,i), 而不在区间(k,j)中的等差数列个数，其中j<i\\ & \end{align*} \]

public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int[] dp = new int[A.length];
        int sum = 0;
        for (int i = 2; i < dp.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp[i] = 1 + dp[i - 1];
                sum += dp[i];
            }
        }
        return sum;
    }
}

5.$O(1)空间复杂度$DP

对于$dp$数组来说，仅有$dp[i-1]$决定$dp[i]$.

故只用保存最近一个$dp$ 就可以了。

public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int dp = 0;
        int sum = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp = 1 + dp;
                sum += dp;
            } else
                dp = 0;
        }
        return sum;
    }
}

6. 公式计算

public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int count = 0;
        int sum = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                count++;
            } else {
                sum += (count + 1) * (count) / 2;
                count = 0;
            }
        }
        return sum += count * (count + 1) / 2;
    }
}

reference

extended

How to sum up elements of a C++ vector?

how to sum up a vector of vector int in C++ without loops

leetcode题解-303-区域和检索 - 数组不可变

发表于 2019-11-03 | 分类于刷题

题目

class NumArray {
public:
    NumArray(vector<int>& nums) {
        
    }
    
    int sumRange(int i, int j) {
        
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */

My way

1. 暴力法

class NumArray {
private:
    vector<int> dp;
    

public:
    NumArray(vector<int>& nums) {
        dp = nums;
    }
    
    int sumRange(int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; ++k)
        {
            sum += dp[k];
        }

        return sum;
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */

结果，时间复杂度极低，仅超过10%的解。

很明显是要先用dp数组存入各个索引$i$, $j$对应的值。

2. 2维DP

状态转移方程：

\[ dp[i][j] = dp[i][j-1] + nums[j-1] \]

class NumArray {
private:
    vector<vector<int>> dp;
    

public:
    NumArray(vector<int>& nums):dp(nums.size()+1, vector<int>(nums.size()+1))
    {
        for (int i = 1; i <= nums.size(); ++i)
        {
            for (int j = i; j <= nums.size(); ++j)
            {
                dp[i][j] = dp[i][j-1] + nums[j-1];
            }
        }
    }
    
    int sumRange(int i, int j) 
    {
        return dp[i+1][j+1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */

结果更慢了，仅超过5%的解。。。

应该是哪里思路出了问题...

class NumArray {
private:
    int **dp;
    int m;

public:
    NumArray(vector<int>& nums)
    {
        m = nums.size() + 1;
        dp = new int*[m];
        for(int i = 0; i < m; ++i)
        {
            dp[i] = new int[m];
        }

        for (int i = 1; i <= nums.size(); ++i)
        {
            int sum = 0;
            for (int j = i; j <= nums.size(); ++j)
            {
                sum += nums[j-1];
                dp[i][j] = sum;
            }
        }
    }
    
    ~NumArray()
    {
        for (int i = 0; i < m; ++i)
        {
            delete []dp[i];
        }

        delete []dp;
    }
    
    int sumRange(int i, int j) 
    {
        return dp[i+1][j+1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */

换成原生数组，时间复杂度仅超过7%，仍然很糟糕。。。

假如直接静态数组int dp[INT_MAX][INT_MAX];，内存会炸掉。。。

官方way

2. 缓存

将计算结果提前存入到 哈希表 中。

PS：而我用的是vector<vector<int>> dp, int **dp, 感觉没区别，应该是resize()/动态分配内存那耗费了不少时间。

private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

public NumArray(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            map.put(Pair.create(i, j), sum);
        }
    }
}

public int sumRange(int i, int j) {
    return map.get(Pair.create(i, j));
}

3. 缓存

优化空间复杂度从$O(n^2) = > O(n)$. \[ sum[k] = \begin{cases} & \sum_{i=0}^{k-1} nums[i] & , k > 0 \\ & 0 & , k == 0\\ \end{cases} \] 优化为: \[ sumrange(i,\ j)= sum[j+1] - sum[i] \] java:

private int[] sum;

public NumArray(int[] nums) {
    sum = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }
}

public int sumRange(int i, int j) {
    return sum[j + 1] - sum[i];
}

C++: use array

class NumArray {
private:
    int *sum;

public:
    NumArray(vector<int>& nums) {
        sum = new int [nums.size() + 1];

        for (int i = 0; i < nums.size(); ++i)
        {
            sum[i+1] = sum[i] + nums[i];
        }
    }
    ~NumArray()
    {
        delete []sum;
    }
    
    int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */

但这也只超过了 78.45%...

C++: user vector<int>

class NumArray {
    vector<int> dp;
public:
    NumArray(vector<int>& nums) {
        int sum=0;
        dp.push_back(0);
        for(int i=0;i<nums.size();++i)
        {
            sum+=nums[i];
            dp.push_back(sum);
        }
    }
    
    int sumRange(int i, int j) {
        return dp[j+1]-dp[i];
    }
};

超过了96.23%，代码类似陈乐乐解2.

但仔细看她代码，你会发现她在C++编码时，有个很不好的习惯，我在这纠正了，就不指出来了。

总结

傻了，老想着把计算结果存起来，到时候直接取，居然忘记了
- $sumrange(i,\ j)= sum[j+1] - sum[i]$
这里也用到了插入了一个虚拟 0 作为 sum 数组中的第一个元素。
- 这个技巧可以避免在 sumrange 函数中进行额外的条件检查，对于base case, corner case等等
- PS：尽管，我其实喜欢加上对于base case, corner case的检查，但却是实现起来有些冗余

Reference

官方解

陈乐乐解

extended

How do I declare a 2d array in C++ using new?

leetcode题解-1143-最公共子序列长

发表于 2019-11-03 | 分类于刷题

题目

简单DP，只给出状态转移方程。

状态转移方程

\[ dp[i][j] = \begin{cases} & dp[i-1][j-1]+1, & \text{if $text1[i]==text2[j]$} \\ & max(dp[i-1][j],\ dp[i][j-1]), & otherwise \\ \end{cases} \]

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size() + 1, n = text2.size() + 1;
        vector<vector<int>> dp(m, vector<int>(n));

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                if (text1[i-1] == text2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[m-1][n-1];
    }
};

总结

这里只求，最大公共子序列的长度，简单的2维DP即可实现
记住，这种在状态转移方程中存在f[i] = f[i-1]的递推式情况下，
- 将设置 新数组长度 = 旧数组长度 + 1
- 从而可以减少在base case, corner case的语句，减少代码冗余程度。

leetcode题解-931-下降路径最小和

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

My way

1.二维DP

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int m = A.size();
        int n = A[0].size();
        vector<vector<int>> dp(A);

        // base case
        for (int j = 0; j < n; ++j)
        {
            dp[0][j] = A[0][j];
        }

        // 
        for (int i = 1; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (j - 1 == -1)
                {
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + A[i][j];
                }
                else if (j + 1 == n)
                {
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + A[i][j];
                }
                else
                {
                    dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]) + A[i][j];
                }
            }
        }

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

2.一维DP

可以将二维DP压缩至一维DP处理。

leetcode题解-714-买卖股票的最佳时机含手续费

发表于 2019-11-01 | 更新于 2019-12-09 | 分类于刷题

My way

一开始审题失误了，没有看到股票可以 多次买入，卖出。

所以想了个 只准单次买入，卖出的解法。

class Solution {
private:
    static bool mycomp(vector<int> a, vector<int> b) 
    {
        return *max_element(a.begin(), a.end()) < *max_element(b.begin(), b.end());
    }

public:
    int maxProfit(vector<int>& prices, int fee) {
        size_t n = prices.size();
        vector<vector<int>> dp(n, vector<int>(n));

        // Base case
        for (size_t i = 0; i < n; ++i)
        {
            dp[i][i] = 0;
        }      

        for (size_t i = 0; i < n; ++i)
        {
            for (size_t j = i + 1; j < n; ++j)
            {
                dp[i][j] = dp[i][j-1] + prices[j] - prices[j-1] - fee;
            }
        }

        auto itv = max_element(dp.begin(), dp.end(), mycomp); // find the vector 
                                                     // with the max element
        return *max_element((*itv).begin(), (*itv).end()); // finds the max element 
                                                        // in the desired vector
    }
};

官方解

通过第$i$天和$i-1$天$cash,\ hold$的递推关系，来得到最后最大收益。

*但是给我的感觉，这个思路，并不是很好捋清楚。

状态定义：

\[ \begin{align*} & cash:\ 不持有股票时的最大利润 \\ & hold:\ 持有股票时的最大利润\\ \end{align*} \]

状态转移方程：

1 2	cash = Math.max(cash, hold + prices[i] - fee); // max(原来请况，假设第i天卖出股票) hold = Math.max(hold, cash - prices[i]); // max(原来情况，假设第i天买进股票)

Base case

1 2	cash = 0; hold = -prices[0]; // 假设第0天买了股票

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(cash, hold + prices[i] - fee);
            hold = Math.max(hold, cash - prices[i]);
        }
        return cash;
    }
}

e.g.

$$ \[\begin{align*} &输入: prices = [1, 3, 2, 8, 4, 9], fee = 2\\ &输出: 8\\ &解释: 能够达到的最大利润: \\ &在此处买入 prices[0] = 1\\ &在此处卖出 prices[3] = 8\\ &在此处买入 prices[4] = 4\\ &在此处卖出 prices[5] = 9\\ &总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8. \\ \end{align*}\] $$

	prices	cash	hold
0	1	0	-1
1	3	max(0, -1+3-2)=0	max(0, 0-3)=-3
2	2	max(0, -1+2-2)=0	max(-1, 0-2)=-1
3	8	max(0, -1+8-2)=5	max(-1, 5-8)=-1
4	4	max(5, -1+4-2)=5	max(-1, 5-4)=1
5	9	max(5, 1+9-2)=8	max(1, 8-9)=-1

Reference

官方解

laluladong解

extended

Find the max value in vector> without for loop

markdown generator

leetcode题解-647-回文子串

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

题目

My way

状态定义：

\[ \begin{align*} & s:\ 字符串s\\ & i:\ 字符串s第i位\\ & j:\ 字符串s第j位\\ & s[i:j]:\ 字符串s第i位到第j位的子串, s[i,j]\\ & dp[i][j]:\ dp数组在s[i,j]上是否为回文串的记录。 \end{align*} \]

Base case：

\[ \begin{align*} &s[i][j] = 1, &\text{if $i==j$}\ \end{align*} \]

状态转移方程：

\[ s[i-1][j+1] = \begin{cases} & 1,\ \text{if $s[i] == s[j]$}\\ & 0,\ otherwise \end{cases} \]

Error:

在如何实现数组遍历上面，出现了问题。

套用了 glamour的逆向对角遍历思路：

class Solution {
public:
    int countSubstrings(string s) {
        int m = s.size();
        int cnt = 0;
        vector<vector<bool>> dp(m, vector<bool>(m, false));


        // base case
        for (int i = 0; i < m; ++i)
        {
            dp[i][i] = true;
            ++cnt;
        }


        for (int i = 1; i < m; ++i)
        {
            for (int j = 0; j <= m - i - 1; ++j)
            {
                int row = j;
                int column = i + j;
                bool cur = s[row] == s[column];
                if (cur && (i == 1 || dp[row+1][column-1]))
                {
                    dp[row][column] = true;
                    ++cnt;
                }
            }
        }

        return cnt;
    }
};

Glamour way

1.DP + 逆向对角遍历

逆向对角遍历思路：

上图中同一条直线上的值有前者依赖于后者的关系，因此我们应该以对角线方向遍历

但是本方法在發現一字符串不是回文串后，仍然對包含其的字符串進行回文判斷。

此方法包含了冗餘的判斷，因此還有優化的地方。

public int countSubstrings(String s) {
       int len = s.length();
       if(len <= 1) return len;
       boolean[][] dp = new boolean[len][len];
       int i;
       int j;
       int row, column;
       boolean current;
       int count = 0;
       for(i = 0; i < len; i++){
           dp[i][i] = true;
           count++;
       }
       for(i = 1; i < len; i++){
           for(j = 0; j <= len - i - 1; j++){
               row = j;
               column = i + j;
               current = s.charAt(row) == s.charAt(column);
               if(current && (i == 1 || dp[row + 1][column - 1])){
                   dp[row][column] = true;
                   count++;
               }
           }
          
       }
       return count;
   }

2. 分治法 + 中心扩散法

分治法，对以不同字符为中心的回文分而治之，同时又将回文的长度分为奇数和偶数，奇数的中心有一个，而偶数的中心有两个.

有一個規律：

回文串左右兩邊同時去掉一個字符仍然是回文串；反之一個字符串不是回文串，

那麽他左右兩邊不論加上什麽字符都不可能是回文串.

public int countSubstrings(String s) {
       int count = 0;
       int i;
       for(i = 0; i < s.length(); i++){
           count += countPalindrome(s, i, i);
           count += countPalindrome(s, i, i + 1);
       }
        return count;
   }
   public int countPalindrome (String s, int left, int right){
       int count = 0;
       while(left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++)){
           count++;
       }
       return count;
   }

C++实现

class Solution {
public:
    int countSubstrings(string s) {
        int m = s.size();
        int cnt = 0;

        for (int i = 0; i < m; ++i)
        {
            cnt += countPalindrome(s, i, i);    // even length of string
            cnt += countPalindrome(s, i, i+1);  // old length of string
        }

        return cnt;
    }

    int countPalindrome(const string& s, int l, int r)
    {
        int cnt = 0;
        while (l >= 0 && r < s.size() && s[l--] == s[r++])
        {
            ++cnt;
        }

        return cnt;
    }
};

Reference

glamour解法

leetcode题解-712-两个字符串的最小ASCII删除和

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

题目

官方解

状态定义：

\[ \begin{align*} & i:\ \text{字符串}s1的第i位\\ & j:\ \text{字符串}s2的第j位\\ & s1[i:]:\ 第i位到末尾的子串\\ & s2[j:]:\ 第j位到末尾的子串\\ & dp[i][j]:\ 表示使字符串s1[i:],s2[j:]从第i位到末尾的子串相等，要删除的ASCII码值最小 \end{align*} \]

状态转移方程：

\[ \begin{align*} dp[i][j] = \begin{cases} & min(dp[i+1][j] + s1.asciiAtPos(i), dp[i][j+1] + s2.asciiAtPos(j))\ & \text{if $s1[i] != s2[j]$ }\\ & df[i-1][j-1]\ &\text{if $s1[i] = s2[j]$} \end{cases} \end{align*} \]

Base case:

\[ \begin{align*} &dp[i][j] = 0 &\text{if $i == 0$ and $j == 0$} \end{align*} \]

Corner case:

\[ dp[i][j] = \begin{cases} & dp[i+1][j] + s1.asciiAtPos(i) & \text{if $s[j:].size() == 0$, 即$j==s1.size()$}\\ & dp[i][j+1] + s2.asciiAtPos(j) & \text{if $s[i:].size() == 0$, 即$i==s1.size()$}\\ \end{cases} \]

C++实现

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1));
        
        int m = s1.size(), n = s2.size();

        for (int i = m - 1; i >= 0; --i)
        {
            dp[i][n] = dp[i+1][n] + s1[i];
        }
        for (int j = n - 1; j >= 0; --j)
        {
            dp[m][j] = dp[m][j+1] + s2[j];
        }

        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                if (s1[i] == s2[j])
                {
                    dp[i][j] = dp[i+1][j+1];
                }
                else
                {
                    dp[i][j] = min(dp[i+1][j] + s1[i], dp[i][j+1] + s2[j]);
                }
            }
        }
        

        return dp[0][0];
    }

private:
    int getStrAsciiSum(const string s)
    {
        int sum = 0;
        for (auto i : s)
        {
            sum += i;
        }
        return sum;
    }
};

Java实现

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];

        for (int i = s1.length() - 1; i >= 0; i--) {
            dp[i][s2.length()] = dp[i+1][s2.length()] + s1.codePointAt(i);
        }
        for (int j = s2.length() - 1; j >= 0; j--) {
            dp[s1.length()][j] = dp[s1.length()][j+1] + s2.codePointAt(j);
        }
        for (int i = s1.length() - 1; i >= 0; i--) {
            for (int j = s2.length() - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i+1][j+1];
                } else {
                    dp[i][j] = Math.min(dp[i+1][j] + s1.codePointAt(i),
                                        dp[i][j+1] + s2.codePointAt(j));
                }
            }
        }
        return dp[0][0];
    }
}

总结

类似于最长公共子序列的一道题。
在二维DP数组初始化的时候，没有考虑到初始化大小为$(m+1)*(n+1)$ .
- 对于$dp[m][n] = 0$其实是一种 base case，
- 是考虑到第$m$位字符到第$m$位字符上的一个情况，即空串情况。

Reference

leetcode官方解

Falcon解

Extended

std::basic_string

basic_string/substr

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

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

题目

官方解

简要改自官网解。

利用树的遍历，以递归方式实现不同二叉树的构造。

我们从序列 $1 ...n$ 中取出数字 $i$，作为当前树的树根。于是，剩余 $i - 1$ 个元素可用于左子树，$n - i$ 个元素用于右子树。如前文所述，这样会产生 $G(i - 1)$ 种左子树和 $G(n - i)$ 种右子树，其中 $G$ 是卡特兰数。

现在，我们对序列 $1 ... i - 1$ 重复上述过程，以构建所有的左子树；然后对 $i + 1 ... n$ 重复，以构建所有的右子树。

这样，我们就有了树根 $i$ 和可能的左子树、右子树的列表。

最后一步，对两个列表循环，将左子树和右子树连接在根上。

C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // [start, end]
    vector<TreeNode*> generate_trees(int start, int end)
    {
        vector<TreeNode*> all_trees;

        if (start > end)
        {
            all_trees.push_back(NULL);
            return all_trees;
        }

        // pick up a root 
        for (int i = 0; i <= end; ++i)
        {
            vector<TreeNode*> leftTrees = generate_trees(start, i - 1);
            vector<TreeNode*> rightTrees = generate_trees(i + 1, end);

            for (auto l : leftTrees)
            {
                for (auto r : rightTrees)
                {
                    TreeNode* curTree(i);
                    curTree->left = l;
                    curTree->right = r;
                    all_trees.push_back(curTree);
                }
            }

        }

        return all_trees;
    }

    vector<TreeNode*> generateTrees(int n) 
    {
        if (n == 0)
        {
            return vector<TreeNode*>();
        }
        else
        {
            return generate_trees(1, n);
        }
    }
};

Java实现

class Solution {
  public LinkedList<TreeNode> generate_trees(int start, int end) {
    LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>();
    if (start > end) {
      all_trees.add(null);
      return all_trees;
    }

    // pick up a root
    for (int i = start; i <= end; i++) {
      // all possible left subtrees if i is choosen to be a root
      LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);

      // all possible right subtrees if i is choosen to be a root
      LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);

      // connect left and right trees to the root i
      for (TreeNode l : left_trees) {
        for (TreeNode r : right_trees) {
          TreeNode current_tree = new TreeNode(i);
          current_tree.left = l;
          current_tree.right = r;
          all_trees.add(current_tree);
        }
      }
    }
    return all_trees;
  }

  public List<TreeNode> generateTrees(int n) {
    if (n == 0) {
      return new LinkedList<TreeNode>();

Reference

官方解

Bowen Peng

something about myself and my career development.

My way

很蠢的思路：

ivan_allen 解

思路转变：

状态转移方程:

遍历方式：

二维DP实现：

总结

Reference

My way

1. 2维DP

状态转移方程：

base case:

corner case:

2. 1维DP

powcai way

组合数学：

Reference

My way

状态转移方程:

官方解

2. 优雅暴力

3. 递归

状态定义：

4.DP

状态定义：

5.\(O(1)空间复杂度\)DP

6. 公式计算

reference

extended

My way

1. 暴力法

2. 2维DP

状态转移方程：

官方way

2. 缓存

3. 缓存

总结

Reference

extended

状态转移方程

总结

My way

1.二维DP

2.一维DP

My way

官方解

状态定义：

状态转移方程：

Base case

e.g.

Reference

extended

My way

状态定义：

Base case：

状态转移方程：

Error:

Glamour way

1.DP + 逆向对角遍历

逆向对角遍历思路：

2. 分治法 + 中心扩散法

Reference

官方解

状态定义：

状态转移方程：

Base case:

Corner case:

C++实现

Java实现

总结

Reference

Extended

官方解

Reference