最近開始認(rèn)真刷題了鸟缕，反正做了些題目就記錄一些吧鸭限，這里記錄了LeetCode初級算法中數(shù)組的一些題目:
加一
本來想先轉(zhuǎn)成整數(shù)，加1后再轉(zhuǎn)回去析桥；耽美想到測試的例子考慮到了這個方法的笨重司草，所以int類型超了最大范圍65536，導(dǎo)致程序出錯泡仗。
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int m=digits.size();
int old=0;
for(int i=0;i<m;i++)
{
old=old*10+digits[i];
}
int re=old+1;
vector<int> a;
while(re!=0)
{
a.insert(a.begin(),re%10);
re=re/10;
}
return a;
}
};
下面完全是從數(shù)組的角度進(jìn)行的思考:分析了各種情況綜合得出代碼:
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int m=digits.size();
if(m==1&&digits[0]==0) {digits[0]+=1;return digits;}
for(int i=m-1;i>=0;i--)
{
if(digits[i]==9) digits[i]=0;
else {digits[i]+=1;return digits;}
}
if(digits.front()==0) digits.insert(digits.begin(),1);
return digits;
}
};
此外還有一種解法:
這種方法就很機(jī)智的將進(jìn)位carry這個思路加了進(jìn)來埋虹，如果carry=0的話就說明暫時沒有進(jìn)位，可以直接返回沮焕；如果有進(jìn)位的話繼續(xù)操作吨岭。最后在循環(huán)結(jié)束后，如果還有進(jìn)位峦树，說明要加1辣辫，用和前一個解法的insert就可以了。
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
if (digits.empty()) return digits;
int carry = 1, n = digits.size();
for (int i = n - 1; i >= 0; --i) {
if (carry == 0) return digits;
int sum = digits[i] + carry;
digits[i] = sum % 10;
carry = sum / 10;
}
if (carry == 1) digits.insert(digits.begin(), 1);
return digits;
}
};
從排序數(shù)組中刪除重復(fù)項
下面是我最初始的想法魁巩，通過循環(huán)急灭，遍歷的這一項等于前一項的話，就通過迭代器iterator it將這一項清除掉谷遂，如果不相等就將count加1葬馋；這樣覺得很完美，但是實際上每次將這一項清除掉的時候，vector的總長度就發(fā)生變化了畴嘶，所以會導(dǎo)致出錯５坝狻！窗悯！下面是錯誤代碼:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int count=1;
if(nums.size()==0) return 0;
if(nums.size()==1) return 1;
for(int i=1;i<nums.size();i++)
{
if(nums[i]==nums[i-1])
{
std::vector<int>::iterator it=nums.begin()+i-1;
nums.erase(it);
}
else count++;
}
return count;
}
};
更換思路区匣，發(fā)現(xiàn)題目中有這樣的一句話:不需要理會新的數(shù)組長度后面的元素；這叫告訴我們蒋院，可以把不需要的元素弄到后面去或者將我們需要的元素弄到前面來亏钩，所以有了下面的解法:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int m=nums.size();
if(m==0) return 0;
if(m==1) return 1;
int count=0;
for(int i=1;i<m;i++)
{
if(nums[i]!=nums[count])
nums[++count]=nums[i];
}
return count+1;
}
};
只出現(xiàn)一次的數(shù)字
#include <algorithm>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
int m=nums.size();
sort(nums.begin(),nums.end());
for(int i=1;i<nums.size();i=i+2)
{
if(nums[i]!=nums[i-1]) return nums[i-1];
}
return nums[m-1];
}
// private:
// bool compare(int a,int b)
// {
// return a<b;
// }
};
移動零
典型的雙指針的應(yīng)用！欺旧！
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int fast=0,slow=0;
int m=nums.size();
while(fast<m)
{
if(nums[fast]!=0)
{
nums[slow]=nums[fast];
slow++;
}
fast++;
}
for(int i=slow;i<m;i++)
nums[i]=0;
}
};
兩個數(shù)組的交集
首先就想到兩個for循環(huán)姑丑，然后在新創(chuàng)建的vector中進(jìn)行排序、去重辞友，輸出即可:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//sort(nums1.begin(),nums1.end());
//sort(nums2.begin(),nums2.end());
vector<int> c;
if(nums1.size()==0||nums2.size()==0) return c;
for(int i=0;i<nums1.size();i++)
{
for(int j=0;j<nums2.size();j++)
{
if(nums1[i]==nums2[j])
c.push_back(nums1[i]);
}
}
sort(c.begin(), c.end());
vector<int>::iterator iter = unique(c.begin(), c.end());
c.erase(iter, c.end());
return c;
}
};
這里說一下如何對vector進(jìn)行去重栅哀，想到的方法有兩個:利用set或者unique()，其中unique()函數(shù)是這樣的踏枣，
sort (a, a + n);
vector<int>v (a, a + n);
vector<int>::iterator it = unique(v.begin(), v.end() );
v.erase (it, v.end() );//這里就是把后面藏起來的重復(fù)元素刪除了
而set則更為簡單昌屉，設(shè)置一個set，再將vector的數(shù)據(jù)重新傳入set中茵瀑，時間復(fù)雜度較小而且較方便间驮。
然后，看了看大神的代碼马昨，他直接用了set的取集合交集set_intersection竞帽，代碼如下:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s1(nums1.begin(),nums1.end()),s2(nums2.begin(),nums2.end()),res;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(res,res.begin()));
return vector<int>(res.begin(),res.end());
}
};
更多關(guān)于set的用法可以參看這一篇博客
兩個數(shù)組的交集2
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> c;
if(nums1.size()==0||nums2.size()==0) return c;
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int i=0,j=0;
while(i<nums1.size()&&j<nums2.size())
{
if(nums1[i]==nums2[j])
{
c.push_back(nums1[i]);
i++;j++;
}
else if(nums1[i]>nums2[j])
j++;
else
i++;
}
return c;
}
};
ValidSudoku
這道題真的挺有意思，但因為不用判斷數(shù)獨(dú)是否有解鸿捧，所以降低了很多難度屹篓。基本思路是這樣的匙奴，針對每一行每一列判斷是否有重復(fù)的數(shù)字堆巧，然后在針對每個九宮格進(jìn)行判斷。而判斷是否重復(fù)的方法挺巧妙的泼菌，就是利用數(shù)組小表的唯一性谍肤。a[nums]初始值為0，出現(xiàn)過一次數(shù)字后變?yōu)?哗伯，nums是由所填數(shù)字的下表來決定的荒揣，舉個例子就會清楚了:假如第一行里有兩個7，nums[7】初始值為0焊刹，在第一次7的時候nums[7]變?yōu)榱?系任，在第二次遇到7的時候由于之前已經(jīng)變?yōu)榱?恳蹲，簡單的判斷語句就能發(fā)現(xiàn)這里實際上出現(xiàn)了問題。下面貼上代碼:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int i,j,k,l,map[10];
if(board.size()!=9 || board[0].size()!=9)return false;
for(i=0;i<9;i++){
memset(map,0,sizeof(map));
for(j=0;j<9;j++){
if(board[i][j]=='.')continue;
if(board[i][j]<'0' || board[i][j]>'9')return false;
int num=board[i][j]-'0';
if(map[num])return false;
map[num]=1;
}
}
for(j=0;j<9;j++){
memset(map,0,sizeof(map));
for(i=0;i<9;i++){
if(board[i][j]=='.')continue;
int num=board[i][j]-'0';
if(map[num])return false;
map[num]=1;
}
}
for(i=0;i<9;i+=3){
for(j=0;j<9;j+=3){
memset(map,0,sizeof(map));
for(k=i;k<i+3;k++){
for(l=j;l<j+3;l++){
if(board[k][l]=='.')continue;
int num=board[k][l]-'0';
if(map[num])return false;
map[num]=1;
}
}
}
}
return true;
}
};
旋轉(zhuǎn)圖像
這道題我感覺比較奇怪俩滥，思路比較好像用的是reverse與swap嘉蕾，我看了別人的代碼只是先后順序不同而已，但是自己的代碼(注釋掉的)卻在輸入為44矩陣時不能執(zhí)行reverse霜旧，而自己在私下測試了reverse確實是可以將44矩陣執(zhí)行reverse操作的荆针，自己的想法是先將行數(shù)倒置，然后沿著主對角線進(jìn)行swap()操作颁糟，得到最終結(jié)果。而我最終的代碼喉悴，是先交換在倒置棱貌，我認(rèn)為先后順序是沒有問題的，但是程序卻沒有執(zhí)行reverse的操作箕肃，就很奇怪婚脱。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
/*
for(int i=0;i<matrix.size();i++)
reverse(matrix.begin(),matrix.end());
for(int i=0;i<matrix[0].size();i++)
{
for(int j=i+1;j<matrix.size();j++)
{
swap(matrix[i][j],matrix[j][i]) ;
}
}*/
int n = matrix.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
買賣股票的最佳時機(jī)2
股票衡量是否為利潤是基于前一天的價格和今天的價格來比較的，知道這個就好做了勺像。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int l = prices.size();
if(l <= 0) {
return 0;
}
int max = 0;
for(int i=1; i<l; i++) {
if(prices[i] - prices[i-1] > 0) {
max += (prices[i] - prices[i-1]);
}
}
return max;
}
};
