``` /* product of array exclude itself */ #include #include using namespace std; class Solution { public: vector productExcludeItself(vector &nums) { int length = nums.size(); vector res; vector preProduct; vector sucProduct; long long product = 1; for(int i = 0; i < length; ++i) { preProduct.push_back(product); product *= nums[i]; } product = 1; for(int i = length - 1; i >= 0; --i) { sucProduct.insert(sucProduct.begin(), product); product *= nums[i]; } for(int i = 0; i < length; ++i) { res.push_back(preProduct[i] * sucProduct[i]); } return res; } }; int main() { int arr[3] = {1,2,3}; vector vec(arr, arr+3); Solution* sol = new Solution(); vector res = sol->productExcludeItself(vec); for(int i = 0; i < (int)res.size(); ++i) { cout << res[i] << endl; } } /* partition array */ #include #include using namespace std; class Solution { public: int partitionArray(vector &nums, int k) { int length = nums.size(); if(length == 0) return 0; int i = 0, j = length - 1; while(i < j) { if(nums[i] >= k && nums[j] < k) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } else if(nums[i] >= k && nums[j] >= k) { j--; continue; } else if(nums[i] < k && nums[j] < k) { i++; continue; } i++; j--; } if(nums[i] >= k) { return i; } else { return i + 1; } } }; int main() { int nums[4] = {3,2,2,1}; vector vec(nums, nums+4); Solution* sol = new Solution(); cout << sol->partitionArray(vec, 2) << endl; } /* first missing positive */ #include #include #include using namespace std; class Solution { public: int firstMissingPositive(vector &A) { int length = A.size(); int i = 0; while(i < length) { if(A[i] != (i+1) && A[i] >= 1 && A[i] <= length && A[A[i]-1] != A[i]) swap(A[i], A[A[i]-1]); else i++; } for(i = 0; i < length; i++) if(A[i] != (i+1)) return i+1; return length + 1; } }; int main() { int arr[3] = {1,2,0}; vector rec(arr, arr+3); Solution* sol = new Solution(); cout << sol->firstMissingPositive(rec) << endl; } /* 2 sum */ #include #include #include using namespace std; class Solution { public: vector twoSum(vector &numbers, int target) { vector res; int length = numbers.size(); if(length == 0) return res; map table; for(int i = 0; i < length; i++) { if(table.find(target - numbers[i]) == table.end()) { table[numbers[i]] = i; } else { res.push_back(table[target - numbers[i]]); res.push_back(i); return res; } } return res; } }; int main() { int arr[4] = {2,7,11,15}; vector rec(arr, arr+4); Solution* sol = new Solution(); vector res = sol->twoSum(rec, 9); cout << res[0] << res[1] << endl; } /* 3 sum */ #include #include #include using namespace std; class Solution { public: vector > threeSum(vector &numbers) { sort(numbers.begin(), numbers.end()); vector > res; int length = numbers.size(); for(int i = 0; i < length; i++) { if(i > 0 && numbers[i] == numbers[i-1]) continue; int j = i+1, k = length - 1; while(j < k) { if(numbers[i] + numbers[j] + numbers[k] < 0) { j++; } else if(numbers[i] + numbers[j] + numbers[k] > 0) { k--; } else { int temp[3] = {numbers[i], numbers[j], numbers[k]}; res.push_back(vector(temp, temp+3)); j++; k--; while(j < k && numbers[j] == numbers[j-1]) j++; while(j < k && numbers[k] == numbers[k+1]) k--; } } } return res; } }; int main() { int arr[10] = {1,0,-1,-1,-1,-1,0,1,1,1}; vector vec(arr, arr+10); Solution* sol = new Solution(); vector > res = sol->threeSum(vec); for(int i = 0; i < (int)res.size(); ++i) { for(int j = 0; j < 3; ++j) { cout << res[i][j] << " "; } cout << endl; } } /* 3 sum closest */ #include #include #include #include using namespace std; class Solution { public: int threeSumClosest(vector &numbers, int target) { int length = numbers.size(); sort(numbers.begin(), numbers.end()); int result = 0x7fffffff; int res = numbers[0] + numbers[1] + numbers[2]; for(int i = 0; i < length; ++i) { if(i > 0 && numbers[i] == numbers[i-1]) continue; int j = i + 1, k = length - 1; while(j < k) { if(numbers[i] + numbers[j] + numbers[k] == target) { return target; } else if (numbers[i] + numbers[j] + numbers[k] < target) { if(abs(numbers[i] + numbers[j] + numbers[k] - target) < result) { result = abs(numbers[i] + numbers[j] + numbers[k] - target); res = numbers[i] + numbers[j] + numbers[k]; } j++; } else if (numbers[i] + numbers[j] + numbers[k] > target) { if(abs(numbers[i] + numbers[j] + numbers[k] - target) < result) { result = abs(numbers[i] + numbers[j] + numbers[k] - target); res = numbers[i] + numbers[j] + numbers[k]; } k--; } } } return res; } }; ```

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