Tag Archives: DP

hihoCoder 1550-顺序三元组

Leave a reply

hihoCoder 1550-顺序三元组

题目1 : 顺序三元组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个长度为N的数组A=[A1, A2, … AN]，已知其中每个元素Ai的值都只可能是1, 2或者3。 请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak。

输入

第一行包含一个整数N 第二行包含N个整数A1, A2, … AN。(1 ≤ Ai ≤ 3) 对于30%的数据，1 ≤ N ≤ 100 对于80%的数据，1 ≤ N ≤ 1000 对于100%的数据，1 ≤ N ≤ 100000

输出

一个整数表示答案
样例输入
6
1 3 2 1 2 3
样例输出
3
给定一个数组，只包含1,2,3这三个数，问数组中有多少个三元组下标(i,j,k)，满足a[i]<a[j]<a[k]。 我一开始的想法是，找出所有1,2,3出现的下标，对于每一个1的下标i，去2的下标数组中找一个lowerbound j，然后用j在3的下标数组中找一个lowerbound k，则3的下标数组中k往后的下标都是符合条件的。这需要两层循环，过了90%的数据，然后TLE了。 后来经过大神点拨，要想得到符合条件的三元组，则2一定要在中间，所以我们可以遍历原数组，对于每一个出现的2，用其左边的1的频数乘以其右边3的频数，就是这个2可以构成的合法三元组的个数。 为了不重复计算，我们可以提前算好每个位置左边和右边1和3的频数，到时候直接用left[1]*right[3]就好了。完整代码如下： [cpp] #include<algorithm> #include<vector> #include<iostream> #include<map> using namespace std; typedef long long ll; int main() { //freopen("input.txt", "r", stdin); int n = 0; scanf("%d", &n); vector<int> nums(n, 0); map<int, int> left, right; for (int i = 0; i < n; ++i) { scanf("%d", &nums[i]); ++right[nums[i]]; } ll ans = 0; for (int i = 0; i < n; ++i) { –right[nums[i]]; if (nums[i] == 2) { ans += left[1] * right[3]; } ++left[nums[i]]; } printf("%lld\n", ans); return 0; } [/cpp] 本代码提交AC，用时18MS。]]>

LeetCode 4 Keys Keyboard

Leave a reply

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 2 Keys Keyboard

Leave a reply

LeetCode 2 Keys Keyboard Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

  1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
  2. Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’. Example 1: 
Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
Note:
  1. The n will be in the range [1, 1000].
