今天再摆一次吧，嘿嘿嘿
一：乘积最大子数组
class Solution { public: int maxProduct(vector<int>& nums) { int n = nums.size(); int pre_min = 1; int pre_max = 1; int max = INT_MIN; for(int i = 0 ; i < n ; ++i) { int curr_min = std::min(nums[i],std::min(pre_min*nums[i],pre_max*nums[i])); int curr_max = std::max(nums[i],std::max(pre_max*nums[i],pre_min*nums[i])); pre_max = curr_max; pre_min = curr_min; max = std::max(max,curr_max); } return max; } };二：分割和等子集
class Solution { public: bool canPartition(vector<int>& nums) { int sum = std::accumulate(nums.begin() , nums.end(),0); if(!sum || sum % 2) { return false; } int target = sum / 2; std::vector<int> dp(target+1); dp[0] = 1; for(auto& num : nums) { for(int i = target ; i >= num ; --i) { if(dp[i - num]) { dp[i] = 1; } if(dp[target]) { return true; } } } return false; } };三：最长有效括号
class Solution { public: int longestValidParentheses(string s) { int n = s.size(); if(n <= 1) { return 0; } std::stack<int> stk; stk.push(-1); int max = 0; for(int i = 0 ; i < n ; ++i) { if(s[i] == ')') { if(stk.top() == -1 || s[stk.top()] != '(') { while(stk.size()) { stk.pop(); } } else if(s[stk.top()] == '(') { stk.pop(); max = std::max(max,i-stk.top()); continue; } } stk.push(i); } return max; } };四：不同路径
class Solution { public: int uniquePaths(int m, int n) { if(!m || !n) { return 0; } std::vector<std::vector<int>> dp(n,std::vector<int>(m)); for(int i = 0 ; i < n ; ++i) { for(int j = 0 ; j < m ; ++j) { if(!i && !j) { dp[i][j] = 1; } else if(!i || !j) { if(!i) { dp[0][j] = 1; } else { dp[i][0] = 1; } } else { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[n-1][m-1]; } };五：完全平方数
class Solution { public: int numSquares(int n) { std::vector<int> dp(n+1,n+1); dp[0] = 0; for(int i = 1 ; i <= n ; ++i) { for(int j = 1; j*j <= i ; ++j) { dp[i] = std::min(dp[i],dp[i-j*j]+1); } } return dp[n]; } };六：只出现一次的数字
class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; for(auto&num : nums) { ret ^= num; } return ret; } };七：多数元素
class Solution { public: int majorityElement(vector<int>& nums) { int ret = 0; int max = 0; for(auto& num : nums) { if(ret != num) { if(max == 0) { ret = num; max = 1; } else { --max; } } else { ++max; } } return ret; } };八：颜色分类
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); int zero = 0; int one = 0; for(int i = 0 ; i < n ; ++i) { if(nums[i] == 0) { std::swap(nums[zero],nums[i]); if(one > zero) { std::swap(nums[one],nums[i]); } ++zero; ++one; } else if(nums[i] == 1) { std::swap(nums[i],nums[one]); ++one; } } } };九：寻找重复数
class Solution { public: int findDuplicate(vector<int>& nums) { int fast = 0; int slow = 0; while(true) { fast = nums[nums[fast]]; slow = nums[slow]; if(fast == slow) { fast = 0; while(fast != slow) { fast = nums[fast]; slow = nums[slow]; } return fast; } } return 0; } };
