题一：leetcode：1143（最长公共子序列）
(https://leetcode-cn.com/problems/longest-common-subsequence/)
题目描述：
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
代码：
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.length();
int len2 = text2.length();
if(len1 == 0 || len2 == 0)
return 0;
vector<vector<int>> data(len1+1, vector<int>(len2+1, 0));
for(int i = 1; i <= len1; i++)
{
for(int j = 1; j <= len2; j++)
{
if(text1[i-1] == text2[j-1])
{
data[i][j] = data[i-1][j-1]+1;
}
else
{
data[i][j] = max(data[i-1][j], max(data[i][j-1], data[i-1][j-1]));
}
}
}
return data[len1][len2];
}
};
题二：leetcode：62（不同路径）
(https://leetcode-cn.com/problems/unique-paths/submissions/)
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> data(m , vector<int>(n, 0));
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(i == 0 || j == 0)
{
data[i][j] = 1;
}
else
{
data[i][j] = data[i-1][j] + data[i][j-1];
}
}
}
return data[m-1][n-1];
}
};
//data[i][j] 走到第ij点，有多少路径
//data[i][j] = max(data[i-1][j], data[i][j-1])
题三：leetcode：63（不同路径II）
(https://leetcode-cn.com/problems/unique-paths-ii/submissions/)
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if(obstacleGrid.empty()) return 0;
long r = obstacleGrid.size();
long c = obstacleGrid[0].size();
vector<vector<long>> data(r+1, vector<long>(c+1, 0));
for(long i = 1; i <= r; i++)
{
for(long j = 1; j <= c; j++)
{
if(i == 1 && j == 1)
{
data[i][j] = obstacleGrid[i-1][j-1] == 0 ? 1 : 0;
}
else
{
data[i][j] = obstacleGrid[i-1][j-1] == 1 ? 0 : data[i-1][j]+data[i][j-1];
}
}
}
return static_cast<int>(data[r][c]);
}
};
题四：leetcode：70（爬楼梯）
(https://leetcode-cn.com/problems/climbing-stairs/submissions/)
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
class Solution {
public:
int climbStairs(int n) {
vector<int> data(n, 0);
for(int i = 0; i < n; i++)
{
if(i == 0) data[i] = 1;
else if(i == 1) data[i] = 2;
else data[i] = data[i-1] + data[i-2];
}
return data[n-1];
}
};
题五：leetcode：120（三角形最小路径和）
(https://leetcode-cn.com/problems/triangle/)
题目描述：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
自顶向下：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.empty()) return 0;
int r = triangle.size();
int maxc = triangle[r-1].size();
vector<vector<int>> data(r+2, vector<int>(maxc+2, 0));
int minValue = INT_MAX;
for(int i = 1; i <= r; i++)
{
for(int j = 1; j <= triangle[i-1].size(); j++)
{
if(i == 1) data[i][j] = triangle[i-1][j-1];
else if(j == 1) data[i][j] = data[i-1][j] + triangle[i-1][j-1];
else if(j == triangle[i-1].size()) data[i][j] = data[i-1][j-1]+ triangle[i-1][j-1];
else data[i][j] = min(data[i-1][j], data[i-1][j-1]) + triangle[i-1][j-1];
if(i == r)
{
minValue = minValue < data[i][j] ? minValue : data[i][j];
}
}
}
return minValue;
}
};
题六：leetcode：53（最大子序和）
(https://leetcode-cn.com/problems/maximum-subarray/)
题目描述：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty()) return 0;
int len = nums.size();
vector<int> data(len, 0);
data[0] = nums[0];
int maxVal = data[0];
for(int i = 1; i < len; i++)
{
data[i] = data[i-1] > 0 ? data[i-1]+nums[i] : nums[i];
maxVal = maxVal > data[i] ? maxVal : data[i];
}
return maxVal;
}
};
题七：leetcode：152（乘积最大子序列）
(https://leetcode-cn.com/problems/maximum-product-subarray/)
题目描述：
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.empty()) return 0;
int len = nums.size();
vector<vector<int>> data(len, vector<int>(2, 0));
data[0][0] = nums[0];
data[0][1] = nums[0];
int maxVal = nums[0];
for(int i = 1; i < len; i++)
{
if(nums[i] >= 0)
{
data[i][0] = max(nums[i]* data[i-1][0], nums[i]);
data[i][1] = min(nums[i]* data[i-1][1], nums[i]);
}
else
{
data[i][0] = max(nums[i]* data[i-1][1], nums[i]);
data[i][1] = min(nums[i]* data[i-1][0], nums[i]);
}
maxVal = data[i][0] > maxVal ? data[i][0] : maxVal;
}
return maxVal;
}
};
题八：leetcode：322（零钱兑换）
(https://leetcode-cn.com/problems/coin-change/)
题目描述：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> data(amount+1, 0);
for(int i = 1; i <= amount; i++)
{
int minVal = INT_MAX;
for(int j = 0; j < coins.size(); j++)
{
if(i >= coins[j] && data[i-coins[j]] >= 0)
{
minVal = min(minVal, data[i-coins[j]]+1);
}
}
data[i] = (minVal == INT_MAX ? -1 : minVal);
}
return data[amount];
}
};
题九：leetcode：198（打家劫舍）
(https://leetcode-cn.com/problems/house-robber/)
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty()) return 0;
int len = nums.size();
vector<int> data(len, 0);
for(int i = 0; i < len; i++)
{
if(0 == i ) data[i] = nums[i];
else if(1 == i) data[i] = max(nums[i], data[i-1]);
else
{
data[i] = max(data[i-2]+nums[i], data[i-1]);
}
}
return data[len-1];
}
};
题十：leetcode：213（打家劫舍II）
(https://leetcode-cn.com/problems/house-robber-ii/)
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
class Solution {
public:
int subRob(vector<int>& nums) {
if(nums.empty()) return 0;
int len = nums.size();
vector<int> data(len, 0);
for(int i = 0; i < len; i++)
{
if(0 == i ) data[i] = nums[i];
else if(1 == i) data[i] = max(nums[i], data[i-1]);
else
{
data[i] = max(data[i-2]+nums[i], data[i-1]);
}
}
return data[len-1];
}
int rob(vector<int>& nums) {
if(nums.empty()) return 0;
int len = nums.size();
if(1 == len) return nums[0];
vector<int> nums1 = nums;
vector<int> nums2 = nums;
nums1.erase(nums1.begin());
nums2.erase(nums2.end() - 1);
int val1 = subRob(nums1);
int val2 = subRob(nums2);
return max(val1, val2);
}
};
题十一：leetcode：91（解码方法）
https://leetcode-cn.com/problems/decode-ways/
题目描述：
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
class Solution {
public:
int numDecodings(string s) {
if(s.empty()) return 0;
int len = s.length();
int last_1 = 1; //最近一个
int last_2 = 1; //
int ret = 0;
if(s[0] == '0') return 0;
else if(s[0] != '0') last_1 = 1;
for(int i = 1;i < len; i++)
{// 1 2 1 2 0
int temp = last_1;
if(isLastOneValid(s[i]) && isLastTwoValid(s[i-1], s[i])) ret = last_1 + last_2;
else if(isLastOneValid(s[i]) && !isLastTwoValid(s[i-1], s[i])) ret = last_1;
else if(!isLastOneValid(s[i]) && isLastTwoValid(s[i-1], s[i])) ret = last_2;
else if(!isLastOneValid(s[i]) && !isLastTwoValid(s[i-1], s[i])) return 0;
last_1 = ret;
last_2 = temp;
ret = 0;
}
return last_1;
}
bool isLastOneValid(char a)
{
if(a != '0') return true;
else return false;
}
bool isLastTwoValid(char a, char b)
{
if(a == '1') return true;
else if((a =='2') && (b <= '6' && b >= '0')) return true;
else return false;
}
};