一个记事本中原本只有一个字符A，每次可以做两种操作中的一种，分别是全选和粘贴。问要得到n个字符A，至少需要经过多少次操作。 这一题我一开始想到用BFS来做，两种操作相当于两条搜索路径，所以很容易能写出BFS的代码： [cpp] class Solution { private: struct Node { int presented_cnt_; // 现在有多少个字符 int copied_cnt_; // 剪切板中有多少个字符 int step_; // 走过多少步了 Node(int p, int c, int s) :presented_cnt_(p), copied_cnt_(c), step_(s) {}; }; public: int minSteps(int n) { queue<Node> q; Node node(1, 0, 0); q.push(node); while (!q.empty()) { Node cur = q.front(); q.pop(); if (cur.presented_cnt_ == n) return cur.step_; if (cur.presented_cnt_ > n)continue; Node copy_node(cur.presented_cnt_, cur.presented_cnt_, cur.step_ + 1); // 全选 q.push(copy_node); if (cur.copied_cnt_ != 0) { // 粘贴 Node paste_node(cur.presented_cnt_ + cur.copied_cnt_, cur.copied_cnt_, cur.step_ + 1); q.push(paste_node); } } } }; [/cpp] 预料到了，本代码提交TLE。 搜索会超时的，用DP一般都不会超时。设dp[i]表示要得到i个字符A，至少需要的操作数。显然，dp[1]=0。 假设已经求到了dp[1,…,i-1]，现在要求dp[i]。要得到i个字符，最多的操作数是i，即先复制一个A，然后粘贴i-1次，总共需要i次操作。比较快的方法是，如果i是偶数，则可以从i/2个字符开始，全选粘贴就能得到i个字符。 所以我们遍历i前面的所有j，如果i能整除j，则可以全选j，然后粘贴i/j-1次得到i个字符，即操作数是1+(i/j-1)=i/j，当然还需要加上到达i的操作数，所以dp[j]=dp[i]+i/j。 完整代码如下： [cpp] class Solution { public: int minSteps(int n) { vector<int> dp(n + 1, INT_MAX); dp[1] = 0; for (int i = 2; i <= n; ++i) { dp[i] = i; for (int j = i – 1; j >= 1; –j) { if (i%j == 0) { dp[i] = min(dp[i], dp[j] + i / j); } } } return dp[n]; } }; [/cpp] 本代码提交AC，用时79MS。 还有一种解法类似于素数筛法，我们首先知道dp[1]=0，如果我们对1个字符先全选，然后不停粘贴，则能得到2,3,4,…个字符，且操作数是2,3,4,…；下一次，我们知道dp[2]=2，如果我们对2个字符全选，然后不停粘贴，则能得到4,6,8,…个字符，且操作数是4,5,6,…。每一轮我们都只保留最小操作数。最终筛完之后，就是全局最优结果了。 完整代码如下： [cpp] class Solution { public: int minSteps(int n) { vector<int> dp(n + 1, INT_MAX); dp[1] = 0; for (int i = 1; i <= n; ++i) { for (int j = 2 * i, k = 2; j <= n; j += i, ++k) { dp[j] = min(dp[j], dp[i] + k); } } return dp[n]; } }; [/cpp] 本代码提交AC，用时3MS，速度飞快，因为越到后面，循环倍数越少。]]>

LeetCode Palindromic Substrings

Leave a reply

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

Leave a reply

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。 这个题可以把每个数对看成一个活动的开始和结束时间，把问题转换为从所有活动中选出尽量多的不重叠的活动，求最多的活动个数。活动选择问题可以用贪心求解，详细介绍和证明请看维基百科。]]>

LeetCode Maximum Average Subarray I

Leave a reply

LeetCode Maximum Average Subarray I Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value. Example 1: 

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].
给定一个数组，问长度为k的子数组的最大平均数是多少。简单题，因为平均数等于和除以k，k相同，也就相当于求长度为k的最长连续子串的和。 解法是维护一个长度为k的滑动窗口，求滑动窗口内的最大连续子数组的和，然后除以k。 代码如下： [cpp] class Solution { public: double findMaxAverage(vector<int>& nums, int k) { int n = nums.size(); if (n < k)return 0; int i = 0, sum = 0, ans = INT_MIN; for (int j = 0; j < k; ++j)sum += nums[j]; for (int j = k; j < n; ++j) { ans = max(ans, sum); sum += nums[j] – nums[i]; ++i; } ans = max(ans, sum); return ans / double(k); } }; [/cpp] 本代码提交AC，用时176MS。]]>

LeetCode Shopping Offers

Leave a reply

LeetCode Shopping Offers In LeetCode Store, there are some kinds of items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price. You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer. You could use any of special offers as many times as you want. Example 1: 

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
Example 2: 
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.
Note:
  1. There are at most 6 kinds of items, 100 special offers.
  2. For each item, you need to buy at most 6 of them.
  3. You are not allowed to buy more items than you want, even if that would lower the overall price.
