美文网首页
刷题记录(初级算法-数组篇)

刷题记录(初级算法-数组篇)

作者: MrYun | 来源:发表于2018-04-11 01:28 被阅读33次

    最近开始认真刷题了,反正做了些题目就记录一些吧,这里记录了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;
        }  
        
    };
    

    相关文章

      网友评论

          本文标题:刷题记录(初级算法-数组篇)

          本文链接:https://www.haomeiwen.com/subject/paiohftx.html