LeetCode 120. 三角形最小路徑和
給定一個三角形百姓，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結(jié)點(diǎn)上。
例如叨咖，給定三角形：
[
[**2**],
[**3**,4],
[6,**5**,7],
[4,**1**,8,3]
]
自頂向下的最小路徑和為 11（即害碾，**2 **+ 3 + **5 **+ 1 = 11）矢劲。
說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個問題，那么你的算法會很加分慌随。
我的答案：
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. 不同的二叉搜索樹
給定一個整數(shù) n芬沉，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種躺同？
示例:
輸入: 3
輸出: 5
解釋: 給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹:
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. 不同路徑
一個機(jī)器人位于一個 *m x n *網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動一步丸逸。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）蹋艺。
問總共有多少條不同的路徑？
例如黄刚，上圖是一個7 x 3 的網(wǎng)格捎谨。有多少可能的路徑？
說明：m和n的值均不超過 100憔维。
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始涛救，總共有 3 條路徑可以到達(dá)右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 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. 回文子串
給定一個字符串业扒，你的任務(wù)是計(jì)算這個字符串中有多少個回文子串检吆。
具有不同開始位置或結(jié)束位置的子串，即使是由相同的字符組成程储，也會被計(jì)為是不同的子串蹭沛。
示例 1:
輸入: "abc"
輸出: 3
解釋: 三個回文子串: "a", "b", "c".
示例 2:
輸入: "aaa"
輸出: 6
說明: 6個回文子串: "a", "a", "a", "aa", "aa", "aaa".
注意:
- 輸入的字符串長度不會超過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;
}
};
