LeetCode 4 Keys Keyboard Imagine you have a special keyboard with the following keys: Key 1: (A): Prints one ‘A’ on screen. Key 2: (Ctrl-A): Select the whole screen. Key 3: (Ctrl-C): Copy selection to buffer. Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed. Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of ‘A’ you can print on screen. Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

---

给定四个按键，有四种操作：

• A: 打印一个字符A
• Ctrl-A: 全选
• Ctrl-C: 复制
• Ctrl-V: 粘贴

问通过n次按键操作，最多可以打印出多少个字符。 稍微分析一下，增加字符比较快的方法是用Ctrl-V，连带着需要Ctrl-C和Ctrl-A的配合，所以要想快速增加字符，必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾，这就需要3个操作。当n比较小时，这3个操作相对来说比较耗时，通过分析可知，当N<=6时，直接用N次Print(A)操作能得到最多的字符。 假设dp[i]表示使用i次操作能得到的最多字符，显然dp[i]=i，当i<=6时。 当i>6时，我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V，所以结尾我们至少要空出3个操作来使用技能，也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能，假设释放技能的位置是b，则b<=i-3；下界是我们可以在一开始只有一个字符时使用技能，即b>=1。所以我们遍历[1,i-3]的地方释放技能，则我们可以有i-b-2个Ctrl-V结尾，再加上释放技能的位置已经有一个dp[b]了，所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。 完整代码如下： [cpp] class Solution { public: int maxA(int N) { if (N <= 6)return N; vector<int> dp(N + 1, 0); for (int i = 1; i <= 6; ++i)dp[i] = i; for (int i = 7; i <= N; ++i) { for (int b = i – 3; b >= 1; –b) { dp[i] = max(dp[i], dp[b] + dp[b] * (i – b – 2)); } } return dp[N]; } }; [/cpp] 本代码提交AC，用时0MS。]]>

LeetCode Palindromic Substrings Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

1. The input string length won’t exceed 1000.

---

给定一个字符串，问该字符串中有多少个回文子串。 暴力解法就是枚举每个子串，判断子串是否是回文串。判断一个字符串是否是回文串，可以用首尾指针法，也可以用中心扩展法，方法很多，需要O(n)时间，所以暴力总时间是O(n^3)。 稍微高效一点的方法是，不枚举子串，直接对每个字符用中心扩展法，请看讨论区代码。 我的解法是O(n^2)的DP方法，dp[i][j]表示子串[i,j]是否是回文串。首先对于长度为1的子串dp[i][i]=1肯定都是回文串；求dp[i][j]时，如果s[i]==s[j]且dp[i+1][j-1]是回文串，则dp[i][j]=1也是回文串。 最后统计一下dp数组中有多少个1就有多少个回文子串。 代码如下： [cpp] class Solution { public: int countSubstrings(string s) { int ans = 0, n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i) { dp[i][i] = 1; ++ans; } for (int len = 2; len <= n; ++len) { for (int i = 0; i < n; ++i) { int j = i + len – 1; if (j >= n)break; if (s[i] == s[j] && (len == 2 || dp[i + 1][j – 1] == 1)) { dp[i][j] = 1; ++ans; } } } return ans; } }; [/cpp] 本代码提交AC，用时12MS。]]>

LeetCode Maximum Length of Pair Chain You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order. Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

1. The number of given pairs will be in the range [1, 1000].

---

如果两个数对(a,b)和(c,d)满足b<c，则(c,d)可以跟在(a,b)的后面。给定一系列数对(s,t)，问从这些数对中最多能取出多少个数对满足连续满足这种条件。 解法1，使用DP。首先对所有数对(x,y)先按x排序，x相同再按y排序。然后遍历数对，对于每个数对，有两种选择，不要或者要，对应dp[i][0]和dp[i][1]，表示到i时能选出来的最多的满足条件的数对。 则dp[i][0]=max(dp[i-1][0], dp[i-1][1])，因为第i个数对不选，所以肯定等于前i-1个能选出来的最大数对，也就是max(dp[i-1][0], dp[i-1][1])。 如果第i个数对选，则要往前找到一个和i不冲突的数对j，接在j的后面，所以dp[i][1]=dp[j][1]+1。 代码如下： [cpp] bool cmp(const vector<int>& p1, const vector<int>& p2) { return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); } class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(pairs.begin(), pairs.end(), cmp); int n = pairs.size(); vector<vector<int>> dp(n, vector<int>(2, 0)); dp[0][0] = 0; dp[0][1] = 1; int ans = 1; for (int i = 1; i < n; ++i) { dp[i][0] = max(dp[i – 1][0], dp[i – 1][1]); dp[i][1] = 1; int j = i – 1; while (j >= 0 && pairs[i][0] <= pairs[j][1]) { –j; } if (j >= 0) { dp[i][1] = max(dp[i][1], dp[j][1] + 1); } ans = max(ans, dp[i][0]); ans = max(ans, dp[i][1]); } return ans; } }; [/cpp] 本代码提交AC，用时49MS。 我隐隐觉得这种解法有问题，就是在求dp[i][1]的时候，应该要找i前面所有和i不冲突的j，求max，即dp[i][1]=max(dp[j][1]+1)。 所以解法2是无懈可击的DP解法。设dp[i]表示以数对i结尾能得到的最长的链式数对，则初始的时候，所有dp[i]=1。然后对于第i个数对，遍历i前面所有数对j，只要i和j能够链起来，则求dp[i]=max(dp[j]+1)。时间复杂度$$O(n^2)$$，代码如下： [cpp] class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); }); int n = pairs.size(), ans = 1; vector<int> dp(n, 1); for (int i = 1; i < n; ++i) { for (int j = i – 1; j >= 0; –j) { if (pairs[i][0] > pairs[j][1]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } return ans; } }; [/cpp] 本代码提交AC，用时122MS。 解法3，首先还是对所有数对排序，然后把这题看成类似于求最长上升子序列。即设dp[k]=构成链条长度为k时最小的结束时间。那么来了一个数对之后，如果该数对的开始时间大于dp末尾的结束时间，则说明该数对可以追加到dp中，链条长度加1，dp[k+1]=该数对的结束时间。否则，如果该数对的开始时间不大于dp末尾的结束时间，则需要像LIS一样，把该数对插入到dp中，因为dp是排好序的，所以二分插入即可。 该思路请参考：https://discuss.leetcode.com/topic/96814/python-straightforward-with-explanation-n-log-n/2。比较有意思的是，正如第一个评论人所说，因为提前对数对按结束时间排序了，所以后面的数对肯定是大于等于dp末尾的数对的，所以新来的数对只可能追加到dp的末尾，不可能插入到dp的其他位置，所以就可以省略二分插入的过程。完整代码简洁如下： [cpp] class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; }); int ans = 0; for (int i = 0, j = 0; j < pairs.size(); ++j) { if (j == 0 || pairs[j][0] > pairs[i][1]) { ++ans; i = j; } } return ans; } }; [/cpp] 本代码提交AC，用时45MS。 这个题可以把每个数对看成一个活动的开始和结束时间，把问题转换为从所有活动中选出尽量多的不重叠的活动，求最多的活动个数。活动选择问题可以用贪心求解，详细介绍和证明请看维基百科。]]>