[关闭]
@tankle 2015-05-22T02:29:20.000000Z 字数 12193 阅读 3133

LintCode 阶梯训练之 Integer Array

LintCode

Remove Element

39% Accepted
Given an array and a value, remove all occurrences of that value in place and return the new length.

The order of elements can be changed, and the elements after the new length don't matter.

Example
Given an array [0,4,4,0,0,2,4,4], value=4

return 4 and front four elements of the array is [0,0,0,2]

  1. class Solution {
  2. public:
  3.     /** 
  4.      *@param A: A list of integers
  5.      *@param elem: An integer
  6.      *@return: The new length after remove
  7.      */
  8.     int removeElement(vector<int> &A, int elem) {
  9.         int result = 0;
  10.         int i=0;
  11.         while(i < A.size()){
  12.             if(A[i] == elem)
  13.                 A.erase(A.begin()+i);
  14.             else{
  15.                 i++;
  16.                 result++;
  17.             }
  18.         }
  19.         return result;
  20.     }
  21. };

Subarray Sum

18% Accepted
Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Example
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Note
There is at least one subarray that it's sum equals to zero.

  1. //O(n^2)解法
  2. class Solution {
  3. public:
  4.     /**
  5.      * @param nums: A list of integers
  6.      * @return: A list of integers includes the index of the first number 
  7.      *          and the index of the last number
  8.      */
  9.     vector<int> subarraySum(vector<int> nums){
  10.         // write your code here
  11.         vector<int> result;
  12.         for(int i=0; i<nums.size(); ++i){
  13.             int sum = nums[i];
  14.             if(sum == 0){
  15.                 result.push_back(i);
  16.                 result.push_back(i);
  17.                 break;
  18.             }
  19.             for(int j=i+1; j<nums.size(); ++j){
  20.                 sum += nums[j];
  21.                 if(sum == 0){
  22.                     result.push_back(i);
  23.                     result.push_back(j);
  24.                     return result;
  25.                 }
  26.             }
  27.         }
  28.         return result;
  29.     }
  30. };
  32. //O(nlogn)解法
  33. class Solution {
  34. public:
  35.     /**
  36.      * @param nums: A list of integers
  37.      * @return: A list of integers includes the index of the first number 
  38.      *          and the index of the last number
  39.      */
  40.     vector<int> subarraySum(vector<int> nums){
  41.         vector<int> result;
  42.         if(nums.empty())
  43.             return result;
  44.         vector<pair<int,int>> sum(nums.size()+1,make_pair(0,0));
  45.         for(int i=0; i<nums.size(); i++){
  46.             sum[i+1].first =  sum[i].first + nums[i];
  47.             sum[i+1].second = i + 1;
  48.         }
  50.         sort(sum.begin(), sum.end());
  52.         for(int i=1; i<sum.size(); i++){
  53.             if(sum[i].first == sum[i-1].first){
  54.                 //需要注意这里的下标，因为上面是从1开始的
  55.                 result.push_back(sum[i-1].second );
  56.                 result.push_back(sum[i].second -1);
  57.                 return result;
  58.             }
  59.         }
  60.         return result;
  61.     }
  62. };

Remove Duplicates from Sorted Array

33% Accepted
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

Example
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: a list of integers
  5.      * @return : return an integer
  6.      */
  7.     int removeDuplicates(vector<int> &nums) {
  8.         // write your code here
  9.         int i=1;
  10.         while(i<nums.size()){
  11.             if(nums[i] != nums[i-1])
  12.                 ++i;
  13.             else
  14.                 nums.erase(nums.begin()+i);
  15.         }
  16.         return nums.size();
  17.     }
  18. };

Merge Sorted Array

41% Accepted
Given two sorted integer arrays A and B, merge B into A as one sorted array.

Example
A = [1, 2, 3, empty, empty], B = [4, 5]

After merge, A will be filled as [1, 2, 3, 4, 5]

Note
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: sorted integer array A which has m elements, 
  5.      *           but size of A is m+n
  6.      * @param B: sorted integer array B which has n elements
  7.      * @return: void
  8.      */
  9.     void mergeSortedArray(int A[], int m, int B[], int n) {
  10.         // write your code here
  11.         int i=m-1, j=n-1;
  12.         int k=m+n-1;
  13.         while(k >= 0){
  14.             if(A[i] >= B[j]){
  15.                 A[k] = A[i];
  16.                 i--;
  17.             }else{
  18.                 A[k] = B[j];
  19.                 j--;
  20.             }
  21.             k--;
  22.         }
  23.     }
  24. };

Product of Array Exclude Itself

