LeetCode刷题记录1-5

朴灿烈づ我的快乐病毒、 2023-07-06 14:53 18阅读 0赞

### 目录 ###

*  1. 两数之和
 *  2. 两数相加
 *  3. 无重复字符的最长子串
 *  4. 寻找两个有序数组的中位数
 *  5. 最长回文子串

# 1. 两数之和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjg5NzM2_size_16_color_FFFFFF_t_70]

dicts = { }
    for index, value in enumerate(nums):
        temp = target - value
        if temp in dicts:
            return [dicts[temp], index]
        dicts[value] = index
        
    # 也可以直接使用数组遍历，效果差不多

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中

enumerate(sequence, [start=0])

*  sequence – 一个序列、迭代器或其他支持迭代对象。
 *  start – 下标起始位置。

![在这里插入图片描述][20200220091626711.png]

面试中该题出现次数：  
![在这里插入图片描述][20200220092845955.png]

# 2. 两数相加 #

![在这里插入图片描述][20200220100130513.png]

prenode = ListNode(0)
    lastnode = prenode
    val = 0
    while l1 or l2 or val:
        val,cur = divmod(val+(l1.val if l1 else 0)+(l2.val if l2 else 0),10)
        lastnode.next = ListNode(cur)
        lastnode = lastnode.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return prenode.next

python divmod() 函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a // b, a % b)。  
![在这里插入图片描述][20200220132831885.png]  
面试中该题出现次数：  
![在这里插入图片描述][20200220132935291.png]

# 3. 无重复字符的最长子串 #

![在这里插入图片描述][2020022013341577.png]

if s is None or len(s) == 0: return 0;
    form = 0
    to =1
    maxlength = 1
    while to<len(s):
        site = s[form:to].find(s[to])
        if site != -1:
            length = to-form
            if length > maxlength:
                maxlength = length
            form = form+site+1
        to += 1
    if to-form > maxlength:
        maxlength = to-form
    return maxlength

参考博客：[https://www.cnblogs.com/mfrank/p/10472651.html][https_www.cnblogs.com_mfrank_p_10472651.html]  
![在这里插入图片描述][20200220151936873.png]  
面试中该题出现次数：  
![在这里插入图片描述][20200220152246694.png]

# 4. 寻找两个有序数组的中位数 #

![在这里插入图片描述][20200220153445358.png]

nums1.extend(nums2)
    nums1.sort()  # 有点作弊
    half = len(nums1) // 2
    return (nums1[half] + nums1[~half]) / 2

中位数算法参考博客：[https://www.cnblogs.com/Lands-ljk/p/5763935.html][https_www.cnblogs.com_Lands-ljk_p_5763935.html]  
python中List sort的实现原理：[https://www.cnblogs.com/clement-jiao/p/9243066.html][https_www.cnblogs.com_clement-jiao_p_9243066.html]  
中位数是按顺序排列的一组数据中居于中间位置的数，如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。  
![在这里插入图片描述][20200220161108507.png]  
面试中该题出现次数：  
![在这里插入图片描述][20200220161344762.png]

# 5. 最长回文子串 #

![在这里插入图片描述][20200220162002516.png]

if len(s) <= 1:
        return s
    
    # 每个字符之间插入 #
    ss = '$#' + '#'.join([x for x in s]) + '#`'
    p = [1] * len(ss)  # R[]的初始化
    center = 0
    mx = 0  # mx 则为 center + R[center]，也就是这个子串的右边界
    max_str = ''
    for i in range(1, len(p)-1):
    
        if i < mx:
            j = 2 * center - i # i 关于 center 的对称点
            p[i] = min(p[j],mx-i)
    
        # 尝试继续向两边扩展，更新 p[i]
        while ss[i - p[i] ] == ss[i + p[i] ]: # 不必判断是否溢出，因为首位均有特殊字符，肯定会退出
            p[i] += 1
    
        # 更新中心
        if i + p[i] - 1 > mx:
            mx = i + p[i] - 1
            center = i
    
        # 更新最长串
        if 2 * p[i]-1 > len(max_str):
            max_str = ss[i - p[i]+1 : i + p[i]]
    
    return max_str.replace('#', '')

参考博客：[https://my.oschina.net/hunglish/blog/747642][https_my.oschina.net_hunglish_blog_747642]  
回文串（palindromic string）是指这个字符串无论从左读还是从右读，所读的顺序是一样的；简而言之，回文串是左右对称的。  
![在这里插入图片描述][20200220175813337.png]  
![在这里插入图片描述][20200220175855132.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjg5NzM2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200220100037618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjg5NzM2,size_16,color_FFFFFF,t_70
[20200220091626711.png]: https://img-blog.csdnimg.cn/20200220091626711.png
[20200220092845955.png]: https://img-blog.csdnimg.cn/20200220092845955.png
[20200220100130513.png]: https://img-blog.csdnimg.cn/20200220100130513.png
[20200220132831885.png]: https://img-blog.csdnimg.cn/20200220132831885.png
[20200220132935291.png]: https://img-blog.csdnimg.cn/20200220132935291.png
[2020022013341577.png]: https://img-blog.csdnimg.cn/2020022013341577.png
[https_www.cnblogs.com_mfrank_p_10472651.html]: https://www.cnblogs.com/mfrank/p/10472651.html
[20200220151936873.png]: https://img-blog.csdnimg.cn/20200220151936873.png
[20200220152246694.png]: https://img-blog.csdnimg.cn/20200220152246694.png
[20200220153445358.png]: https://img-blog.csdnimg.cn/20200220153445358.png
[https_www.cnblogs.com_Lands-ljk_p_5763935.html]: https://www.cnblogs.com/Lands-ljk/p/5763935.html
[https_www.cnblogs.com_clement-jiao_p_9243066.html]: https://www.cnblogs.com/clement-jiao/p/9243066.html
[20200220161108507.png]: https://img-blog.csdnimg.cn/20200220161108507.png
[20200220161344762.png]: https://img-blog.csdnimg.cn/20200220161344762.png
[20200220162002516.png]: https://img-blog.csdnimg.cn/20200220162002516.png
[https_my.oschina.net_hunglish_blog_747642]: https://my.oschina.net/hunglish/blog/747642
[20200220175813337.png]: https://img-blog.csdnimg.cn/20200220175813337.png
[20200220175855132.png]: https://img-blog.csdnimg.cn/20200220175855132.png