Word Break
题意
给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。 给出
s = “leetcode”，dict = [“leet”,”code”]，返回 true 因为“leetcode”可以被空格切分成“leet code”。
思路
凡是和字符串有关的题，在应用动态规划方法时主要有两种思路：
- 用
dp[i][j]表示子串s[i,j]满足某一要求 - 用
dp[i]表示子串s[0,i]满足某一要求
LeetCode-91-Decode Ways
题意
有一个消息包含A-Z通过以下规则编码：
|
1 2 3 4 5 |
'A' -> 1 'B' -> 2 ... 'Z' -> 26 |
现在给你一个加密过后的消息，问有几种解码的方式 ？如给出消息“12”，有两种解码的方法 AB(12) 或者 L(12)，所以返回 2。 继续阅读“LeetCode-91-Decode Ways”
LeetCode上几道经典的回溯法题目
把相同类型的题目放在一起总结，可以便于整理思路，理解异同。下面是LeetCode上几道比较经典的可以使用回溯法来解决的题目，也是笔试面试时常考常问的。
在找实习时我就被问了两次Subsets这道题。因此熟练掌握这几道题，面试时遇到类似的题目即使是不能一下子写出正确的代码，至少也能按照正确的思路去思考。 继续阅读“LeetCode上几道经典的回溯法题目”
LeetCode 上几道经典的排列组合题
LeetCode 上有几道题都和排列组合有关，非常经典，值得放在一起总结一下。这几道题分别是：
- Permutations。给定一组各不相同的数字，求这些数字的所有排列。
- Permutations II。给定一组数字，这些数字中可能有重复的，求这些数字的所有不重复的排列。
- Next Permutation。给定一组数字的全排列中的一个排列，求这个排列的下一个排列。
- Permutation Sequence。给定一组数字和一个数字 K，求这组数字的全排列中，按照字典序顺序排序的第 K 个排列。
在其他数字都出现K次的数组中找到只出现M次的数字
在其他数字都出现偶数次的数组中找到只出现奇数次的1个数字
题目描述
给定一个数组 arr，其中只有一个数字出现了奇数次，其他数字都出现了偶数次，找出这个数字。
思路
使用异或运算符。我们可以声明一个变量 x，用它去和数组中的每个元素做异或运算，由于 n ^ n = 0, n ^ 0 = n，那么那些出现偶数次的数字和自身异或，结果为0。最后x中存的就是数组中只出现奇数次次的数字。 继续阅读“在其他数字都出现K次的数组中找到只出现M次的数字”
LeetCode-437-Path Sum Ⅲ
在 Path Sum 和 Path Sum Ⅱ之后，Path Sum 大家庭又迎来了第三位成员。那么这个新成员又提出了什么样的要求呢？
题意是这样的：给出一棵二叉树和一个数值 sum，计算这棵树上的节点之和等于sum 的所有路径的条数。和之前不同的是，这道题中路径可以从树中的任何一个节点开始。 继续阅读“LeetCode-437-Path Sum Ⅲ”
LeetCode-646-Maxinum Length of Pair Chain
题意：给出 n 组数，每组有两个数，第一个数总是比第二个数字小。如果两组数 (a,b) 和 (c,d) 之间，有 b < c，那么就称 (a,b)和 (c,d) 之间形成了一个chain。求出这 n 组数中能形成的最长的 chain 的长度。
例子：输入[[1,2], [2,3], [3,4]]，因为[1,2] -> [3,4]，所以返回2。 继续阅读“LeetCode-646-Maxinum Length of Pair Chain”
LeetCode-494-Target Sum
这个题也是一道动态规划题目。题意是：给出一系列数和一个目标数，使用+和-来使这些数字的和等于给定的目标数，求总共可行的方法数。
例子：输入[1, 1, 1, 1, 1]，target = 3，那么：
|
1 2 3 4 5 6 |
-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 |
所以最后的输出结果是：5 继续阅读“LeetCode-494-Target Sum”
LeetCode-120-Triangle
这道题的题意是：给定一个数组形成的三角形，在从三角形的顶部出发的路径中，求节点数值相加结果为最小的和。
例子：输入
|
1 2 3 4 5 6 7 |
[ [2], [3,4], [6,5,7], [4,1,8,3] ] |
那么从顶部到底部最小的一条路径和为：2+3+5+1=11。
思路：这是一道逆序的二维动态规划题，和之前看过的一道题–《龙与地下城》非常相似，都是逆序地从下往上求 DP数组。代码很简单，就不多做分析了，相信大家一看就能看懂。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { for (int i = triangle.size() - 2; i >= 0; i--) { for (int j = 0; j < i + 1; j++) { triangle[i][j] = min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j]; } } return triangle[0][0]; } }; |
LeetCode-279-Perfect Squares
又是一道非常典型的动态规划的题目。这道题的题意是：给定一个正整数n，那么总可以有若干个完全平方数之和等于n，求出最少的个数。如 n = 12, 12 = 4 + 4 + 4，因此返回3。又如 n = 13, 13 = 4 + 9，因此返回2。 继续阅读“LeetCode-279-Perfect Squares”