25% Accepted
Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.

Example
For A=[1, 2, 3], return [6, 3, 2].

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: Given an integers array A
  5.      * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
  6.      */
  7.     vector<long long> productExcludeItself(vector<int> &nums) {
  8.         // write your code here
  9.         int m = nums.size();
  10.         vector<long long> left(m);
  11.         vector<long long> right(m);
  12.         long long tmp = 1;
  13.         for(int i=0; i< m; ++i){
  14.             left[i] = tmp;
  15.             tmp *= nums[i];
  16.         }
  17.         tmp = 1;
  18.         for(int i = m-1; i >= 0; i--){
  19.             right[i] = tmp;
  20.             tmp *= nums[i];
  21.         }
  22.         vector<long long> result(m);
  23.         for(int i=0; i< m; ++i){
  24.             result[i] = left[i] * right[i];
  25.         }
  26.         return result;
  27.     }
  28. };

First Missing Positive

23% Accepted
Given an unsorted integer array, find the first missing positive integer.

Example
Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Challenge
Your algorithm should run in O(n) time and uses constant space.

  1. class Solution {
  2. public:
  3.     /**    
  4.      * @param A: a vector of integers
  5.      * @return: an integer
  6.      */
  7.     int firstMissingPositive(vector<int> A) {
  8.         // write your code here
  9.         //利用数组的下标作为hash，每个对应的下标对应相应的值
  10.         //然后循环，找到最小的那个值和下标不对应的地方即为答案
  11.         int m = A.size();
  12.         int i = 0;
  13.         while(i < m){
  14.             if(A[i] > 0 && A[i] <= m && A[i] != i+1 && A[i] != A[A[i]-1])
  15.                     swap(A[i], A[A[i]-1]);
  16.             else
  17.                 i++;
  18.         }
  19.         for(i=0; i<m; i++){
  20.             if(A[i] != i+1)
  21.                 return i+1;
  22.         }
  23.         return m+1;
  24.     }
  25. };

2 Sum

26% Accepted
Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

Example
numbers=[2, 7, 11, 15], target=9

return [1, 2]

Note
You may assume that each input would have exactly one solution

Challenge
Either of the following solutions are acceptable:

O(1) Space, O(nlogn) Time
O(n) Space, O(n) Time

  1. class Solution {
  2. public:
  3.     /*
  4.      * @param numbers : An array of Integer
  5.      * @param target : target = numbers[index1] + numbers[index2]
  6.      * @return : [index1+1, index2+1] (index1 < index2)
  7.      */
  8.     vector<int> twoSum(vector<int> &nums, int target) {
  9.         // write your code here
  10.         unordered_map<int ,int> res;
  11.         vector<int> idx;
  12.         for(int i=0; i<nums.size(); ++i){
  13.             int left = target - nums[i];
  14.             if(res.find(left) == res.end()){
  15.                 res[nums[i]] = i;
  16.             }
  17.             else{
  18.                 idx.push_back(res[left]+1);
  19.                 idx.push_back(i+1);
  20.                 break;
  21.             }
  22.         }
  23.         return idx;
  24.     }
  25. };

3 Sum

18% Accepted
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Example
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)
Note
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

  1. class Solution {
  2. public:    
  3.     void twoSum(vector<int> &nums,int begin, int target, vector<vector<int>>& result) {
  4.         //使用set集合来添加元素，因为target是固定的，这样就不会有重复的结果
  5.         //使用双指针，前后夹逼
  6.         int start = begin;
  7.         int end = nums.size()-1;
  8.         set<pair<int,int>> two;
  9.         while (start < end){
  10.             if(nums[start] + nums[end] == target){
  11. //                result.push_back({target, nums[start], nums[end]});
  12.                 two.insert(make_pair(nums[start], nums[end]));
  13.                 start++;
  14.                 end--;
  15.             }
  16.             else if(nums[start] + nums[end] > target)
  17.                 end--;
  18.             else
  19.                 start++;
  20.         }
  21.         //这里注意target 需要变换一下
  22.         for(auto it = two.begin(); it != two.end(); ++it){
  23.             result.push_back({0 - target, (*it).first, (*it).second});
  24.         }
  25.     }
  27.     //首先对结果进行排序，对于重复的target只需要计算一次，避免重复
  28.     vector<vector<int> > threeSum(vector<int> &nums) {
  29.         // write your code here
  30.         sort(nums.begin(), nums.end());
  31.         vector<vector<int>> res;
  32.         int m = nums.size();
  33.         for(int i=0; i<m; ++i){
  34.             if(i > 0 && nums[i] == nums[i-1]) continue;
  35.             int target = 0 - nums[i];
  36.             twoSum(nums, i+1, target, res);
  37.         }
  38.         return res;
  39.     }
  40. };

