100天代码挑战：DAY11

LeetCode 120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：

[
     [**2**],
    [**3**,4],
   [6,**5**,7],
  [4,**1**,8,3]
]

自顶向下的最小路径和为 11（即，**2 **+ 3 + **5 **+ 1 = 11）。

说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

我的答案：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int ans;
        vector<int> path,temp;
        path.push_back(triangle[0][0]);
        for(int i=1; i<triangle.size(); i++){
            temp.push_back(triangle[i][0] + path[0]);
            for(int j=1; j<triangle[i].size()-1; j++){
                temp.push_back(min(path[j-1], path[j])+triangle[i][j]);
            }
            temp.push_back(triangle[i][triangle[i].size()-1] + path[path.size()-1]);
            path = temp;
            temp.clear();
        }
        ans = path[0];
        for(int i=1; i<path.size(); i++){
            if(path[i]<ans) ans = path[i];
        }
        return ans;
    }
};

---

LeetCode 96. 不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:
输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

我的答案：

class Solution {
public:
    //46min, with help
    int numTrees(int n) {
        int sum = 0;
        vector<int> res;
        res.push_back(1);
        for(int i=1; i<=n; i++){
            sum = 0;
            for(int j=0; j<i; j++){
                sum += res[j] * res[i-j-1];
            }
            res.push_back(sum);
        }
        return res[n];
    }
};

---

LeetCode 62. 不同路径

一个机器人位于一个 *m x n *网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

image

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m和n的值均不超过 100。

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:
输入: m = 7, n = 3
输出: 28

我的答案：

class Solution {
public:
    //10min
    int uniquePaths(int m, int n) {
        int map[m][n];
        for(int i=0; i<m; i++) map[i][0] = 1;
        for(int i=0; i<n; i++) map[0][i] = 1;
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                map[i][j] = map[i][j-1] + map[i-1][j];
            }
        }
        return map[m-1][n-1];
    }
};

---

LeetCode 647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:
输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

1. 输入的字符串长度不会超过1000。

我的答案：

class Solution {
public:
    int countSubstrings(string s) {
        string str = "#";
        int ans = 0;
        for(int i=0; i<s.length(); i++){
            str = str + s[i] + "#";
        }
        for(int i=1; i<str.length(); i++){
            int len=0;
            while(str[i-len] == str[i+len] && i>len && i+len<str.length()){
                if(str[i-len] != '#') ans++;
                len++;
            }
        }
        return ans;
    }
};