``` /* RemoveElement */ #include #include using namespace std; class Solution { public: int removeElement(vector &A, int elem) { if(A.size() == 0) { return 0; } vector::iterator it; for(it = A.begin(); it != A.end();) { if(*(it) == elem) { A.erase(it); } else { it++; } } return A.size(); } }; int main() { vector vec; vec.push_back(1); vec.push_back(2); vec.push_back(2); vec.push_back(3); vec.push_back(2); vec.push_back(3); vec.push_back(4); vec.push_back(2); Solution* sol = new Solution(); cout << sol->removeElement(vec, 2) << endl; } /* SubarraySum */ #include #include using namespace std; class Solution { public: vector subarraySum(vector &nums) { int length = nums.size(); vector res; if(length == 0) return res; int sum = 0; for(int i = 0; i < length; i++) { for(int j = i; j < length; j++) { if(i == j) { sum = nums[i]; } else { sum = sum + nums[j]; } if(sum == 0) { res.push_back(i); res.push_back(j); return res; } } } return res; } }; int main() { Solution* sol = new Solution(); vector args; args.push_back(-3); args.push_back(1); args.push_back(2); args.push_back(-3); args.push_back(4); vector res = sol->subarraySum(args); if(res.size() != 0) { cout << res[0] << res[1] << endl; } int i; cin >> i; } /* SubarraySumK */ #include #include #include using namespace std; class Solution { public: vector subarraySum(vector nums, int k) { int length = nums.size(); vector res; if(length == 0) return res; map table; table[nums[0]] = 0; int lastSum = nums[0]; for(int i = 1; i < length; i++) { int curSum = lastSum + nums[i]; map::iterator it; it = table.find(curSum - k); if(it != table.end()) { res.push_back(table[curSum - k] + 1); res.push_back(i); return res; } else { table[curSum] = i; lastSum = curSum; } } return res; } }; int main() { vector nums; nums.push_back(1); nums.push_back(4); nums.push_back(20); nums.push_back(3); nums.push_back(10); nums.push_back(5); Solution* sol = new Solution(); vector res = sol->subarraySum(nums, 33); cout << res[0] << " " << res[1] << endl; } /* Subarray Sum Closest */ #include #include #include #include using namespace std; class Solution { public: struct node { node(int _sum, int _index):sum(_sum), index(_index) {} int sum, index; bool operator<(const node &other) const { return (sum < other.sum || (sum == other.sum && index < other.index)); } }; vector subarraySumClosest(vector &nums) { vector s; vector result(2); s.push_back(node(0, -1)); int sum = 0, len = nums.size(); for(int i = 0; i < len; ++i) { sum += nums[i]; s.push_back(node(sum, i)); } sort(s.begin(), s.end()); len = s.size(); int ans = 0x7fffffff; for(int i = 0; i < len - 1; ++i) if(abs(s[i+1].sum - s[i].sum) < ans) { ans = abs(s[i+1].sum - s[i].sum); result[0] = min(s[i].index, s[i+1].index) + 1; result[1] = max(s[i].index, s[i+1].index); } return result; } }; int main() { int arr[5] = {-3,1,1,-3,5}; vector vec(arr, arr+5); Solution* sol = new Solution(); vector res = sol->subarraySumClosest(vec); cout << res[0] << res[1] < #include using namespace std; class Solution { public: void recoverRotatedSortedArray(vector &nums) { int length = nums.size(); if(length == 0) return; int i = 1; while(i < length && nums[i] >= nums[i-1]) { i++; } if(i == length) return; reverse(nums, 0, i-1); reverse(nums, i, length-1); reverse(nums, 0, length-1); } private: void reverse(vector &nums, int begin, int end) { int i = begin, j = end; while(i < j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; j--; } } }; int main() { vector rec; rec.push_back(4); rec.push_back(5); rec.push_back(1); rec.push_back(2); rec.push_back(3); Solution* sol = new Solution(); sol->recoverRotatedSortedArray(rec); for(vector::iterator it = rec.begin(); it != rec.end(); ++it) { cout << *(it) << endl; } } ```

“经典算法解题实战”实验报告