[LeetCode]139. Word Break

[LeetCode]139. Word Break

问题给定一个非空字符串,和一个词典,判断字符串能否分割成词典中的单词的组合。Note:词典中的词可以重复出现,词典不包含重复单词例子1 :输入: s = "leetcode", wordDict = ["leet", "code"]输出: true"leetcode" 可以被分成 "leet code".解法动态规划假设 dp[i] 是字符串 s[:i] 是否可以被分割成词典中的单词dp[0] = true在字符串的每个位置 i 遍历词典中的单词 wclass Solution { public: bool wordBreak(string s, vector<string...

2020-01-20 PM 5℃ 0条
[LeetCode]121. Best Time to Buy and Sell Stock

[LeetCode]121. Best Time to Buy and Sell Stock

题目描述给定一个股票价格的数组, 只能一次卖出和一次买入操作,寻找最大收益是多少例子:Input: [7,1,5,3,6,4]Output: 5Explanation: 在第2天买入价格为 1 在 第5 天卖出价格为6 收益最高为5解法一class Solution { public: int maxProfit(vector<int>& prices) { int days = prices.size(); int maxProfit = 0; int minPrice = INT_MAX; f...

编程 2020-01-14 PM 10℃ 0条
[LeetCode]120.Triangle

[LeetCode]120.Triangle

给定一个三角形,找到从最上层到最下层的最小和路径例子 输入下面的三角形[ [2], [3,4], [6,5,7], [4,1,8,3] ]输出为:2 + 3 + 5 + 1 = 11 第一行取 2 第二行取 3 第三行取 5 第四行取 1。解法一:从最后一层往上计算class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); for(...

编程 2020-01-14 PM 11℃ 0条
[LeetCode]115. Distinct Subsequences

[LeetCode]115. Distinct Subsequences

问题描述给定字符串 S 和 T, 计算 S 有多少子串和 T 相等。一个字符串的子串是从原字符串删除部分字符之后的字符,子串种字符的顺序和原串一致。(例,"ACE" 是 "ABCDE" 的子串, “AEC”不是)例子1Input: S = "rabbbit", T = "rabbit"Output: 3Explanation:三个子串分别如下:rabbbit^^^^ ^^rabbbit^^ ^^^^rabbbit^^^ ^^^解法一 动态规划$ f(i,j) $ 表示字符串 s 的前 j 个字符 和 字符串 t 的 前 i 个字符作为子串的个数class Solution { publi...

编程 2020-01-12 PM 16℃ 0条
[LeetCode]97. Interleaving String

[LeetCode]97. Interleaving String

问题描述原题链接解法一 动态规划class Solution { public: bool isInterleave(string s1, string s2, string s3) { int lens1 = s1.length(); int lens2 = s2.length(); int lens3 = s3.length(); if ( (lens1 + lens2) != lens3){ return false; } vector<vecto...

编程 2020-01-10 PM 18℃ 0条