首页 > 代码库 > 做几个leetcode数组题二

做几个leetcode数组题二

1.Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.


解析: 要求时间复杂度 O(n),循环需要n,所以必须在常数时间内查找出某个特定的值--〉哈希表(散列表)


class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, bool> helparray;     //散列表STL
        for (auto i : num) helparray[i] = false;  //这里用了auto , auto i : vector是把容器内从第一个开始的值依次赋值给i
        int longest = 0;
        for(auto i : num)
        {
            if (helparray[i]) continue;           //如果查过了用true,未查到用false
           
            int length = 1;
            helparray[i] = true;
            for (int j = i + 1; helparray.find(j) != helparray.end(); ++j)   //查比i大的
                {
                    helparray[j] = true;
                    length++;
                }
            for (int j = i - 1; helparray.find(j) != helparray.end(); --j)  //查比i小的
            {
                helparray[j] = true;
                length++;
            }
           
            longest = max(longest,length);                     //总是维护longest为目前最大值
           
        }
        return longest;
       
    }
};

2.

3Sum

 Total Accepted: 29031 Total Submissions: 173719My Submissions

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

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.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)


解:
一开始自己试的,把所有满足的都放到了一个vector里
#include<iostream>
#include<vector>
using namespace std;
vector<int> threeSum(vector<int> &num) {
        vector<int>::iterator r1;
        vector<int>::iterator r2;
		const int target = 0;
        vector<int> result;
        for (r1 = num.begin(); r1 != num.end(); ++r1)
    	{
    		int a = *r1;
    		for (r2 = r1 + 1; r2 != num.end(); ++r2)
    			{
		        	int b = *r2;
		        	int c = target - a - b;  //找第三个数时可以用二分法等来缩短时间复杂度,前两个是就这样了,n^2,第三个可logn 
,后来查的,注意find不是成员函数,是STL算法,返回位置,二分法是binary_find(起位置,终位置,要查找的值);也是算法,但返回是bool
		        	vector<int>::const_iterator r3 = find(r2 + 1, num.end(), c);
		        	if (r3 != num.end())
		        	{
						result.push_back(a);
		        		cout << " a: " << a;
		        		result.push_back(b);
		        		cout << " b: " << b;
		        		result.push_back(c);
		        		cout << " c: " << c;
		        		cout << endl;
        			}		
		        }
        }
        return result;
 }
int main()
{ 	
	vector<int> a;
	a.push_back(1);	
	a.push_back(-4);	
	a.push_back(0);	
	a.push_back(4);	
	a.push_back(-1);	
	a.push_back(5);	
	a.push_back(5);	
	vector<int> resultr;
	vector<int>::iterator rp;	
	resultr = threeSum(a);
	for (rp = resultr.begin(); rp != resultr.end(); ++rp)
	 cout << " " << *rp;
    cout << endl;
	
}
由此算法改成vector数组存放到vector,提交结果是Output Limit Exceeded
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<int>::iterator r1;
        vector<int>::iterator r2;
		const int target = 0;
		vector<vector<int>> result;
        for (r1 = num.begin(); r1 != num.end(); ++r1)
    	{
    		int a = *r1;
    		for (r2 = r1 + 1; r2 != num.end(); ++r2)
    			{
		        	int b = *r2;
		        	int c = target - a - b; 
		        	 
		        	if (binary_search(r2 + 1, num.end(), c))
		        	{
		        		result.push_back(vector<int> {a,b,c});
        			}		
		        }
        }
        return result;
   
    }
};
后来发现没考虑数组元素少于3的情况,和用二分法之前需要对其进行排序,更正后还是Output Limit Exceeded,后又查到for循环的判断条件1:-2; 2: -1 ;,后来找到原因,是我的算法不能排除重复的三个数,比如0,0,0,0,会出现好多组{0,0,0},而题目要求不能,后来想到第二个for中加个一个if(r2 == prev(r2)) continue;这样首先r2第一个元素时不行,另外对r1的考虑也不健全(如 -1,-1,-1,2还是会有重复),后来还是采用答案中那种,把++r1换成了r1 = upper_bound(r1,prev(num.end(),2),*r1),++r2换成r2 = upper_bound(r2,prev(num.end()),*r2)后就AC了。既然找到问题所在,那么我那个思路也是应该可行的,只是注意对特殊边界的处理,这里是第一个,所以改成这个版本后就AC了哈哈(一开始没AC是马虎了,r2写r1)。(注意这种排除重复的满足条件的三个数的前提是排好序了)
 vector<vector<int>> threeSum(vector<int> &num) {

        vector<int>::iterator r1;
        vector<int>::iterator r2;
		const int target = 0;
		vector<vector<int>> result;
		if (num.size() < 3) return result;
		sort(num.begin(),num.end());
        for (r1 = num.begin(); r1 < prev(num.end(), 2); ++r1)
    	{
    	    if (r1 > num.begin()&&(*r1 == *prev(r1))) continue;
  //这里注意顺序,先保证不是第一个,再进行prev,原本用了两个连if,觉得太不规范了, 但是Run Time 却从288到了328ms,难道 if (r1 > num.begin()) if((*r1 == *prev(r1))) continue;比 &&快?
    		int a = *r1;
    		for (r2 = r1 + 1; r2 < prev(num.end(), 1); ++r2)
    			{
    			    if (r2 > r1 + 1 && (*r2 == *prev(r2))) continue;
		        	int b = *r2;
		        	int c = target - a - b; 
		        	 
		        	if (binary_search(r2 + 1, num.end(), c))
		        	{
		        		result.push_back(vector<int> {a,b,c});
        			}		
		        }
        }
        return result;
        }

