Vector类相关OJ题目的理解

系统管理员 2023-01-18 09:29 126阅读 0赞

![在这里插入图片描述][20210506131408260.png]

### Vector类OJ题目 ###

*  目录:
 *   *  一.连续子数组的最大和
     *  二.电话号码的字母组合
     *  三.找出数组中出现次数超过一半的数字
     *  四.删除一个有序数组中的重复项
     *  五.找出只出现一次的元素i
     *  六.找出只出现一次的元素ii
     *  七.找出只出现一次的元素iii
     *  八.杨辉三角

# 目录: #

## 一.连续子数组的最大和 ##

**框架:**

1.因为要求一个数组中的最大数值,我们想将每个数利用sum进行相加起来  
2.然后当sum的值res的时候,就进行交换就行了

class Solution { 
    public:
        int FindGreatestSumOfSubArray(vector<int> array) { 	//定义整型的vector容器
            int res=INT_MIN;	//创建最小的数 
            int sum=0;		//创建sum
            for(int i=0;i<array.size();++i){ 	//在容器内部进行循环
                
                if(sum<0){ 		//当sum小于0的时候,让其等于对应位置的值
                    sum =array[i];
                }else{ 	//大于等于的时候,则继续进行++操作
                    sum+=array[i];
                }
                if(sum>res){ 		//如果sum的值大于res的时候,则进行交换操作
                    res=sum;
                }
            }
            return res;		//最终将最大的值进行输出
        }
    };

## 二.电话号码的字母组合 ##

**框架:**

1.先将对应数字中的字母通过string对象存储起来  
2.读入数据,将对应的string对象进行分布存储

class Solution { 
    public:     
    	//先定义出对应的string对象,将要存储的数据进行存储 
        vector<string> phone = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
        vector<string> letterCombinations(string digits) { 	//输入的数字
            if (digits.size() == 0) return { };	//如果输入的为空,则直接输出
    		vector<string> res;	//定义新的string类对象的容器
            res.push_back("");	//进行尾插
            for(char digit : digits) 	//进行范围for循环呢
            { 
                vector<string> tmp;		//内部定义对应的string类容器
                for(string s : res)     //范围for循环
                    for(char candidate : phone[digit - '0'])   	//范围for循环上面定义的string对象中的数据
                        tmp.push_back(s + candidate);	//进行尾插数据
                res.swap(tmp);  //将定义的tmp中的数据进行交换
            }
            return res;		//将交换后的值进行输出
        }
    };

## 三.找出数组中出现次数超过一半的数字 ##

**框架:**

1.先将输入的数据利用计数器进行计数  
2.如果对应的数据>size(),则证明存在,直接输出,不存在则返回0

class Solution { 
    public:
        int MoreThanHalfNum_Solution(vector<int> numbers) { 
            
            if(numbers.empty())		//先对其进行判空的操作
                return 0;
                
            sort(numbers.begin(),numbers.end());	//先对输入的数据进行排序操作
            int mid=numbers[numbers.size()/2];		//求出中间的元素
            
            int count=0;		//定义一个count值
            for(int i=0;i<numbers.size();++i){ 	//循环进行遍历,并且对其进行计数操作
                    
                if(numbers[i]==mid) ++count;
            }
            return (count>numbers.size()/2)?mid:0;	//如果最后的count数大于一半的size()则输出对应的值,如果不大于则输出0
        }
    };

## 四.删除一个有序数组中的重复项 ##

**框架:**

1.先进行判空的操作  
2.用前后的两个下标来实现比对的操作,因为是有序的,先将前后比对后  
3.如果不同则插入到新的nums\[idx\]中,这样就实现了删除操作

class Solution { 
    public:
        int removeDuplicates(vector<int>& nums) { 
        
            int n = nums.size();		//先进行判空的操作
            if (n == 0) 
                return 0;  
    
            int idx = 0;	//定义对应的整型
            for (int j = 1; j < n; j ++){ 	//循环内部
            
                if (nums[idx] != nums[j]){ 	//如果不等于下一个数
                    idx ++;					//则对应的idx进行++操作
                    nums[idx] = nums[j];	//将对应的元素赋予到idx中,在idx中赋予的元素时单一种类的,不会出现重复的
                }
            }
            return idx + 1;	//将挑选完成的数据进行输出
        }
    };