3 Sum Closest

30% Accepted
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.

Example
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Note
You may assume that each input would have exactly one solution.

Challenge
O(n^2) time, O(1) extra space

  1. class Solution {
  2. public:    
  3.      /**
  4.      * 找到与target最接近的两个数之和
  5.      * @param numbers : Give an array numbers of n integer
  6.      * @return : Find all unique triplets in the array which gives the sum of zero.
  7.      */
  8.     int twoSum(vector<int> &nums,int begin, int target) {
  9.         int result = 0;
  10.         int start = begin;
  11.         int end = nums.size()-1;
  12.         int min_gap = INT_MAX;
  13.         while (start < end){
  14.             int gap = abs(nums[start] + nums[end] - target);
  15.             if(gap < min_gap){
  16.                 result = nums[start] + nums[end];
  17.                 min_gap = gap;
  18.             }
  19.             if(nums[start] + nums[end] - target > 0)
  20.                 end--;
  21.             else
  22.                 start++;
  23.         }
  24.         return result;
  25.     }
  27.     /**
  28.      * @param numbers: Give an array numbers of n integer
  29.      * @param target: An integer
  30.      * @return: return the sum of the three integers, the sum closest target.
  31.      */
  32.     int threeSumClosest(vector<int> nums, int target) {
  33.         // write your code here
  34.         //先排序
  35.         sort(nums.begin(), nums.end());
  36.         int m = nums.size();
  37.         int min_gap = INT_MAX;
  38.         int result;
  39.         //记录最小间隔
  40.         for(int i=0; i<m-2; ++i){
  41.             int tmp = target - nums[i];
  42.             int res = twoSum(nums, i+1, tmp);
  43.             if(abs(tmp - res) < min_gap){
  44.                 min_gap = abs(tmp - res);
  45.                 result = res + nums[i];
  46.             }
  47.         }
  48.         return result;
  49.     }
  50. };

4 Sum

18% Accepted
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Example
For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is:

(-1, 0, 0, 1)

(-2, -1, 1, 2)

(-2, 0, 0, 2)

Note
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)

The solution set must not contain duplicate quadruplets.

  1. class Solution {
  2. public:
  3.     void twoSum(vector<int> &nums,int begin, int target, vector<vector<int>>& result) {
  4.         int start = begin;
  5.         int end = nums.size()-1;
  6.         set<pair<int,int>> two;
  7.         while (start < end){
  8.             if(nums[start] + nums[end] == target){
  9. //                result.push_back({target, nums[start], nums[end]});
  10.                 two.insert(make_pair(nums[start], nums[end]));
  11.                 start++;
  12.                 end--;
  13.             }
  14.             else if(nums[start] + nums[end] > target)
  15.                 end--;
  16.             else
  17.                 start++;
  18.         }
  19.         //因为是从begin后开始循环的
  20.         for(auto it = two.begin(); it != two.end(); ++it){
  21.             result.push_back({nums[begin-1], (*it).first, (*it).second});
  22.         }
  23.     }
  25.     vector<vector<int> > threeSum(vector<int> &nums, int begin, int target) {
  26.         // write your code here
  27.         vector<vector<int>> res;
  28.         int m = nums.size();
  29.         for(int i=begin; i<m; ++i){
  30.             if(i > begin && nums[i] == nums[i-1]) continue;
  31.             int tmp = target - nums[i];
  32.             twoSum(nums, i+1, tmp, res);
  33.         }
  34.         return res;
  35.     }
  36.     //调用3Sum程序
  37.     vector<vector<int> > fourSum(vector<int> &nums, int target) {
  38.         // write your code here
  39.         int m = nums.size();
  40.         sort(nums.begin(), nums.end());
  41.         vector<vector<int>> result;
  42.         for(int i=0; i<m-3; i++){
  43.             //避免重复
  44.             if(i > 0 && nums[i] == nums[i-1]) continue;
  45.             int targ = target - nums[i];
  46.             vector<vector<int>> res = threeSum(nums, i+1, targ);
  47.             for(int j=0; j<res.size(); j++){
  48.                 res[j].insert(res[j].begin(), nums[i]);
  49.                 result.push_back(res[j]);
  50.             }
  51.         }
  52.         return result;
  53.     }
  54. };

Partition Array

24% Accepted
Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:

All elements < k are moved to the left
All elements >= k are moved to the right
Return the partitioning index, i.e the first index i nums[i] >= k.

