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

目录

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;i1;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.lengthlength){
        [str1,str2] = [str2,str1]
    }
    let max = 0
    let res = ''
    for(let i=0; ilength; 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