算法题练习——JS Node+python题解NC53 删除链表的倒数第n个节点、NC127 最长公共子串

以你之姓@ 2024-04-07 14:33 71阅读 0赞

**目录**

NC53 删除链表的倒数第n个节点

NC127 最长公共子串

--------------------

### NC53 删除链表的倒数第n个节点 ###

**描述**

> 给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针  
> 例如:
> 
> 给出的链表为: 1→2→3→4→5, n= 2n=2.  
> 删除了链表的倒数第 nn 个节点之后,链表变为1→2→3→5.

> 数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足0≤val≤100
> 
> 要求：空间复杂度 O(1)，时间复杂度 O(n)
> 
> 备注：题目保证 n 一定是有效的

**示例1**

> 输入：\{1,2\},2
> 
> 返回值：\{2\}

**解析：**

>  *  本题有两种解法，一种是用快慢指针，快指针先走n步，在快慢指针同时走，最后快指针结束时慢指针的下一个就是要删除的元素了；
>  *  第二种就是我下面的解法，先遍历出链表的长度，再直白的找到要删除的点，删除就好了；

**JavaScript题解：**

/*
     * function ListNode(x){
     *   this.val = x;
     *   this.next = null;
     * }
     */
    
    /**
      * 
      * @param head ListNode类 
      * @param n int整型 
      * @return ListNode类
      */
    function removeNthFromEnd( head ,  n ) {
        // write code here
        if(!head) return null
        let node = head
        let len = 0
        while(node){
            node = node.next
            len++
        }
        node = head
        if(len-n==0) return head.next
        for(let i=0;i<len-n-1;i++){
            node = node.next
        }
        node.next = node.next.next
        return head
    }
    module.exports = {
        removeNthFromEnd : removeNthFromEnd
    };

**python题解：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param head ListNode类 
    # @param n int整型 
    # @return ListNode类
    #
    class Solution:
        def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:
            # write code here
            node = head
            len = 0
            while node:
                node = node.next
                len += 1
            node = head
            if len-n==0:
                return head.next
            for i in range(len-n-1):
                node = node.next
            node.next = node.next.next
            return head

--------------------

### NC127 最长公共子串 ###

**描述**

> 给定两个字符串str1和str2,输出两个字符串的最长公共子串
> 
> 题目保证str1和str2的最长公共子串存在且唯一。

> 数据范围：1≤∣str1∣,∣str2∣≤5000  
> 要求： 空间复杂度 O(n^2)O(n2)，时间复杂度 O(n^2)O(n2)

**示例1**

> 输入："1AB2345CD","12345EF"
> 
> 返回值："2345"

**JavaScript题解 ：**

/**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    function LCS( str1 ,  str2 ) {
        // write code here
        if(str1.length<str2.length){
            [str1,str2] = [str2,str1]
        }
        let max = 0
        let res = ''
        for(let i=0; i<str1.length; i++){
            const tmp = str1.slice(i-max,i+1)
            if(str2.match(tmp)){
                res = tmp
                max++
            }
        }
        return res
    }
    module.exports = {
        LCS : LCS
    };

**python题解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # longest common substring
    # @param str1 string字符串 the string
    # @param str2 string字符串 the string
    # @return string字符串
    #
    class Solution:
        def LCS(self , str1: str, str2: str) -> str:
            # write code here
            if len(str1)<len(str2):
                str1,str2 = str2,str1
            res = ''
            max_len = 0
            for i in range(len(str1)):
                if str1[i-max_len:i+1] in str2:
                    res = str1[i-max_len:i+1]
                    max_len += 1
            return res