给定每个商品的单价和需要购买的数量，并且有一些special offer，相当于捆绑销售的优惠套餐。问刚好买到给定数量的商品，所花的最低费用是多少。 注意给定的限制条件中商品最多只有6种，且每件最多只购买6件，所以可以考虑用暴力方法。 把special offer看成一个背包问题里的“商品”，对于每个special offer，我们有两种选择，可以用或者不用。如果需要的needs数组每一项都大于等于某个special offer的每一项，即可以用该special offer，我们比较用和不用该special offer的最终花费，取花费低的。如果用该special offer，则needs数组需要减掉sp捆绑的每件商品的件数，然后继续递归该sp是否可用，相当于完全背包，不计件数的。如果该sp不能用，则递归考虑下一个sp。最后如果递归考虑完所有sp了，则剩余的商品只能按原价购买，算出按原价购买的费用即可。 完整代码如下： [cpp] class Solution { private: int dot(vector<int>& price, vector<int>& needs) { int ans = 0; for (int i = 0; i < needs.size(); ++i) { ans += price[i] * needs[i]; } return ans; } int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) { if (idx == special.size())return dot(price, needs); // 原价购买 int i = 0, n = special[idx].size(); vector<int> small_needs = needs; for (i = 0; i < n – 1; ++i) { if (special[idx][i] > needs[i])break; small_needs[i] -= special[idx][i]; } if (i == n – 1)return min(shopping(price, special, small_needs, idx) + special[idx][n – 1], shopping(price, special, needs, idx + 1)); else return shopping(price, special, needs, idx + 1); } public: int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { return shopping(price, special, needs, 0); } }; [/cpp] 本代码提交AC，用时6MS。 参考：https://leetcode.com/articles/shopping-offers/，下次记得看到这种数据量非常小的题，首先尝试暴力方法！]]>

LeetCode Decode Ways II

Leave a reply

LeetCode Decode Ways II A message containing letters from A-Z is being encoded to numbers using the following mapping way: 

'A' -> 1
'B' -> 2
...
'Z' -> 26
Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9. Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it. Also, since the answer may be very large, you should return the output mod 109 + 7. Example 1: 
Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
Example 2: 
Input: "1*"
Output: 9 + 9 = 18
Note:
  1. The length of the input string will fit in range [1, 105].
  2. The input string will only contain the character ‘*’ and digits ‘0’ – ‘9’.
本题是LeetCode Decode Ways的升级版本，引入了一个星号’*’，可以表示’1′-‘9’这9个数字。给定一个加密的字符串，问有多少种解密方法。 这个题说难也难，说简单也简单，我居然跪在了int上，把dp数组由int改为long long就AC了！ 和前一题的思路差不多，对于每个字符，都有两种可能的选择，要么该字符单独解码，要么和前一个字符组合起来解码。 设dp[i]表示前i个字符总的解密数。 对于当前字符是数字，前一个字符也是数字的情况，和前一题的思路完全一样，如果是’1’-‘9’，则可以自行解码，dp[i]+=dp[i-1]；如果前一个字符和当前字符组合的数字范围在[10,26]，可以和前一个字符组合解码，dp[i]+=dp[i-2]。 如果当前字符是数字，但前一个字符是*。如果要和前一个字符组合，当前字符如果在[‘0′,’6’]，则前一个*可以取’1’或者’2’，所以dp[i]+=dp[i-2]*2；如果当前字符是[‘7′,’9’]，则前一个*只能取’1’，所以dp[i]+=dp[i-2]。 对于*需要特殊处理。如果当前字符是*，前一个字符不是*，要和前一个字符组合，则如果前一个是’1’，则当前*可以取[‘0′,’9’]，所以dp[i]+=dp[i-2]*9；如果前一个是’2’，则当前*可以取[‘0′,’6’]，所以dp[i]+=dp[i-2]*6。其他情况都不能组合。 如果当前字符和前一个字符都是*的情况，要组合，则**的情况只有15种，注意不是26种，因为要去掉那些个位数和包含0的十位数的情况，剩下就只有15种了。所以dp[i]+=dp[i-2]*15。 完整代码如下： [cpp] const int MOD = 1000000007; typedef long long ll; class Solution { public: int numDecodings(string s) { if (s == "" || s[0] == ‘0’)return 0; s = "^" + s; int n = s.size(); vector<ll> dp(n, 0); dp[0] = 1; if (s[1] == ‘*’)dp[1] = 9; else dp[1] = 1; for (int i = 2; i < n; i++) { if (s[i] >= ‘1’ && s[i] <= ‘9’) dp[i] += dp[i – 1] % MOD; // 独自解析 if ((s[i – 1] == ‘1’ && s[i] >= ‘0’ && s[i] <= ‘9’) || (s[i – 1] == ‘2’ && s[i] >= ‘0’ && s[i] <= ‘6’)) dp[i] += dp[i – 2] % MOD; if (s[i – 1] == ‘*’&&s[i] >= ‘0’&&s[i] <= ‘9’) { if (s[i] >= ‘0’&&s[i] <= ‘6’)dp[i] += dp[i – 2] * 2 % MOD; if (s[i] > ‘6’)dp[i] += dp[i – 2] % MOD; } if (s[i] == ‘*’) { dp[i] += dp[i – 1] * 9 % MOD; // 独自解析 if (s[i – 1] != ‘*’) { if (s[i – 1] == ‘1’)dp[i] += dp[i – 2] * 9 % MOD; else if (s[i – 1] == ‘2’)dp[i] += dp[i – 2] * 6 % MOD; } else { dp[i] += dp[i – 2] * 15 % MOD; } } dp[i] %= MOD; } return dp[n – 1]; } }; [/cpp] 本代码提交AC，用时72MS。比赛的时候dp数组用int存的，死活WA，比赛结束那一秒，改成long long之后就AC了，但是比赛已经结束了。。。 看了下TOP代码，思路比我的稍微清晰一点，原理都是一样的，重构我的代码如下： [cpp] class Solution { public: int numDecodings(string s) { if (s == "" || s[0] == ‘0’)return 0; s = "^" + s; int n = s.size(); vector<ll> dp(n, 0); dp[0] = 1; if (s[1] == ‘*’)dp[1] = 9; else dp[1] = 1; for (int i = 2; i < n; i++) { char cur = s[i], pre = s[i – 1]; ll &curCnt = dp[i], preCnt = dp[i – 1], prePreCnt = dp[i – 2]; if (cur == ‘0’) { if (pre == ‘1’|| pre == ‘2’)curCnt += prePreCnt % MOD; else if (pre == ‘*’)curCnt += prePreCnt * 2 % MOD; else return 0; } else if (cur == ‘*’) { curCnt += preCnt * 9 % MOD; if (pre == ‘1’)curCnt += prePreCnt * 9 % MOD; else if (pre == ‘2’)curCnt += prePreCnt * 6 % MOD; else if (pre == ‘*’)curCnt += prePreCnt * 15 % MOD; } else { // [‘1′,’9′] curCnt += preCnt % MOD; if(pre==’1’)curCnt += prePreCnt % MOD; else if (pre == ‘2’ && cur <= ‘6’)curCnt += prePreCnt % MOD; else if (pre == ‘*’) { if (cur <= ‘6’)curCnt += prePreCnt * 2 % MOD; else curCnt += prePreCnt % MOD; } } curCnt %= MOD; } return dp[n – 1]; } }; [/cpp] 本代码提交AC，用时105MS。]]>

LeetCode Continuous Subarray Sum

Leave a reply

LeetCode Continuous Subarray Sum Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer. Example 1: 

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2: 
Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
Note:
  1. The length of the array won’t exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
给定一个非负整数数组和k，问数组中是否存在长度至少为2的连续子数组，子数组的和是k的n倍，n也是一个整数。 这个题之前好像在哪遇到过。遇到连续子数组的问题，首先要想到前缀和。因为这里要求和是k的n倍，有点麻烦。 首先我们需要知道一个数学知识，如果到i的前缀和accusum1和到j的前缀和accusum2除以k的余数相等，那么(i,j]的连续子数组的和就是k的整数倍。比如第一个样例中，连续子数组的和以及连续子数组的和除以k的余数：
  • [23,25,29,35,42]
  • [5,1,5,5,0]
如果下标从0开始，则下标为0和2的accusum%k都等于5，说明(0,2]的连续子数组的和是k的整数倍。accusum(0,2]=2+4=6，确实是6的整数倍。 这个道理其实很好理解，accusum0%k=5，到了accusum2%k还等于5，说明中间只加了整数倍的k，才导致余数没变，因为整数倍的k 模k是等于0的。 知道了这个道理就好办了，我们用map保存accusum%k的值和计算到现在的accusum的下标，如果后来遇到一个accusum模k的余数在map中，说明找到了一个可能，我们再判断一下他们之间的距离是否至少为2即可。 还有一个特殊的地方需要注意的是，如果k等于0，则不能取模运算。 最后还要注意的一点是，第12行，把当前余数和下标插入map是在else分支的，只有当map中不存在这个余数才插入，否则不插入。比如上面的例子，我们遇到多个accusum模k的余数是5，但是我们map中保存的应该是第0个下标，后续的余数等于5的下标不能更新0这个下标，因为这样才能使得后续的余数相等的下标和map中的下标的差越大，即更好的满足距离至少为2的约束。 完整代码如下： [cpp] class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { unordered_map<int, int> reminders; reminders[0] = -1; int accusum = 0; for (int i = 0; i < nums.size(); ++i) { accusum += nums[i]; if (k != 0)accusum %= k; // 注意k为0时，不能取模 if (reminders.find(accusum) != reminders.end()) { if (i – reminders[accusum] >= 2)return true; } else reminders[accusum] = i; // 注意必须是在else分支 } return false; } }; [/cpp] 本代码提交AC，用时26MS。]]>

LeetCode Range Sum Query 2D – Immutable

Leave a reply

LeetCode Range Sum Query 2D – Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). Range Sum Query 2D The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8. Example: 
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.
给定一个矩阵，要求矩阵中的任意一个子矩阵的和，而且可能有很多次这样的请求。 因为之前在hiho上做过一个用DP求子矩阵的和的题，所以这题就很easy了。 定义一个二维数组dp[i][j]表示固定子矩阵的左上角坐标为(1,1)（假设矩阵的下标从1开始），当右下角坐标为(i,j)时，这个子矩阵的和是多少。则有： dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+matrix[i][j] 这个很好理解，相当于求面积，dp[i][j-1]+dp[i-1][j]加了两遍dp[i-1][j-1]，所以要减掉一个，最后再加上dp[i][j]独有的matrix[i][j]。 有了dp[i][j]之后，怎样求任意一个子矩阵的和呢？假设我们要求第i,j两行、u,v两列交成的子矩阵的和，应该怎样计算呢。这个也很好算，也是面积的加加减减，如下图所示，把(j,v)的面积减去(j,u)左边以及(i,v)上边的面积，但是(i,u)左上的面积减了两次，所以还要加上。总结成公式就是： cursum=dp[j][v]-dp[j][u-1]-dp[i-1][v]+dp[i-1][u-1] 
      |               |
-----(i,u)----------(i,v)----
      |               |
      |               |
-----(j,u)----------(j,v)----
      |               |
通过cursum公式，我们很容易就能求出任意一个子矩阵的和了。代码如下： [cpp] class NumMatrix { private: vector<vector<int>> dp; public: NumMatrix(vector<vector<int>> matrix) { if (matrix.empty() || matrix[0].empty())return; int m = matrix.size(), n = matrix[0].size(); for (int i = 0; i < m + 1; ++i)dp.push_back(vector<int>(n + 1, 0)); // 为了方便，多增加了一行和一列 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = dp[i][j – 1] + dp[i – 1][j] – dp[i – 1][j – 1] + matrix[i – 1][j – 1]; } } } int sumRegion(int row1, int col1, int row2, int col2) { if (dp.empty())return 0; ++row1; // 因为dp多一行和一列，所以这里提前加上 ++col1; ++row2; ++col2; return dp[row2][col2] – dp[row2][col1 – 1] – dp[row1 – 1][col2] + dp[row1 – 1][col1 – 1]; } }; [/cpp] 本代码提交AC，用时22MS。]]>