【Leetcode刷题笔记 持续更新】Day01

Day01

是要在给定的类下写函数完成功能,由于是才开始刷题,所以对给的函数体不熟悉,连vector< int >都不知道是啥。
从今天开始坚持刷题,并将刷题的心得及时记录下来,希望可以从这个寒假开始,真正为自己开始努力。

两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum

思路:

看到题目之后便会直接想到的便是由两层循环,直接找到两个相加之和为target的数组下标(这也是我目前所能会的唯一一个方法。。。)

但是由于在学校学的c++并不深,因此不知道应该怎么输出,函数是vector< int >的返回值,所以得重新创建一个数组用于输出(后来在题解区看到官方题解代码中直接return了{i,j}就也就不需要创建额外的数组了。

而我在这里就用到了vector< int> 中的一个函数push_back(),这个函数的作用是在数组最后添加一个元素。

我的代码:

class Solution {
     
public:
    vector<int> twoSum(vector<int>& nums, int target) {
     
        vector<int> res;
        int len = nums.size();
        for (int i=0; i<len; ++i) {
     
            for (int j = i+1; j<len; ++j) {
     
            if((nums[i] + nums[j]) == target){
     
                res.push_back(i);
                res.push_back(j);
                return res;
            }
        }
    }
    return res;
    }
};

哈希表解法

注意到上一个方法的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。

使用哈希表,可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)。

这样我们创建一个哈希表,对于每一个 x,我们首先查询哈希表中是否存在 target - x,然后将 x 插入到哈希表中,即可保证不会让 x 和自己匹配。

class Solution {
     
public:
    vector<int> twoSum(vector<int>& nums, int target) {
     
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
     
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
     
                return {
     it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {
     };
    }
};

两数相加

给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers

思路

看到之后就有一种比较熟悉的感觉,因为在数据结构课上做过两个链表合并并排序的算法,因此觉得还是很容易的,就只是遇10进1的地方有一点不同。

讨论l1和l2是否为空,若l1为空则将l2给到l1,这样就不需要写两个判断分别判断l1或l2为空的情况了。

但是在写的时候还是出了状况,因为在课上写的代码都是自己typedef的结构体,然后利用指针的next完成链表操作,在类里面写的倒是没有,因此在细节的处理上,比如p每次都要new,用到类里面的构造函数,之前没接触过,这次算是了解了…

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
     
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
     
        ListNode *l3 = new ListNode(0);
        ListNode *p = l3;
        int temp = 0;
        while(l1 && l2) {
     
            p->next = new ListNode((temp + l1->val + l2->val) % 10);
            temp = (temp + l1->val + l2->val) / 10;
            p = p->next;
            l1 = l1->next;
            l2 = l2->next;
            }
            if(l1==NULL) l1=l2;
            while(l1) {
     
                p->next = new ListNode((temp + l1->val) % 10);
                temp = (temp + l1->val) / 10;
                p = p->next;
                l1 = l1->next;
                }
                    if(temp) {
     
                        p->next = new ListNode(1);
                        }
                        return l3->next;
    }
                        };

ps:为啥实例中别人的代码明明运行时长挺短,但我一运行就特慢,还没有我的运行快。。还有内存消耗也是

无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

思路

拿到题目后感觉很简单,就想着暴力枚举遍历,但是在写for循环的时候有点方,不知道应该怎么循环,外面的一个for比较好写,但是里面的就不知道该怎么写。想到的是从s[0]开始与后面的比,当匹配到相同的字符时就把前面的长度存下来,再从s[1]开始比。

class Solution {
     
public:
    int lengthOfLongestSubstring(string s) {
     
        int back=0,front=0;
        int maxlength=0;
        for(;front<s.size();front++){
         
            for(int i=back;i<front;i++){
     
                if(s[front]==s[i]) 
                {
     
                    back=i+1;
                    break;
                    }
                    }
        maxlength=max(front-back+1,maxlength);
     }
    return maxlength;
    }
};

滑动窗口

可以使用「滑动窗口」来解决这个问题了:

我们使用两个指针表示字符串中的某个子串(的左右边界)。其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的 rk;

在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;

在枚举结束后,我们找到的最长的子串的长度即为答案。

class Solution {
     
public:
    int lengthOfLongestSubstring(string s) {
     
        // 哈希集合,记录每个字符是否出现过
        unordered_set<char> occ;
        int n = s.size();
        // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int rk = -1, ans = 0;
        // 枚举左指针的位置,初始值隐性地表示为 -1
        for (int i = 0; i < n; ++i) {
     
            if (i != 0) {
     
                // 左指针向右移动一格,移除一个字符
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
     
                // 不断地移动右指针
                occ.insert(s[rk + 1]);
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

你可能感兴趣的