Instantly share code, notes, and snippets.

# Shitaibin/LIS.cpp

Last active June 24, 2016 13:28
Show Gist options
• Save Shitaibin/06c0eef2a077c7879ed69338c9fd9560 to your computer and use it in GitHub Desktop.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // https://leetcode.com/problems/coin-change/ // 一堆硬币，给你个金额，你用最少的硬币数量合起来等于它，找不到返回-1 #include #include #include using namespace std; template void print_vector(vector v) { cout << "size = " << v.size() << ": "; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } //dp[i] = min{dp[i-a[j]]}+1, for j in [1,n] //dp[0] = 0 int coin_change(vector a, int amount) { // dp: 使用 INT_MAX 作为没有找到分解方法的标记 ///////////////// 不能使用INT_MAX，因为+1会越界 const int MAX = amount+1; vector dp(amount+1, MAX); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int j = 0; j < a.size(); j++) { if (i >= a[j]) { dp[i] = min(dp[i], dp[i-a[j]] + 1); } } } return dp[amount] != MAX ? dp[amount] : -1; } void test(vector a, int amount, int result) { //print_vector(a); int ret = coin_change(a, amount); if (ret != result) { cout << "false result: " << ret << endl; cout << "test "; print_vector(a); cout << "test amount:" << amount << endl; assert(false); } } int main() { test(vector({}), 0, 0); test(vector({2,5}), 0, 0); test(vector({}), 1, -1); test(vector({2}), 3, -1); test(vector({2,5}), 6, 3); test(vector({1}), 3, 3); test(vector({2}), 4, 2); test(vector({1,2,5}), 8, 3); test(vector({1,2,5}), 10, 2); test(vector({1,2,5}), 13, 4); test(vector({474,83,404,3}), 264, 8); return 0; }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 有一行硬币，挑选出若干硬币，这些硬币的和最大，并且任何两个硬币都不相邻。 #include #include #include using namespace std; template void print_vector(vector v) { cout << "size = " << v.size() << ", "; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } //dp[i] = max{a[i-1]+dp[i-2], dp[i-1]}, for i > 1 //dp[0] = 0 //dp[1] = a[1] int pick_up_coin(vector a) { int n = a.size(); if (n == 0) { return 0; } vector dp(n+1, 0); dp[0] = 0; dp[1] = a[0]; // be care of here, first element of a at 0 for (int i = 2; i <= n; i++) { dp[i] = max(a[i-1]+dp[i-2], dp[i-1]); // be care of i-1 } return dp[n]; } void test(vector a, int result) { //print_vector(a); int ret = pick_up_coin(a); if (ret != result) { cout << "false result: " << ret << endl; assert(pick_up_coin(a) == result); } } int main() { test(vector({1}), 1); test(vector({1,2}), 2); test(vector({1,2,3}), 4); test(vector({1,3,2}), 3); test(vector({5,1,2,10}), 15); test(vector({5,1,4,2,10}), 19); }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 198. House Robber // 一个数列，不能取连续的两个，求最大和。其实就是coin row。 // dp[i] = max {dp[i-2] + A[i], dp[i-1] }, i >= 2 // dp[0] = 0, dp[1] = A[1] typedef long long utype; // lintcode //typedef int utype; //leetcode class Solution { public: /** * @param A: An array of non-negative integers. * return: The maximum amount of money you can rob tonight */ long long houseRobber(vector A) { // write your code here if (rand() % 2) return rob1(A); return rob2(A); } long long rob1(vector &A) { int n = A.size(); if (!n) return 0; vector dp(n, 0); dp[0] = A[0]; if (n > 1) dp[1] = max(A[0], A[1]); for (int i = 2; i < n; i++) { dp[i] = max(dp[i-1], dp[i-2]+A[i]); } return dp[n-1]; } long long rob2(vector &A) { utype n1 = 0; // dp[i-1] utype n2 = 0; // dp[i-2] for (int i = 0; i < A.size(); i++) { utype current = max(n1, n2 + A[i]); n2 = n1; n1 = current; } return n1; } };
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 213. House Robber II // https://leetcode.com/problems/house-robber-ii/ // 把圆化成直线 // 要么考虑第一个，不考虑最后一个 // 要么考虑最后一个，不考虑第一个 class Solution { int rob_in_line(vector nums) { const int n = nums.size(); if (n == 0) return 0; int n1 = nums[0]; int n2 = 0; for (int i = 2; i <= n; i++) { int cur = max(n1, n2 + nums[i-1]); n2 = n1; n1 = cur; } return n1; } public: int rob(vector& nums) { const int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; int rob_with_1 = rob_in_line(vector(nums.begin(), nums.end()-1)); int rob_with_n = rob_in_line(vector(nums.begin()+1, nums.end())); return max(rob_with_1, rob_with_n); } };
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 337. House Robber III // https://leetcode.com/problems/house-robber-iii/ // 二叉树结构的村子，相邻的节点不能抢，求最大和。 // 不论几条线，要么是自己加孙子，要么是孩子。 // 一条线，是都是单传，是自己加一个孙子和一个孩子相比。 // 两条线，是自己加四个孙子，和两个孩子相比。 // 抢了当前位置，再加从孙子开始抢的结果 // 不抢当前位置，将从两个子树开始抢的结果 class Solution { int robber(TreeNode* node, int &l, int &r) { if (node == NULL) { return 0; } int ll, lr, rl, rr; ll = lr = rl = rr = 0; l = robber(node->left, ll, lr); r = robber(node->right, rl, rr); return max(node->val+ll+lr+rl+rr, l+r); } public: int rob(TreeNode* root) { int l, r; return robber(root, l, r); } };
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 最长递增子数列 // O(N^2) // dp[i] = max{dp[j]+1 | [i] > [j], 0<=j& nums) { const int n = nums.size(); if (n <= 1) return n; dp[0] = 1; int max_len = 1; for (int i = 1; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j]+1); } } max_len = max(max_len, dp[i]); // update the max length } return max_len; } }; //-------------------------------------------------------------- // O(NlogN) // "贪" // 使用栈保存数据，约束是约束从小到大。 // 如果当前值比栈顶元素大，进栈。 // 否则，查找第一个大于等于该值的元素，执行替换。 // 这样在当前位置而言，栈的大小仍代表最大LIS的长度。 // 但又能让他继续添加，比当前位置大的元素入栈。 class Solution { public: int lengthOfLIS(vector& nums) { if (nums.empty()) return 0; vector stack; stack.push_back(nums[0]); for (int i = 1; i < nums.size(); i++) { if (nums[i] > stack.back()) { // push stack.push_back(nums[i]); } else { int low = 0, high = stack.size()-1; while (low <= high) { int mid = low + (high - low) / 2; if (stack[mid] >= nums[i]) { high = mid - 1; } else { low = mid + 1; } } stack[low] = nums[i]; } } return stack.size(); } };
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // https://leetcode.com/problems/maximum-subarray/ // 具有最大和的连续子数组 #include #include #include using namespace std; template void print_vector(vector v) { cout << "size = " << v.size() << ", "; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } //dp[i] = dp[i-1] + a[i], d[i-1]>0, for i > 1 //dp[i] = a[i], else, for i > 1 //dp[0] = a[0] int max_sub_array_sum(vector a) { int n = a.size(); if (n == 0) { return 0; } vector dp(n, 0); dp[0] = a[0]; int max_sum = a[0]; for (int i = 1; i < n; i++) { dp[i] = a[i] + max(0, dp[i-1]); max_sum = max(max_sum, dp[i]); // update max_sum } return max_sum; } // 精简为贪心：每个状态的最优解都从上一个状态的最优解得来 int max_sub_array_sum_2(vector a) { int cur_sum = 0; int max_sum = 0; for (int i = 0; i < a.size(); i++) { cur_sum += a[i]; cur_sum = max(cur_sum, 0); max_sum = max(max_sum, cur_sum); } return max_sum; } void test(vector a, int result) { //print_vector(a); int ret = max_sub_array_sum_2(a); if (ret != result) { cout << "false result: " << ret << endl; print_vector(a); assert(false); } } int main() { test(vector({1}), 1); test(vector({1,-5}), 1); test(vector({1,-2,3}), 3); test(vector({1,-1,5}), 5); test(vector({5,-1,-2,10}), 12); test(vector({5,1,-10,2,10}), 12); }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 221. Maximal Square /* 如果DP写起来很复杂，你肯定想错了，用相反的角度思考一下，也许才是对的。*/ /** * 更多讨论： * https://leetcode.com/discuss/38489/easy-solution-with-detailed-explanations-8ms-time-and-space * 列出了如何使用1维数组解决的方案，去手动模拟吧 */ // v1: O(m*n) class Solution { public: int maximalSquare(vector>& matrix) { const int m = matrix.size(); if (m == 0) return 0; const int n = matrix[0].size(); if (n == 0) return 0; int max_len = 0; vector> dp(m, vector(n)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { dp[i][j] = matrix[i][j] - '0'; if (i != 0 && j != 0 && dp[i][j] != 0) { dp[i][j] = min( min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] ) + 1; } if (dp[i][j] > max_len) { max_len = dp[i][j]; } } } return max_len * max_len; } };
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 给你个字符串，把它分解为回文的合集，问至少切几下（等价于最少分成几个回文-1）？ // 132. Palindrome Partitioning II // 这里面有两个DP，第一个是DP求字符串是不是回文。 // 第二个求一个字符串最少可以分为几个回文。 #include #include #include using namespace std; class Solution { static const size_t bufsize = 2000; bool palindrome[bufsize][bufsize]; int dp[bufsize]; string str; public: int minCut(string s) { const int n = s.size(); if (n <= 1) return 0; s.insert(s.begin(), 'x'); str = s; // sub string: s[i,j] is palindrome or not // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= n; j++) { // if (is_palindrome(i, j)) { // palindrome[i][j] = true; // } else { // palindrome[i][j] = false; // } // } // } // DP的方式去判断字符串子串是不是回文 // dp[i][j] = dp[i+1][j-1], for s[i]=s[j], i= 1; i--) { // for (int j = i; j <= n; j++) { // if (s[i]==s[j] && (j-i<2 || palindrome[i+1][j-1]) ) { // palindrome[i][j] = true; // } else { // palindrome[i][j] = false; // } // } // } // 自前向后的DP2 for (int i = 1; i <= n; i++) { // i在后，j在前 for (int j = i; j >= 1; j--) { if (s[i] == s[j] && (i-j<2 || palindrome[j+1][i-1]) ) { palindrome[j][i] = true; } else { palindrome[j][i] = false; } } } // dp[i]: 长度为i的字符串分成回文的最小段数 dp[0] = 0; dp[1] = 1; const int INF = (1<<30); for (int i = 2; i <= n; i++) { dp[i] = INF; for (int j = 0; j < i; j++) { if (palindrome[j+1][i]) { dp[i] = min(dp[i], dp[j]+1); } } } return dp[n]-1; } }; void test(string s, int result) { Solution so; int ret = so.minCut(s); if (ret != result) { cout << "test cast:" << endl << s << endl; cout << "true result: " << result << endl; cout << "false result: " << ret << endl; assert(false); } } int main() { test("", 0); test("a", 0); test("aa", 0); test("aaa", 0); test("ab", 1); test("aab", 1); test("aabb", 1); test("aabba", 1); test("aabbaa", 0); test("aabaa", 0); test("aabccabcd", 6); return 0; }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters