刷题记录(初级算法-数组篇)
2018-04-11 本文已影响33人
MrYun
最近开始认真刷题了，反正做了些题目就记录一些吧，这里记录了LeetCode初级算法中数组的一些题目:
加一
本来想先转成整数，加1后再转回去；耽美想到测试的例子考虑到了这个方法的笨重，所以int类型超了最大范围65536，导致程序出错。
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;
}
};
下面完全是从数组的角度进行的思考:分析了各种情况综合得出代码:
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;
}
};
此外还有一种解法:
这种方法就很机智的将进位carry这个思路加了进来，如果carry=0的话就说明暂时没有进位，可以直接返回；如果有进位的话继续操作。最后在循环结束后，如果还有进位，说明要加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;
}
};
从排序数组中删除重复项
下面是我最初始的想法，通过循环，遍历的这一项等于前一项的话，就通过迭代器iterator it将这一项清除掉，如果不相等就将count加1；这样觉得很完美，但是实际上每次将这一项清除掉的时候，vector的总长度就发生变化了，所以会导致出错！！！下面是错误代码:
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;
}
};
更换思路，发现题目中有这样的一句话:不需要理会新的数组长度后面的元素；这叫告诉我们，可以把不需要的元素弄到后面去或者将我们需要的元素弄到前面来，所以有了下面的解法:
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;
}
};
只出现一次的数字
#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;
// }
};
移动零
典型的双指针的应用！！
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;
}
};
两个数组的交集
首先就想到两个for循环，然后在新创建的vector中进行排序、去重，输出即可:
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进行去重，想到的方法有两个:利用set或者unique()，其中unique()函数是这样的，
sort (a, a + n);
vector<int>v (a, a + n);
vector<int>::iterator it = unique(v.begin(), v.end() );
v.erase (it, v.end() );//这里就是把后面藏起来的重复元素删除了
而set则更为简单，设置一个set，再将vector的数据重新传入set中，时间复杂度较小而且较方便。
然后，看了看大神的代码，他直接用了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());
}
};
更多关于set的用法可以参看这一篇博客
两个数组的交集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
这道题真的挺有意思，但因为不用判断数独是否有解，所以降低了很多难度。基本思路是这样的，针对每一行每一列判断是否有重复的数字，然后在针对每个九宫格进行判断。而判断是否重复的方法挺巧妙的，就是利用数组小表的唯一性。a[nums]初始值为0，出现过一次数字后变为1，nums是由所填数字的下表来决定的，举个例子就会清楚了:假如第一行里有两个7，nums[7】初始值为0，在第一次7的时候nums[7]变为了1，在第二次遇到7的时候由于之前已经变为了7，简单的判断语句就能发现这里实际上出现了问题。下面贴上代码:
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;
}
};
旋转图像
这道题我感觉比较奇怪，思路比较好像用的是reverse与swap，我看了别人的代码只是先后顺序不同而已，但是自己的代码(注释掉的)却在输入为44矩阵时不能执行reverse，而自己在私下测试了reverse确实是可以将44矩阵执行reverse操作的，自己的想法是先将行数倒置，然后沿着主对角线进行swap()操作，得到最终结果。而我最终的代码，是先交换在倒置，我认为先后顺序是没有问题的，但是程序却没有执行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());
}
}
};
买卖股票的最佳时机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;
}
};
