力扣刷题记录 · 2022年1月14日 1

Day 1: 第一天刷个力扣吧

从今天开始每天或多或少刷几道力扣题目,以后应付应付面试啥的还是听需要的。
今天刷两道Easy题,我跟着官方的刷题指南来做的。好久没做这样的题目了,天天做调包大师,只会用python了。为了锻炼锻炼以后的技能,于是我先用C++写再用py改写。希望能对我有所帮助

LC217 Contains Duplicate

我的代码:

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        n = sorted(nums)
        for i in range(len(nums)-1):
            if n[i] == n[i+1]:
                return True

        return False
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end() );

        for (int i=0;  i<nums.size()-1 ;i++){
            if (nums[i]==nums[i+1]){
                return true;
            }
        }
        return false;
    }
};

LC53 Maximum Subarray

操了这题第一次用遍历超出时间规定了。我是傻逼
暴力破解法

class Solution {
public:
    int sum(vector<int> nums,int begin, int length){
        int sum = 0;
        for (int i=begin;i<begin+length;i++){
            sum += nums[i];
        }
        cout<<endl;
        return sum;
    }

    int maxSubArray(vector<int>& nums) {
        int maxInt = INT_MIN;
        for (int i=1; i<=nums.size(); i++){ //数组可能的长度
            for (int j=0; i+j <= nums.size(); j++){ //j是起始位置
                int localSum = sum(nums,j,i);
                if (localSum > maxInt){
                    maxInt = localSum;
                }
            }
        }
        return maxInt;
    }
};

最后看了解题思路,用了动态规划的思想,写了下面的解决方法,写的很垃圾
动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxInt = INT_MIN;
        int localSum = 0;
        for (int i = 0; i < nums.size(); i++){
            // Current sums[i]
            if (localSum + nums[i] >= nums[i]){
                localSum += nums[i];
            }else{
                localSum = nums[i];
            }
            if (localSum > maxInt)
                maxInt = localSum;
        }

        return maxInt;
    }
};

做完两题感觉自己好菜啊,于是我去看了力扣官方的算法教程

数组初级:删除排序数组中的重复项

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成

这是我写的傻逼解法, 这样两个for循环的nlogn的解法满足不了时间复杂度

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int length = nums.size();
        for (int i = 0; i < length - 1; i++){
            if ( nums[i] == nums[i+1]){
                for(int j = i+1;j<length - 1;j++){
                    nums[j] = nums[j+1];
                }
                i--;
                length--;
            }
        }
        return length;
    }
};

于是我又看了答案的双指针来写这道题目,时间复杂度为O(2n)空间O(1)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        int left_index = 0;

        for (int right_index = 1;right_index < nums.size(); right_index++){
            if (nums[left_index]!=nums[right_index]){
                nums[++left_index] = nums[right_index];
            }
        }
        return ++left_index;
    }
};

总结一下:废物罢了