**这里也可以通过list类内部的一个unique()接口来实现**,[链接理解][Link 1]

## 五.找出只出现一次的元素i ##

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

**框架:**

1.因为其他元素出现两次的时候,当所有的字符按照二进制来看的时候,都是01来表达的  
2.我们可用异或的操作,直接将重复出现两次的数据进行消掉,比较方便的解决这个题目

class Solution { 
    public:
        int singleNumber(vector<int>& nums) { 
            int ret = 0;			//定义整形
            for (auto e: nums) 		//范围for类似进行循环
             ret ^= e;				//循环内对所有的数据进行异或操作,就会保留下单次出现的数据
            return ret;				//将异或后保留的数据进行返回
        }
    };

## 六.找出只出现一次的元素ii ##

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

**框架:**

1.利用二进制的方式来进行分布的遍历  
2.因为他是三个一样的元素,所以无论如何都会是3的倍数  
3.我们将其取和,%3剩下的余数就是对应第i哥二进制位

class Solution { 
    public:
        int singleNumber(vector<int>& nums) { 
            int res = 0;
            for (int i = 0; i < 32; i++) {  	//先循环相加
                int sum = 0;
                for (int num : nums) { 	//范围for
                    sum += ((num >> i) & 1); 	//相加
                }
                if (sum % 3 == 1) {  		//取余数
                    res |= (1 << i);  //向左偏移
                }
            }
            return res; 		//输出
        }
    };

## 七.找出只出现一次的元素iii ##

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

**框架:**

1.因为有两个数据,所以我们需要定义一个变量来记录数据  
2.在堆所有的数据进行异或的时候,因为有两个的不同,所以在出现1的时候,  
3.就是对应的位数出现差异,然后我们对其进行分类的操作,就可以完成并且输出

class Solution { 
    public:
        vector<int> singleNumber(vector<int>& nums) { 
           
            int temp = 0; //定义整型进行记录
            for (int num : nums) { 	//对所有的进行异或操作
                temp ^= num;
            }
            
            int i;
            for (i = 0; i < 32; i++) { 		//对每一位的数据进行挨个的与操作,来辨别出哪一位的数据不为1
                if (temp >> i & 1 == 1) break;
            }
           
            int num1 = 0, num2 = 0;
            for (int num : nums) { 	//范围for进行数据写入
                if (num >> i & 1 == 1) num1 ^= num;		//在出现等于1的时候,对num1进行异或操作
                else num2 ^= num;		//否则则对num2进行异或操作
            }
            return { num1, num2};		//返回值
        }
    };

## 八.杨辉三角 ##

**框架:**

1.首先我们要利用vector来实现杨辉三角的话我们就要像数组一样的进行二维包含关系  
2.进行二维包含后,我们对两边的值直接赋予1即可  
3.对于中间值的变化,就是上面的数等于左下加右下而已,我们直接循环操作即可

class Solution { 
    public:
        vector<vector<int>> generate(int numRows) { 	//二维包含
            vector<vector<int>> ret(numRows);
            for (int i = 0; i < numRows; ++i) { 		//先进行循环操作
                ret[i].resize(i + 1);				//在每一个新开的行数比上面的大一位
                ret[i][0] = ret[i][i] = 1;			//边角赋予1
                for (int j = 1; j < i; ++j) { 		//在对于中间的进行循环
                    ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];	//上面的数据等于左下加右下
                }
            }
            return ret;		//返回即可实现代码
        }
    };

主要是讲解的敢于vector容器的合理运用,更好的掌握容器的用法.[vector的基本用法回顾][vector]

[20210506131408260.png]: /images/20221021/058fc38cd93947a18cd60c726102966c.png
[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/116125965
[vector]: https://blog.csdn.net/weixin_46554582/article/details/115312220