这里记录了LeetCode初级算法中数组的一些题目:
加一
本来想先转成整数，加1后再转回去；耽美想到测试的例子考虑到了这个方法的笨重，所以int类型超了最大范围65536，导致程序出错。
1class Solution { 2public: 3 vector<int> plusOne(vector<int>& digits) { 4 int m=digits.size(); 5 int old=0; 6 for(int i=0;i<m;i++) 7 { 8 old=old*10+digits[i]; 9 } 10 11 int re=old+1; 12 vector<int> a; 13 while(re!=0) 14 { 15 a.insert(a.begin(),re%10); 16 re=re/10; 17 } 18 19 return a; 20 } 21};
下面完全是从数组的角度进行的思考:分析了各种情况综合得出代码:
1class Solution { 2public: 3 vector<int> plusOne(vector<int>& digits) { 4 int m=digits.size(); 5 if(m==1&&digits[0]==0) {digits[0]+=1;return digits;} 6 for(int i=m-1;i>=0;i--) 7 { 8 if(digits[i]==9) digits[i]=0; 9 else {digits[i]+=1;return digits;} 10 } 11 12 if(digits.front()==0) digits.insert(digits.begin(),1); 13 return digits; 14 } 15};
此外还有一种解法: 这种方法就很机智的将进位carry这个思路加了进来，如果carry=0的话就说明暂时没有进位，可以直接返回；如果有进位的话继续操作。最后在循环结束后，如果还有进位，说明要加1，用和前一个解法的insert就可以了。
1class Solution { 2public: 3 vector<int> plusOne(vector<int>& digits) { 4 if (digits.empty()) return digits; 5 int carry = 1, n = digits.size(); 6 for (int i = n - 1; i >= 0; --i) { 7 if (carry == 0) return digits; 8 int sum = digits[i] + carry; 9 digits[i] = sum % 10; 10 carry = sum / 10; 11 } 12 if (carry == 1) digits.insert(digits.begin(), 1); 13 return digits; 14 } 15};
从排序数组中删除重复项
下面是我最初始的想法，通过循环，遍历的这一项等于前一项的话，就通过迭代器iterator it将这一项清除掉，如果不相等就将count加1；这样觉得很完美，但是实际上每次将这一项清除掉的时候，vector的总长度就发生变化了，所以会导致出错！！！下面是错误代码:
1class Solution { 2public: 3 int removeDuplicates(vector<int>& nums) { 4 int count=1; 5 if(nums.size()==0) return 0; 6 if(nums.size()==1) return 1; 7 for(int i=1;i<nums.size();i++) 8 { 9 if(nums[i]==nums[i-1]) 10 { 11 std::vector<int>::iterator it=nums.begin()+i-1; 12 nums.erase(it); 13 } 14 else count++; 15 } 16 17 return count; 18 } 19};
更换思路，发现题目中有这样的一句话:不需要理会新的数组长度后面的元素；这叫告诉我们，可以把不需要的元素弄到后面去或者将我们需要的元素弄到前面来，所以有了下面的解法:
1class Solution { 2public: 3 int removeDuplicates(vector<int>& nums) { 4 int m=nums.size(); 5 if(m==0) return 0; 6 if(m==1) return 1; 7 int count=0; 8 for(int i=1;i<m;i++) 9 { 10 if(nums[i]!=nums[count]) 11 nums[++count]=nums[i]; 12 } 13 return count+1; 14 } 15};
只出现一次的数字
1#include <algorithm> 2using namespace std; 3class Solution { 4public: 5 int singleNumber(vector<int>& nums) { 6 if(nums.size()==0) return 0; 7 if(nums.size()==1) return nums[0]; 8 int m=nums.size(); 9 sort(nums.begin(),nums.end()); 10 for(int i=1;i<nums.size();i=i+2) 11 { 12 if(nums[i]!=nums[i-1]) return nums[i-1]; 13 } 14 return nums[m-1]; 15 16 } 17// private: 18// bool compare(int a,int b) 19// { 20// return a<b; 21// } 22 23};
移动零
典型的双指针的应用！！
1class Solution { 2public: 3 void moveZeroes(vector<int>& nums) { 4 int fast=0,slow=0; 5 int m=nums.size(); 6 while(fast<m) 7 { 8 if(nums[fast]!=0) 9 { 10 nums[slow]=nums[fast]; 11 slow++; 12 } 13 fast++; 14 } 15 16 for(int i=slow;i<m;i++) 17 nums[i]=0; 18 } 19};
两个数组的交集
首先就想到两个for循环，然后在新创建的vector中进行排序、去重，输出即可:
1class Solution { 2public: 3 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { 4 //sort(nums1.begin(),nums1.end()); 5 //sort(nums2.begin(),nums2.end()); 6 7 vector<int> c; 8 if(nums1.size()==0||nums2.size()==0) return c; 9 for(int i=0;i<nums1.size();i++) 10 { 11 for(int j=0;j<nums2.size();j++) 12 { 13 if(nums1[i]==nums2[j]) 14 c.push_back(nums1[i]); 15 } 16 } 17 18 sort(c.begin(), c.end()); 19 vector<int>::iterator iter = unique(c.begin(), c.end()); 20 c.erase(iter, c.end()); 21 return c; 22 } 23}; 24
这里说一下如何对vector进行去重，想到的方法有两个:利用set或者unique()，其中unique()函数是这样的，
1sort (a, a + n); 2vector<int>v (a, a + n); 3vector<int>::iterator it = unique(v.begin(), v.end() ); 4v.erase (it, v.end() );//这里就是把后面藏起来的重复元素删除了
而set则更为简单，设置一个set，再将vector的数据重新传入set中，时间复杂度较小而且较方便。 然后，看了看大神的代码，他直接用了set的取集合交集set_intersection，代码如下:
1class Solution { 2public: 3 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { 4 set<int> s1(nums1.begin(),nums1.end()),s2(nums2.begin(),nums2.end()),res; 5 set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(res,res.begin())); 6 return vector<int>(res.begin(),res.end()); 7 } 8 };
更多关于set的用法可以参看这一篇博客
两个数组的交集2
1class Solution { 2public: 3 vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { 4 vector<int> c; 5 if(nums1.size()==0||nums2.size()==0) return c; 6 sort(nums1.begin(),nums1.end()); 7 sort(nums2.begin(),nums2.end()); 8 int i=0,j=0; 9 while(i<nums1.size()&&j<nums2.size()) 10 { 11 if(nums1[i]==nums2[j]) 12 { 13 c.push_back(nums1[i]); 14 i++;j++; 15 } 16 else if(nums1[i]>nums2[j]) 17 j++; 18 else 19 i++; 20 } 21 return c; 22 } 23};
ValidSudoku
这道题真的挺有意思，但因为不用判断数独是否有解，所以降低了很多难度。基本思路是这样的，针对每一行每一列判断是否有重复的数字，然后在针对每个九宫格进行判断。而判断是否重复的方法挺巧妙的，就是利用数组小表的唯一性。a[nums]初始值为0，出现过一次数字后变为1，nums是由所填数字的下表来决定的，举个例子就会清楚了:假如第一行里有两个7，nums[7】初始值为0，在第一次7的时候nums[7]变为了1，在第二次遇到7的时候由于之前已经变为了7，简单的判断语句就能发现这里实际上出现了问题。下面贴上代码:
1class Solution { 2public: 3 bool isValidSudoku(vector<vector<char>>& board) { 4 int i,j,k,l,map[10]; 5 if(board.size()!=9 || board[0].size()!=9)return false; 6 for(i=0;i<9;i++){ 7 memset(map,0,sizeof(map)); 8 for(j=0;j<9;j++){ 9 if(board[i][j]=='.')continue; 10 if(board[i][j]<'0' || board[i][j]>'9')return false; 11 int num=board[i][j]-'0'; 12 if(map[num])return false; 13 map[num]=1; 14 } 15 } 16 for(j=0;j<9;j++){ 17 memset(map,0,sizeof(map)); 18 for(i=0;i<9;i++){ 19 if(board[i][j]=='.')continue; 20 int num=board[i][j]-'0'; 21 if(map[num])return false; 22 map[num]=1; 23 } 24 } 25 for(i=0;i<9;i+=3){ 26 for(j=0;j<9;j+=3){ 27 memset(map,0,sizeof(map)); 28 for(k=i;k<i+3;k++){ 29 for(l=j;l<j+3;l++){ 30 if(board[k][l]=='.')continue; 31 int num=board[k][l]-'0'; 32 if(map[num])return false; 33 map[num]=1; 34 } 35 } 36 } 37 } 38 return true; 39 } 40};
旋转图像
这道题我感觉比较奇怪，思路比较好像用的是reverse与swap，我看了别人的代码只是先后顺序不同而已，但是自己的代码(注释掉的)却在输入为4_4矩阵时不能执行reverse，而自己在私下测试了reverse确实是可以将4_4矩阵执行reverse操作的，自己的想法是先将行数倒置，然后沿着主对角线进行swap()操作，得到最终结果。而我最终的代码，是先交换在倒置，我认为先后顺序是没有问题的，但是程序却没有执行reverse的操作，就很奇怪。
1class Solution { 2public: 3 void rotate(vector<vector<int>>& matrix) { 4 /* 5 for(int i=0;i<matrix.size();i++) 6 reverse(matrix.begin(),matrix.end()); 7 8 for(int i=0;i<matrix[0].size();i++) 9 { 10 for(int j=i+1;j<matrix.size();j++) 11 { 12 swap(matrix[i][j],matrix[j][i]) ; 13 } 14 }*/ 15 16 int n = matrix.size(); 17 for (int i = 0; i < n; ++i) { 18 for (int j = i + 1; j < n; ++j) { 19 swap(matrix[i][j], matrix[j][i]); 20 } 21 reverse(matrix[i].begin(), matrix[i].end()); 22 } 23 } 24};
买卖股票的最佳时机2
股票衡量是否为利润是基于前一天的价格和今天的价格来比较的，知道这个就好做了。
1class Solution { 2public: 3 int maxProfit(vector<int>& prices) { 4 int l = prices.size(); 5 if(l <= 0) { 6 return 0; 7 } 8 9 int max = 0; 10 for(int i=1; i<l; i++) { 11 if(prices[i] - prices[i-1] > 0) { 12 max += (prices[i] - prices[i-1]); 13 } 14 } 15 return max; 16 } 17 18};