记录一次使用leetcode

    选择打赏方式

第一次使用LeetCode

简单介绍一下leetcode

今天是我第二次使用leetcode这个网站了,这个网站可以说是每一个程序员都必须知道的网站,里面有很多的编程知识提供给我们学习,有问题不会的时候还可以发表自己的问题,请大神来解决,还可以和大家讨论问题和发表自己的观点。但是里面的内容不止这些,leetcode最主要的用处还是用来刷题目,可以说leetcode是我用过的最好的编程习题网站,据网络流传上面刷过的题目合起来可以绕地球三圈,可见是有多么牛批了吧!

第一次使用leetcode

虽然好了,但是对于我这种对算法还是不太深入的人来说,上面的题目确实有一定的难度,前面的简单的题目还好我提交了两次就顺利通过了

  • 题目

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* res = (int *)malloc(sizeof(int) * 2);
    for(int i = 0; i < numsSize-1; i++) {
        for(int j = i + 1; j < numsSize; j++) {
            if(nums[i] + nums [j] == target) {
                res[0] = i;
                res[1] = j;
                *returnSize = 2;
                return res;
            }
        }       
    }
    return res;
}

我感觉还是挺好的,满足了我的内心,然后我就继续了下一题,但是到这题我就直接懵了,虽然是中等难度,但是对于我这种很少接触算法的人来说还是有那么亿点点难度

  • 题目

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

看着这个题目是不是很短,但是我直接懵了,因为就是因为题目短,我差点没读懂他的意思,读了几遍终于读懂了,按照中学的惯例,题目短的题,一般都不怎么好解,最后还真的被我说中了,这个题,我竟然花了一下午的时间,中间经历了若干次失败

终于历经千辛万苦,抓破头皮,我终于解出来了------真的是太难了,不过只是对于我来说,哈哈哈哈,来看看我这惨不忍睹的算法吧

int lengthOfLongestSubstring(char * s){
    int len = strlen(s);
    int star = 0;
    int end = 0;
    int max = 1;
    int max2 = 0;
    int mid = 0;
    if (len == 0)
    {
        max2 = 0;
    }
    else if(len == 1)
    {
        max2 = 1;
    }
    else{
        for (end = 0; end <= len - 1; end++)//1
        {
            mid = end-1;//0
            max = 1;
            while (mid >= star)//重复比较end和star之间的元素是否重复//0
            {
                if (s[mid] != s[end])
                {
                    max++;
                    mid--;
                }
                else {
                    star = star+1;
                }
                if (max2 < max) {
                    max2 = max;//
                }
            }
        }
    }
    return max2;
}

是不是很拉,

做完之后我也认真的分析了一下,看了很多大神的解题方法,发现我这种只能算暴力解法,其实还有很多非常不错的解题方法,这里就简单介绍几种

方法一:滑动窗口

思路和算法

我们先用一个例子考虑如何在较优的时间复杂度内通过本题。
我们不妨以示例一中的字符串 \texttt{abcabcbb}abcabcbb 为例,找出从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串:

以 \texttt{(a)bcabcbb}(a)bcabcbb 开始的最长字符串为 \texttt{(abc)abcbb}(abc)abcbb;
以 \texttt{a(b)cabcbb}a(b)cabcbb 开始的最长字符串为 \texttt{a(bca)bcbb}a(bca)bcbb;
以 \texttt{ab(c)abcbb}ab(c)abcbb 开始的最长字符串为 \texttt{ab(cab)cbb}ab(cab)cbb;
以 \texttt{abc(a)bcbb}abc(a)bcbb 开始的最长字符串为 \texttt{abc(abc)bb}abc(abc)bb;
以 \texttt{abca(b)cbb}abca(b)cbb 开始的最长字符串为 \texttt{abca(bc)bb}abca(bc)bb;
以 \texttt{abcab(c)bb}abcab(c)bb 开始的最长字符串为 \texttt{abcab(cb)b}abcab(cb)b;
以 \texttt{abcabc(b)b}abcabc(b)b 开始的最长字符串为 \texttt{abcabc(b)b}abcabc(b)b;
以 \texttt{abcabcb(b)}abcabcb(b) 开始的最长字符串为 \texttt{abcabcb(b)}abcabcb(b);

发现了什么?如果我们依次递增地枚举子串的起始位置,那么子串的结束位置也是递增的!这里的原因在于,假设我们选择字符串中的第k个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为rk。那么当我们选择第k+1个字符作为起始位置时,首先从k+1rk 的字符显然是不重复的,并且由于少了原本的第k个字符,我们可以尝试继续增大rk,直到右侧出现了重复字符为止。这样一来,我们就可以使用「滑动窗口」来解决这个问题了:我们使用两个指针表示字符串中的某个子串(或窗口)的左右边界,其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的rk;在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;在枚举结束后,我们找到的最长的子串的长度即为答案。

判断重复字符

在上面的流程中,我们还需要使用一种数据结构来判断 是否有重复的字符,常用的数据结构为哈希集合(即 C++ z中的std::unordered_set,Java 中的 HashSet,Python 中的 set, JavaScript 中的 Set)。在左指针向右移动的时候,我们从哈希集合中移除一个字符,在右指针向右移动的时候,我们往哈希集合中添加一个字符。
至此,我们就完美解决了本题。

复杂度分析

时间复杂度:O(N)O(N) ,其中 NN 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
空间复杂度:O(|\Sigma|)O(∣Σ∣) ,其中 \SigmaΣ 表示字符集(即字符串中可以出现的字符),|\Sigma|∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在 [0, 128)[0,128) 内的字符,即 |\Sigma| = 128∣Σ∣=128 。我们需要用到哈希集合来存储出现过的字符,而字符最多有 |\Sigma|∣Σ∣ 个 ,因此空间复杂度为O(|\Sigma|)O(∣Σ∣)

还有其他方法,这里我就不一一介绍了

至此我终于知道了自己整天学习,其实还是有好多东西都没有掌握,在编程的这条路上,我还有很多的东西需要去了解,还有很多的东子等着我去发现去掌握,我也知道leetcode也将成为一把,利器。

结语

第一次使用leetcode就给我来了个下马威,但是我不怕,希望他来得更多一点,哈哈哈哈,这样我才能快速提升
另外,附上我的leetcode主页,虽然很拉,但肯定值得一看:leetcode——若离风

版权声明:若无特殊注明,本文为《若离风》原创,转载请保留文章出处。
本文链接:https://www.rlfit.cn/post-32.html
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框
可使用QQ号实时获取昵称+头像

私密评论

吃奶的力气提交吐槽中...


既然没有吐槽,那就赶紧抢沙发吧!