3.

3Sum Closest

 Total Accepted: 21058 Total Submissions: 78146My Submissions

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. You may assume that each input would have exactly one solution.

    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).
分析: 与上题的不同,上题是等于,这题是接近,看似还是两个循环,再第三个再用循环把最近的找出来就行,可是这样时间复杂度n^3
再分析,与上个题不同的是,上个提相当于1+1+1 三个部分,这个题相当于1+ 2两个部分,把后两个数的和看成一个整体
这样思路就出来了,先排序,然后选一个数,剩下两个左右夹逼(因已经排好序,比要求大就后面的前移,小就前面的后移)时间复杂度n^2,空间复杂度O(1)(是不是对空间来说,没开辟新的数组在存原数组就是1哈哈)(补:算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n)
int threeSumClosest(vector<int> &num, int target) {
        int result = 0;
        int min_gap = INT_MAX;
        sort(num.begin(),num.end());
        
        for(auto a = num.begin(); a != prev(num.end(),2); a = upper_bound(a,prev(num.end(),2),*a))
        {
            auto b = next(a);
            auto c = prev(num.end());
            
            while (b < c)
            {
                int sum = *a + *b + *c;
                int gap = abs(sum - target);
                if (gap < min_gap)
                {
                    result = sum;
                    min_gap = gap;
                }
                if (sum < target) ++b;
                else --c;
            }
        }
        return result;
    }
该算法的改进就是在 if (sum < target) ++b;
                else --c;
处,处理掉对重复元素的检测, 改为b = upper_bound(b,c,*b); c= prev(lower_bound(b,c,*c)); 这样处理后算法,只有常数级别的优化

4.

4Sum

 Total Accepted: 18939 Total Submissions: 88978My Submissions

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

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.
    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)

解: 初始的方法,三个for循环,找第四个数,即使用二分法,也需要n^3*log(n),超时

参考答案后AC的,思路是先缓存两个数的和到集合中,这样空间增大来缩短时间
class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
  //注意两个> >之间有个空格,否则成了>>右移了
        if (num.size() < 4) return vector<vector<int> >();
 //依然考虑少于4的情况

        sort(num.begin(),num.end());
       // 排序
        map<int ,vector<pair<int,int> > > cache; // int 对应一个 vector ,vector里放的几个pair<int ,int>
        for (int a = 0; a < num.size(); ++a) 
            for (int b = a + 1; b < num.size(); ++b)
                 cache[num[a] + num[b]].push_back(pair<int,int>(a,b));
 //把和当做key,对应其两个值,
            //注意这里,和为某个值可能有好多对,而map是一对一,这里的push_back可不是map的操作,而是一个和值,对应一个vector,vector的push_back操作,另外vector里存的是元素是pair,每个pair有两个数。同理下面那个cache[key]的size也是vector
                 
        set<vector<int> > result;
         //set本身有去重效果,其当内有重复key时,自动忽略后来的
        for (int c = 2; c < num.size(); ++c)
            //这种int c,也有用的size_t c ;来定义
            for (int  d = c + 1; d < num.size(); ++d)
      //size_t 类型定义在cstddef头文件中,                             
                {
                                            //该文件是C标准库的头文件stddef.h的C++版。它是一个与机器相关
                    int key = target - num[c] - num[d];
        //的unsigned类型,其大小足以保证存储内存中对象的大小。
                    if (cache.find(key) != cache.end())
         //在想用这个,是不是怕数组大小大出int表示范围。
                    {
                        for (int k = 0; k < cache[key].size(); ++k)
  //一个和可能有多个对
                        {
                            if (c <= cache[key][k].second) continue;
   //这里是防止重复查找,两个数依次向前,查两个数的和可以查
                            result.insert(vector<int> {num[cache[key][k].first],
 //其后面的,也可以其前面的,但是不用都查,比如
                                       num[cache[key][k].second],num[c],num[d]});
//一直查,前面的,后面的随cd增大也会查到
                        }
                    }
                }
        return vector<vector<int> >(result.begin(),result.end());
    }
};     


做几个leetcode数组题二