Example
If nums=[3,2,2,1] and k=2, a valid answer is 1.

Note
You should do really partition in array nums instead of just counting the numbers of integers smaller than k.

If all elements in nums are smaller than k, then return nums.length

Challenge
Can you partition the array in-place and in O(n)?

  1. class Solution {
  2. public:
  3.     int partitionArray(vector<int> &nums, int k) {
  4.     // write your code here
  5.         if(nums.size() == 0)
  6.             return 0;
  7.         int start = 0;
  8.         int end = nums.size()-1;
  9.         while(start < end) {
  10.             //寻找左边
  11.             while(start < nums.size() && nums[start] < k)
  12.                 start++;
  13.             while(end >=0 && nums[end] >= k)
  14.                 end--;
  15.             //退出条件
  16.             if(start >= end) break;
  17.             else {
  18.                 int tmp = nums[start];
  19.                 nums[start] = nums[end];
  20.                 nums[end] = tmp;
  21.                 start++;
  22.                 end--;
  23.             }
  24.         }
  25.         return start;
  26.     }
  27. };

Remove Duplicates from Sorted Array II

29% Accepted
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

  1. class Solution {
  2. public:
  3.     int removeDuplicates(vector<int>& nums) {
  4.           // write your code here
  5.         if(nums.size() == 0)
  6.             return 0;
  7.         //设置一个重复次数的变量
  8.         int idx = 0;
  9.         int occur = 1;
  10.         for(int i=1; i<nums.size(); i++){
  11.             if(nums[i] == nums[idx]){
  12.                 //两次就继续，不需要添加
  13.                 if(occur == 2)
  14.                     continue;
  15.                 occur++;
  16.             }
  17.             else{
  18.                 occur = 1;
  19.             }
  20.             nums[++idx] = nums[i];
  21.         }
  22.         //需要对数组大小进行变换
  23.         nums.resize(idx+1);
  24.         return nums.size();
  25.     }
  26. };

Merge Sorted Array II

32% Accepted
Merge two given sorted integer array A and B into a new sorted integer array.

Example
A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge
How can you optimize your algorithm if one array is very large and the other is very small?

  1. class Solution {
  2. public:
  3.     /**
  4.     * 对于Challenge问题没有进行优化，思路可以是对大的数组进行二分查找，找到插入的位置
  5.      * @param A and B: sorted integer array A and B.
  6.      * @return: A new sorted integer array
  7.      */
  8.     vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
  9.         // write your code here
  10.         int m = A.size();
  11.         int n = B.size();
  12.         int l = m + n;
  13.         vector<int> C(l);
  14.         int i = 0, j = 0;
  15.         int k = 0;
  16.         while(i < m && j < n){
  17.             if(A[i] <= B[j])
  18.                 C[k++] = A[i++];
  19.             else
  20.                 C[k++] = B[j++];
  21.         }
  22.         while(i<m)
  23.             C[k++] = A[i++];
  24.         while(j<n)
  25.             C[k++] = B[j++];
  26.         return C;
  27.     }
  28. };

Subarray Sum Closest

16% Accepted
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Example
Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4]

Challenge
O(nlogn) time

  1. //考察数组前缀和
  2. class Solution {
  3. public:
  4.     /**
  5.      * @param nums: A list of integers
  6.      * @return: A list of integers includes the index of the first number 
  7.      *          and the index of the last number
  8.      */
  9.     vector<int> subarraySumClosest(vector<int> nums){
  10.         vector<int> result;
  11.         if(nums.empty())
  12.             return result;
  13.         vector<pair<int,int>> sum(nums.size()+1,make_pair(0,0));
  14.         for(int i=0; i<nums.size(); i++){
  15.             sum[i+1].first =  sum[i].first + nums[i];
  16.             sum[i+1].second = i + 1;
  17.         }
  19.         sort(sum.begin(), sum.end());
  21.         int min_gap = INT_MAX;
  22.         int closed_idx = 1;
  23.         for(int i=1; i < sum.size(); i++){
  24.             int gap = sum[i].first - sum[i-1].first;
  25.             if(min_gap > gap){
  26.                 min_gap = gap;
  27.                 closed_idx = i;
  28.             }
  29.         }
  30.         //用来确保左值必须小于右值
  31.         int left = min(sum[closed_idx].second, sum[closed_idx-1].second);
  32.         int right = -1 + max(sum[closed_idx].second, sum[closed_idx-1].second);
  33.         result.push_back(left);
  34.         result.push_back(right);
  35.         return result;
  37.     }
  38. };
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注